# Data structures Interview Questions

interview questions shared by candidates

## Data structures Interview Questions

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

Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function). 9 AnswersI 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. Show More Responses boolean isBST(TreeNode node) { if(node.isLeafNode( )) return true; else { if(node.value node.rightChild) return false; else return (isBST(node.leftChild) && isBST(node.rightChild)) } } traverse in order and see if they r same @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. ============= Those are just two function calls and the function never returns true. Alexander is right - you are missing a terminating clause in your recursion. Forgot to add - your second solution is correct since it returns true. // For +ve number OR use INT_MIN instead of -1(s) bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin rightMax ? leftMax : rightMax; return true; } // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } |

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

Given a string find the first non-repeated character. 10 AnswersHint: use a hash table public static char getFirstNonRepeatedChar(String s) { List charList = null; char nonRepeatedChar ='?'; if (s != null) { s = s.trim(); charList = new ArrayList(); for (int i=0; i @Rajiv : Your solution is completely wrong. It will fail for input of "aaa" Reason: on first check, you insert "a". On next check you remove it. On next check you again insert it and return that as your answer, even though it was repeated thrice. Show More Responses hash of non repeating characters tied to a double linked list, remove any repeating character from the hash and the list. at the end the head of the list is the answer. you can use the same hash to keep the counters. public static String findFirstNonRepeatedCharacter(String S) { int[] T = new int[256]; for (int i = 0; i < S.length(); i++) { char next = S.charAt(i); T[next] = T[next] + 1; } for (int i = 0; i < S.length(); i++) { if(T[S.charAt(i)] == 1) return String.valueOf(S.charAt(i)); } return null; } Three ways to find first non repeating character in a string c# find the code below - public char firstNonRepetitive(string inputString) { int nextOccurrence = 0; char firstDistinctChar = ' '; for (int i = 0; i < inputString.Length; i++) { nextOccurrence = 0; for (int j = (i + 1); j < inputString.Length; j++) { if (inputString[i] == inputString[j]) nextOccurrence++; } if (nextOccurrence == 0) { firstDistinctChar = inputString[i]; break; } } return firstDistinctChar; } Check out amazing two more way - program to find first non repeating character in a string c# - three ways http://www.dotnetbull.com/2013/08/find-first-non-repeating-character-string.html program to find first non repeating character in a string c# - three ways My python implementation: def firstNonRepeatingCharacter(inputString): hashmap = {} for x in inputString: if (x in hashmap): hashmap[x] = hashmap[x] + 1 else: hashmap[x] = 1 for x in inputString: if (hashmap[x] > 1): continue else: return x return "No nonrepeating character found" for (int index = 0; index < str.Length; index++) { if (str.LastIndexOf(str[index]) == str.IndexOf(str[index])) { return str[index].ToString(); } } I will have one variable x to store the first non repeating character, variable y as a backup And a set of characters already encountered. I will start from position n to position 0 where n is the lenght of the string. If char(n) is not present in the set, then check if x=char(n), if yes, x = y. If no, y=x and x=char(n). The idea is to keep updating the newest character that has not been repeated and also keeping the second newest character as a backup. In the end return x. |

### Software Engineer at Facebook was asked...

Print a singly-linked list backwards, in constant space and linear time. 10 AnswersOne can create a function that takes a node as an argument and checks whether the next of the passed node is NULL or not.In case it is not NULL,the same function is again called for the NEXT node.if the Next of the passed node is NULL,the function prints the value of the node and returns. void f1(node* p) { if(p->next!= NULL) { f1(p->next) } else { print ("%d",p->value); } } Arpit, that's not constant space, that's linear (stack) space, since you will have as many function calls waiting to be returned on the stack as there are nodes. The trick is to reverse the list first (constant space, linear time when done iteratively or tail-recursively) then print it in order (against constant space, linear time). void f1(LinkedListNode lln) { if(lln.next != null) f1(lln.next); System.out.print(lln.value); } Show More Responses Bobby, that is not constant space because it uses O(N) stack space. There are obvoius O(N^2)-time O(1)-space algorithms, and obvious O(N) time O(N) space algorithms. This is my best guess. Assuming you have exclusive access to the list, you can reverse it, walk it, and then reverse it again. Something like this: #include #include struct node { int value; struct node * next; }; void print_backwards( node * head ) { node * prev = NULL; node * cur = head; node * next; while( cur ) { next = cur->next; cur->next = prev; prev = cur; cur = next; } cur = prev; prev = NULL; while( cur ) { printf( "%d\n", cur->value ); next = cur->next; cur->next = prev; prev = cur; cur = next; } assert( prev == head ); } main() { node a, b, c; a.value = 1; a.next = &b; b.value = 2; b.next = &c; c.value = 3; c.next = NULL; print_backwards( &a ); } Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. void BWDisplayLinkedList(node* pHead) { if(!pHead) return; BWDisplayLinkedList(pHead->next); cout data "; } Does this work well? Reverse a list, print it, and then reverse it again. struct node *reverse(struct node *oldlist) { struct node *newlist = NULL; while(oldlist!=NULL) { struct node *temp = oldlist; oldlist=oldlist->next; temp->next=newlist; newlist=temp; } return newlist; } void display(struct node **q) { struct node *temp; temp = *q; if(*q==NULL) { printf("List is empty\n\n"); } else { while(temp!=NULL) { printf("%d=>",temp->data); temp=temp->next; } printf("||\n\n"); } } //p is our list p = reverse(p); display(&p); p = reverse(p); Thanks to recursion :) void print_backward(node* n) { if(n == NULL) return; print_backward(n->nxt); cout val << endl; } Yes recursion does the job in linear and constant time. :-) |

### Software Engineer at Facebook was asked...

Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes). 8 AnswersRecursively: - convert the left subtree (returns a dbl-linked list (DLL) with a head ptr & tail ptr) - convert the right subtree (same) - connect the left DLL tail to the right DLL head bi-directionally - return the combined list (head = left-head, tail = right-tail) struct StackEntry { Node *pNode; bool fVisit; }; inline void linkNodes(Node *pLeft, Node *pRight) { pLeft->pNext = pRight; pRight->pPrev = pLeft; } inline void visitNode(Node **ppFirst, Node **ppPrev, Node *pNode) { if(ppPrev == NULL) { *ppFirst = pNode; *ppPrev = pNode; } else { linkNodes(*ppPrev, pNode); *ppPrev = pNode; } } void doubleLink(Node *pRoot) { stack stack; Node *pFirst = NULL; Node *pPrev = NULL; StackEntry rootEntry = {pRoot, false}; stack.push(rootEntry); while(stack.size() != 0) { StackEntry &top = stack.top(); stack.pop(); if(top.fVisit) { visitNode(&pFirst, &pPrev, top.pNode); } else { StackEntry entry; if(pNode->pLeft != NULL) { entry.pNode = pNode->pLeft; entry.fVisit = false; stack.push(entry); } entry.pNode = pNode; entry.fVisit = true; stack.push(entry); if(pNode->pRight != NULL) { entry.pNode = pNode->pRight; entry.fVisit = false; stack.push(entry); } } } if(pPrev != NULL) { linkNodes(pPrev, pFirst); } } class TreeNode { TreeNode* left; TreeNode* right; int value; } TreeNode* MakeCircularDoublyLinked(TreeNode* head) { DoublyLink(head, head); return MakeCircular(head); } TreeNode* MakeCircular(TreeNode* node) { TreeNode* leftEnd = node; while (leftEnd->prev != NULL) { leftEnd = leftEnd->prev; } listNode* rightEnd = node; while (rightEnd->prev != NULL) { rightEnd = rightEnd->prev; } rightEnd->next = leftEnd; leftEnd->prev = rightEnd; return leftEnd; } listNode* DoublyLink(TreeNode* current, TreeNode* prevTreeNode) { if (current == NULL) { return NULL; } current->left = DoublyLink(current->left, current); if (current->left != NULL) { current->left->right = current; } current->right = DoublyLink(current->right, current); if (current->right != NULL) { current->right->left = current; } if (prevTreeNode->left == current) { // we are processing the left subtree, return the rightmost // element to the parent while (current->next != NULL) { current = current->next; } } else if (prevTreeNode->right == current) { // we are processing the right subtree, return the leftmost // element to the parent while (current->prev != NULL) { current = current->prev; } } return current; } Show More Responses Detailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html Java, non-recursive. O(n) time, O(1) space: import java.util.Stack; public class TreeToCircList { public static class Node { public Node left = null; public Node right = null; public int data; } public void convert(Node node) { boolean leftChecked = false; Node prev = null; Node start = null; Stack s = new Stack(); while(node != null) { if(leftChecked == false && node.left != null) { s.push(node); node = node.left; } else { // Perform the linking node.left = prev; if(prev != null) prev.right = node; else start = node; // Mark start of the list prev = node; if(node.right != null) { node = node.right; leftChecked = false; } else if(s.empty() == false) { node = s.pop(); leftChecked = true; } else { node = null; } } } // Find the first node to link with the last node if(prev != null) { start.left = prev; prev.right = start; } } } Thanks to recursion .. this is a sorted linked list .. to make it circular just make a pointer from the last to the head. :) bst_node* getList(bst_node* nd) { if(nd == NULL) return NULL; bst_node* head; bst_node* l = getList(nd->lft); bst_node* r = getList(nd->rt); if(l != NULL) { head = l; head->lft = nd; nd->lft = r; } else { head = nd; head->lft = r; } return head; } void print_list(bst_node* bst) { bst_node* head = bst; while(head != NULL) { cout val lft; } } void BinTree::convert() { Node * head, * tail; convert_to_dlist(root, head, tail); Node * current = head; while(current != tail) { cout val right; } cout val val left; } cout val left, lhead, ltail); convert_to_dlist(node -> right, rhead, rtail); if(lhead == NULL && rhead == NULL) { head = node; tail = node; head -> left = head; head -> right = head; } else if(lhead == NULL && rhead != NULL) { head = node; head -> right = rhead; rhead -> left = head; tail = rtail; head -> left = tail; tail -> right = head; } else if(lhead != NULL && rhead == NULL) { head = lhead; head -> left = node; node -> right = head; tail = node; tail -> left = ltail; ltail -> right = tail; } else { head = lhead; tail = rtail; ltail -> right = node; node -> left = ltail; node -> right = rhead; rhead -> left = node; head -> left = tail; tail -> right = head; } return; } Solution by recursive in-order traversal. To make code simply I did not make linked list circular. It can be done by simply modification to return both head and tail and connect them outside recursion. Node Convert(Node root) { if (root == null) return null; Node last = null; return InOrder(root, ref last); } Node InOrder(Node node, ref Node last) { Node left = null; if (node.Left != null) left = InOrder(node.Left, ref last); node.Left = last; if (last != null) last.Right = node; last = node; if (node.Right != null) InOrder(node.Right, ref last); return left ?? node; // return the smallest node which will be the head } |

### Data Scientist Intern at LinkedIn was asked...

Find the second largest element in a Binary Search Tree 16 Answersfind 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; } Show More Responses Above answer is wrong. it has to be something like this. public static int findSecondLargest(Node node) { Node secondLargest = null; Node parent = null; Node child = node; if (node!=null && (node.hasLeftChild()||node.hasRightChild())) { if (node.hasRightChild()) { while (child.hasRightChild()) { parent = child; child = child.rightChild(); } secondLargest = parent; } else if (node.hasLeftChild()) { child = node.leftChild(); while (child.hasRightChild()) { child = child.rightChild(); } secondLargest = child; } } return secondLargest; } The above answer is also wrong; Node findSceondLargest(Node root) { // If tree is null or is single node only, return null (no second largest) if (root==null || (root.left==null && root.right==null)) return null; Node parent = null, child = root; // find the right most child while (child.right!=null) { parent = child; child = child.right; } // if the right most child has no left child, then it's parent is second largest if (child.left==null) return parent; // otherwise, return left child's rightmost child as second largest child = child.left; while (child.right!=null) child = child.right; return child; } Soln by "mindpower" works. Thank you. I am trying to solve a similar problem Find the 2nd nearest high(in in-order traversal) value for a given node Eg: Given nums: 12 7 14 3, construct a BST. If the given value is: 7 then we should return 14 (in the sort order: 3, 7, 12, 14) if the given value is: 3 then we should return 12 (in the sort order: 3, 7, 12, 14) Generic solution in C# for any k. Notice that this example can be easily changed to find the k-th smallest node by doing a depth-first recursion on root.Left first, and then a tail recursion on root.Right. public Node GetKthLargest(int k) { return GetKthLargest(ref k, this.Root); } Node GetKthLargest(ref int k, Node root) { if (root == null || k < 1) return null; var node = GetKthLargest(ref k, root.Right); if (node != null) return node; if (--k == 0) return root; return GetKthLargest(ref k, root.Left); } recursion is not needed. SecondLargest(Node root, Node secondLarge) { if(root.right==null) return root.left; Node secondLargest = root; while(secondLargest.right.right==null) secondLargest=secondLargest.right; return secondLargest; } int getmax(node *root) { if(root->right == NULL) { return root->d; } return getmax(root->right); } int secondmax(node *root) { if(root == NULL) { return -1; } if(root->right == NULL && root->left != NULL) { return getmax(root->left); } if(root->right != NULL) { if(root->right->right == NULL && root->right->left == NULL) { return root->d; } } return secondmax(root->right); } In-order traverse the tree. The second last element in the array in the answer. In Python: def find_second_largest_bst_element(root, parent=None): if parent is None: # BST root if root.right is None: # no right subtree if root.left is not None: # if a left subtree exists... return root.left else: # root is the only element of the BST return False else: if root.right is None: # right-most element if root.left is not None: # left subtree exists return root.left else: # leaf return parent else: # check right subtree find_second_largest_bst_element(root.right, root) find_second_largest_bst_element(root) For kth smallest, descend the left subtree first. class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def findKthLargest(root, k): global count if root is None: return findKthLargest(root.right, k) count += 1 if count == k: print root.value return findKthLargest(root.left, k) count = 0 r = Node(10, Node(5, Node(2), Node(7)), Node(30, Node(22), Node(32))) findKthLargest(r, 3) // solution in java // main routine Node findSecondMax(Node root) { if(root == null || (root.left == null && root.right == null) return null; else { Node max = findMax(root); return (max.parent == null) ? findMax(max.left) : max.parent; } } //helper routine, recursive implementation.... can also be done non-recursively Node findMax(Node root) { return (root.right == null) ? root : findMax(root.right); } Show More Responses Find the largest number in the binary tree and delete it. And again find the largest number. Short and fast. Reverse in-order traversal of the BST, keeping a count of # of visited nodes. This methods works great to return the kth largest element in a BST. mindpower's solution looks right |

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 Answerspublic static int notRepeated(int[] given) { Map m = new HashMap(); for(i=0; i < given.length; i++) { if(m.get(given[i])) { m.put(given[i], 2); } else m.put(given[i], 1); for(x:m) { if(x == 1) return x; } } } If you have an array of positive integers with only ONE non repeated integer, the easiest thing is just xor them all. Whatever you return will be the answer. Perl answer below sub findNotRepeated{ my ($arr) = @_; if(@$arr==0) { return - 1; } my $val = 0; foreach(@$arr) { $val ^= $_; } return($val); } sub findMissingElement{ my ($arr,$arr2) = @_; if(@$arr==0 || @$arr2 == 0 ) { print " arr2=" .@$arr2 . "X\n";; return - 1; } my $val = 0; foreach((@$arr , @$arr2)) { $val ^= $_; } return($val); } first sort the array.n then 1)for i=1 to n { if ( element [i] !=element [i+1] ) { cout< Show More Responses This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer. public int returnNonRepeat(int[] input) { if(input.length < 3) return -1; else { int repeat = null; if(input[0] == input[1]) repeat = input[0]; else if(input[0] == input[2]) return input[1]; else return input[0]; for(int i = 2; i Cant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) space only 2 possible solutions 1.) using sorting 2.) using additional space. which will be less than o(n) sub find_odd { my @a = @{$_[0]}; my ($i, $n); $n = $a[0]; for $i (1 .. $#a) { $n = $n ^ $a[$i]; } printf("number is %s\n", $n); } Use xor idea: 2(1 + 2 + 3) - (1+2+3+2+3) = 1 array = [1, 2, 3, 2, ,3] return( (2*sum(set(arr)) - sum(arr)) This person from Amazon told me what to expect in this interview. it was really good info and helpful. Here's their profile: https://www.rooftopslushie.com/profile/ask public static int NotRepeated (int ar[], int n) { int answer = -1; ArrayList arList = new ArrayList(); System.out.println(Arrays.toString(ar)); int n1 = 0; int n2 = 1; for (int i = 0; i < n; i++) { n1 = i; n2 = i +1; if (i == ar.length && (ar[i] != ar[i-1])) answer = ar[i]; else if (ar[n1] == ar[n2]) i++; else if (ar[0] != ar[1]) answer = ar[0]; else { if (ar[n1-1] == ar[n1]) { if (ar[n2] == ar[n2+1]) i++; else answer = ar[n2]; } else answer = ar[n1]; } } |

### Software Engineer at Google was asked...

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 Answers1) Each person is represented by an object, with two pointers: "mom" and "dad" that point to their respective parent. 2) Choose one of the two people arbitrarily. Perform depth-first traversal and create a set of ancestors reachable from that person. Perform depth-first traversal on the 2nd person and for each node visited check if they are in the set; if yes, return true. Use a hash-set for best performance. calculate the height of person 1 in the tree, calculate the height of person 2. Move them up to be the same height. Then keep going until they intersect. @user: Its not a tree. A genealogy is a graph due to the fact that you have maternal and paternal trees intersecting. Therefore there is no root from which to calculate height. Show More Responses If you've optimizing for worst case, hash set is O(n) for search. You'd do better in worst case with a sorted structure. You'd do even better if you store a "visited" flag at each node. Alternately you can number each node and keep an array of visited flags. since depth first seach might find a longer link through dad before checking mom, you're better off with breadth first search. Anything reachable in one hop would be seen before anything reachable at best in 2 hops Yes. Good points. The second traversal should be breadth first. The first traversal it doesn't matter, as you need to visit all ancestors anyways. The use of a visited flag is a good optimization. Based upon the way the question was worded, it wasn't clear if you could design the data structure to optimize the algorithm or not. I belive both the first and second should be BFS traversals |

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

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 AnswersUse any collection data structure to insert and remove the numbers, such that at the end the only one remaining will be the one repeated an odd number of times. For example we can use a tree. We consider on number at the time. We first search for the number in the tree. If found, we will remove it. Otherwise, we will insert it. At the end, the number (or the numbers, in general) repeated an odd number of times will be in the tree. For the complexity it is necessary to perform an amortized analysis. Another data structure that we can use is the hashmap. However, the space consumption and management could be high, if the map automatically resizes. Ex-or the numbers. For the odd occurrence, the ex-oring will not result in zero. Ex-oring is a great idea, one other solution is to sort the array and then in one pass you can find out the number that occurs odd number of time with quicksort avg case nlogn and worst case n^2 Show More Responses Few steps of counting sort can help us do it in O(n) time. Step I: find min and max, thus the range Step 2: initialize array of the range with 0 Step3: as numbers come in, increment the a[number] by 1. Step4: scan the array to find the odd number. Ex-or is a good solution only if 0 is not in the input list. If 0 occurs odd number of times, not sure it will report it. Tellig about zero is an excellent catch.. +1 by using LINQ it can be acheived. var numList = new List() {1 ,2, 3, 3, 2, 2, 1, 4, 2 }; var oneOccurance = numList.GroupBy(x => x).Where(y => y.Count() == 1).Select(y => y.Key); //Ans = {4} |

### Software Developer at Epic was asked...

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 Answershint: the memory can only hold n data, use them wisely. we can solve this problem using n^2 complexity time we scan the whole enters to find the smallest value and we do that in a for loop its complexity is bad, n square anyone knows better answer? how about using hash table? Show More Responses Use an external mergesort http://en.wikipedia.org/wiki/External_sorting hash table |

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 Answers2^10 You judge from the result of test. There is 2^10 kinds of possible conditions and each of them leads to a different result. So you can tell from 2^10 bottles. The mixtures are made as: 1. label all the 2^10 bottle from 0-1023 in binary numbers. 2. for each numbers, if any of the figures is 1, then mix this bottle into the corresponding cup. Like bottle 0000100101(2) =37(10) , figures in place 6, 3 and 1 are "1", so mix this bottle of wine into cup 1, 3, & 6. If and only if the mouses of cup 1, 3 and 6 die, the poisoned bottle will be 37. I solved it a different way, but got the same answer -> 2^10. Start with base cases and work up. 1. If you have one glass, can have at most two bottles one poison, one not (if mouse dies, the bottle is poisoned. if mouse doesn't die, it's not poisoned and the untested one is) 2. Two glasses, four bottles one bottle untouched, one bottle in glass 1, one bottle in glass 2, one bottle in glasses 1 & 2. (similar idea: if no mice die, first bottle is poisoned. if mouse 1 dies, second bottle is poisoned. if mouse 2 dies, third bottle is poisoned. if both mice die, fourth bottle is poisoned) 3. 3 glasses, 8 bottles distributed as follows: - 1 bottle untouched - 1 bottle in glass 1 - 1 bottle in glass 2 - 1 bottle in glass 3 - 1 bottle in glasses 1 & 2 - 1 bottle in glasses 2 & 3 - 1 bottle in glasses 1 & 3 - 1 bottle in glasses 1, 2, & 3 4.... All the way up to 10 glasses seems a bit garbled. just put wine from one bottle in one cup, and give it to the mouse. if he dies, you are done. if he lives, add wine from a second bottle and give it to the mouse. repeat until the mouse is dead. the last bottle you opened is the poisoned one. hard to believe the question was actually worded that way. Show More Responses I also came with the same answer in a different way. if n bottles, then make mixture of n/2 bottles and test, you would know which half the poisoned bottle belongs to. Next take n/4 and n/8 and so on. so log2(n) = 10 , n = 2^10 Notice that "you must give all the mixtures of the 10 cups before the test.", so you cannot test them one bottle by one bottle or half of bottles in one time |