Software Developer Interview Questions | Glassdoor

# Software Developer Interview Questions

"Software developers design, write, test, and maintain the code for a software system. Extensive knowledge of programming languages, data structures, and algorithms are necessary to pass the technical interview which is designed to test these skills. Employers are looking for candidates with a bachelor's degree in computer science or related field or equivalent work experience. "

## Top Interview Questions

Sort: Relevance Popular Date

### Software Development Engineer at Microsoft was asked...

Dec 30, 2011
 Pancakes, size varies, and are put in a stack with random order. You have one operation called Flip(int[] pancakes, int k) to flip all pancakes from the top one to kth pancake, write a sort(int[] pancakes]) method 6 Answers You can implement quicksort since swapping two items (i and j) can be done in three steps using the 1st item as a temporary position. Never mind the previous comment, misread the description of the Flip operation Could you make a more clear description the operation of Flip functon? Thanks! Show More Responses For example, if pancakes are {1,2,4,3}, (number means pancake sizes), and if we flip(pancakes, 2), then the first two pancakes are flipped and result will be {2,1,4,3} Well, selection sort would work, but it's slow. Find position j of the minimum between [i,n-1], starting with i = 0. If j != i, then use Flip(pancakes,n-j) to get it to the top, then flip to its subsequent minimum position i, therefore Flip(pancakes,n-i). Keep repeating until increasing i reaches n. Hmm, if indirect sorting is allowed (via pointers in extra space), then one could use quicksort, and place into target positions by flipping. But if that flipping is the only operation available, then even finding the minimum value AND it's current position for the selection sort above gets nontrivial (but doable).

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

Feb 15, 2012
 To return the 'm' smallest numbers from a file of 'n' numbers 8 Answers I 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 Development Engineering Intern at Amazon was asked...

Jun 23, 2012
 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. 7 Answers public 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<

Dec 17, 2009

Nov 13, 2010

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

Mar 20, 2009
 How would you implement a top 3 word count in a text editor application? 7 Answers What is the answer to this question? Would one just parse through the whole document and hash each word occurrence, with the key as the word itself, and the value as the number of occurrence? Can we use a BST to store word and length values? And then do a pre-order traversal? Another approach would be to sort in place in n log n. Then scan the sorted list of words and maintain a count of top three. Show More Responses max-Heap This can be done using Linked Hash. Each element of Hash has two pointer. Min pointing to element which comes next in the seq with count. When we add new word, either it will be added to hash or updated its count. If count is updated then we need to correct the Min and Max pointer accordingly. Also we need to corecct obj.Min.Max pointer and obj.Max.Min pointer accordingly. Keep track of the Max and Min element of the heap elements. Other optimization can be done to improve the worst case scenario like storing head pointer of list of words which has same count. Using Heap and Hash will solve the problem optimally. Keep a hash of word as key and count as value. And keep a Min heap of 3 elements. Build the heap with first 3 elements. For every new element increase the count in HashMap. Check if the element is in the heap, then update the count and reheapify. Else check if the element count is greater than top element of Min heap, if yes then replace that element with our new element and reheapify. Else don''t touch our heap and keep counting. This will make sure the heap will always have top 3 elements. Complexity: O(n) as heapify is constant always. MaxHeap/priorityQueue whose key is the word itself and the priority is the word count. When you need the top three words, just pop the heap three times 3*O(logN).

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

Jan 21, 2010
 Given a set of N numbers, assume that you have the set of numbers from 1 to N+1, with the exception of one number. How do you determine what number that is? What is the complexity of your solution? 5 Answers Two Step Process - 1) Sum of N Numbers Formula - (N*N+1)/2 [Complexity O(1)] 2) Iterate over the given N-1 numbers and calulate the sum [Complexity O(n)] Subtract result 1 - result 2; this gives the missing number! How about binary search on a sequence ???? This would take O(log n) to find ... Binary search on a sequence is O(log n), but you are assuming that you have been given an ordered set, which is not specified. The sort on the set will most likely be O(n log n). Show More Responses binary search in general meaning, not binary search on sorted list Binary search only works on a sorted list. It doesn't work anyways since you won't know what you are searching for. The correct answer is to iterate through the sorted list and look for the missing value, which takes n time.

### Financial Software Developer at Bloomberg L.P. was asked...

Nov 2, 2010
 Reverse an integer using C. 5 Answers in C: int reverseint(int x) { int y, k=1; while ( x > 10 ) { y = k * ( x % 10 ); k *= 10; x /= 10; } return y; } whoops! "int y" should be "int y=0" and "y = k * ( x%10 )" should be "y += k * (x%10)" num = 0 for (i=0; i 1 ) { a = ( x % 10 ); y = y *10 + a; x /= 10; } printf ("%d", y); return 0; } And the output will be 126.

### Software Development Engineer In Test at Amazon was asked...

Jan 27, 2012
 First explain what a tree, then binary tree, then a binary search tree is. Now implement a function that verifies whether a binary tree is a valid binary search tree. 5 Answers Sadly I ran out of time for this question. But I e-mailed the response after my time was up. First create a small implementation of a binary tree, I did it in java with the standard implementation Nodes with left and right children as data points. Check whether the left child and right child have valid values, which is to say make sure all children on the right of a node have values greater than parents that they came from. The key thing that I missed during the interview was the fact that if you traverse once to the right, then once to the left, you have to make sure the value is between the max and min that you've encountered up to that point. int validate_BST(struct tnode *tree){ int ret1, ret2; if (tree == NULL) return 1; else { if (tree->left != NULL){ if (tree->data > tree-left->data){ ret1 = validate_BSR(tree->left); } else return 0; } if (tree->right != NULL) { if (tree->data right->data){ ret2 = vaidate_BSD(tree->right); } else return 0; } return (ret1 == 1 && ret2 == 1)? 1: 0; } return 0; } To find whether a binary tree is valid Binary search tree, do inorder traversal and check if the nodes are sorted. Show More Responses private boolean isBST(){ return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isBST(Node node, int min, int max){ if(node == null) return true; if(node.data max) return false; else return (isBST(node.left, min, node.data) && isBST(node.right, node.data+1, max)); } In order to verify the Binary Search Tree, Read the nodes in Inorder mode. Also at every step check if the current node value is less than the one previously found then exit the traversal as the items are not sorted.

### Software Development Engineer at Microsoft was asked...

Aug 20, 2012
 Find the 20 longest strings in a text file. 5 Answers If you don't have to worry about space, you could use a hash with each word being the "key" and its length being the "value". Then sort bu hash by value, and choose the top 20. Another way can be to just traverse the strings and keep a min b-tree to keep the minimum element on the top. When size of tree + 20, then only insert (replace) in tree, if the current string length > root of tree(min) . This will take O(log20) for each insertion and O(N) for traversal. In the hash map approach described in the first answer, instead of having the word as the key, we can have the length as the key and value as the list of words with the length pointed by the key. You can use LinkedHashSet if you want sorting. Or you can maintain the largest 20 lengths in a separate data structure. This obviously is not a really optimal solution in terms of space complexity. Instead of that we can maintain a min-heap. Add first 20 words as it is. And then, if the new word has a larger length than the word at the top of the heap (smallest word as it's a min-heap) you remove the word from the heap and insert the new word into the heap. The heap size is always going to be 20 so you don't take much space and don't take much time to insert the word in the heap as well. Show More Responses The min-heap solutions looks nice..However, it would take O(n.logn) right? On worst case, we do have to insert/delete in min-heap (log n) for every n words. Any better solution exists?? Can we use dynamic programming to find the longest word and then remove the longest word and repeat the routine for 19 more times? That would be 20times O(N) , which is better than O(n.log n). Any comments? Correction: The min-heap version takes n.log(k) only which is O(n) only. -This looks the best solution so far.
4150 of 9,428 Interview Questions