# Software Engineer Intern Interview Questions

Software engineer intern interview questions shared by candidates

## Top Interview Questions

Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale . What's the fewest number of times you have to use the scale to find the heavier ball? 48 Answers3 times. (2^3 = 8) Two. Split into three groups of three, three, and two. weigh the two groups of three against each other. If equal, weigh the group of two to find the heavier. If one group of three is heavier pick two of the three and compare them to find the heaviest. Brian - this would be correct if you in fact were using a weighing scale, and not a balance scale. The ability to weigh one group against another with a balance scale allows Marty's answer to be a correct answer. Although - the question as worded provides a loophole. If it had been worded as "What's the fewest number of times you have to use the scale to CONSISTENTLY find the heavier ball", then Marty's answer would be the only correct answer. However, it is possible that you could get lucky and find the heavier ball in the first comparison. Therefore, the answer to the question as stated, is ONE. Show More Responses This question is from the book "How to move Mt Fuji".... Marty has already got the right answer. Actually Bill, by your interpretation of the question the answer is zero, because you could just pick a ball at random. If you get lucky, then you've found the heaviest ball without using the scale at all, thus the least possible amount of times using the scale would be zero. The answer is 2, as @Marty mentioned. cuz its the worst case scenario which u have to consider, otherwise as @woctaog mentioned it can be zero, u just got lucky picking the first ball.... None- weigh them in your hands. Assuming that the balls cannot be discerned by physical touch, the answer is 3. You first divide the balls in two groups of 4, weigh, and discard the lighter pile. You do the same with the 4 remaining, dividing into two groups of 2, weighing, and discarding the lighter pile. Then you weigh the two remaining balls, and the heavier one is evident. 2 3a+3b+2 = 8 if wt(3a)==wt(3b) then compare the remaining 2 to find the heaviest if wt(3a) !== wt(3b) then ignore group of 2 discard lighter group of 3 divide the remaining group of 3 into 2+1 weigh those 2 If == the remaing 1 is the heaviest if !== the heaviest will be on the scale With the systematic approach, the answer is 3. But, if you randomly choose 2 balls and weigh them, and by coincidence one of these two is the heavier ball, then the fewest number of times you'd have to use the scale is 1. Although the real question is: are the balls truly identical if one is heavier than the rest? just once. Say you are lucky and pick the heavy ball. One use of the scale will reveal your lucky choice so once, or the creative answer zero if you allow for weighing by hand Without judging by hand: Put 4 balls on one side, and 4 on the other. Take the heavier group and divide again, put 2 balls on one side, and 2 on the other. Take the 2 that were heavier, and put one on each side. You've now found the heaviest ball. This is using the scale 3 times, and will always find the right ball. Show More Responses None. They are identical. None is heavier. 2 weighings to find the slightly heavier ball. Step 1. compare 2 groups of three balls. Case 1. if they are both equal in weight, compare the last 2 balls - one will be heavier. case 2. If either group of 3 balls is heavier, take 2 balls from the heavier side. compare 1 ball against the 2nd from the heavy group result 1. if one ball is heavier than the other, you have found the slightly heavier ball. result 2. if both balls are equal weight, the 3rd ball is the slightly heavier ball. Easy Shmeezi Fewest - get lucky and pick the heaviest one. But wait! How would you know it is the heaviest one by just weighing one ball? Your logic is flawed. Two groups of four. Split heavier one, weigh. Split heavier one, weigh. 3 times. i think its 3. i would take it like this OOOO OOOO then OO OO then OO problem solved. i do this everyday. bye. praise be to allah. thats it. It's 2. Period. If you can't figure it out look it up online or in "How Would You Move Mount Fuji" (like somebody else said). This is one of the most basic brainteasers you could be asked in an interview. The answer is 2. 1) Divide the balls into 3 groups. 2 piles with 3 balls each, 1 pile with 2 balls. 2) Weigh the 2 piles of 3 balls. If both piles are the same weight, discard all 6 and weigh the last 2 to find the heavier one. 3) If 1 pile of 3 is heavier than the other, discard the lighter pile and the pile of 2 balls. Weigh 2 of the remaining 3 balls from the heavier pile. If both of the weighed balls are equal, the last ball is the heavier one. 2=if all the balls are identical and you pick up the first...weigh it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. 1=if all the balls are identical and you pick up the first...balance it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. Amy is 100% correct for the following reason: everyone (except Amy) is solving the theoretical problem. The practical side of the problem - notwithstanding jimwilliams57's brilliant observation that if one weighs more than the others IT IS NOT IDENTICAL (would have loved to see the interviewer's face on that one) - in order to 'weigh' them on a scale, one has to pick them up, therefore, you will immediately detect the heavier one without weighing: pick-up three and three ... no difference, no need to weight. Pick-up the remaining two to determine the heavier one. Steve First off, take yourself through the process visually and forget square roots, that doesnt apply here and here is why: The question is the Minimum, not the MAXIMUM. BTW, the max would be 7 ( 8-1); you are comparing 2 objects, so 1 ball is eliminated automatically in the first step. Anyway, you have a fulcrom of which you are placing 2 of 8 objects on each end. If by chance you pick the slightly heavier object as one of the two balls, you have in fact, found the slightly heavier one in the first round... btw dont be a smartass with your interviewer, he is looking for smarts not smarmy;) Show More Responses Respectfully, the folks who are answering "3" are mathematically modeling the nature of the balance incorrectly. Performing a measurement on a balance scale is not binary. It is trinary. Each measurement gives you one of three responses: The left is heavier, the right is heavier, or they are equal. So while you do need three binary bits to specify a number from one to eight, you need only two TRINARY-DIGITS Formally, you want the smallest value of n such that 3^n >= 8. The answer is 2. Note that you could add a ninth ball, and still, you'd only need to make two measurements. Of course, the smarty pants answer would be one. Just pick two balls at random and be lucky to have chosen the heavy one. But you're not guaranteed to be able to do it in just one measurement. English isn't my mother tongue... What is a balance scale? If looking up on Google, I find some devices with two bowls on a bar bearing in the center. Hence, the answer is once (if I'm luck enough to select the heavier ball in teh first measurement) If a balance scale allows to measure only one ball at a time, then it would take two measurements, unless you'd have more information on the weight, which is not listed here, hence doesn't exist in the context of the question^. 3 times. Not having looked at the other comments, hopefully, I am the 26th to get this right. Put the balls 4 and 4 on the scale, Take the heavier side and place those balls 2 and 2 on the scale. Take the heavier side and place them 1 and 1 giving the heaviest ball. OK, now I read the comments and see that the people, like the question are divided into to groups, systematic approach people that say 3 (like I did) and analytic people that say 2. It takes a systematic person (me) a minute to get the answer. I'm guessing it took the analytic 5 minutes just to interpret all the ramifications of the question, i.e. they aren't idenitical if..., do it by hand..., get lucky. minimum is 1 (if lucky - 25% chance by picking 2 balls at random) & max is 2 (using most efficientl process to absolutely determine without luck - 3/3/2 scenario) While Symantec was busy weighing my balls I took a job with NetApp.... They need to focus on hiring good, capable security engineers, not weighing their balls. The point of these interview questions is to both check your logical brain function and to hear how you think. Most of you are just posting jerk off answers trying to be funny, or you are really dumb. These answer get you nowhere with me in an interview. Think out loud, go down the wrong path back track try another logic path, find the answer. None of this "0 if you use your hands". That is fine if you are interviewing for a job in advertising where creativity is desired, nobody wants you writing code like an 8 year old. You have 12 balls, equally big, equally heavy - except for one, which is a little heavier. How would you identify the heavier ball if you could use a pair of balance scales only twice? The problem is based on Binary Search. Split the balls into groups of 4 each. Choose the heavier group. Continue till you get the heavier ball. This can be done in log(8) (base 2) operations, that is, 3. Since there is only one scale available to weigh. You first divide the balls in half. Weigh each group, take the heaviest group. This is using the scale twice so far. Now, divide the previous heaviest group into half, weigh both groups. Take the heaviest. Divide this last group and take the heaviest. This is the heaviest ball. We have used the scale 5 times. Show More Responses Would it be wrong to say for a sample size as small as 8, we might as well not waste time thinking about an optimal solution and just use the scale 7 times, as this will be more efficient than coming up with an ideal solution prior to using the scale? 3. I stumbled across this while looking for something else on Google but I had to answer. It is 2, split balls into 2,3 and 3. weigh the 2 groups of 3 against each other. If equal weigh the group of 2 and the heaviest is obvious. If they are not equal keep heavy group of 3 and weigh 2 of the balls. if equal heaviest ball is one you didn't weigh. If not equal the heavy ball is obvious. 2 times. 8 balls. 1st step: [3] [3] [2] 2nd step: [[1] [1] [1]] [[1] [1] [1]] [[1] [1]] No idea The fewest number of times to use the scale to find the heavier would be Eight to One times ? It will actually be 1 because the question asks what's the fewest amount of times which is one because you could just get lucky you can use any method you want it would still be one because that is the fewest amount of turns you can have It's one. The fewest number of tries on using a balance scale would be one. If you put one ball on each side and one is heavier, you have the found the heavier ball. Use an equilateral triangular lamina which is of uniform mass throughout. It is balanced on a pole or a similar structure. Steps: Place 2 balls at each corner (total 6 balls) i. if the odd ball is one of those, one side will either go up or go down. Now repeat the process with one ball at each corner including the 2 unbalanced ones. ii. if balance is perfect, repeat the process with the remaining two balls and one of the already weighed balls. test answer 2016-01-12 00:34:07 +0000 Show More Responses You would not be able to find a ball heavier than the others. All eight balls are identical; therefore, they must all be the same weight. Correct answer has already been posted. I just want to contribute some theoretical analysis. Given N balls, one of them is heavier. Finding out the ball requires log3(N) trit of information. (trit is the 3-base version of bit). Each weighing may give you one of the three outcomes: equal, left-heavier, right-heavier. So the amount of information given by each weighing is upper-bounded at 1 trit. Therefore, theoretical lower-bound for number of weighings in the worst case is log3(N), which is actually attainable. So 27 such balls need only 3 weighings and 243 balls need only 5 weighings, etc. 3 2 as many have indicated above. The 3 is the kneejerk reaction but 2 is the correct answer. Marty's answer is correct, but he does not explain why. The logic of the balance scale is three-valued: . Its most efficient use is the recursive application of the three-valued logic until there is only one item left. The integral ceiling of ln(x)/ln(3) thus gives the fewest number of times you have to use the balance scale to find the uniquely heaviest ball of x balls. Ceiling(ln(8)/ln(3)) = 2. |

Implement a power function to raise a double to an int power, including negative powers. 11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills. #include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv[1]); int b = atoi(argv[2]); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } } c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; } Show More Responses int power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; } C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); } double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; } I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation... I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; } Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact? TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution. public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; } |

To find and return the common node of two linked lists merged into a 'Y' shape. 13 Answershow did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8. For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9 5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same. Show More Responses @kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9 Can this be done using hash tables? Or is there anything more efficient? i think that kvr's answer is the best. @snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this 1 -2 -3 -4-7-8-9 x -x -x -x -x-o 12-13-14-5-6-8-9 (sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning. HASH TABLE seems the only efficient wt. 1. add each element's address (of the smallest list)and push it to the hash table. 2. start walking second list. 3. get element compar eits address with hash table if match is found in hash table, return 4. if list is not exhausted, go to step 2. 5. return NULL Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left. First reverse both list and find point where both gets diverged For Y condition the list could be List 1: 1->2->3->4->5->6 List 2: 7->8->9->4->5->6 So reverse list would be 6->5->4->3->2->1 6->5->4->9->8->7 now compare two list and move forward the position where you find next node of both are different is the point of merging Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better. Let's say L1 is the list starting with the lower number, and L2 is the other Set X = Head of L1 Set Y = Head of L2 While X <= Y Set X = Next(L1) End While If (X==Y) Return X Else While Y<=X Set Y = Next(L2) End While If X==Y Return X End If End If Repeat until you reach the end of either list. |

Determine if an array from 1..n has a duplicate in constant time and space. 12 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate. ^^ Sorry, that's linear time *and* at best linear space, you fail. What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates. Show More Responses SUM(array) - (N(N+1)/2) = missing number. @Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4} I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap. I'm pretty sure OP posted something wrong there, and they were probably asking to do it in linear time and not constant. If it's constant, the way I would do it would be using a HashSet to check if the key (value in array) is contained, and if not add it to the set. If at any time I find an element that's already inside, return false; If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate. I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1. |

### Software Engineering Intern at Google was asked...

how would you find the shortest path between two nodes in a social network? 7 Answersdo breadth first search from both ends at the same time. Keep a set of all nodes that each has reached. When the sets have any element in common, there is a path. Does the above method have any advantage over the method in which we do bfs from one node of the nodes and stop when the other node is reached? BFS from both sides is massively faster than just doing BFS from one. Suppose each person has k friends and that the two nodes are d apart. BFS from one node is O(k^d). BFS from both nodes is O(k^(d/2)) -- the exponent is half as big. To put some example numbers on it, if each person has 100 friends and they are 10 apart, then BFS from one node takes 10^20 operations, whereas BFS from both nodes is 2*100^5= 200 billion operations. BFS from one node is intractable. BFS from both nodes is slow, but tractable. Show More Responses How about using Dijkstra's shortest path algorithm? Isn't that more efficient than a bfs? If you only care about the distance between two nodes and every edge length is 1 (both of which are true in this problem), then Dijkstra's shortest path algorithm basically is breadth first search (and BFS from both sides is faster than a simple BFS). If that doesn't make sense, then explain how http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode is different from a breadth first search in this case and I will clarify. Aren't you ignoring the time taken for checking for a common element in the two sets (which will be O(k^d))? Checking for set inclusion is constant time (assuming a reasonable hashset). Thus, it is O(1) to know whether or not a node that I add to one side's fringe is already in the other side's fringe. Does that make sense? |

Given two strings representing integer numbers ("123" , "30") return a string representing the sum of the two numbers ("153") 13 AnswersI don't understand...it's a very stupid question! return Integer.toString(Integer.parseInt("123") + Integer.parseInt("30)); It's not stupid a stupid question. What if the strings have 10000 characters? It's not stupid question, but it's not hard either. I believe the way to do it is to implement the manual addition process by looping through the digits starting from the right to left and adding them one by one. This is an O(N) operation. I'm not sure if there is a better way to do it. Show More Responses lol it is a stupid question i agree. All you have to do is parse the strings add em parse em again and return em It is basic but yet not stupid. I assume that the interviewer asked to implement atoi and itoa (in case the interview was in C/C++). The interviewer wanted a loop through the digits starting form right to left, adding them one by one, and keeping track of the carriage. public static String sumStrings(String a, String b){ char[] num1 = a.toCharArray(); char[] num2 = b.toCharArray(); int i = num1.length - 1; int j = num2.length - 1; StringBuilder sumString = new StringBuilder(); int carry = 0; while(i >= 0 || j >= 0){ int d1 = 0; int d2 = 0; if (i >= 0) d1 = num1[i--] - '0'; if (j >= 0) d2 = num2[j--] - '0'; int sum = d1 + d2 + carry; if (sum >= 10){ carry = sum / 10; sum = sum % 10; }else carry = 0; sumString.insert(0, sum); } return sumString.toString(); } public class StringToInt { public int stringToInt(String str) { int tens = 1; int num = 0; for(int i = 0; i < str.length(); ++i) { num += (str.charAt(str.length() - 1 - i) - '0') * tens; tens *= 10; } return num; } public int addStrings(String str1, String str2) { return stringToInt(str1) + stringToInt(str2); } public static void main(String [] args) { StringToInt s = new StringToInt(); System.out.println(s.addStrings("145", "23")); } } @Conner What if the strings are 1000 characters long? does your int tens and int num variables support that? int stringToNumber(char *a){ char *end = a; int it = 1; int acum = 0; while (*end != NULL){ end++; //move pointer to last char of string } while (&end != &a){ acum+=((*end - '0') * it); it *= 10; end--; } return acum; } int sum (char *a, char *b){ return stringToNumber(a) + stringToNumber(b); } import java.util.Arrays; import java.util.Scanner; public class AddNumericStrings { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter 2 numeric strings : "); String x = in.nextLine(); String y = in.nextLine(); System.out.println(add(x.toCharArray(), y.toCharArray())); } } private static char[] add(char[] big, char[] small) { char[] result = new char[big.length + 1]; Arrays.fill(result, '0'); for (int i = big.length - 1, j = small.length - 1; i >= 0 || j >= 0; i--, j--) { char x = big[i]; char y = '0'; if (j >= 0) { y = small[j]; } int val = x - '0'; val += (y - '0'); result[i+1] += val % 10; if (val > 10) { result[i] += (val/10); } } return result; } } You all know that negative integers exist, right? The question does not specify if the integers are non-negative. One just assume, therefore, that negative integers are possible. It would not be called subtraction. Subtraction does not exist. It would just be addition of the additive inverse. https://github.com/codelucas/puzzles/blob/master/java_interview/StringNumAdd.java |

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

Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number. For example, from array 1, 1, 2, 3, 3, 1 You should get 2, 1, 1, 2, 2, 3, 1, 1 Write a program to solve this problem. 7 Answersint[] Reformat(int[] original, int length) { LinkedList list = new LinkedList(); int currentCount; for(int i=0;i function numberArray( $arr ){ $a = array(); $number = null; $c = -1; foreach( $arr as $v ){ if( $v != $number ){ if( $number ){ $a[] = $c; $a[] = $number; } $number = $v; $c = 1; } else { ++$c; } } if( $c > 0 ){ $a[] = $c; $a[] = $number; } return $a; } var_export( numberArray( array( 1,1,2,3,3,1 ) ) ); $val) { echo $val . "\t"; } echo " \n"; } ?> Show More Responses working in php: sizeof($list)-2) || ($list[$i]!=$list[$i+1])){ $result[]=$count; for($j=0;$j vector reformat(int arr[], int size) { vector res; int j, count = 0; for(int i = 0; i < size; ) { cout << i << endl; count = 0; for(j = i; j < size; j++) { if(arr[j] != arr[i]) break; count++; } res.push_back(count); res.push_back(arr[i]); i = j; } return res; } int i=0; int j=1; ArrayList array=new ArrayList(); while(i @Anonymous: Your inner while loop will cause an out-of-bounds exception to be thrown when your scanning hits the end of the array. Your while loop will try to access givenArr[i+j] even when j increments to the point that surpasses the length of the array. You need while((i+j) != givenArr.length ... ) |

25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 11 AnswersWe can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N. Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once. We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5} Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore. We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3. As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses. We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses. Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse. Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses. just run them all on the one track :) one race, and you get your 3 fastest horses in one go........or am I missing something! 6 races. Divide 25 horses into 5 groups. Each group races and the fastest is selected. The winner of each of the 5 races all race together. Pick Top 1,2 and 3. My only concern: Could the answer be this simple? Show More Responses B, you're mistaken. Imagine the top three fastest horses are Santa's Little Helper, Yojimbo, and I'm Number One. By random luck, in your first race, the five random horses you choose includes all three of those. I'm Number One wins and goes on to the final race; the other two do not. 8 5 top horses from each race of 5 races (25 / 5) 5 top contenders race; 1 wins--that's one top horse (5-1) 4 remaining top horses race, one wins; that's 2 top horses (4-1) 3 remaining top horses contend; winner is #3 That's 3 top horses from 8 races Race#1 Race#2 Race#3 Race#4 Race#5 A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Race#6 A1 B1 C1 D1 E1 Let's Say ranking 1st 2nd 3rd 4th 5th Eliminate D1 E1 D2 E2 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 Left with B1 C1 A2 B2 C2 A3 B3 C3 Eliminate C3 as there are more than three faster horses C2, C1, B1, A1 Eliminate C2 as there are three faster horses C1, B1, A1 Eliminate B3 as there are three faster horses B2, B1, A1 Left with 5 horses for Race#7 B1 C1 A2 B2 A3 So 7 races 7 races. put 25 horses in 5 group. and we will have 5 sorted list of horses in each group. put 1st place horse in each group, and we will have a sorted list X. X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate. 2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse. 8 the answer is one race as the question doesn't specify all the horses have to run in separate races. 0 Races. Ask the jockeys to rate the 10 fastest horses and take the average of the top 3. Nobody knows the horses that are fast better than the jockeys. Race results can vary from race to race but the jockeys truly know the fastest and besides because race results vary anyway you will not find the fastest horses with the least races you will find the fastest on that day. Either way your results will not be accurate without a larger dataset. The jockeys however already have a deeper dataset. Better yet find the local bookie for the track and ask for the odds on the horses. Why solve a problem that has already be solved. |

Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer. 6 AnswersThe best I can do in Java: int findMinimum(int[] a, int start, int end){ if (end-start == 0){ return a[end]; } if (end-start == 1){ if (a[end] = 2){ int split = (start+end)/2; int leftLeast = findMinimum(a, start, split); int rightLeast = findMinimum(a, split+1, end); if (leftLeast void GetMinMax(int[] array, out int minValue, out int maxValue) { if (array == null || array.Length == 0) throw new ArgumentException("array null or empty."); MinMax minmax = GetMinMax(array, 0, array.Length - 1); minValue = minmax.Min; maxValue = minmax.Max; } MinMax GetMinMax(int[] array, int begin, int end) { if (begin == end) return new MinMax { Min = array[begin], Max = array[begin] }; else if (begin + 1 == end) return new MinMax { Min = Math.Min(array[begin], array[end]), Max = Math.Max(array[begin], array[end]) }; else { int mid = begin + (end - begin) / 2; MinMax left = GetMinMax(array, begin, mid); MinMax right = GetMinMax(array, mid + 1, end); return new MinMax { Min = Math.Min(left.Min, right.Min), Max = Math.Max(left.Max, right.Max) }; } } struct MinMax { public int Min; public int Max; } #include #include void devide_conque(int*, int, int, int*, int*); int main(int argc, char** argv) { int min, max; int i = 0, array_size = (argc - 1); int* array = (int*) malloc(sizeof(int) * (argc - 1)); for (; i rmax ? lmax : rmax; } } Show More Responses public static int[] minMax(int[] a) { int[] mm = new int[2]; if (a.length > 0) { mm[0] = a[0]; mm[1] = a[1]; } mm = minMax(a,0,a.length-1); return mm; } public static int[] minMax(int[] a, int low, int high) { int[] temp = new int[2]; if (low+1 < high) { int mid = (low+high)/2; int[] temp1 = minMax(a,low,mid); int[] temp2 = minMax(a,mid+1,high); temp[0] = Math.min(temp1[0],temp2[0]); temp[1] = Math.max(temp1[1],temp2[1]); return temp; } else if (low <= high) { if (a[low] < a[high]) { temp[0] = a[low]; temp[1] = a[high]; } else { temp[0] = a[high]; temp[1] = a[low]; } } return temp; } def find_min_max(arr): return min_max(arr, 0, len(arr)-1, 1e308,-1e308) def min_max(arr, i, j, mn, mx): if not arr or i > j: return mn, mx elif i == j: return min(mn, arr[i]), max(mx,arr[i]) else: mid = ( i + j) / 2 left = min_max(arr, i, mid-1, min(mn, arr[mid]), min(mn, arr[mid])) right = min_max(arr, mid+1, j, min(mn, arr[mid]), max(mx,arr[mid])) return min(left[0], right[0]), max(left[1], right[1]) first divide list in two, compare number from each list so we got 1list where the minimum is and second list where maximun is. Search for the min in the first list and the max in the second list. $list[$n-1-$i]){ $temp = $list[$i]; $list[$i] = $list[$n-1-$i]; $list[$n-1-$i] = $temp; } } $min = $list[0]; for($i=1;$i$max) $max=$list[$i]; } $result = array('min'=>$min, 'max'=>$max); return $result; } ?> |

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

**1**–

**10**of

**1,051**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Intern
- Software Engineering Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer
- Software Engineering
- Data Scientist
- Technology Analyst
- Product Manager
- Engineering
- Analyst