Software Development Engineer I Interview Questions | Glassdoor

# Software Development Engineer I Interview Questions

308

Software development engineer i interview questions shared by candidates

## Top Interview Questions

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

Jan 24, 2010
 i)doubly linked list pairwise swap Be the first to answer this question

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

Jan 24, 2010
 ii) 2D matrix with nums increasing in right direction and downwards direction. Search for a target number. Be the first to answer this question

### Software Development Engineer In Test (SDET) I at Microsoft was asked...

Mar 1, 2011
 Implement a graph class, find the minimum spanning tree?Be the first to answer this question

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

May 24, 2011
 Given a log file containing (User_Id, URL, Timestamp) user can navigate page from one to the other. Find the three page subset sequence repeated maximum number of times. Records are sorted by Timestamp.1 AnswerSolved using queue of queues and Hash table.

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

May 24, 2011
 Bar raiser Given a NumberPool containing number sequence of numbers from 1 to infinity. Implement an interface, essentially two functions- checkin(N): which adds number to the number pool and makes it available. checkout(): returns minimum number from the pool and makes it unavailable.1 AnswerGave 4 implementations using ArrayList (checkin: O(N), checkout: O(N lg N)), Binary Search Tree (checkin: O(lg N) + balancing cost, checkout: O(lg N)), Binary Heap (checkin: O(lg N) + heapify cost, checkout: O(1) + heapify cost) and Hash table (checkin: O(1), checkout: O(N)).

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

May 24, 2011
 Bar raiser 1. Given array of numbers, find a, b, c such that a + b = c. Can you beat O(N**2) ? 2. Difference between Quick sort and Merge sort. What modifications you make in Quick sort so that it provides O(N lg N) worst case complexity.2 Answers1. Solved using hash table. complexity O(N**2). Told that there exist algorithm 3SUM which beats O(N**2) - http://en.wikipedia.org/wiki/3SUM. 2. Didn't get this question even after he gave me a hint. Answer is to find median in O(N) time(yeah it is possible to find median in O(N) in an unsorted array !) and assign that as pivot in each pass of quicksort. Thus quicksort behaves like merge sort by splitting array exactly in the middle.This is almost the same as 3sum problem and check http://bit.ly/2aJyjFx for full solution and all its variants.

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

May 24, 2011
 Given a set of numbers, partition the set in to two, such that sum of all the candidates in first subset = sum of all the candidate numbers in second subset.2 AnswersSolved by factoring sum of entire set and finding all candidate numbers which sums up to that factor. That is if the set sum = 15. Factorize 15 such as 1+14, 2+13, etc. And find all the candidates in the set which sums up to 1 and 14(and so on). Then subgroup them. Then follow up was how to handle negative values, what if values are largely distributed like {-1M1, -1, 0, 1M} The above method performs miserably. One solution I gave was to reduce numbers by orders of magnitude. That is above set is equivalent to {-11, -1, 0, 10} and while finding out factors of sum, go from -x to +y where x being most negative and y being most positive value in a given set.it's a subset sum problem with the targetted sum equal to half of the sum of elements in the array. It can be solved usin DP.

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

May 24, 2011
 Given a acyclic graph, find out its root; that is point where all the nodes converge. eg. G(V, E) = {(A->B), (B->C), (D->C)} C should be the root.1 Answershould be a straight forward.

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

Jun 1, 2011
 Design an algorithm to find out if an array has a pair of integers summing to some number X.2 AnswersPerl: store all the array elements as keys in a hash. for each key see if (X-key) exists in hash. Return true and exit as soon as condition satisfied. Works only for unique non-duplicated integers in array.Make a hash for all numbers [0-sum]. In each index store the number of times that number appears in the sequence. Scan the first half of this hash array. Check Count[Sum-index] and you got your answer. Linear :D

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

Jun 1, 2011
 Complexity of this algorithm. How to improve the complexity?3 AnswersN^2 and can be improved to n logn using binary serach.or could be linear time if you're allowed to use a hash tableI'm pretty sure hash table is the answer they were looking for...
110 of 308 Interview Questions