Interview#1: Interviewer was very genial and we started with:
I: Please code a fibonacci sequence for an input number N (not Nth position)? F(N) = F(N-1) + F(N-2) (for N>2)
Me: Provided recursive solution and said its a first stab and is very inefficient. Can be improved a lot.
I: How will you improve?
Me: Memoization.
I: Can you do without lookup?
Me: Sure, iterative approach.
I: Please code.
Me: Coded. Made a minor error but fixed it quickly.
I: How will you write your own malloc that guarantees 128bit alignment (same as
phone interview)?
Me: Pointed out phone interview experience and provided better answers (than
phone interview).
I: How much extra memory do we need, in addition to input arg 'size' passed to my_malloc(size_t size)?
Me: We discussed a bit more on how much additional memory is required to store this pointer.
Interview #2: This was the most technically challenging interview, not because of the difficulty of the question itself, but because the question was framed from a hardware perspective.
I: Can you write a program to write to memory certain data using a register at every uptick of a clock? Note that one pin of the register gives us clock signal and one pin helps us write to memory.
Me: I was quite lost.
// Interviewer tried to simplify his best. It finally boiled down to this.
I: Write a C program to write some data to memory whenever a bit is set (representing a clock) in a memory location. Some other bit in that 8-bit memory needs to hold data. Assume the data is passed as function argument.
Me.
// assume int has to be written.
// assume d is 4th bit, c is 1st bit (from right)
void func(int data) {
char *mem = 0x01234567;
size_t SZ = sizeof(int);
int d = 0;
while(SZ) {
d = 0;
if(mem & 0x01) {
// write to d bit
// copy LSB
d = (data & 0x1);
// right shift
data >>= 1;
// set d in its position
mem |= (d<<3)
// resize data size
SZ--;
}
}
}
Getting here took some time. And the difficulty to understand the original question could have hurt my chances.
Interview #3: There were few questions on past work, what will my current company loose if I leave them (I like this question), pay expectations, working habits and such.
There were two technical questions.
I: Write an algo to rotate bits in an integer by N positions.
A. There is a somewhat similar and popular question on
Stackoverflow.
I: If there is a huge data (say 100 MB) on hard disk and very limited memory (say 1MB) to work with. This data contains only positive and possibly repeating integers. Write an algo to find "missing" integers. All integers that are not present in the file and less than largest integer present in the file are considered "missing".
Similar questions on Stackoverflow are
here,
here:
My first attempt was to use bit map to count existence of each integer.
1 MB = 8 Mega bits
100 MB = 25 Mega integers (Mega here is 1024 * 1024), assuming each int
takes 4 bytes. So, bit map clearly doesn't work.
Interview #4:
Technical Questions:
I: Please explain STP and RSTP protocol.
I: What are various states of ports on a switch running STP protocol.
// Couple of other questions on networking.
I: Given an IP address as a string, print it in decimals.
Me: Provided an algo with lot of bit manipulations of octects. It needs lot of improvements.
Interview #5: This was by Director of Engineering and involved a puzzle question. Other questions are important but non-technical.
I: You are given 3 opaque jars containing: Red, Blue and Red+Blue balls in each and the labels on them mixed up such that no jar has correct label on them. To get a ball from a jar, you have to pay $1. Now, using minimum amount, determine correct labels to jar mapping. What is that amount?
Me: Solutions starting with Red and Blue jars are symmetric. So, start with jar containing mixed label. Rest follows deductive logic.
Interview #6: This was an interesting and mostly the reason for not getting selected.
I: Couple of questions in networking area (Ethernet, VLAN protocols).
I: Can you draw an Ethernet Header.
I: Now, can you write a C data structure to represent its fields.
Me: I answered all question pretty well.
I: Suppose, you are given following data structure representing a node in a graph:
struct node {
int data;
// assume each node has at most 3 peers
struct node *peer[3];
struct node *next;
}
// for simplicity, assume each node has at most 3 peers.
Write a function that takes a node as argument and prints 'data' of all nodes that are reachable from that start node.
Me: This is a tree walk (a DFS or BFS will do). But I messed up in coding. 'next' variable is a decoy and has no real value. Interviewee should ask questions and get this clarified before proceeding. Once its clear, standard DFS/BFS would do. I messed up there and perhaps lost points.
Lesson: Be very very clear on the role of data structures, what is expected, what is given and all that. My tendency to jump in to solutions without absorbing full problem cost me.
// By this point my usual interview brain freeze set in and didn't do rest of the interview up to my expectations.
I: Have you contributed to open source.
I: Which version of GCC do you use?I: Do you know 'nm'?
I: Do you know 'ldd'?
I: What is the structure of an executable file?
The book Linkers and Loaders by John Levin is by far the only book and most comprehensive on this subject. Its worth reading for preparing for such questions.
Thanks to
Riverbed for the opportunity.