Data structures Interview Questions | Glassdoor

Data structures Interview Questions


interview questions shared by candidates

Data structures Interview Questions

Sort: RelevancePopular Date

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

9 Answers

I came up with a recursive solution something like this: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if (node != null) { if (node.left != null && node.left > max || node.right != null && node.right < min) { return false; } else { return (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)); } } else { return false; } }

How come this function never returns true? And why would you need min and max?

Ok, so I should have spent a little more time posting this (I was admittedly rushing through it so I could get access to more questions/answers). Here's a revised version that should hopefully make more sense: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if(node == null) { return true; } if(node.value > min && node.value < max && IsValidBST(node.left, min, node.value) && IsValidBST(node.right, node.value, max)) { return true; } else { return false; } } The main change is that I decided to avoid checking the children of the tree in the body, and leave it to recursion to take care of that. Thus, we just have to look at the current "node" and that's it... the constraints will be handled by passing min and max down. @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. Finally, the min and max values are required because a BST requires that each value in the left branch be smaller than ALL parent values on that branch (and similarly for those on the right branch being larger). Another way of saying this is that the entire left tree of any node must be smaller than the node's value, and the entire right tree must be larger than the node's value. Thus, in a recursive solution, you have to have a way to pass down the upper and lower bounds to the lower levels of the tree, otherwise the third level won't be able to check whether it's smaller/larger than the root two levels up. That's why we pass down the min and max values. Hope this helps.

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

Find the second largest element in a Binary Search Tree

16 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.

11 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