# Engineer Intern Interview Questions

Engineer intern interview questions shared by candidates

## Top Interview Questions

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<rightLeast){ return leftLeast; } else { return rightLeast; } } else return a[start]; } int min(int[] a){ return this.findMinimum(a, 0, a.length-1); } 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; } ?> |

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

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<end) { sum=array[start]+array[end]; if(sum==target) { printf("([%d:%d],[%d:%d],[%d:%d])\n",i,array[i],start,array[start],end,array[end]); return true; } else if(sum<target) ++start; else --end; } } return false; } Show More Responses the algorithm for 3 elements sum up to a given number is also the same; the only change one needs to make is replace line target=array[i]; with target=total-array[i]; is there an algorithm with a lower order? says O( nlogn ); I am not able to think of anything! we can modify the 3sum algorithm for this. It is possible to do it in O(n) create a binary tree from the sorted array in O(n) subtract each value in array from target and find if its there in the tree, if found push to hash map, with the array item as key and the subtracted value as key next time before subtracting value in the array from target check if it is in the hash map @Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*logn import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Random; import java.util.Scanner; import java.util.Set; public class SumOfTwoElements { public static void main(String[] args) { final Scanner in = new Scanner(System.in); final Random random = new Random(); while (true) { System.out.println("Enter array size : "); int size = in.nextInt(); int[] array = new int[size]; for (int i = 0; i > 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; } |

To return the 'm' smallest numbers from a file of 'n' numbers 8 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 array Show More Responses Anuj, 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 partitioning Maintain 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...

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 Pattern Show More Responses I would use doubly link list Doubly linkedList Use 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. |

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

Online median. 5 AnswersUse 2 heaps, one has stuff median, balance as necessary. can you please share some other technical questions that you can recall Hey when were u informed about the offer after the onsite interview? Thanks Show More Responses Right 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? |

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 temp oh 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 Responses do 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. |

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

Traverse a binary there so that the order returned is ordered from smallest to greatest. 5 AnswersIn order binary tree traversal void 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 Responses If 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) |

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 Responses I 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). |

Given the head pointers to two linked lists of unknown length, find the node of intersection if they do intersect. 5 AnswersSuppose that the pointers are head1 and head2. Move head1 and increment a count1 till head1 reaches null. Move head2 and increment count2 till head2 reaches null. If head1 > head2 or head2 > head1, move the respective pointer to such a position in the linked list so that the length of the linked lists from there are equal. Then, start checking if both pointers point to the same node and incrementing both until that condition is met. If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection. I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer. My solutions: Suppose length of List A is m, length of List B is n, If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop) If time is more of a concern, 1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n). 2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)). 3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)). the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n))) pblm can be solved by making a circular linked list. Start with head1 and traverse thru the list and modify the lastnode.nxtptr -> head2 Now start with head2 and traverse. If you reach the head2 again then the list do intersect. Show More Responses Vijay has the best solution with linear time. Vijay's solution works great for finding out whether they intersect, but the question asks for finding the node of intersection. I think William's solution will work best for finding the node of intersection. The obvious one is an O(n^2) solution by traversing the first list with the nodes of the second list and doing a comparison. |

**11**–

**20**of

**1,935**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