Written:
There were 4 questions, 3 of coding & 1 was for debugging. We were asked to write algorithm, code with comments & proper naming conventions
I attempted-
1st question completely
2nd was correct, but my approach was not the best
3rd was able to write only the initial approach about the problem
I couldn’t attempt the 4th one
So as such you guys need not worry about attempting all the questions. There were two telephonic interviews, and in both the interviews the interviewer first gave his formal introduction & then asked me for my intro.
So here goes the description...
First round tech Interview:
TRI: Tell me something about any recent project that you did, the one you like the most.
I described the GSD project, and my role in it. (GSD was the best project in terms of what I had learned)
TRI: Given a general stack implementation, can you write a function MAX(s) that returns the current maximum value in the stack?
ME: I gave him two O(n) solutions, basically to scan the array or link list used to implement the stack
TRI: Which is a better approach, array or Link list in terms of efficiency?
ME: Array, due to locality of reference
TRI: Good, but I want the MAX to be returned in O(1)
ME: (After 2 mins of thinking) Can I modify the Data Structure
Well he agreed to modify the DS but by using my approach the original push/pop operations became O(n). He had some discussions even thou he was satisfied with my approach he wanted me to improve my approach. His only requirement was to have push, pop & max functions to be O(1). I got stuck at this point. Then he gave me sample data to work upon. Using the given data I was able to correct my approach and finally gave him the correct solution.
TRI: The next problem goes like this, suppose I give you an integer array, Can you generate all triplets such that a^2 + b^2 = c^2 where a, b, c are all elements of the array?
ME: I said, I have done a similar question, where we find all pairs a[i] & a[j] such that a[i] +a[j] =X, I can you use this approach.
TRI: Ok go ahead.
I gave him an O(n^2) solution. Then I told him that I can optimize by calculating the square and replacing the contents of each element by the corresponding square. This will reduce computations regarding squaring of elements again & again. He was impressed with this approach. The problem then reduces to finding triplets such that X+Y = Z.
TRI: Can you write the code for it? Take your time & then dictate me complete error free code. (He asked me about the signature of the function, name & type of variable too.)
TRI: You must know about tree, traversals. Can you write code to perform a level wise traversal of a binary tree?
ME: Sir I know this problem, Shall I continue.
TRI: Is that so, well then just give me an overview.
I dictated him the entire code. :D
TRI: Suppose we have two nodes of a binary tree; find its least common ancestor. I hope you don’t know this one.
ME: Not, exactly, but I did this problem, a few months ago.
TRI: Ok then do it for a BST
I gave him the approach; he was satisfied with it & asked me to tell the order of the algorithm. Its O(lg N) guys.
TRI: Well, Mr. Sandeep your interview went pretty well & that’s all I wanted to discuss. Would you like to ask me anything?
ME: I do not have any particular question. I just hope there is no problem with my call getting disconnected.
Second round tech Interview:
This was a tough one; I can’t give the entire description. But trust me I was shivering & sweating during the interview. There was only one question; I had to implement a game.
It goes something like this-
There are two 3-letter words for e.g. CAT & TRY
If you are allowed to alter any single letter then in how many steps can you convert CAT into TRY, the only constraint is that the intermediate words should be valid 3-letter words.
I asked him if we have a repository of words. He said I can assume a dictionary with all possible 3-letter words.
We discussed the algorithm for around 25-30 mins. After which I was asked to write a code for it, such that we can calculate the minimum number of steps required (as there are many chains possible or we may have none).
So return -1 if we cannot convert Source to Destination.
After 15-20 mins of coding. He further made me optimize the code. I had given him a recursive approach, which scanned the DB in a DFS manner. He made me convert my code to BFS, & then asked me to compare the two in terms of efficiency & space.
This one question covered: String matching, Hashing, General Tree, BFS, DFS, Recursion, Tail-Recursion, Tree pruning, & god knows what...
One thing was for sure I was exhausted after the interview... BUT it was an awesome experience.
All The best... :)
There were 4 questions, 3 of coding & 1 was for debugging. We were asked to write algorithm, code with comments & proper naming conventions
I attempted-
1st question completely
2nd was correct, but my approach was not the best
3rd was able to write only the initial approach about the problem
I couldn’t attempt the 4th one
So as such you guys need not worry about attempting all the questions. There were two telephonic interviews, and in both the interviews the interviewer first gave his formal introduction & then asked me for my intro.
So here goes the description...
First round tech Interview:
TRI: Tell me something about any recent project that you did, the one you like the most.
I described the GSD project, and my role in it. (GSD was the best project in terms of what I had learned)
TRI: Given a general stack implementation, can you write a function MAX(s) that returns the current maximum value in the stack?
ME: I gave him two O(n) solutions, basically to scan the array or link list used to implement the stack
TRI: Which is a better approach, array or Link list in terms of efficiency?
ME: Array, due to locality of reference
TRI: Good, but I want the MAX to be returned in O(1)
ME: (After 2 mins of thinking) Can I modify the Data Structure
Well he agreed to modify the DS but by using my approach the original push/pop operations became O(n). He had some discussions even thou he was satisfied with my approach he wanted me to improve my approach. His only requirement was to have push, pop & max functions to be O(1). I got stuck at this point. Then he gave me sample data to work upon. Using the given data I was able to correct my approach and finally gave him the correct solution.
TRI: The next problem goes like this, suppose I give you an integer array, Can you generate all triplets such that a^2 + b^2 = c^2 where a, b, c are all elements of the array?
ME: I said, I have done a similar question, where we find all pairs a[i] & a[j] such that a[i] +a[j] =X, I can you use this approach.
TRI: Ok go ahead.
I gave him an O(n^2) solution. Then I told him that I can optimize by calculating the square and replacing the contents of each element by the corresponding square. This will reduce computations regarding squaring of elements again & again. He was impressed with this approach. The problem then reduces to finding triplets such that X+Y = Z.
TRI: Can you write the code for it? Take your time & then dictate me complete error free code. (He asked me about the signature of the function, name & type of variable too.)
TRI: You must know about tree, traversals. Can you write code to perform a level wise traversal of a binary tree?
ME: Sir I know this problem, Shall I continue.
TRI: Is that so, well then just give me an overview.
I dictated him the entire code. :D
TRI: Suppose we have two nodes of a binary tree; find its least common ancestor. I hope you don’t know this one.
ME: Not, exactly, but I did this problem, a few months ago.
TRI: Ok then do it for a BST
I gave him the approach; he was satisfied with it & asked me to tell the order of the algorithm. Its O(lg N) guys.
TRI: Well, Mr. Sandeep your interview went pretty well & that’s all I wanted to discuss. Would you like to ask me anything?
ME: I do not have any particular question. I just hope there is no problem with my call getting disconnected.
Second round tech Interview:
This was a tough one; I can’t give the entire description. But trust me I was shivering & sweating during the interview. There was only one question; I had to implement a game.
It goes something like this-
There are two 3-letter words for e.g. CAT & TRY
If you are allowed to alter any single letter then in how many steps can you convert CAT into TRY, the only constraint is that the intermediate words should be valid 3-letter words.
I asked him if we have a repository of words. He said I can assume a dictionary with all possible 3-letter words.
We discussed the algorithm for around 25-30 mins. After which I was asked to write a code for it, such that we can calculate the minimum number of steps required (as there are many chains possible or we may have none).
So return -1 if we cannot convert Source to Destination.
After 15-20 mins of coding. He further made me optimize the code. I had given him a recursive approach, which scanned the DB in a DFS manner. He made me convert my code to BFS, & then asked me to compare the two in terms of efficiency & space.
This one question covered: String matching, Hashing, General Tree, BFS, DFS, Recursion, Tail-Recursion, Tree pruning, & god knows what...
One thing was for sure I was exhausted after the interview... BUT it was an awesome experience.
All The best... :)
No comments:
Post a Comment