Interviews with other companies!

Following are the questions that I and some of my friends had faced in different interviews, some time back.

Q1. Given a sorted array, how do you find the index of the first occurrence of a given number, x? For example, consider the sorted array, 1 2 3 3 4 5 and the index of the first occurrence of the number 3 (=x) is 2 (assuming that the array begins with 0 index).


This can be solved by slightly modifying the binary search algorithm. Perform binary search for number x in the array and if you find a match, recursively perform binary search on the left sub-array for the number x, to check whether the match found is the first occurrence or not. Running time complexity is O(lg n).


Q2. Given two arrays A and B of same size 'n', find if there exists a set of pairs (a_i, b_i), such that a_i belongs to A and b_i belongs to B and a_i+b_i = S, for all 1 < i < n. Note that, an element a_i (or b_i) can only appear in exactly one pair, in the entire set.


Sort the two arrays, one in non-increasing order and the other in non-decreasing order. If there exists such a set, then the set will be formed only with the pairs obtained by combining the first elements of the two sorted arrays. For example, let a₁....a_n be one sorted array (in non-increasing order) and b₁....b_n be the other sorted array (in non-decresing order). Then the required set, if at all exists, is (a₁, b₁), ...... (a_n, b_n) (Think why??).


Q3. (Interviewed for: Software Development Engineer)Given an array of 'n' numbers and a number 'k' (< n), compute the numbers which are obtained by computing the smallest number in the window of size 'k' with starting index i (varying from 0 to n-k).


Hint: Use heap :)


Q4. Write a code to perform breadth first search in a binary tree.


This is nothing but level-order traversal.

Q5. Write a code to convert a decimal number to a binary number.


Following are a set of simple puzzles.


Puzzle-1: There are three baskets with one having apples in it, the other having oranges in it and the third basket having both oranges and apples. Each of the basket have labels on them, saying what is contained in each of the basket. However, all the three baskets have been labeled WRONGLY. That is, not even one basket bears the correct label on it. A trial is defined as choosing a basket and drawing a fruit from it, observing it and replacing it in the basket. How many minimum trials are needed to label each basket correctly.


Answer to this puzzle is 1 (Find out how??).


Puzzle-2: There are 25 horses with a race track, in which only 5 horses can run at a time. How many races need to be conducted to identify the top 5 fastest running horses.


Answer is 7 (how??).

Puzzle-3: The classic puzzle of 2 eggs and 100 floors problem (google for the exact question).

A New Experience with a Networking Start-up!

Please note that I am a fresher from one of the IITs. So, the interviews for the same companies might be different for non-freshers.

Brief Intro about the company: Arista Networks is the name of the company, that I got interviewed for. It is a networking start-up company.


The interviews I had for this company are very different from the ones that I had before. They gave me a laptop to work on and the interviewer was sitting right infront of me on another laptop, looking at what I was doing, by 'ssh'ing in to my laptop. They weren't keen on asking questions related to a specific topic. Rather, they were just looking at how sharp the candidate is. There were just two rounds of interviews, pretty big ones though with each one lasting about 2-3 hrs.

Round-1 Interview:

The interviewer asked me questions to test my familiarity with Linux. He was not just asking about basic linux stuff, he asked me to find out the memory layout for a process. He asked me questions about /proc filesystem. How would I go about using the /proc filesystem to extract the information corresponding to each running process. He was completely obsessed with acronyms. He says "copy-on-write" is called "COW". I have NEVER heard of such an acronym. Huffff!!! It was a very tiresome job and I was absolutely lost!!!

Then the second part of the interview starts, which is about the Algorithms and Data structures (my favourite!). Here are the questions:

Q1. Given a pointer to a node in Binary Search Tree, return the next inorder successor of that node.

Straight forward code. Kids stuff! :P

Q2. Given a binary tree, write a function which would return true if the tree is a valid binary search tree or false if the tree is not a valid binary search tree.

Straight forward again! He was a bit impressed that I solved them without taking any hints.

Q3. Given a linked list and a number, remove all the nodes in the linked list whose 'key' value is equal to the given number. For example, given the linked list 5->6->1->3->5->5->7->8 and number 5 as input to the function, the function should modify the linked list as 6->1->3->7->8.

This again, pretty straight forward kids stuff! :P :P

Then he tells me that he was absolutely worried about the first part of my interview. I realized that he wasn't impressed with the first part, at all. But, he was happy with my second part. However, I still don't know whether he would select me or not.


Round-2 Interview:

This guy is an absolute genius. He seems to have quite some experience with the networking and stuff. He asked what would be my favourite area. I said operating systems. And then he started.

Q1. How would two processors inter-communicate with each other?

I told him things about Advanced Programmable Interrupt Controller(APIC). And then I realized that I got the question incorrectly. The questions was:

Q1. How would two "processes" inter-communicate with each other?

I told him that this can be done using shared memory, signals, memory queues, etc. He asked me to explain the signals a bit more. I told him about how the signals are generated and how they are handled in uniprocessor and multi-processor systems. I knew what I said was correct.

Q2. This is a very hypothetical question that he had asked me. There are two processes running and you want to send a text string from one process to another process. And the only way these processes can communicate with each other is by using signals. He asked me not use shared memory/message queues etc. Like as I said, the only way of communication between these two processes would be through signals.

I gave a very wacky solution. Convert the string into a binary string. And assign two signals (let us call them SIGX and SIGY), one to the binary '1' and the other to the binary '0'. For the bit '1'(/bit '0'), process-1 sends the signal SIGX(/SIGY) to process-2 and in the signal handler of SIGX in process-2, it sends a signal(let us call this as SIGZ) to process-1 as an ack for the signal received. After receiving ack from process-2, process-1 transmits the next bit in the same way and so on. (You would understand why I am doing this if you know how signals are handled in the linux kernel). He seemed to be satisfied with the solution.

Q3. He asked me questions about the memory management in linux. How is virtual memory handled and how is that converted into physical address and so on.

Q4. He asked me the difference between Arrays and Linked lists. Pros and cons for both of them. I even told him about dynamic arrays and how are they implemented. Asked me to analyze each of them interms of the resources available in the system(memory and cpu time). Took me to the systems level.

I think I have done a good job in answering this question.

Q5. There is memory(RAM) of size 32GB and you want to count the number of times the word 'a' occurs in the entire memory. How would you go about solving this problem on a (i) uni-processor machine and (ii) a multi-processor machine.

I told him that parallelization can be done on a multi-processor system where as, single thread would be more efficient on a uni-processor system. Reason: On uni-processor multi-threading leads to unnecessary overhead because of context switches.


That's all folks! I haven't been told the result yet and I think they might not select me.