Monday, April 23, 2012
My senior interview experience for SDE2 position
Every round had exactly 2 questions. Even if you answer it at first shot, you will be asked to more deeper into it so that half an hour is spent on that.
What is Hashing, hash map
Recursive and Iterative solution for in-order traversal of a binary tree
Implement queue from two stacks.
II:
Design "Customers who bought also bought" section in ecommerce site.
Design a restaurant order management system.
III:
Given a BST, populate a pointer 'inOrderSuccessor' at every node of the tree. Should not use any global variables. No coding.
Given an array, find the maximum sum obtained by adding as many number of elements as you like, but not including any adjacent elements. No coding.
IV:
Given 3 sorted arrays, find a triplet (3 numbers taken one from each array) whose difference between max and min is minimum.
Eg: (1,2,3), (4,5,6), (7,8,9) - one max triplet is (3,6,7) where the max diff is 4 (7-3). 4 is the lowest among any triplet you consider. Optimize for < n^3. (Use merging technique) Just approach, no coding.
Design a java Vector class which allows a maximum of 3 threads to access add & get methods simultaneously.
J2EE questions - very quick / easy ones.
V:
Conflicts with your manager - how did you solve, how will you handle if your manager asks you to put a hack.
How will you keep yourself upto date with the technology?
How will you code review?
How will you mentor new hires?
Design Chess game. Code the move coin method. - There are actually too many edge cases to consider. Consider check every move, check mate, pawn movements, horse jump, pawn to queen, castling, etc. (Code it down)
VI:
Tell your current company's architecture.
Find if a tree is a subtree of another tree. (Code it down)
Convert a number to Roman equivalents. (Code it down)
VII:
Architecture for sending pdf to kindle device: Every kindle device has a unique email id. If you want to send a pdf to the kindle device, you compose an email in your personal email client(gmail) and send to the kindle unique email, backend should receive email, convert to kindle's own format and send to the device.(assume you have webservice to send to kindle device over internet). How will you scale now with your architecture. Identify bottlenecks (Eg. conversion from pdf to kindle format takes CPU, etc)
Find if a binary tree is a mirror image at its root. If you cut the binary vertically at the root, the tree should be a mirror image. code it down.
VIII:
You are given a function addLinkedList which takes in 2 parameters - h1 & h2 denoting the head pointers of 2 linked lists. Write a function which returns a list having addition of the two input list.
Sample TestCases:
Input #00:
2->3->9->7
5->1->7
Output #00:
2->9->1->4
Explanation:
The 1st linked list represents the number 2397 and the second represents 517. The sum of these 2 numbers results in the number 2914 which the resultant linked list represents.
-----------------------------
Another Person:
Ist round:
a) Merge 2 BST
b) Lexical ordering of permutation -- eg 12354, then what is the next lexical permutation 12435
2nd round
a) Sorted rows and sorted column in a matrix, Find whether an element x is present or not.
b) M[i,j]=1 if j is the descendent of i in nary tree. Construct this matrix.
3rd round:
a) find LCA of 2 nodes in a binary tree.
b) Extend it to k nodes in a binary tree
4th round:
a) How makefile compilation work, how it is be represented.
b) Inheritance question and Singleton Thread synchronisation
5th round
a) Random pointer in a link list, Clone another list, which has the similar structure of 1st list
b) Run Length Encoding eg abbcc then ans ab2c2
-----------------
Another person
Round 1:
1. Vertical traversal of binary tree. Your should print nodes in the vertical lines.
2. Given a range (say, 5 to 100) , you should do dictionary operations like insert,delete,search,random operations.
Note: Initially, i said array, then queue, then map. Interviewer is not expecting exact answer. he is just observing the way we handles the problem.
Round 2:
1. Given binary tree with left and right child, we should create new tree with left child becomes first child and right child becomes sibling of first child. So, the new tree has two pointers, one for first child, and another points to its sibling.
2. Given an array, print all pairs whose sum is also a number in the same array.We should not use hashmap. It's fine, if complexity is more.
Round 3:
1 . Standard Java questions, thread sync problem in singleton pattern (adding extra null check).
Round 4: (Bar Raiser Round)
1. Given n players, where everyone had played against every other person at least once. Now, we have to stand the player in a line such that immediate left of the current player should have lost to him. (I didn't give the correct answer).
2. General questions, like achievements in previous company, any conflict with managers and how u handled that.etc.
Round 5:
1. print two dimensional matrix spirally, (like , from East -> South -> West -> North ),
2. Given array of integers, we should form another array where each element is the product of elements in the given array except that index.
For eg:, input is 5,6,1,3,2 .... then, o/p will be 36,30,180,90
Note: we should not use division operator. But, we can use extra space.
Interview experience with via.com
1) Asked me brief intro about myself.
2) Why do you want to change company?
3) Given a string. Remove duplicate characters from the string in optimum way.
4) How do u design a stack such that push(), pop() and getMin() opearations are done in O(1) time complexity
5) Given two sorted arrays. Return Kth maximum sum formed by pairs of elements such that first element in from array1 and second element is from array2.(For this one i gave brute force approach)
6) Given a sorted rotated array.Write an algorithm to find the element in the array.
7) Did you ever override hashcode() method ? If yes, in which cases you overrode?
8) Advantage of using Thread class over Runnable interface?
Subscribe to:
Posts (Atom)