biobot

Congratulation Beyang and Quinn. Looks really slick!

Too bad it is GPL v2. https://github.com/facebook/flashcache/blob/master/LICENSE

Apache Software License, Version 2.0

https://oss.sonatype.org/content/repositories/snapshots/org/...

You should've tried this: https://wiki.archlinux.org/index.php/Yaourt

Interesting! But I think $70k salary for early employees is not realistic. They will probably take $10k-$20k less than market price for significant shares.

NO (Samsung galaxy S II, T-Mobile)

One of my friend came up with this solution:

m is missing,d is duplicate. I is 1..N, A is input.

Step 1: Compute m XOR d by XOR all values of A and I together. let say x = m XOR d. Then x must has at least one 1 bit (or else m == d). Call the bit p. So now we can separate A into two list A0 are those with bit p == 0 and A1 are those with bit p == 1. So we have separated m and d into two different list.

Step 2: Iterate through I, maintain two number x0 and x1 as the results of XOR operations of those elements with p bit == 0 and == 1 respectively. Do the same for A to get a0 and a1. Then we know that m is either a0 XOR x0 or a1 XOR x1. One more linear test in A to confirm the missing element m.

In the end, the running time can be squeezed into 2 N. space = O(1).

OK. I think I find a way around.

Assume d XOR m = a. Find k = position of the first bit (from MSB to LSB) in a. Then d + m can be in [a + 2^(k+1),a + 2^(k+2),...,a + 2^63].

We will have less than 63 cases. In each case, after we find d and m, make sure they are in range and then linear test.

So in the end, we may need to run at most 63+3 = 66 N. But it still linear though.

Make sense!

That fails my solution!

There are at most 2 solutions: if m XOR d = a then either m+d = a or m+d = a+N.

With the combination of m-d = b, you will find m and d.

If both of them satisfied ( remember m and d are bounded by 1 and N) then we actually have two solutions.

This is the solution I posted there:

Called the missing number m, duplicate d.

The main idea is to find m+d and m-d. Then it’s trivial to find m and d.

1) Find n XOR d:

   X_array = 1;
   I_array = 1;

   for (i=2..N)

      X_array = X_array XOR A[i]; I_array = I_array XOR i;

   endfor

Then m XOR d = I_array XOR X_array

2) Find m – d

It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result.

   Diff = 0;

   i = j = 0; // i index I, j index A

   while (i < N) && (j < N)

     if (Diff + i < N-1)

         Diff = Diff + i;

         i++; //consume one in I

     else

         Diff = Diff – A[j];

         j++; // consume one in J

     endif

   end

// Need some corner case check here to but I will omit

3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d.

running time : 3 N <- can be squeeze to 2N if merge the two logic

space : O(1)

For every open position, they will bring in onsite about 10 people. And most of those 10 are pretty good too. So you had to make a very good impression with the interviewer to make the cut. And of course, a some luck won't hurt too.

Again, I reiterate my point : knowing the answer to a coding question is one thing, explaining it to others is the other thing. They won't hire anyone cannot explain such easy questions clearly. It needs some practice!

I think you left the interviewers some bad impressions about your technical skills.

Blame the interviewers throw easy questions at you and think that it's all they get is blatantly wrong. Most Microsoft's devs are better than that!

Based on my experience, the fact that you did not get harder questions show that they thought you did not sail through the easy ones as they expected. And believe me, knowing the answer is one thing, explaining it clearly is another thing.

When I interviewed in Redmond last year, I got 5 interviews total. The first one is easy with all similar questions you got. The second was harder as the guy asked me a problem that starts off easy but when you add more data to it, it becomes more like an open problem. The third one is a OOP design question. The fourth one I met an engineer that joined MS from 1992 and he asked me only one algorithmic question that I have never seen before (Believe me, I read all those 'interviews' books and I know many ). It was very strange tree structure that I did not remember. I spent about 20 minutes stared at it and I got the first part after 35 minutes and then he asked me to explain how I finish the problem. He seemed to be OK with my answer. The last interviewer is a manager. He did not ask me anymore technical question but focus mostly on my preferences, experiences, previous jobs and some behavioral questions.

I think the interviews are on par with other top companies like Google ( but Google focus much more on scale ), Facebook and Amazon ( focus more on design and scale ).

In conclusion, rest assure that your interviewers are much smarter than you think. Hope you do better next time!

I have applied there for a fulltime position. I got a friend at Google refer and an HR called my immediately to set up a phone interview. It went well and they flew me in for onsite. After more than a week, they sent me an offer after the quite rigorous background check. The whole process takes about 3 weeks. Even though, it's not as fast as the company I will join (took them less than 2 weeks total to get me an offer) but I don't think Google process is slow.

One stark difference between programmers in the east and west is that in the east, people tend to stay in one company much longer. I think that effectively limit their development. Those who are in the west tend to be much more well rounded.

JVM is written in C/C++ so technically Java cannot be faster than C/C++ because everything in Java are (direct / indirect) products of C/C++. :)