Engineer Intern Interview Questions | Glassdoor

# Engineer Intern Interview Questions

1,935

Engineer intern interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Mar 6, 2011
 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 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; } ?>

Mar 30, 2010
 25 racehorses, no stopwatch. 5 tracks. Figure out the top three fastest horses in the fewest number of races. 9 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 ResponsesB, 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 racesRace#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 races7 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.8the answer is one race as the question doesn't specify all the horses have to run in separate races.

Mar 8, 2012
 Given a sorted array, write a program to decide if two elements sum up to a third.9 AnswersDid you coded a solution < O(n^2 + logn) ?Assuming each number only appears once: //Java code public static void targetsum(int[] arr, int target) { if(arr == null) return; int start = 0; int end = arr.length -1; while(start target end--; } }typedef vector vint; bool check_element_sum(vint &array) { // n^2 algorithm sort(array.begin(),array.end()); //general case : nlogn copy(array.begin(),array.end(),ostream_iterator(cout," ")); cout=0;--i) //n^2 { start=0; end=i-1; target=array[i]; //note a<=b<=c for the tuples formed here hence check for c=a+b only while(start findSummingTriplets2(int[] array) { final Set> summingTriplets = new HashSet>(); for (int k = 2; k array[k]) { j--; } else if (sum > findSummingTriplets(int[] array) { final Set> summingTriplets = new HashSet>(); for (int i = 0; i end) { return false; } int mid = start + (end - start) / 2; if (array[mid] > value) { return contains(array, start, mid - 1, value); } else if (array[mid] < value) { return contains(array, mid + 1, end, value); } else { return true; } } }bool sumExists(vector nums, int target) { auto front = nums.begin(); auto back = nums.end() - 1; while (front != back) { if (*front + *back == target) return true; else if (*front + *back < target) front++; else back--; } return false; }

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

Feb 15, 2012
 To return the 'm' smallest numbers from a file of 'n' numbers8 AnswersI would first create an array holding the first m values of the file, and sort. Then, each value I read from the file, I can compare the the last (largest) value in the array. If its smaller, do a binary search to find the correct spot in the array. Insert the number and shift everything behind it back by 1. Worst case runtime will be O(n lg m)Why cant we simply start with min=INT_MIN. Then, read first number from file, if lower, set min=that number. Seek next number and so on... We dont need to load the whole file. We will go to the disk often though.I will create a min heap with the given numbers and extract 'm' minimums from the heap which will get stored into the resultant arrayShow More ResponsesAnuj, Wont it take time of O((M+N)log N)@spammer, I think it's O(n+m*log n), since you can construct the min heap bottom-up and that only takes O(n)Why don't we just sort the array and return the first m numbers? Takes O(nlogn) for sorting and O(m) to return the first m numbers.Modified quick sort. Pick a pivot and test if one half is smaller than m. If it is, drag the rest from the other half; if it is not, keep partitioningMaintain a heap of m numbers and also track a variable which stores the current highest value. So as u go through the n numbers, if the number is higher than the current highest number, ignore it else insert it into the heap and set the current highest value to the newly inserted value

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

Jan 19, 2011
 Questions related to data structures like "What data structure would you use for a browser's BACK & FORWARD ability"6 AnswersMay be Stack , any one please correct me if I am wrong.This can be implemented by using two different stacks, one for back and one for forward.Command PatternShow More ResponsesI would use doubly link listDoubly linkedListUse two stacks. Every time you visit a site, push its address in stack1. When you press back, pop from stack1 and also push in stack2. When user presses forward, pop from stack2 and also push in stack1.

Mar 24, 2013
 Online median.5 AnswersUse 2 heaps, one has stuff median, balance as necessary.can you please share some other technical questions that you can recallHey when were u informed about the offer after the onsite interview? ThanksShow More ResponsesRight after the interview.Sorry but this is about the homework problem: how long do they give you to solve it? what was the format of the table?

### Software Engineer Intern at Motorola Mobility was asked...

Mar 19, 2009
 Write a function in Java that will take a sorted array of ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation.5 Answerscreate temp array; starting from the second element copy the i'th char if input[i-1] != input[i] return tempoh efficiency is O(n)you can't create a temp array because you don't know the size until after you process. you could count the number of dupes in one pass, then allocate the array, then do the compacting. or you could allocate the array equal to the size of the original and accept that some elements will be null (or -1, or whatever). or you could use some dynamic data structure like an ArrayList to build the compacted list and convert it to an array at the end (ArrayList.toArray(...)). regardless, it's still O(n) and uses 2x the memory. makes me think there's a more elegant solution though.Show More Responsesdo bitwise XOR of consecutive numbers. When the xor is 0, you know the number is duplicate. It will require single pass thru the array to identify number of duplicates in the array.you can also use 2 index, at the beginning they both = 0, then you will have a previous and a next, if previous value = next value increment next index until next value != previous value then increment previous index by 1 and assign "next value" to it and so forth until you "next index reach the end of the array and then increment all previous index assigning null or -1. O(n) without using 2x memory. Anyway, I hope it is not too confusing, its late but I hope you got the big picture.

Aug 24, 2012
 Traverse a binary there so that the order returned is ordered from smallest to greatest.5 AnswersIn order binary tree traversalvoid inorder (Node * root){ if (root) { inorder(root->left) coutvalue; inorder(root->right) } }This is a binary tree, not a binary search tree. Thus, in order traversal may not work.Show More ResponsesIf it isn't a binary search tree, then just traverse the tree in any which way and put the elements into a min heap. Then iteratively pop the min off the top to return smallest to greatest. Traversal would take O(n), building the min heap is also O(n), and popping min off n times is also O(n) so total is O(n).each popping takes logn. hence O(ologn)

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

Jan 6, 2011
 Write a program to find the square root of a double.5 Answersuse binary search to narrow down the search space and keep multiplying the answer in each iteration by itself to check if it is equal to the double given. If it is lesser, move up the lower bound, else move down the upper bound.One easy to remember method that also has much better performance than binary searching for the result is the Babylonian Method. It is similar to Newton's method for finding derivatives. See the algorithm here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method Also, combining this algorithm with the Rough Estimation also described on that page will compute the squareroot of most double numbers in less than 10 iterations.Is it too obvious to ask if you can do double^.5 ?Show More ResponsesI would respond by showing that I am thinking about the problem as it is defined, not by making assumtions about what is implied. This can result in product that does not meet the requirement specifications, which can be very costly: "What do you mean, a program or a function? A program would require input and output mechanisms to make it meaningful, but makes it pretty usesless as a job assessment question. A function makes more sense in this context. "There's a variation of the problem which says "find the square root of a double up to the third decimal digit". I'd just multiply the original number by 10^position (meaning, for 3 digit accuracy it'd be 10^3) and ran a simple loop to find the closest integer. As soon as i*i > 10^position * number, you can return (i-1)/10^position. It's hella slow and unimaginative, but it works and you won't sound like you knew this problem ahead of time (if you come up with a Babylonian solution).

Jan 6, 2011