After the CSRC Career Fair, I got an interview from Bloomberg on campus.
In the interview, it was not as serious as I thought. After quickly pass my resume, they started asking Algorithms and Data structures. And, only Algo and Data Structs
First one:
Given an array, front part is ascend and sorted, when some point it turns descend and sorted. Given target, find the target's index in the array.
Require: smaller than O(n). e.g: [1,2,8,7,6,5,4,3], find 4
The first thought I came up is binary search. But it's not very clear how to binary. Struggling for a while, the interviewer gave me some hints.
int low = 0, high = arr.length-1 , mid = (low+high)/2 ;
while(low < high)
{
if(arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]) // left
low = mid+1;
if(arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]) // right
high = mid-1;
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1])
return mid; // index of the biggest element
mid = (low+high)/2;
}
Second one:
Design a datastructure to implement this: A speciall lottery, let's say [A,B,C,D,E] is playing it. Every round pick a random number, suppose is 4. Then A,B,C,D, eliminate D (now[A,B,C,E]). Next round, suppose 3, then E,A,B, eliminate B(now[A,C,E]. Play this until only one left
I came up the solution very fast, Circled Linked List
After one week, I am rejected by Bloomberg. I think the reason is I didn't do very quickly on the first question. But what I did nicely was I wrote down my thinking clue as comments, and explained it to the recruiter. The code I wrote on the paper is well commented and the style is faily nice. So the only reason I believe is the interviewees are better than me. Because that night of Microsoft Coding Competition, the second price team's girl also went to Bloomberg's interview. Maybe that's why I am rejected
After this rejection, I think I need to be damn good at Algorithms and Datastructure. That is the key point of getting a intern or a job. Whether you get the offer, not because how you perform in the interview, the place you are in all the candidates matters. So finally, try to do more algorithms. Hope next time interview, I can be better.