Wednesday, January 26, 2011

Technical phone interview

Eventually I had the technical phone interview with Facebook. It went pretty well, I think, but did not result in further interviews. The interviewer was a relatively new engineer there that got a PhD doing distributed systems work.

The interviewer started out by asking me to say some more about my background. I mentioned briefly what I am currently doing and then went into more detail about my graduate work. The interviewer asked follow up questions that required me to go into more detail than I normally need to when answering this type of question. At one point the interviewer asked me to explain the unique contribution of my dissertation and I floundered a bit. Oh well.

I got asked "Why are you interested in Facebook?" I was honest here and said that basically "you guys came to me" and "Facebook is cool." I think this, more than anything else, is what deterred a future interview. If you are interviewing with a company, have some good reasons why you want to work there!

The interviewer shared a little about their background.

We also discussed hip-hop. Alright, so it is really HPPHP, High Performance PHP. It is a tool they use at Facebook to enable web designers to code in PHP and still get the performance of C++. The interviewer did some rough math on a hypothetical situation. Suppose we have 100,000 servers. Each of those servers costs $5000 for the hardware and then another $5000 for maintenance over three years. That's $1,000,000,000. HPPHP results in a 50% savings. Instead of 100,000 servers, we can get away with 50,000 servers. That's $500,000,000 in savings. Now consider if it is just 1% savings. That's still $10,000,000! One of the interviewer's points was that in academics, 1% is nothing. In the real world, it matters.

Of course, there was also a technical question. The interviewer had me go to a website which opened up a shared notepad-type interface. We could both type on this interface, although there was some lag. Once I got a strange pop-up come up because I tried to use an Emacs shortcut (fingers were on autopilot).

The interviewer listed some numbers in a sequence. My job was to figure out the next element in the sequence and then write some code that would print out the for n elements of the sequence. The sequence started at 1 and then each next number was the previous number read out loud. So 1, then 11 (one 1), then 21 (two 1s), and so on. Not too bad.

At first I tried to reason out the mathematical relationship between the numbers, but the interviewer quickly intercepted me and indicated there was not one to be found. The interviewer suggest I just code it up like I did it in my mind. So I did.
             1
            11
            21
          1211
        111221
        312211
      13112221
    1113213211
31131211131221

// Prints first n numbers in the sequence
void seq(string n)
{
    cout << 1;
    string last_number = "1";

    for( int num = 1 ; num < n ; num ++ )
    {
    
    
  // Last char
  char last_char = 'x'; 
  unsigned count = 0;
  string new_number = "";
  for( int x = 0; x < strlen(last_number) ; x++)
  {
    //character
    char c = last_number[x]; 
    if( c == last_char )
    {
        count++;
    }
    
    if(( c != last_char) ) 
    {
        if( count > 0)
        {
            new_number+=(itoa(count));
            new_number+=last_char; 
        }
        last_char = c;
        count = 1;
    } 
  }
     new_number+=(itoa(count));
     new_number+=last_char; 
  
    cout << new_number;
    last_number = new_number;
    
    //int y = atoi( c );
  }
}
The formatting is awful but the interviewer seemed satisfied with my response. Here is a version that I spent a few minutes getting to actually compile:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <cassert>

using namespace std;

// Prints first n numbers in the sequence
void seq(int n)
{
  if(n < 1) return;
  cout << 1 << endl;
  string last_number = "1";
  
  for( int num = 1 ; num < n ; num ++ )
  {
    // Last char
    char last_char = 'x'; 
    unsigned count = 0;
    string new_number = "";
    for( int x = 0; x < last_number.length() ; x++)
    {
      //character
      char c = last_number[x]; 
      if( c == last_char )
      {
        count++;
      }
      if(( c != last_char) ) 
      {
        if( count > 0)
        {
          ostringstream tmp;
          tmp << count;
          new_number+= tmp.str();
          new_number+=last_char; 
        }
        last_char = c;
        count = 1;
      } 
  }
    ostringstream tmp;
    tmp << count;
    new_number+= tmp.str();
    new_number+=last_char; 
    
    cout << new_number << endl;
    last_number = new_number;
  }
}

main(int argc, char** argv)
{
  assert(argc==2);
  seq(atoi(argv[1]));
} 
That compiles with g++ in cygwin and it appears to work correctly. I noticed a few mistakes in making the version that actually compiles and did things a bit differently in some places. Might be one of the reasons they didn't want another interview.

As I have written this up I recall the problem was posed as a basis case and an inductive case. That seems to indicate that a recursive function could also solve it. That would have been clever. Might have been what the interviewer hoping to see.

After writing the code the interviewer had to leave for another meeting. I got to ask one question, so I asked what Facebook was doing to maintain its culture as it became larger. He gave a semi-generic answer, which is about all I should have expected. Then that was all.

A few days later I emailed the recruiter to follow up, and the recruiter let me know they would not be pursuing further interviews with me at this time. It was actually a relief to not have to decide between a sweet job and our #1 location.

5 comments:

  1. Is there a simple explanation for why the numbers never seem to exceed three?

    ReplyDelete
  2. I think the trick comes from the number 2. If there are two 2s next to each other then that they will stay the same. Two 1s become 21 and two 3s become 23. That means there can be three 2s but never more than two of one or three.

    ReplyDelete
  3. Interesting saga . Even if my only experience writing code was seventeen years ago to make a hot air balloon float across the screen.

    ReplyDelete
  4. Recursive solution in JAVA:

    public class SequencePrint {

    public void print(int n) {
    print(n, "");
    }


    private void print(int n, String seq) {
    if(seq.isEmpty()) {
    seq = "1";
    } else {
    char[] charArray = seq.toCharArray();
    seq = "";
    int count = 0;
    for (int i=charArray.length-1; i>=0; i--) {
    char temp = charArray[i];
    count++;
    if (i==0) {
    seq = ""+count + temp + seq;
    } else if (temp != charArray[i-1]) {
    seq = ""+count + temp + seq;
    count=0;
    }
    }
    }
    System.out.println(seq);
    if (n!=0) {
    print(--n, seq);
    }


    }

    /**
    * @param args
    */
    public static void main(String[] args) {
    new SequencePrint().print(10);

    }

    }

    ReplyDelete
  5. I think the use of strings makes it more difficult. I would stick to using ints, vector, and map. Store the current set of numbers in the vector, cycle through them with a for loop comparing each current number to the previous. Store tye number and frequency in the map, when a new number is encountered store it in a new map entry. After the for loop reaches the end of the vector print the contents,of the map with another for loop going value, key, value, key,.....

    ReplyDelete