# Software Engineer Intern Interview Questions in New York State

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

Write an algorithm to insert a new value into a circular sorted linked list. 4 Answerspublic void InsertCircular(List head, int value) { List current = head; if (value > head.value) { current = head; while(current.value < value && current.value < current.next.value) { current = current.next; } } else { while(current.value < current.next.value) { current = current.next; } //go to largest value while(current.next.value < value) { current = current.next; } } ListNode addedNode = new ListNode(value); addedNode.next = current.next; current.next = addedNode; } See more videos at youtube.com/user/programminginterivew http://www.youtube.com/user/programminginterview } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 struct Node { int val; Node * next; }; void List::insert(Node * n) { if(head == NULL) { head = n; n -> next = NULL return; } if(head -> val val) { n -> next = head; head = n; return; } while(tmp -> next != NULL && tmp -> next -> val val) { tmp = tmp -> next; } if(tmp - > next == NULL) { tmp -> next = n; n -> next = NULL; } else { n -> next = tmp -> next; tmp -> next = n; } return; } Show More Responses class Node { public: Node* next; int value; Node(int v) { value=v; next=NULL; } }; void InsertNode(Node* head, int value) { if(!head) { head=new Node(value); head=head->next; return; } Node* node=head; if(node->value>value)// Update head pointer { //trick is firstly insert after the head, then swap it Node*tmpNode= node->next; node->next= new Node(value); node->next->next=tmpNode; int tmp=node->next->value; node->next->value=node->value; node->value=tmp; return; } while(node->next!=head) { if(node->next->value>value) { Node*tmpNode=node->next; node->next=new Node(value); node->next->next=tmpNode; return; } node=node->next; } Node*tmpNode=node->next; node->next=new Node(value); node->next->next=tmpNode; return; } |

Explain tail recursion. 3 Answerstail recursion is tail recursion Tail recursion does computation before recursive calls. A typical implementation is to pass the current result as a parameter to recursive call. A tail recursive function is one that performs a recursive call as its final step. Tail recursion is important because it can be more efficient - you can reuse the same stack frame for the next call, saving some time and memory. For example, a NON tail recursive Fibonacci function in OCaml (forgive me if I mess the syntax up any, most of the functional programming I've done is in Haskell): let rec fib n = match n with 0 -> 1 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) Obviously, the call to fib isn't the last thing that gets evaluated. That'd be the sum of the two recursive calls. Here's a tail recursive Fibonacci function, from Literate Programming Wiki: let fib n = let rec aux n b a = if n <= 0 then a else aux (n-1) (a+b) b in aux n 1 0 It works by "carrying along" the present sum as an argument in the aux function. That way, each call of aux can only make one recursive call (in the else branch), and the Fibonacci numbers are calculated as part of that recursive call. |

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

How would you find the n-th greatest element in a binary search tree? 2 AnswersI was able to choose the language to code the solution in. Traverse the BST in 'inorder'. That gives a sorted sequence. |

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

textbook algorithms questions 2 AnswersCan you tell me which questions they asked u? please send me an email to 5aht@gmx.at ...thanks! please post an example |

How would you go about finding the kth to last element in a singly linked list? 2 AnswersFirst check the size of the linkedList- O(1) operation Then walk through the linkedList from the head to the nth element, use a counter to keep track of how many elements you have walked through. return linkedListSize-number of elements you have walked through. use 2 pointers pointer 1 is 7 units ahead in position relative to pointer 2. Increment both pointer 1 reach end -> return pointer 2 |

Second Round: This was a bit difficult. The question is to generate sample math problems(additions) for a 8th grade student and the results should be stored in such a way that they can be printed when required. Sample problem is 7+8=_____ The constraints are:- 1) The numbers that are to be added should be <=9 2) The result should be <=17 2 Answersthis actually fairly simple, for the second constraint its x+y <=17, then all you need to do is have a random generator that finds some x solve for y (i.e. y<=17-x, that way you dont have to use the random generator twice and then have run it multiple times to make sure the result is valid) then a simple if statement to test whether user input is correct one more thing to get every result less than 17 , you would have to another if statement that uses 2 randomly generatored numbers if x+y <=17 isnt true do what i mentioned earlier |

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

Why Google? 1 Answergoogle is a world to access |

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

2 sum. 1 AnswerFirstly I said hash map. Then he ask me try not to take any additional space. Than I said that we can sort the list and use 2 pointers which gives O(n(logn)) time. He said it is good. |

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

find if two linked lists join each others or not and if yes where is the intersection point. 1 AnswerI didn't figured out the linear time algo at the first thought, then he gave me some hints and I was able to find the intersection point in linear time. |

**1**–

**10**of

**81**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