My Interview Experiences with CS Companies

This blog is about my personal interviews experiences with various companies. I will talk about the questions that I've been asked and hints to their answers.

Microsoft, India Development Center
Interviewed for: Internship

The first phase of the selection process was a written exam. I found it pretty straight forward. Then there were 4 rounds of technical interviews.

Round-1 Interview(Technical):

Q1. How do you divide two numbers with out using division operator?

Unfortunately, the interviewer wasn't friendly, in the way that she wasn't giving any hints. I gave a solution by using continuous subtraction. I had this feeling that there should be a much better way of solving this problem. However, the I couldn't get the idea then. Later, I found that this problem can be solved using an idea similar to binary search.

Q2. Design a single remote that can be used to control TV, Music Player and DVD player.

I talked about a system similar to the 'Project Natalie' of the XBox systems of Microsoft. She was happy with the design that I gave.

Round-2 Interview(Technical):

Q1. Design a cache system. What data structure would you use?

I gave the solution, using a dynamic hash table.

Q2. Given a pointer to a node in a binary tree, return the pointer to the successor node. Every binary node has a parent pointer stored in it, as well. (Note that the pointer to the root is not given - not needed anyway :) )

This was a pretty straight forward. Wrote the code easily without any problem.

Round-3 Interview(Technical):

Q1. There are k systems given and each system has n numbers in the sorted order. You are given a new system which has a space of O(k). Your system can contact with any other system and fetch a number from it. Your task is to write all these n*k numbers into a file in the sorted order using the system that was given to you.

This was a straight forward implementation of the generalized merge-sort(merging k arrays). (Hint: Get the smallest number from each system and build a min-heap with them and take it from there.)

Q2. How are parameters passed to a function, at the machine level?

Parameters are pushed onto the stack(this is the most common and popular way of doing it).

Q3. How is inheritance implemented in C++ and Java? What are the differences?

C++ involves building Virtual tables at compile time and Java involves resolving at run-time.

Round-4 Interview(Technical):

Q1. What are your areas of interest?

I told that operating systems are my favorite.

Q2. Implement semaphor and spinlock using test&set instruction.

Q3. Solve the readers-writers problem. How do you ensure fairness(the bounded waiting) for both readers and writers?

These are the classical synchronization problems.

Finally, got selected for the internship program.

Amazon Development Center, India

Interviewed for: Position of Software Development Engineer(SDE)

Telephonic Interview(Technical):

Q1. Given a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5. Note that the nodes need to be altered and not the data contained in them.

Q2. Write the code for finding the least common ancestor in a Binary Search Tree.

Q3. The classical puzzle of 25 horses with a race track for 5.

5 rounds of on-site technical interviews!(sigh!)

Round-1 Interview(Technical):

This round is what they call 'Data structures and Algorithms round'.

Q0. Intro about me and about the projects that I've done.

Q1. Given a set of words, divide them into groups such that, each group contains words which are anagrams to each other.

Idea that I used to solve: If I alphabetically sort each word belonging to a group, the resulting sorted words would be the same for all the words in the same group.

Ex: bca, cab, cba are all anagrams to each other. Sorting each of them alphabetically gives the same word, abc.

Take every word, sort it alphabetically and insert this sorted word into a patricia trie, with each node containing a linked list of all the words which have the same sorted word. Every node in the resulting trie would correspond to a group.

Q2. You will be given a dictionary containing all possible English words and your job is to store the dictionary in such a way that, you should be able to solve any given cross-word puzzle, as soon as possible.

The data structure that I suggested is very complex to be explained here. However, the idea is to store all the words according to their word lengths and build a structure to choose the words to fill a slot in the cross-word puzzle. You would also need to do the back-tracking to solve this.

Q3. Implement a stack using queues.

This is pretty straight forward.


Round-2 Interview(Technical):

This round is the 'Coding and Problem Solving' round.

Q0. Intro about myself and my final year project.

Q1. Write a program to return the word count, character count and line count for a given input file.

Straight forward.

Q2. Write a code to return the first non-repeating character of a very long string.

I gave the working code with one pass of the string and with an extra space of 26 character array.

Q3. Given a word, print all the possible anagrams of that word. Also, take care of repeating characters.

Gave a recursive solution involving a static variable.

Round-3 Interview(Non-Technical):

This round was with my hiring manager. Absolutely, HR stuff and HR questions like "When was the last time you felt that you lost in something?", "When was the last time your team mate complained about you?", etc. I guess the key to this round was to be absolutely patient.

Round-4 Interview(Technical):
This round is the 'CS Basics' one.

Q1. Questions about the necessity of cloud computing. Design a simple cloud of servers to serve the queries for amazon.com(considering the scale of number of queries/sec).

As, Networks was not my area of interest, I had to logically think and solve each of the issues he posed on me. Luckily, my solutions turned out to be the ones which are currently being used in the industry.

Q2. A code to test my understanding of memory management for processes in the system.

Basics of architecture and OS.

Q3. Semaphors vs Spinlocks. Advantages of one over the other and justification for the necessity of having both, rather than, having just one of them.

OS fundamental stuff.

Q4. There were other questions on CS fundamentals, which I couldn't recollect.

Round-5 Interview(Technical & Non-Technical):

This interview was with another manager of another team.

Q1. Explained in detail about my final year project and summarization of the results.

Q2. Some HR questions.

Q3. Write a code to find contiguous sub-array, whose sum is maximum, in an array containing both positive and negative numbers.

Straight forward code with O(n) running time and O(1) space complexity.