It was a 4-round interview. The first round was a written round with 50 questions (20 aptitude + 30 technical) for 1 hour. The second round was a technical round (1 hour). The third was a technical + management round (20 mins). The fourth round was a short HR round (10 mins).

In the first round, 20 aptitude comprised of simple-medium-complex aptitude questions. Some were answerable within 10 seconds, some took 30-40 seconds, and the harder ones took slightly over a minute to solve. The questions were based on all the classic aptitude topics. Some questions were stated in a confusing way, but other than that, no hiccups were present. The technical side had 30 questions. I was able to answer most of the aptitude questions (17-18 were correct out of 20) and more than 22 questions were right out of 30 in the technical side. I think the cutoff for the second round was around the 40 mark, which I had gotten, and I made it to the second round.

In the second round, the interview started off with simpler, shorter questions, like for example the interviewer pointed to one of the technical questions in the previous round (the interviewer has your answer sheet from the previous round) and asked me to explain the approach I had taken to solve the problem. In the question, I had to estimate the worst-case time complexity of the function. The recursive function had something like this:

return function(params-1) + function(params-1)

The answer to this was O(2^n). The interviewer modified the question to this:

return (function(params-1) + function(params-1)) * function(params-1)

The complexity of this was O(3^n). He asked me to derive it on paper, which I did.

The next question was regarding how to set the nth bit in a 32-bit integer. The answer was pretty straightforward: variable | 1 << (n-1).

The next question was about a linked list. The interviewer asked me to print a singly linked list in a reverse manner.

After that, we moved on to trees. The first question was to find the min element in the tree. The second question was to implement level order traversal in trees.

After I did that, he asked me to traverse the tree and print it in reverse level order fashion, but the associativity of the child node should be from L-R. For eg..

  4    Then the answer would be: 1357264
/   \   

2 6 / \ /
1 3 5 7

After taking a few hints from the interviewer, I was able to code it up without errors.

The next question was to print the tree in a zig-zag manner. i.e.: for the tree above, the zig-zag traversal would yield: 4267531. After thinking for some time, hints from the interviewer, I was able to code this up as well. The key points the interviewer looked for were approach, error-less coding, boundary cases, clarity, and confidence. Also, try to speak to the interviewer about your thought process; this not only gives a better opinion to the interviewer, but if you tell them where you're stuck, he/she might give you clues to proceed further.

In the 3rd round, the technical-management round, the key focus was your thought process. They were not too keen about the technicality of the solutions. The interviewer asked me what were my favorite topics, and I replied data-structures and algorithms. Then he asked me to code up a part of a social network where people were nodes and different types of connections existed between them. My job was to write functions to connect any two nodes of the graph, and also another function to check if 2 nodes are directly or indirectly (transitively) connected.

I asked him whether all these edges/connections were directed or undirected. They were assumed to be undirected. The socialGraph class had insertion, deletion functions, and connect(node*, node*), isconnected(node*, node*) functions as friend functions to connect 2 nodes and check if 2 nodes are connected. The connect function was straightforward, as I had to append the node reference to the edge-list of the node. Then to check if 2 nodes are connected, I did a DFS from the source node to the destination node. The interviewer asked me to make the code such that it could scale. So I suggested that we could do an A* search instead of a DFS to make the search space smaller. The interviewer seemed satisfied with my solutions, and then we moved on to the other questions. He asked me other simple questions about my projects. I did well enough to get qualified for the final round, which was a casual HR round where they asked simple questions like the meaning of my name

Zig Zag printing of the tree.