Data structures Interview Questions | Glassdoor

# Data structures Interview Questions

117

interview questions shared by candidates

## Data structures Interview Questions

Sort: RelevancePopular Date

### Software Development Engineering Intern at Amazon was asked...

Jun 23, 2012
 Write a function that returns the depth of a tree.4 Answerspublic static int depth(Node root, int level) { if(root != null) { if(depth(root.right, level + 1) > depth(root.left, level + 1)) return depth(root.right, level + 1); else return depth(root.left, level + 1); } return level; }Slightly simplified :] (I think this works; not doubling up on the recursive calls either) public static int depth(Node root, int level) { if (root == null) return level-1; return Math.max(depth(root.right, level+1), depth(root.left, level+1)); }int finddepth(node_t* node) { if(node == NULL) return -1; else return 1 + MAX(finddepth(node->lchild), finddepth(node->rchild)); }Show More ResponsesThis person is a product leader at Amazon who may be able to give you some good advice. Good luck! https://www.rooftopslushie.com/profile/ask

### Software Development Engineer Intern at Microsoft was asked...

Mar 18, 2009
 Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively.4 AnswersHint: You'll want to use a stack in the iterative version.Haha, I got that same question on my interview. It made me sweat, because I knew I was supposed to use a stack, but I had never done it before. It was fun working it out on my own.public void inOrder(Node* root) { if(root == NULL) return; inOrder(root->left); cout element; inOrder(root->right); }Show More Responses// recursive void InorderTraversal( Node *root) { if ( root== NULL) return ; // status 2 InorderTraversal( root->left ); // status 1 Print (root); InorderTraversal(root->right); // status 0 } // NON-Recursive Version for Pre/In/Post-Order the idea behind this method is to employ a stack to emulate the recursion void NonRecTraversal( Node *root ) { if ( root == NULL ) return ; stack stk; bool flag = 2;// the key: keep track of the status of the top element stk.push(root); while( !stk.empty()) { if ( flag == 2 ) { /* Print (node) ; this is preorder */ if ( stk.top()->left != NULL ) stk.push(stk.top()->left ); else flag = 1; } else if ( flag == 1) { /* Print (node) ; this is inorder */ if ( stk.top()->right != NULL) { stk.push(stk.top()->right); flag = 2; } else flag = 0; } else { /* Print (node) ; this is postorder */ Node *temp = stk.top(); Stk.pop(); If ( !stk.empty() && stk.top()->left == temp ) Flag = 1; // come back from left child Else Flag = 0; // come back from right child } } }

Aug 27, 2012

### Software Engineer Intern at TechSmith was asked...

Oct 13, 2010
 Given a singly linked list, how can you find if there is a loop in the list?3 AnswersI came up with an O(N^2) method, but he told me there is a simpler O(N) method. (Look it up if you are interested)if you get back to the starting node after reversing the list, that means there is a loop in the list.http://ostermiller.org/find_loop_singly_linked_list.html

### Software Development Engineer at Amazon was asked...

Feb 1, 2011
 Given an array of integers, all but one of which appears an even number of times, find the one integer which appears an odd number of times.3 AnswersI answered him that we can do a XOR, and then he asked me to it in another way and wanted me to write a code, read out so that he could note it. I wrote the code using HashMap.XOR fails for an invalid input [2,4,6,6] as it will return 6. You should validate your args and in this case the cost of validating your args is the same as obtaining the solutionCreate a hash set. Iterate through the array. If the set contains this value already, remove it Else add the value to the set In the end, if a value was in the array an even number of times, it is no longer in the set. Otherwise, it's still in the set. After iterating through the array, the set will contain only one value, the one that was repeated an odd number of times.

### Software Engineer Internship at Palantir Technologies was asked...

Oct 18, 2011
 Print the nodes of a complete binary tree in level order.2 AnswersBreadth first searchDetailed analysis and solution are available in the following blog: http://codercareer.blogspot.com/2011/10/no-11-print-binary-trees-from-top-to.html

### Software Engineer at Zynga was asked...

Sep 1, 2011
 Blocking queue implementation. Coding was required.2 AnswersConventional implementation that can be found in most data structures and algorithms books or Wikipedia.get the synchronization right on the push and offer on the BlockingQueue. Use either Locks or wait / notify mechanism.

Oct 1, 2010