Data structures Interview Questions | Glassdoor

Data structures Interview Questions

117

interview questions shared by candidates

Data structures Interview Questions

Sort: RelevancePopular Date

Find the second largest element in a Binary Search Tree

16 Answers

find the right most element. If this is a right node with no children, return its parent. if this is not, return the largest element of its left child.

One addition is the situation where the tree has no right branch (root is largest). In this special case, it does not have a parent. So it's better to keep track of parent and current pointers, if different, the original method by the candidate works well, if the same (which means the root situation), find the largest of its left branch.

if (root == null || (!root.hasRightChild() ) { return null;} else return findSecondGreatest(root, root.getValue()); value findSecondGreatest(Node curr, value oldValue) { if(curr.hasRightChild()) { return (findSecondGreatest( curr.getRightChild(), curr.value)); } else return oldValue; }

Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function).

9 Answers

Given a string find the first non-repeated character.

10 Answers

Print a singly-linked list backwards, in constant space and linear time.

10 Answers

Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).

8 Answers

You are given an array with n positive integers where all values in the array are repeated except for one. Return the one that is not repeated.

7 Answers

You have a genealogy: 1) Describe a data structure to represent it. 2) Given any two people within the genealogy, describe an algorithm to determine if they share a common ancestor. You just need to return true/false, not all ancestors.

6 Answers

Given a (potentially large) array of integers, all but one repeating an even number of times, how would you find the one repeating an odd number of times in an efficient way? eg [1 2 3 3 2 2 1 4 2] should return 4

7 Answers

I have a log that consists of more than 100 million lines. Each line is just a data about user login, login time, etc. I want to sort them based on user login, and then if there is a tie based on login time, etc. However, I have limited memory, so don't think of storing all of them in an array. The memory can only hold n data where n is much smaller than 100 millions. You can access the disk though although it is much slower. How will you do it so that it is as efficient as possible?

5 Answers

Given 10 cups to locate the bottle poisoned wine from a batch of normal ones, you can make any mixture of them and test your mixtures by mouses. However the density of poison in the mixture, the testing mouse will certainly die. And you must give all the mixtures of the 10 cups before the test. There is only one poisoned bottle. How many bottles of wine you can test at most?

5 Answers
110 of 117 Interview Questions