Algorithm Interview Questions
interview questions shared by candidates
Algorithm Interview Questions
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 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 One or more comments have been removed. |
Describe and code an algorithm that returns the first duplicate character in a string? 12 AnswersSimple Python example. Not sure it's most efficient. def findDup(str): match=[] i=1 while (i first clarify if it is ASCII or UNICODE string For ASCII, create BOOL checkArray [128] = {false}; walk the string and update the index of checkArray based of the character. for (int index=0;index< strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } public class FirstDupCharacter { public static void main(String[] args) { System.out.println(findDupCharacter("abcdefghiaklmno")); } private static Character findDupCharacter(final String input) { final Set set = new HashSet(); Character dup = null; for (int i = 0; i < input.length(); i++) { if (set.contains(input.charAt(i))) { dup = input.charAt(i); break; } else { set.add(input.charAt(i)); } } return dup; } } Show More Responses String samp = "Testing"; samp = samp.toLowerCase(); char chararr[] = samp.toCharArray(); int size = chararr.length; char repeat = ' '; for (int i=0;i for (int i=0;i public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index < characters.length; index++ ) { // insert the character into the map. // returns null for a new entry // returns the index if it previously if it existed Integer initialOccurence = charsMap.put(characters[index], index); if ( initialOccurence != null) { return initialOccurance; } //there where no characters that where duplicates return -1; } } Another python solution: def findFirstNonRepeatedCharInOneIteration(str1): for i,j in enumerate(str1): if j in str1[:i] or j in str1[i+1:]: print "First non-repeated character is "+ j break str1 = "abcdefglhjkkjokylf" findFirstNonRepeatedCharInOneIteration(str1) function getFirstDuplicateCharacter(str) { const seen = new Set(); for (const char of str) { if (seen.has(char)) return char; seen.add(char); } } import java.io.*; import java.util.*; /* * code an algorithm that returns the first duplicate character in a string? */ class Solution { public static void main(String[] args) { String input = ""; int j = removeduplicate(input); if(j == input.length()){ System.out.println("String has unique characters" ); } else{ System.out.println("duplicate character is "+input.charAt(j)); } } public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i import java.io.*; import java.util.*; class Solution { public static void main(String[] args) { String input = ""; int j = removeduplicate(input); if(j == input.length()){ System.out.println("String has unique characters" ); } else{ System.out.println("duplicate character is "+input.charAt(j)); } } public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i public static int removeduplicate(String input){ Set set = new HashSet(); boolean flag = false; int i =0; for(; i One or more comments have been removed. |
Senior Software Engineer at Facebook was asked...
Write some pseudo code to raise a number to a power. 11 Answerspretty trivial... int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; } Show More Responses In Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}" If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations. Because it uses dynamic programming and is lots more efficient than your algorithm. If the power is not integer, use ln and Taylor series If I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1. There is a way to do this in a logN way rather than N. function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1); } This is from Programming pearls.. interesting way. small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; } # Solution for x ^ n with negative values of n as well. def square(x): return x * x def power(x, n): if x in (0, 1): return x if n == 0: return 1 if n < 0: x = 1.0 / x n = abs(n) # Even number if n % 2 == 0: return square(power(x, n/2)) # Odd number else: return x * power(x, n - 1) print ("0 ^ 0 = " + str(power(0, 0))) print ("0 ^ 1 = " + str(power(0, 1))) print ("10 ^ 0 = " + str(power(10, 0))) print ("2 ^ 2 = " + str(power(2, 2))) print ("2 ^ 3 = " + str(power(2, 3))) print ("3 ^ 3 = " + str(power(3, 3))) print ("2 ^ 8 = " + str(power(2, 8))) print ("2 ^ -1 = " + str(power(2, -1))) print ("2 ^ -2 = " + str(power(2, -2))) print ("2 ^ -8 = " + str(power(2, -8))) |
Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this? 8 AnswersIt can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming. Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!? Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Show More Responses Awesome!! The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features Let a[][] be the 2d array, int i=0; for( j = row_start; j <= row_end; j++) for( k = col_start; k <= col_end; k++) i+=a[j][k]; Iterate over matrix as an array storing (new sums array) in each position the cumulative sum up to that point. For each row in the desired submatrix we can compute its sum as a difference between its end and start positions. Repeat for other rows. Add up all the row sums. One or more comments have been removed. |
IT Developer at FDM Group was asked...
How many unique handshakes if each person in a group of 10 give handshakes out to each and every other individual. (a) 100 (b) 50 (c) 45 (d) 20 (e) 10 5 Answers45. Imagine it as a polygon of side 10. Or draw out triangle, square, pentagon, and see the pattern yourself, if you don't know the algorithm. true, or 9+8+7+...+2+1 Or just do: (10 Combination 2) = 10!/(2!8!) = 45 Show More Responses n(n+1)/2 Where n =9 Answer: 45 One or more comments have been removed. |
Write code in your favorite programming language that will accept two strings and return true if they are anagrams. 2 AnswersThis was not really that hard to write it, however the interviewer asked me to reduce the complexity. My initial version had n*log(n) complexity and he asked me to reduce it to no more than n complexity. If you have had some upper level Computer Science classes this is not too difficult, however what they are looking for is a way to stump you. If you adjust your code or thinking rapidly to their request they will change it again until they find something that you have trouble with. Do not be discouraged by this, it is the interviewers job to determine how much you know! Found this good link. Time complexity is O(n). http://www.dreamincode.net/code/snippet1481.htm The algorithm can still be improved but gives some basic idea on how to implement. |
Manager at Amazon was asked...
If you had 5,623 participants in a tournament, how many games would need to be played to determine the winner 63 AnswersBefore I could figure that out, I'd need to know whether the # of participants represents the number of individuals on larger teams, or the number of teams A specific numerical answer can be given, but there are multiple ways the tournament can be setup, for example, are there play-in games, byes, etc. I would think the question is being given to a manager to see how they think and process, and then come up with a specific numerical answer, as opposed to just a math problem. It can be just one game. A huge mock battle. Show More Responses 5,622. Assuming it is a single elimination tournament. All teams lose one game except the champs. It's always # of teams - 1 if each team plays until it loses in one(team)-on-one(team) contests, the answer is ln(5623)/ln(2) Assuming it is a simple process of elimination, it takes 5622 losers to get 1 winner from 5623 participants. So, it would require 5622 games. Assuming it is a simple process of elimination, it takes 5622 losers to get 1 winner from 5623 participants. So, it would require 5622 games. if it's a 1:1 type draw, then # rounds = (5623)**x where x is base 2. a good answer is between 12 and 13 rounds. 2**12 = 4096 so I'd draw up 13 rounds and give out 1,527 byes. There is no true answer as the question is very open ended. The interviewer is probably looking at task delegation, management and creativity skills. One One. Obviously. One game, all players participate. If participants equal number of teams involved, think power of 2. Show More Responses The interviewer is not looking for the right answer because there can be many. What he/she is looking for is your logical approach in solving the answer. So you could start by probing more is first I would like to understand if 5,623 participants represent the number of team or individuals. Then ask the next logical question based on the answer. Everyone who didn't ask a follow up question except Mike is right. The question says, "if YOU had ...". This requires no follow up questions, because YOU should decide how YOU are going to operate YOUR tournament. Why would Mike or any of the others think it's someone else's job to organize his/her tournament. Oh just a follow up. My tournament would be held in the top of a hardly dormant volcano. Everyone would get a backpack full of grenades and the first one out of the crater without dying wins. That makes 1 game. Also, I think most participants who got out of the volcano alive would consider themselves winners, but only one would get to keep the gold plated dancing chiquita banana. Yipee!!!! I'm right too! Take that Mike! it'd be one game if it was a battle to the DEATH I agree with Nancy there is no strict answer to this question it is all about problem solving. First thing to do is to get more information, if it is not forthcoming then make assumptions, as an interviewer I would not be impressed if the candidate didn't ask for more information, although I probably would not supply any more. Then looking for a logical (and humane) answer which is substantiated with appropriate reasoning. Ie number of people on a team, game being played, what is required to win a match, are there several games in a match? knockout style tornamant sounds like a good approach. I agree with Mike. Just show the interviewer how you think and how you will tackle the problem in a colloborative environment 1 I agree with the very first response. Many of you are perhaps making the assumption that this is a one-on-one tournament such as singles tennis. Isn't it possible the question could refer to a soccer or basketball tournament where there are multiple players on each team? That would certainly bring the number of games to be played down considerably. I'd give an approximate answer, stating my assumptions. The question asked is not the number of rounds (2 people per game: log base 2, giving approximately 13 rounds with everyone playing at least one game ) - it's the number of games. So, if two people per game, then it's the sum of 5623/2 + 5623/4 + 5623/8 + 5623/16 + ... The limit of this is not something I know off the top of my head, but it's less than 5623. Also, interestingly, you need to account for the original number being odd. That could be accommodated in a number of ways, none of them straightforward. 5622 ... if based on elimination between 2. Show More Responses I personally agree with most of you. If you read the posts here, you see all types of answers. Some say "1". Short and simple rules to a simple game. Others have posted all types of formulas and methods to figure out a process. The answers here are all a good example of different minds using different means to find an end. Those different answers are what a good interviewer would be looking for. If the job needs a person that is logical and takes time to plan things out, or perhaps someone that needs to think fast on their feet. That kind of question could come in handy for any kind of interview in my opinion. 1 I think the interviewer is asking you to ask for more information, ask three qualifieng questions to be exact in order to show you have the probing skills to fully understand a customers situation or company problem and have the ability to ask the appropriate questions to or to get the help to solve. Question 1) How many players are allowed per round? Question 2) Is there a time restriction on these rounds? (Daylight or Night as well) Question 3) Are there going to be different classes for the golfers? Are we taking handicaps into consideration? I guess there could be more questions but chances are the interviewer would stop you after the third question. The correct answer is: "I didn't come here to play bulls**t games for 8 hours, you Mac-slinging hipster. Ask me a real question." 5622....................................assuming single elimination 5623 is a prime number. Good luck dividing into even teams. Also, there is no use of the word "minimum" in the original question. This question is a good example of a problem with no absolute answer. If I were to ask this of an interview candidate (which I wouldn't because I think subjective questions are mostly a waste of time for everyone involved), I would look for someone who can: A) Ask questions to pin down a few details. B) Formulate options. C) Suggest options with recommendation and take feedback. D) Execute (pretty hard to demonstrate in the 10 minutes max I'd give this). p.s. I'd hire chapped. Good answer! Depends on the numbers of players per team. 'Excuse me, I'm just waiting for excel to open and my math wiz buddy in accounts to pick up to verify my calculation. I'll get back to you in two minutes with the answer.' 'Excuse me, I'm just waiting for excel to open and my math wiz buddy in accounts to pick up to verify my calculation. I'll get back to you in two minutes with the answer.' I would try and be creative and put my suggestions in front of them while I give them a reason for all the options that I choose. For instance, I'd say I would create 5 levels for each game as adding more levels makes the game more challenging and interesting. I wouldn't want to set up too many games as it would require a lot of overhead using up a lot of resources for organizing large number of games. Hence, in each round I would eliminate 20 participants. That would make 100 players getting eliminated after every game. After every 10 games, I would allow all the eliminated contestants to battle it out and 15 can re-enter the game as the eliminated ones would get a chance to observe, learn, refresh and get a second chance... (The interviewer might stop me eventually before it gets too long). Even though my answer was too long, I think I would show them how my logical thinking works. They would see that I am thinking aloud and in the end all that matters is how we approach the problem rather than giving them a vague answer with no reasoning. Show More Responses Oh and I agree with Toasty, I would hire chapped :) I like the way they think. Oh and I agree with Toasty, I would hire chapped :) I like the way they think. i dont know how everybody else thinks butI divided by two with an extra game for when the number is odd and came up with 5627. the question was straight forward, " How many games".... I would have been startled as well, just reading it. Congrats on keeping your calm! My intuitive answer would have probably been: Game theory - 1 or rather none - when it's a battle to death everyone loses, even the winner (last man standing, howling at the moon). I would have likened it to the company and customer situation - in good company EVERYONE is a winner (win-win scenario). Good luck with your endeavors! 1. I think, this question is for a management position. The size of team is given as a too big random number. One cannot control a team of 5627. Divide them in a measure size, e.g size of 10 or 20 (any measureble size). With 10, there will ve 563, which can be further divided into 10, leading to apx 57. that can be futher divided into 10, leaving it to 6 teams. proformance/ goals can be set and can be evaluated later. 2. or do a marathon. None. Our PC world demands everyone gets a trophy. ********************* Keep in mind the position, Nathaniel is right. YOU are organizing the tournament, make a rational decision and describe it. Your answer should be formulated to convey a skill. For example I might suggest something like this: 1 on 1 round robin, 5,623 players, SUM(1+2+3+...+5621+5622) games Quick and simple, shows some knowledge of algorithms but not very practical. The 1st participant plays 5622 others, the 2nd plays 5621, until the 5622nd plays 1 (5623rd participant). Notice you don't add 5623. Participant with the most wins is the champion. Supposed it is a single elimination. should be 5626 games because the first row would be 5623/2 = 2811.5 which means 1 person must be going to the next round to compete therefore we will have 2812 contestants then the second row would be 2812/2 = 1406 the third row would be 1406/2 = 703(odd number which means the one of them is going to the next round without a fight. ect... I believe I would have responded with "Is that how many applicants there are for this job?" Followed by "One game, one victor." Before answering you should read the interview report this question is linked from, where the question is explained in more detail -- """If you had 5,623 participants in a tournament, and each participant had to play games until he/she one or lost, and every game had a winner and loser, how many games would have to be played in order to determine the winner of the tournament""" So it's pretty unambiguous: Participants are individuals; the tournament is single elimination; games involve just two parties (a winner and a loser.) The question doesn't ask about the number of rounds involved, nor about timeframe. Just the sheer number of games. So we're left with an answer of 5622 games (because every game has one and only one loser and 5623 - 1 participants need to lose for there to be a single participant left as the winner, so that's how many games there must be.) Show More Responses Assuming in each game "n" people participate and there is just one winner in a game. If N is the total number of people (in this case 5623), then the approximate number of games would be: log(N)/log(g) -1 After each round, you would have half the number that started the previous round; except if it were an odd number it would he half + 1. So 13 rounds. 2812 1 1406 2 703 3 352 4 176 5 88 6 44 7 22 8 11 9 6 10 3 11 2 12 1 13 It is far simpler than you guys are making it out to be. In ALL single elimination tournaments there is one less game than the number of participants. Because in every game 1 team gets eliminated. And at the end 1 team has to be left standing. This will be a detailed explanation. Since they're asking for a tournament, that means one on one matches, and eliminations of 'participants' or players. With such a large number doing a round robin style tournament would not be very efficient, as every player would have to play every other player, ((N-1)^2)/2 =15,803,442 matches. I would first start to get more details of the tournament. If it were up to me to design the tournament and easily determine the number of matches, I would go with single elimination bracket because since its based on power of 2. Contrary to what what Bob InNorCal did, you dont start halving the at the beginning with 5623, because its not power of 2. You will get to a point where there wont be even numbers, and BYEs will have to be given, it would be unfair to give byes out at the end or middle of the tournament, players would complain that others got BYEs and they didnt. Detailed Explaination: In a single elimination bracket, the brackets end with 1 match between 2 players, then 2 matches and 4 player, and eventually for this tournament, 4096 matches between 8192 players. But since we dont have 8192 players, there will have to be BYEs which wont count as matches. In this case we'll have to use a 8192 single bracket, with the first 4096 players spread every other position then the last 1527 players spread evenly throughout the bracket and the remaining 2569 positions are BYEs (4096 + 1527 + 2569 = 8192). Here are how the rounds look like: A - 1527 matches, (4096 matches was suppose to happen, but 2569 BYEs are no counted) B - 2048 matches, C - 1024 matches, D - 512 matches, E - 256 matches, F - 128 matches, G - 64 matches, H - 32 matches, I - 16 matches, J - 8 matches, K - 4 matches L - 2 matches, M - 1 match From round B-M, its (2^12)-1 = 4095, so with Round A, its 4095+1527=5622. The calculated answer 5622 is one match less than the number of participants. However, just because its easy with single elimination to determine the number of matches, does not mean that it is what they initially asked, conversing with the interviewer for more details of the tournament is important. If the interviewer said it was a double elimination tournament then a player would have to lose twice in the bracket to be eliminated from the tournament. Depending on the number of players and the placement of the BYEs, then calculating the number of matches in a true double elimination maybe difficult. Also in Double Elimination, the winner maybe won by someone without a loss or with 1 loss, the winner without a loss means one less game. it is assumed that the competition is a head to head knockout competition like wimbledon. the only correct answer is 5,622. the quickest and smartest way to get that answer is to see that in a knockout tournament every body loses once and only once, except the winner. in every match, one person loses. therefore the number of matches required equals the number of players minus 1. PaulO, Jordan, madhur, simplebrain and key2success you are all hired! How many games are played? Well all of them of course, how else do you find the winner. It need only one game to find the winner If it is your game you can appoint a winner without playing any games. Then 0 is a possible answer. 1 is also a viable answer, if it is a game of life and death it is possible that no one lives then there are no winners on the first round. Such as a game that on the first round were everybody is exposed to a nuclear blast. Even those exposed to the fall out might be considered losers. A game like chess where you eliminate draw contestant then 1 round to 13 rounds would be required. You could divide by 2 to get the rounds or use logarithms to convert 2**13 which is greater than 5,623 to a log equation such as log(5,623)/log(2). Potentially everybody can loose on the first round because of the draw rule and the person with the bye on the first round can loose because they have no one to play to win. You can change the rules so that infinite rounds are required to determine a winner. One way to do this is to increase the elimination rounds so that it approaches infinity. As this goes on your interviewers glaze over and fall to sleep and when they wake up they decide not to give you the job. This can be poker tournament (as too many players). From 5-7 people - one wins. This can keep number of games to reasonable limit. Depends on how many rounds there are to determine a winner. Logical answer here could be 5623 Show More Responses There would be 5613 head-to-head games cosisting of 12 rounds with one team receiving a bye in each round except the fourth round, the tenth round, and, of course, the twelfth round. Assuming the tournament is Mortal Kombat everyone knows that earth realm has to win because out realm is evil and evil... Sucks. No games necessary. What kind of tournament? There will be 2 games. The first game is a question: Would you like to play a game? Which is then followed by the second game - one involving thrones. One The simple answer is Number of Teams minus ONE. Simplified, a four team bracket plays 3 games. All of them. One or more comments have been removed. |
Engineering at Qualcomm was asked...
given 20 "destructable" light bulbs(which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks. 56 Answersbinary search start at the top floor and work down toward the first floor to see on which floor the bulb breaks first Start at the lost likely point based on your experience – the first floor -- and see if the bulb breaks when dropped. If not, then a test is warranted. Start at half way point and keep going up or down to the next halfway point until you determine the height. You should be able to determine the floor within 7 bulbs or fewer and – assuming each floor is 10 feet high, you should be able to determine the exact height in feet within another 5 bulbs or fewer. The greatest number of bulbs you could break to reach the answer would be 12, plus the one for the initial test = 13 total. Show More Responses In my interview at Apple, this question also stated: "You will get a bonus of $1000 for each remaining glass bulb after the test. What is the highest bonus you can absolutely guarantee, and with what algorithm?" The interviewer told me that he only had it answered correctly once, and that person had a master's degree in pure mathematics. The candidate explained the theory behind the answer using lots of appropriately mathematical terms. The long-winded, logic-based solution to prove that you can earn an $18'000 bonus goes as follows: • If you drop a ball from floor X and it shatters, you will need to drop the other from floors 1 to x-1 in that order to find out the lowest floor at which the ball would break. • Therefore, if you started at floor 20 and the ball shatters, you have to drop the other from 1 to 19 to see at which that one will shatter. • If it shatters at floor 19, your bonus is all gone (you're performed 20 drops, losing $20'000 from your bonus). • If the ball does *not* shatter at floor 20, then you might try again at floor 40, but then you'd only have 18 drops left— if it broke at 40, but not at 38 (when you've used all your drops) you don't know if 39 or 40 was the breaking-point. • Therefore, after trying 20, you go up 19 floors to 39 and try again there. • You repeat, going up 18 floors to 58, then 77, then 86, etc. • However, this isn't optimized. You can't *guarantee* a bonus by stepping up by [20 19 18 …], since you could conceivably deduce the amount only using a full 20 drops. • Therefore we look at how we can divide up our 100 floors by a descending sequence: • 10 + 9 + 8 + … = 55 => No Good. • 11 + 10 + 9 + … = 66 => No Good. • Try going the other way; starting at 1 and counting up (sort of like the Fibonacci sequence), at which point do we pass 100? • 1 + 2 + 3 + 4 + … + 12 + 13 + 14 = 105. • Therefore, we can start dropping the ball at floor 14 using the algorithm above, and still have enough drops to determine the exact floor at which the ball breaks, even should it be floor 99 or 100. • Using 14 as a base, this means that the *maximum* number of times we will drop the ball is 14 times, while still guaranteeing that we drop at $BREAK_HEIGHT and $BREAK_HEIGHT-1. Therefore, the correct solution can be calculated using only two glass balls, a maximum of two of which will smash, guaranteeing us a bonus of $18'000. QED :o) Only one light bulb is needed. Start at floor level, drop it, and if it does not brake USE THE SAME BULB for next trial higher up until the very same bulb brakes. One light bulb is not sufficient because even if it does not break, after one drop, it will become more fragile, thus may break at a lower floor than a new bulb. Thus a different bulb should be used for each drop. BTW, there is a closed formula giving the maximum number f of floors for which one can find the height with a given number b of bulbs and a given number w of bulbs that can be broken (and the algorithm can be deduced at the same time). This is probably a well-known combinatoric problem. If the balls do not weaken, then one ball is sufficient and the guaranteed bonus is $19,000. If a different ball is required for each drop, then binary search will find the height of breakage with 7 drops or less (2^7 = 128 > 100), so the guaranteed bonus is $13,000. I believe it can be proven that you can't guarantee better than this. Take the stairs... 1. the question does not say they break when you drop them, it could be air pressure. The question needs clarification 2. the question does not say the bulbs are all the same The question was about light bulbs not about the building or its height. I would get $19000. Take a bulb hold it ,say, 1 inch above a hard surface. Drop it. If it does not break try 2 inches keep adding a inch until it breaks. Nothing was said about testing it from a floor. I could also drop it on a very soft surface and if soft enough make the $20000. Sometimes we think too much. You were misdirected. Take the elevator or walk up the stairs with just 1 light bulb. Once it breaks, check the floor number in the elevator or number on the stair well. You get $19,000 if it breaks, you get $20,000 if it never breaks. You never need 20 light bulbs in the first place. The bulb always breaks against the tarmac so you don't even need to go to the top, just know that the bulb breaks at 0 Show More Responses This is a Newtonian math question. Go to the 50th floor. Does the light bulb break? if yes go to the 25th floor. If no go to the 75th floor. If on the 25th floor the bulb breaks go to the 12 floor if not go to the 37 floor. If on the 75th floor and it breaks go to the 62 floor. If it does not break go to the 87 floor. Basically you continuously do an break vs. not break analysis and divide the most recent floor delta by 2. If it breaks subtract the value from your current floor and go to that floor. If it did not break add the value to your current floor and go to that floor. This is the most efficient way (uses the least amount of bulbs) to find the highest floor that the light bulb will not break. I think Apple took a good approach, but in general, the follow-up question to this one is more interesting, and one I would look for: What is the desired OUTCOME? There are a number of ways to determine the correct floor. But in most tasks, there are desired outcomes. Does the questioner wish the most efficient way to determine the floor number (that's not in the question)? Or does the questioner care more about having extra light bulbs at the end? People often jump into the programmatic solution first, without ever thinking to ask "What should my end state be?" Agree with Andrew and Anthony........start walking down the stairs with one bulb. When it breaks you have your answer. 19 left. I hold a light bulb with care because I know it will break if I drop it. I would question the competence of marketing for wanting to determine height of destruction of a light bulb. I would ask that they just slap a "fragile: contains glass" label on the package and shift resources to R&D to create a light bulb that burns longer and uses less energy because that is what people really care about in light bulbs. Read the manual people!!!!or call the company manufactoring those bulbs!!! 20k in the bank. I believe the answer to the question lies simply in the asking. The point is to get these responses, and more importantly put you into a different frame of mind. You are no longer providing canned responses to generic questions but are now faced with a situation or question that requires novel thought process. Again the answer is not necessarily important, but the result is. You could put all 20 bulbs in a box and start walking up the stairs. Label each bulb as to what floor you were on when it broke. Is this too simplistic, or am I missing something?? Why are alot of people dropping the bulbs. A bulb will most likely break when dropped from almost any height. Who is the Einstein who said to start at the top floor. I think most of the bulbs would already be broken if you were on the tpo floor to start with. Nutbags!!!! In response to Jim, I think you can actually figure it out with only lightbulb lost. Assuming you started from the bottom floor and worked up to the top floor dropping the bulb and then picking it up and dropping it again on the next floor. It would take quite a while though. That is assuming you want to optimize the number of bulbs lost. If you want to optimize based on time, you would want to do a binary search algorithm All of these answers implies two (2) important facts being overlooked. Fact one - no one said you couldn't pick up an unbroken bulb and try it again. Fact two - no one said you had to drop the bulb. It just said "breaks at a certain height." None of you considered that...maybe by ascending the building carrying one (1) bulb...it might just...break? Convergent thinkers!!! Show More Responses I would first correct the grammar in the statement: "how do you determine the height *that* the light bulb breaks..." to "the height *at which* the light bulb breaks..." and proceed to not get the job. Why would you need to know that? The BA in me would seek clarification in the requirements. The questions being asked is unclear. A) Does the question mean the bulb would break if placed on a certain floor of the building or is the asker really meaning the bulb would break if dropped from a certain height? B) Is the goal to find the most efficient solution to the question (i.e. fewest number of tests)? C) Assuming we are dropping the bulbs from the building, can we collect unbroken bulbs and reuse them? Without this information, there is no way to answer the question. The answer depends on this additional information. Simple: Do a Bruceton staircase analysis. This method is used to determine the mean failure height along with a confidence interval ("95% confident that 50% will fail at floor x") and percentile ("99% will fail by floor y") of packages all the time. It also takes into account variations in bulb fragility and minimizes the chance that you have a "bad" light bulb that was more fragile and thus failed early. The one I'm going to cram up your bum for wasting my time... Me: Throw a bulb off at 50th floor, if it breaks go to the 25th. If it breaks go to the 12th and test out a bulb. At that point you have 18 bulbs and about 11 or 12 floors to test either above or below the 12th floor. The same applies if the bulb does not break at the 50th floor, try 75 and follow the same procedure. work from bottom up and throw one at every 10 floors. if the light bulb breaks at this throw, then work downwards and throw at each floor to determine the exact point where the light bulb will break? is it really that hard?? I will go with Bruce! Given the condition that Jim Dovey added in above comments, if one is going to get bonus of $1000! algorithm depends on what you want to achieve. 1. Optimize number of trials: Solution- use binary search approach. guaranteed bonus=13k 2. optimize profit: solutino - start from 1st floor. go up one level. Only 1 bulb needed. guaranteed bonus = 19k CG Your logic is interesting. But when you say (uses the least amount of bulbs) your word usage is incorrect. Amount is for a measured quantity as in amount of sugar. You should have said (uses the least number of bulbs) or (uses the least bulbs) Number is for counted quantities It's funny, variations of this question are so common in the industry I'm currently in that it's become a parody of itself...the answer I gave for an app engineer job after hearing it from the 11th different firm: "I'm not answering it for the same reason you Googled the questions to ask: neither of us have time for this." I kind of just blurted it out. As you might expect, I wasn't offered the engineer position. I was instead offered the group supervisor position. I would not try this at home -- but they told me they'd never had anyone answer it that way, and it was the reason they made me that offer. It's an extreme example of how these questions are as much about attitude as aptitude. Show More Responses $19,000 bonus and one bulb is enough - drop as follws 1,3,6,10,15,21,28,37,47,58,70,83,97 contune untill all 1-100 distances are covered. We can reduce trials and sacrifices some bonus, if each trial cost something that will impact bonus DownOn3 has it. The question didn't say anything about dropping. It said the bulb will break at a certain height, I'll say that means it will break at a certain atmospheric pressure. Take one bulb, leave the rest at the bottom of the building. Walk up the stairs until the bulb breaks. At most, one will break. $19,000 bonus guaranteed. Divide the # of floors in half each time and go to the nearest whole #. Drop a bulb from that floor, then go the next 1/2 way point (50, 12 or 25, and so on). If this is not an atmospheric/pressurization question, all bulbs will break at a height of 0. I'm not even going to waste a bulb on that one. There would be questions before doing the test. What is more important to save time or save bulbs? (Similar question as what is more costly the light bulbs or my time?) If they are experimental bulbs that cost $1000 each, I'm pretty sure I could walk to eah floor in less than 16 hours (and unless I get payed $1000 an hour) then it is more economical to go up one floor at a time (although I would not quite do that). If the bulbs are cheap (let say $1 each) then my time is more expensive. So the number of times over 1 that I drop it an it does not break is wasted time (or money). Then I would use a binary search algorithm. Also if there is an elctro magnet attached to a cable it may help in making the test shorter (ideally it needs to be 25 stories in length). How accurate do the findings need to be? (down to a floor or down to an inch). BTW, the minimum number of bulbs that would need to be destroyed is 3. Since the experiment (yes, it is a scientific experiment) needs to be verified at least 3 times. BTW, LED light bulbs are very tough is is essentially a piece a piece of metal inside a piece of plastic. This bulbs are tough. I have drop an entire fixture from 20 feet (bulbs and metal casing) and it survived. So for those who "ASSUMED" that all bulbs break at distance greater than 0. Thank you for applying, but the management positions are already taken, they were looking for an engineer. As I can tell many people here are not the core group Qualcomm was looking for. This is similar to a question on the published "Cracking the coding interview" on chapter 6.5 in the "Brain Teaser". It is on P96 in 5th edition. Given 20 destructable light bulbs and a 100 story building.... You know what? I don't need this job anymore, I have a 100 story building now!!! I'll stand at the base of the building and smash a lightbulb into the floor. If it breaks, problem solved. If it doesn't break then I'll start taking steps up the stairwell banging on the lightbulb on each step. You only need one light bulb to figure out at what height it breaks, assuming that they're all the same. I generally agree with all the people that say that the lightbulbs break at a height of zero though, assuming that you're dropping the lightbulbs off the building FROM any height. The question wasn't what height the bulb breaks when dropped FROM. Obviously the height that the bulb breaks is ZERO when it hits the ground. But that's assuming that you drop it on the ground next to the building and not on each of the 100 floors. Then again, the bulbs might break at EVERY height. If you so much as touch these light bulbs they will break, let alone drop them! Maybe these lightbulbs and the new high-tech ultra-thin glass breaks in anything short of an absolute vaccuum and zero gravity. Maybe this really is an altitude issue. Maybe your 100 story, 350-foot tall building is insufficient and irrellivent because the bulbs break at an altitude of 35,000 feet. Also, every single one of you assumed that you recieved these light bulbs intact. Maybe to answer the question you simply need to look at the light bulb where it already lies in pieces on the floor. Alternatively, these could be self-destructable lightbulbs with an altimeter and an explosive charge built in. Walking up or down the stairs holding one of these lightbulbs would be suicide. The question then would be what might motivate you to figure this out if it would cost you your life? First read the question and figure out what is being asked, then think outside the box. The question states that the bulbs break at a certain height. That is, not when you drop the bulb from that height, simply that they break at that height (presumably due to air pressure?)... I lose zero bulbs. Simply wait until evening and look up. The number of floors that have lights turned on will tell you which floor they start breaking at. Show More Responses Well I don't see how the number of floors of the building matter. It doesn't ask what floor you need. It asks at what height will the bulb break. Therefore, you just need to know the height at the time the bulb breaks, not what height it was dropped from. You need final height, not initial height. No matter the initial height, the final height will always be the ground. So the height will be zero when the bulb breaks. And I didn't even need a formula! :-) The question does not mention why the bulbs would break. The only reason a bulb would just break at a certain height without impact is because of air pressure. Bulbs are in a vacuum and because of the shape of a typical bulb, positive external pressure will not be a factor. However, a negative external pressure may have an effect depending on the pressure inside the bulb. Also varying barometric pressure will also have an effect. On a bright sunny summer day, the bulb would burst at a greater height. On a cloudy day the barometric pressure is lower so the bulb would burst at a lower height. And the question does not ask for height above sea level or above ground level. This is an open-ended question that leaves for more questions than answers. But if I really want to come up with an definite answer, I would say the "certain" height is the height at which I smash the bulb. So if I am in a building that has a foundation 535 feet above sea level and I smash the bulb on the 100th floor and each floor is 12 feet above the one below: (12 X 99) + 535 = 1723 feet. You do not add 12 feet for the 100th floor because the 1st floor is 0 feet above 535. actually its very hard to understand the question only .. and d ans given here all crap // guys atleast if u dnt knw d ans plzzz dnt give your opnions.. ty It needs just 2 bulbs to efficiently know the floor from where it will break. Assume you have just 1 bulb, then there is no other way to test except trying it one by one from each floor. i.e. start with 1st, if it breaks, well, we know the answer, otherwise go to the next... Now take 2 bulbs...go to the 1st floor, throw one bulb at ground and the other at the height of 2nd floor at the same time. If 1st bulb doesn't break and second one breaks, then 2nd floor is the answer, and we knew it in just one attempt. If neither of the bulbs breaks, we need go to 3rd floor, as we tested already for the 2nd floor. And from 3rd floor, throw one bulb at he ground and the other at the height of 4th floor...we just need to repeat it until one of the two bulbs breaks or we reach at the 99th floor and test the same... But in case you want to use all the 20 bulbs...you need more resources to test... >given 20 "destructable" light bulbs(which breaks at certain >height), and a building with 100 floors, how do you determine >the height that the light bulb breaks. Ha! You ALL failed. This wasn't an interview question to think outside the box. It wasn't a complicated math question, it was a SPELLING test. You failed. "destructable" is spelled destructible. And those of you that used "destructable" in your posts? You're fired.... I agree with Jose, the same answer is mine The question doesn't say you have to drop them. I would place them inside a pressurized container and take them all the way up to the 100th floor and get the full $20k :) I used to work in a 110 story building. If you handed me a box of lightbulbs and told me to toss them off the roof, I'd call Security on you and keep the lightbulbs. End of story. The true maximum bonus acquirable is $19,000, for you would understand that the bulb will break at some floor above floor one, otherwise the question itself would be insensible to ask. with this being said, starting at floor one (for assurance), drop a bulb. if the bulb breaks, you have your answer, and a nice $19,000 bonus. if the bulb survives, you simply drop the bulb from a higher point, i.e. the next floor up. you repeat this process until you find which floor the bulb breaks, since it will break at some height above the ground. all that mumbo jumbo about an algorithm from a person with a masters in mathematics is complete garbage. very simple question with a very simple answer, -Andrew Romero, ChE Major, Junior, University of South Florida. Go Bulls! This question catches people who are not wired to pick up on details and who also make assumptions or jump to conclusions quickly. I was a licensed EMT-SS in college and similar questions were notorious for being on patient assessment exams. If is fundamental to a full assessment to observer everything and assume nothing. Read the problem carefully and don't make any assumptions, ""given 20 'destructable' light bulbs(which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks." Premise: Light bulbs are air tight and are filled with an inert gas or evacuated to prevent oxidation of the filament. Inferences: 1. The problem to solve is "HOW DO YOU DETERMINE the height that the light bulb breaks." 2. The solution to the problem is a "method" (eg. How?) and not "a quantity of units." 3. The light bulbs break "at certain height" which is a single height and not at any or many heights. 4. The problem to solve has nothing to do with the 100 foot building. It could be a resource that could be used to help solve the answer but it is not a variable of the problem. Solutions 1. Light bulbs will break when the difference between their internal and external air pressures exceeds the tolerance of the glass globe of the light bulb. Higher or lower elevations have lower and higher air/barometric pressures, respectively. Therefore, raising or lowering an object changes it ambient air pressure. Hence, the solution is to raise or lower a light bulb until the differences in the internal and external air pressures exceed the tolerance of the light bulb and it breaks. Comments 1. The problem to solve is NOT "determine the height that the bulb breaks when dropped." If it was the answer would be "the ground" because the bulb would break when it hits the ground, not where it is let go to drop. 2. The problem to solve is NOT "determine the height that dropping a light bulb from will cause it to break." NOTE: There are now several versions of this question being asked. It only takes one or two words to completely change the problem and answer. The very point of many questions is not test for higher reasoning and problem solving skills but rather to see how carefully you read the question and how easily you make assumptions or jump to unfounded conclusions. It is the profession of testing groups and HR professionals to keep these test effective. Be aware that the easiest questions to cause someone to slip up on are the most common questions that have been slightly changed. A few years ago I had to hire twelve document reviewers in a week and used a group format in our conference room for the first interview and to test a theory I had. I gave each group a short multiple choice assessment test and instructed them to read the instructions and questions very carefully. The instructions at the very top of the first page were, "Read each question carefully and select the correct choice to not pass this test. Do answer the odd questions all option 'a' and leave the even questions unanswered." It took three groups before anyone followed the instructions. We didn't eliminate anyone over this, but we now use it regularly as a training tool to drive home the importance the details and not making assumptions when reviewing legal documents. Show More Responses the statements says the bulbs break at a certain HEIGHT - then why not just take a bulb and start walking up and see at what floor/height the bulb breaks ..... Go up in 1/5th intervals to the the top Wouldn’t you just contact the lightbulb manufacturer if this was important information to consider? The bigger issue is not breaking the lightbulbs because that’s not what they’re designed to do. The goal is to receive 100% of the bonus without damaging any of the lightbulbs. |
25 horses, 5 race tracks. How many races you have to run to select top 5 horses. 60 Answers7 Races First race all 25 in groups for 5 to figure out top 3 in each group. (15 left) Call them A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 Here A1 is faster than A2. A2 is faster than A3. The same applies for the rest of the groups. Now race A1, B1 C1 D1 E1 Lets say the order of the horses according to ranking was A1, B1,C1,D1,E1 So A1 is No 1 Now A1 is faster than B1 and B1 is faster than C1. So we can get rid of the entire D and E groups 9 horses remaining Also A1 is faster than B1 and B1 is faster than C1. So we can get rid of C2 and C3 7 horses remaining A1 is faster than B1. B1 is faster than B2. get rid of B3 6 horses remaining Out of these, We know A1 is the fastest. So now race A2, A3, B1,B2,C1 to figure out No2 and No3 positions One race is the answer Why 1? Show More Responses because, the top 5 are the fastest right ? so you run one race and take the best five times. It's a trick question to see if you'll make a mountain out of a mole hill. The first question to ask to clarify is: how many horses can fit in one track? Technically, one track can be used for all 25 horses, but this is too crowded for an efficient race. Let's say track size is not a factor, then, you need 1 race. Without overcomplicating things - the answer is 1 race. All other answers are based on dissecting the problem into, imo, unnecessary details. There is no mention of the capacity of each race track or number of gates available etc. Even if there are less than 25 gates available at a track, I'd say fetch enough number of gates so you can find the outcome with single race. This isn't a trick question. Normally this question has a track limit of 5 horses. I agree with Anuradha's answer. Anuradha's solution still has problems. (Even if we go with Anuradha's assumptions that you can only race one horse per track, and also assuming that we don't have a stopwatch and must compare horses placing positions) What if the fastest five horses are A1, B1, C1, D1, and E1 ? In Anuradha's second step, he elminates two of the fastest horses (D1 and E1) . He's assuming that A2, B2, or some of the other horses from the other heats are faster, but he hasn't actually tested to see if that is true. @anuradha: I think there are 2 problems: 1. How do you know A4 is not faster than B1 .... Suppose A1,A2,A3,A4,A5 are the fastest. 2. Using the logic posted we can get the answer in 6 races, 5 races for finding A1,B1,C1,D1,E1 and 1 race to find the ranking. Assuming 1 track for 1 horse then it need 5 races to select top 5 horses. Each race for 5 horses and count the time for each race. The top 5 fastest horses are the top 5 horses. 2 max: top 4 from first race, if 5th is a tie, then two, or else just one. Show More Responses You guys are not doing CS! 10 runs is my answer. 1. randomize 5 groups, each of 5 horses 2. rank them within each group, I will use Anuradha's notation (5 races) 3. pick the best of each group, race to figure the 1st place, call it A1 (1 race) It should be clear, it wins all times, every one lost once. 4. remove it. substitute 2nd best in. repeat 3 (in my eg. A2,B1,C1,D1,E1) now you have second place. keep going, you get the first 5 and ranking! So, 5+5=10 races in total. The answer is 9. Assuming: - There's no time measuring (stopwatch), just relative places. - The horses perform consistently. - A maximum of 5 horses per race. First we need 5 races (A to E) to get relative scores for all 25 horses. Let's take a worst scenario: the list was already ordered (A1 fastest and E5 slowest), so race A contained the top 5. The 6th race would be the winners of the 5 races (A1, B1, C1, D1, E1), and would give A1 as the fastest of all. This would also mean that some horses can be excluded (only 4 more places to fill): B5 C4, C5 D3, D4, D5 E2, E3, E4, E5 For the 7th race, A2 would replace A1, and A2 would be appointed as the runner-up (of all). We also can exclude some more (only 3 more places to fill): B4 C3 D2 E1 For the 8th race, A3 would replace A2, but as E1 has been excluded, we got a vacancy. Let's add C2 for worst case scenario. The winner would be A3, and we can exclude more horses (only 2 more places to fill): B3 C2 D1 At this point there're only 5 horses who have not yet been classified or excluded, so the winner and runner-up of the 9th race would give 4th and 5th overall. To Patrick: I had to slightly modify your almost correct solution and got 10 races. You has an excellent idea to remove subset of candidates after final selection of the i-th horse, and my modifications are not an essential ones. Actually it is necessary to fix two small things: 1. get rid off the suggestion about the ordered list To avoid this suggestion I would rename groups from the fastest A to the slowest E with order by 1st horse after final selection of the i-th horse. So after race #6 we have order: A1, B1, C1, D1, E1, but there is no suggestion that all A are better than all B and so on. And after every race #7, #8, #9 we have to rename groups. With this modification your method works fine until final selection of horse #5 2. Without this suggestion you need race #10 to find the last 5th horse. To test both methods you may use 25 randomly selected integers and select the 5 minimal or maximum ones. I can't prove that 10 is the minimum number of required tests, but it looks very convincing. Thank you. Maybe Ziqi Dai also meant the same method, but it was difficult to understand without a couple of details. To Leo, I checked some random sequences with a spreadsheet, and all the remaining (not placed or excluded) horses run in the 9th race, so there's no need for a 10th race. Sometimes there're only 4 or even 3 horses left in the 9th race. I didn't check every possibility, but there was no indication a 10th was ever necessary. This answer is 1 regardless of track. If it can fit all 25 then you only need one race. If you make the assumption that only 5 can race at a time then you put 5 on each track and start the race on each track at the same time. Either way, the fastest 5 horses win. Using complex math on this is pointless since a pragmatic approach is available. @ Anuradha -- this is a great solution to the wrong problem! The classic problem is to find the THREE fastest, and that's what your solution is. However, the question posed in this thread is (likely incorrectly quoted from the interview) to find the FIVE fastest of the group. why would you make an assumption that makes this more difficult? I mean given this is an IQ test of sorts, making it harder than stated is........ Attention to details, Anuradha! You're answer would've been correct had the question asked for top 3 horses. This is like merge sort. In the first 5 races (when we run 5 horses per race) we get 5 sorted sublists. Each sub-list contains 5 horses sorted by their relative speeds within that sub-list. Now just merge these 5 sorted sublists to get your answer. Every "merge" means 1 race to find the fastest horse from the front of these 5 sorted sublists. To summarize: 1. Creating 5 sorted sublists of 5 horses each = 5 races 2. Getting fastest horse = 1st round of merge = 1 race 3. Getting second horse = 2nd round of merge = 1 more race 4. and so on... Show More Responses Why is this harder than having five races with five horses, recording the times of each horse, and sorting the list of observed values to get the top 3? it is seven race For 3 fastest horses no doubt the answer is 7 but for 5 fastest I worked it out to be 9. And pretty sure too 1 only if you can do good flow control and horse will start with different time / space out based on best estimate. It is kind of feeding the horse to the gate. Simply 5 races only, i.e. 5 horses in 5 race tracks per race. Finally, select top 5 horses by best fastest timing at finish line after 5 races. As a BA, the answer I would give is: We don't yet have enough information to provide a solution. There is critical information missing that could affect the solution. And flushing out all the critical factors of the problem are one of the most important responsibilities of the BA. As a BA, it is very important to NOT start building solutions to problems that you don't yet fully understand. Actually, it's one of the biggest mistakes inexperienced BAs make: solving the wrong problem because they rushed to solutions and did not fully investigate and understand the problem! Once they're committed to the wrong problem, they end up with a beautifully done inadequate solution. 5 races, because you can fit 5 horses in 1 race and there are 25 horses. You just note the timings of each horse and compare them after all the races are done. That way, you won't have to arrange more than 5 races and stopwatch is a common tool for every phone!!! First of all guys, you guys are making critical mistakes. You assume we have a timer but that would make it too easy, right? I'm just assuming that 5 horses a track and no timer. So I have two potential solutions: 1. You could always just race them all at the same time on 5 tracks...but that'll be too easy. Then there's my solution: --------------------------------------- First, group all the horses into five groups of five. It doesn't matter which horse goes into which group, it honestly doesn't matter. Then, race all the horse in one groups against each other. It helps to name them A-E(Group name) and the number place they came in (ex: 1st place a group would be A1). So now we have A1 to A5 and B1 to B5 and so on until E5. Then race all the 1s against each other. You should get something like A1, C1, B1, E1, D1 and then you should arrange their groups in collumns from left to right based on that race (1st on left, 5th on right). Here is where it starts getting complicated, so I will just assume it is A1 fastest in that race and E1 slowest and so on just for simplicity. So so far this is 6 races. Get E1 and race them against D2-5. You can ignore E2-5 because no matter what they can never be in the top 5 because A1, B1, C1, and D1 is the fastest of their groups and you know that the fastest five can come from those groups but not E2-5 because E1 is the slowest of the 1's and there's no way those horses can be in the top five. SO just throw them away. Since there are four spots available max you race the slowest four of the D which happens to be D2-5. Get the place numbers and arrange them. EX: D1 D2 E1 D3 D4 --- D5 E1 can be anywhere based on E1's speed but you immediately want to discard the D5. You might be saying, "Hey, why can't we discard anything below D2 since A1 and B1 and C1 are all faster than D1 and E1?" But...you could be unlucky and have A2-5 and B2-5 and C2-5 be all dirt slow. So just keep them for now. So the rule now is to keep all the horses that are in the top 5 and discard the rest until you get to A, when you know, "Oh, A1 has to be the fastest horse." 7 races. So we have our list above just for examples. Next you want to race D4 against C5 to see if our group can EVEN pass the C's, cause we might get super unlucky and see that C1-5 is faster than D1...if D4 loses in 5th place we just throw this all away and our new list becomes: C1 C2 C3 C4 C5 But otherwise we'll just assume that our D4 luckily got to 3rd place. It becomes: C1 - Our group can go anywhere inside the lines so race them again C2 minus D4 since its in 3rd place to see where they go. Let's assume we got SUPER lucky and C2 became last place in that race. - C3 C4 C5 8 races. We raced this group at that time and left out D4 because D4's fate was already decided: D1 D2 E1 D3 C2 It turnes into this: C1 - D1 D2 The single dash indicates where our new group was spliced, ofc the triple E1 dash lines show where the cutoff is, so discard everything under the line. D3 -(---) C2 D4 C5 9 races. Kay, so now we have the five fastest in the E, D, and C groups. Now continue with the B groups and let's say that our D3 passed B4 only... It becomes: B1 B2 - With our top five so far group racing against B4 B3 - D3 B4 B5 10 races. And then with another race you get this with lets say...only our top two making it through with B3 getting ironically first place: B1 B2 B3 C1 D1 --- D2 E1 Yep...E1 got kicked out. Aw well. SO NOW our to group D3 is the group above the triple dash marks. B4 B5 11 races. Now we're up against the A group. Assume that they are all wusses and that our D2 beat all of them except for A1. So we got lucky and the new lineup is this: A1 B1 B2 B3 C1 --- It was inevitable that A1 would become first but now this is how you do it! D1 D2 A2 A3 A4 A5 12 races/13 if our B1 didn't beat all of the other A's on the first try. Conclusion: 5 races (initial races)+1 race(for initial group leader ranking)+1 races(E-->D)+2 races(D-->C)+2 races(C-->B)+2 races(B-->A) =13 races/10 races if you get insanely lucky and have all our previous groups beat all the #2s of the groups. Show More Responses Oh nvm ignore that it was all crushed into one place with no spaces...I'll stick a better one later. The answer is 8 races assuming that you can fit only one horse on one track. Divide the group into 5 horses. In five races we can find the 5 fastest horses in the 5 groups. The 6th race is among the top 5 fastest horses. The top three fastest horses in the 6th race are faster than the horses in the group of the 4th and the 5th fastest horse. The horse that came third in the 6th race may or may not be faster that the horses in the group of the fastest and the send fastest horse. To determine that, we hold 2 more races. So 6+2 = 8 races is what I think is the correct answer ****************ANSWER -- 3 RACES.************* Given : 25 horses, 5 tracks Assuming : 5 horses to a track Five groups of 5 horses for each track (5 tracks, tracks ABCDE, each track with horses labeled "X#") First race allows you to find out the top 5 horses (however this isnt the true top 5) [A1,B1,C1,D1,E1] Second race the top horse is discovered (lets say its A1) Now you have to find out if B1 is better than A2, B2 is better than C1, etc. (each predecessor of each winner) We know that B1 is better than [(CDE)1] Third race we have A2,B1,B2,C1,D1 Conclusion : If both of the predecessors are NOT last place, then we have our answer at race 3 by taking the top 4 to be the bottom 4 of the top 5. Otherwise, repeat this process one more time to find the 5th placed horse. Ans is 14 Patrick gets the right number but his logic is not the most efficient. Initially follow the standard procedure and race 5 groups of 5 (races 1-5) and then race the winners (race 6). The winner is the fastest overall. Now name the groups with the horses in the winners group A1,A2,A3,A4,A5, the first four horses in the runner-ups group B2,B3,B4,B5, the first three horses in the third group C3, C4, C5 down to E5 for the winning horse from the slowest group. The numbers indicate the highest possible position a horse could attain (i.e. C4 is definitely slower than C3, B2 and A1 but may be slower than several others). The rest of the horses are eliminated and so don't need to be labeled. Now race (race 7) the horses labeled 2 or 3 (there are 5 - A2,A3, B2, B3, C3) The top two are second and third overall and the loser is eliminated. You can eliminate a total of 5 or 6 horses - those known to be slower than the fourth or fifth place finisher and any two positions slower than the third place finisher in race 7. There aren't that many options here so you can just inventory all the possibilities if you wish. At this point you have a maximum of 7 horses for the remaining two positions You just race any 5 (race 8) to eliminate at least 3 and race the rest (race 9) to get the fourth and fifth fastest overall. If you choose all the potential fourth place finishers in race you may not need race 9. As noted elsewhere Anuradha gets the right answer to a different question than the one asked. I have stepped among a lot of smart folks here. Maybe even several analyst's. So here it goes. I am looking at this as who the question is coming from and for what. A Business Operations Analyst for Google. Everyone is so focused on answering the question based on assumptions. Ie. That every horse and rider are at their best condition and that every track is exactly the same. That you are running all the races in the same day and that horses, riders, and tracks dont change. Horses and riders get tired, not to mention the possibility of injuries, and track conditions can change so forth and so on. So to me. In order to (analyze) to get the best possible answer. I would start by asking questions and not assuming. The more information you have leads to the best possible answer. Guys think as a programmer, (mind my language and grammar) algorithm would be of these steps ->group the horses (5 horses each) -> get the best runner of each group (five races) -> store the horses in winning orders to five stacks (a,b,c,d,e) ->until the top 5 are found, repeat ->race all the 5 on top of the stack ->pop the winner from its stack and store in top five that all, now lets see how it will work. lets have 5 horses per group and group them as a,b,c,d,e. 1=a1 a2 a3 a4 a5 a1 (winner) 2=b1 b2 b3 b4 b5 b1 3=c1 c2 c3 c4 c5 c1 4=d1 d2 d3 d4 d5 d1 5=e1 e2 e3 e4 e5 e1 now we have best of each group, let them race 6=a1 b1 c1 d1 e1 a1 for every winner get the best candidate for the group, and race again, until top 5 are found 7=a2 b1 c1 d1 e1 a2 8=a3 b1 c1 d1 e1 a3 9=a4 b1 c1 d1 e1 a4 10.a5 b1 c1 d1 e1 a5 for any scenario just get the so the ten races. its like finding five highest numbers from 25 numbers, when you can only compare 5 at a time. Answer- 7 Races Give names H1....H25 Divide into 5 groups as 5 can run at a time H1, H6 , H11, H16, H21 are fastest in there groups Now we can remove last two from each groups as we need fastest 3 now we left with 15 horses 6th Race- between all fastest in groups After 6th Race H1> H6 > H11> H16,>H21 Now H21 was fastest in group but is 5th in 6th race so H22 and H23 who already slower than H21 can't be in first 3 Same thing applied for H17 and H18 as H16 was fastest in group race but 4th in 6th race Same applied for H12 and H13 as H11 was fastest in group race but 3rd in 6th race Already three horses are faster than H16 and H21 so they both also can be rules out Now we left with H1, H2, H3,H6, H7, H8 and H11 But H8 is slower than H7 and H7 is slower than H6 in group race and we have H1 on top already so H8 also can't be in fastest 3 Now we left with H1, H2, H3,H6, H7, H11 H1 we know is fastest..so lets 7th race between H2, H3, H6, H7 and H11 and find the other two After 7th race you will get fastest 3 Make a group of 5 horses per track and race them all at once. The winners of each track totals to "the top 5" ! The answer is 7. Assuming: - There's no time measuring (stopwatch), just relative places. - The horses perform consistently. - A maximum of 5 horses per race. Race r1: A1 A2 A3 A4 A5 (By order of winners) Race r2: B1 B2 B3 B4 B5 Race r3: C1 C2 C3 C4 C5 Race r4: D1 D2 D3 D4 D5 Race r5: E1 E2 E3 E4 E5 Race r6: A1 B1 C1 D1 E1 (rename R1 R2 R3 R4 R5) Here comes the tricky race. From race 6, we already know the ranks. As a demonstration, assume R1 = A1, R2 = B1, R3 = C1, R4 = D1, R5 = E1. Then: 1) D1 D2 D3 D4 D5, E1 E2 E3 E4 E5 are out of the contest. Because D1 and E1 are ranked 4th and 5th in a race. 2) C2 C3 C4 C5 are out of the contest. Because two horses already are faster than C1 ==> 3 horses are already faster than C2 C3 C4 C5. 3) B3 B4 B5 are out of the contest. Because one horse already faster than B1 ==> 3 horses already faster than B3 B4 B5. Remaining potential horses are: A1 A2 A3 B1 B2 C1. Here, A1 is redundant because we already know it is fastest. Race 7: A2 A3 B1 B2 C1. The top 2 will be added to A1 to be the fastest three. Show More Responses Take a look at previous horse race statistics from horse newspapers. Make your analytic and you have your top 5 horses without any new race :) It will take min 9 race not 7: first five race and find top 3 @ every slot now total race=5; one race between first five, now we find top 3 and take 2nd and 3rd from the race as 1st is declared. race=1; 1 race between 2nd finisher of all slot and take 2 from them , race=1; 1 race between 3rd finisher of all slot and take top finisher, race=1; now we have race between 5 horses(2+2+1) and find 2nd and 3rd; so total no of races= 5+1+1+1+1=9 ; The question is not a good one! Let those horses be marked X1~X25. First divide them into 5 groups X1~X5, X6~X10, .... Assume the first X1, X6, X11, X16, X21 are the fast ones in each group after the first round. Also, X2 > X3, X6>X7, during the first round. We then, during the 2nd round, form the first group with those fastest from each group in the first round. Assuming that X1 > X6 > X11 > X16 > X21 after the first try of the 2nd round, we will then have X2, X3, X6, X7, X11 to form a new group and determine which are fastest 2 in this new group. Nevertheless, during the 2nd try of 2nd round, it can happen that X3 > X2 or X11 > X6. The inference fails all the relation set in the previous try. ( that the X2 > X3 ,after the first round, and X6 > X11, after the first try of 2nd round). It would be better to change all those horses to be boxes carrying different integer value. You want to sort those boxes to find which carrying the largest 3 numbers and, at any time, you can only open 5 boxes to inspect . You cannot mark the content of boxes but you can put down the relation between boxes during the inspection. Then, the number of inspections needed to find boxes with the largest 3 number will be 7# This seems like a simple answer, but I'm pretty sure it's 9. Race 5 groups of 5, then race all the 3rd place, then the winning 3rd races the seconds, then you have either have five firsts and two seconds left or 5 firsts a second and a third left from the original racing groups. Worst case scenario you have one more race of three ones and two twos or two ones and the 2nd and third place to find the fastest there out of that last group. 9 races. So driving down the road I figured out I should have started from the top after the first five races. Then worst case scenario you run three more races to find out the top three. 11111, 21111, 31111. Damn. Six races, six groups. First group will have five horses, the 5 others groups will have only 4 horses. The winner of the first group of 5 horses will pass to the second race, then the winner of the second race will pass to the third race and so on, bay the end of the 6 race you will have top 5 horses. Assuming no limit to how many horses on a track, 1, because the fastest 5 will obviously finish in 1st, second, third, fourth, and fifth place. If there is a limit to the number of horses on a track, then it will take (25/number of horses to a track) rounded up to the next integer races because you can just compare the times of all of the horses and pick out the five fastest times. There are a lot of wrong answers on here or answers for different questions. Answer for top 5 is 8 races. You can find explanations online for this. Show More Responses Friends only 5 races are required As mentioned we have 5 tracks and 25 horses. So divide them into set of 5 And winner of each set is fastest so only 5 races are required. If there in no limit on track one race is enough. But if 5 horses can run at a time we need 6 races. 5 races to find top of each group. And additional 1 race among those top 5 horses to find out top 3. answer is 8 suppose we have limit of 5 horses per track and all horses run together on 5 track so *-5 races-* conducting on five track, the top one of each track is selected for further race and now race is conducting between the all top 5 horses which is *-6th race-* and the remaining 4 horses will race again for 2nd and 3rd position hence total no. of race are 5(all five races)+1(6th race)+1(7th race)+1(8th race). So many wrong answers here, first of all the question is about FIVE fastest horses, not three, so all the posts giving 7 as an answer are wrong. All the answers above 9 are also wrong. You need 7 races to find 3 fastest horses, after that by using logic you come down to either 6 or 7 remaining horses as candidates for places 4-5, and you need 2 races to figure out which 2 of them are the fastest. So it's 9 races in total. 6 races: 25 Horses - categorize in 5 races of 5 horses each (if there is a 5 horse limit) merge and sort timings for top 3 of each of the above races. Now race 6--> race 5 horses with top 5 timing --->Winner 5 races in groups of 5 (as not to crowd the track). Placement means nothing only time matters "If your not first your last" One or more comments have been removed. |
Software Engineer at Cerner was asked...
Allergy,posting date according to timezone,person demographics problem Medication Frequency problem and given error log to identify error Fever temperature problem and discuss a time when you automated a task to make life easier 43 AnswersHi . Did they inform about results till now? Hi ..Yes i got the offer! Can you please elaborate the question ? Show More Responses How many days did it take to respond ? My recruiter responded after a week Can I please have the answer? Hi Here are the questions: 1st hour: 1) Design a system for entering and displaying the allergies patients have with given fields! 2) Person Demographic Problem to store information about every person! 3)To record a new born's birth date and time reflecting the timezone. 2nd hour: 1) Implementing a system that notifies nurse when a patient should receive medications 2) An error log is give , we need to identify error 3rd hour: Temperature class to know whether patient has fever or not and in what location is the reading taken such as mouth,armpit,ear For some questions answers are posted in glassdoor! Hi...did you answer all the questions correctly?? They asked me the same questions. I have answered the programs correctly except that fever program there i got bit confusion.but I couldn't properly explain the error log. Hey i didnt answer all the questions correctly ..they helped me if i am struck .. Is this for entry level or new grad position? Can you explain how to notify a nurse please ? They are hiring new grads also for these Software Engineer positions! Show More Responses I dont have the logic for medication question..when i was struck in this question..Interviewer helped me that u can implement a queue algorithm! What is the relation between queue algorithm and notify? Well he(interviewer) just said that as a queue is a fifo datastructure..when a nurse looks for medication, it shows the first medication to be given and then it shows the next one when to be given. I dint implement the logic!! my hr status is showing a . (dot) , any idea what does this status tell It means there are chances you are going to get the offer! And for how many days did your status change? Thanks, I had Interview on Last Thursday and status changed to dot(.) on Monday Do we have to wear a suit for onsite rounds? not required Hey, even my status changed from interviewing to dot(.) Did you end up getting the job eventually? I had my Experience Cerner Day on June 30. As of today July 8, my HR Status says "Interviewing." What is my chance of getting the offer? Show More Responses @above Hey, even I came to Experience Cerner Day on June 30th, my HR status went from interviewing to dot(.) on July 6th. Any idea what this means? do you know anyone you came that day to get the offer? No, I don't know anyone who came that day. My status also changed to . (dot) I got selected with .(dot) status @above, your status changed to dot and you got offer? Can I know when you had your interview, when it changed to dot and when you got offer? Can someone please provide approximate answers to those FEVER and NOTIFY NURSE MEDICATION problems?? I had my interview on July 8th. The status is still "Interviewing". I emailed the recruiter too but no reply yet. What should i expect with this? Hi ! Even I had my interview on July 7th. I did'nt got any response. Can we still expect ? Hi, this is the response i got when i asked for update on Thursday the next week... Thanks for following up again! As was stated, we do ask that you please give the recruiters about two weeks time to get back to you with a response. Tomorrow will mark the two week time period so you should hear something soon! If you don’t hear anything next week, feel free to reach back out! But my status on portal is still "Interviewing", any chance? How long does it take to get feedback from them?? Hi ,if u dont mind, how much time did your first phone interview last? Show More Responses I had interview on 21st Sep,2016 in Malvern,PA for software engineer position did anyone give interview on the same day? They are 3 rounds of interview on the same day back to back lasting 1hr each. Does anyone got the result or feedback from the HR or recruiter? How long does it take for Cerner to give the decision in this case? I emailed HR regarding the decision no reply yet. Is there anyone with the similar situation. Portal status "Interviewing". Hey what are questions asked in the interview, can you please elaborate them because I have an interview for Software Engineer Malvern, PA position. I had my interview on 21sep 2016, PA position. Still waiting for the feedback. Did anyone got the feedback interviewed on 21st sep? Hi, I had my interview last week. It shows .(dot) status in application status. Any idea what does it mean? .How many days does it take to get back? So if the status changes to .(dot) , does it mean I am selected or still not? Did anybody with .(dot) got rejected too? Please post here. @above Did you get selected? And is there anyone who got rejected with the .(dot) status. @above can anyone please confirm .(dot) status means we got the job. Hey, Are they expecting a solution using Threads for the medication problem? How did you add the alert functionality for the nurse? |