I faced this company during campus placements.
There was a preliminary test(usually online) followed by another online coding round and then followed by two personal interviews.
I hardly rememeber any questions from the first two rounds. Following are some of the questions that I remember from the two personal interviews:
Q1. You are given 'n' nuts and 'n' bolts. Each nut will fit to exactly one bolt and viceversa. For a given nut and a bolt, you can check if the nut is large for the bolt or the nut is small for the bolt or they form a perfect fit. There is no way you can compare two nuts or two bolts. Given this scenario, design an algorithm to identify the perfect fit pairs.
A. The idea is something similar to quicksort. Randomly pick a bolt and compare it with every other nut. Place all the nuts which are larger for the bolt in one set and all the nuts which are smaller in other set. Now, pick the nut which is a perfect fit for the bolt and make the split over the other bolts is the same way as described above. Repeat the operation on thw two sets recursively(Divide and conquer).
Q2. What are heaps? Where are they used and what are the running times for each of the operations performed on a heap.
Please note that the running time complexity of Build-Heap operation is O(n) and make sure that you know the proof for it.
Q3. How are the databases implemented? What data structure is used?
A. B-Trees. Important to know about B-Trees.
These are the questions that I remember.
Monday 25 July 2011
Sunday 19 June 2011
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 (ai, bi), such that ai belongs to A and bi belongs to B and ai+bi = S, for all 1 < i < n. Note that, an element ai (or bi) 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 a1....an be one sorted array (in non-increasing order) and b1....bn be the other sorted array (in non-decresing order). Then the required set, if at all exists, is (a1, b1), ...... (an, bn) (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).
Q1.
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.
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 a1....an be one sorted array (in non-increasing order) and b1....bn be the other sorted array (in non-decresing order). Then the required set, if at all exists, is (a1, b1), ...... (an, bn) (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).
Thursday 16 June 2011
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.
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.
Wednesday 18 May 2011
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.
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.
Subscribe to:
Posts (Atom)