Software Development Engineer Interview Questions | Glassdoor

# Software Development Engineer Interview Questions

3,476

Software development engineer interview questions shared by candidates

## Top Interview Questions

Sort: Relevance Popular Date

Sep 26, 2012

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

Jan 12, 2011
 Print all permutations of a given string. 4 Answers # include # include /* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } /* Driver program to test above functions */ int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } a string of N characaters will have following number of string combination Np1 + Np2 + Np2+...NpN Using recursion we can solve this. I am giving the pesudo code with a small example. let the string be "abc". I am showing the recursive call within the bracket itself. Just to understand. Don't confuse that this is a code inside permute function. permute(abc) { ----level 1----- letter saved at this level is = a; all combination List obtained at this level = permute(bc); after the call returns put the saved letter {a} at each position in each entry and do the same for all entry in the list List obtained here is only bc and cb; that means put a every position of the return bc and cb ----> for bc {abc,back,bcd} and for cb {cab,cab,cba} return all the entries. At the highest level you will get all the permutation of the string. --------------level 2----------- letter saved = b ; all combination List obtained at this level = permute(c); after the call returns put the saved letter at each position in each entry and do the same for all entry in the list List obtained here is only c; that means put b every position of the return c --> bc{putting b before c} and cb{putting b after c} return bc and cb. --------------level 3----------- letter saved = c ; all combination List obtained at this level = 1; //Here it only c is returned Last letter is returned as this is only 1 combination exist -- base condition of recursion. } Show More Responses C# code. I'm a tester, so my code is a bit rusty, but the algorithm works. public static void Permutations(string orgStr) { List permutations = new List(); _perm(orgStr.ToCharArray(), String.Empty, ref permutations); foreach (string str in permutations) { Console.WriteLine(str); } } private static void _perm(char[] sample, string filled, ref List permutations) { if (sample.Length == 1) { string perm = String.Format("{0}{1}", filled, new string(sample)); permutations.Add(perm); } else { for (int i = 0; i i) { newSample[j-1] = sample[j]; } else { newSample[j] = sample[j]; } } _perm(newSample, newFilled, ref permutations); } } }

Feb 19, 2013

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

Sep 22, 2012
 1) A puzzle to find 3 numbers in an array which summed to 0. 5 Answers Sort the array (N Log N). Then, for each i, keep two pointers j at the beginning and k at the end of the subarray{i -> N]. If subarray[j] + subarray[k] + subarray[i] = 0, you're done. If the sum is positive, then move k back. If the sum is too small, then move j forward. Try this until j > k, at which point, increment i, and do this again with j = i and k = N initially. You'll have O(n^2). Classical Computer Science problem... http://en.wikipedia.org/wiki/3SUM Classical Computer Science problem... http://en.wikipedia.org/wiki/3SUM Show More Responses def sumOfThree(inputList): A = sorted(inputList) for i in range(len(A)): j = i k = len(A) - 1 # -1 is to account for python's zero-based index while (k >= j): sumOfThree = A[i] + A[j] + A[k] if (sumOfThree == 0): print A[i], A[j], A[k] # return (A[i], A[j], A[k]) # We didn't match. Let's try to get a little closer: # If the sum was too big, decrease k. # If the sum was too small, increase j. if sumOfThree > 0: k -= 1 else: j += 1 sumOfThree([-1,-2,-3,-4,1,2,3]) Super popular question 3sum and this post has the full solution with all its variants http://bit.ly/2aJyjFx

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

Jul 12, 2011
 Given an array, put all repeated characters together. 4 Answers simply perform the sorting according to their ASCII values. #include #include #include using namespace std; int main() { //declare variables const int size = 2000; // N const int startRange = 97; const int endRange = 122; const int length = endRange - startRange + 1; vector arr(size); vector newArr(length); char ch = ' '; //initialize character array in O(N) srand(time(NULL)); for(int i = 0; i < size; i++) { arr[i] = (char) (rand() % length + startRange); } //sort array in O(Nlong(N)) sort(arr.begin(), arr.end()); //combine similar characters in O(N) for(int i = 0, j = -1; i < size; i++) { if( arr.at(i) == ch) { newArr.at(j).append(1, ch); } else { j++; ch = arr.at(i); newArr.at(j) = ch; } } for(int i = 0; i < newArr.size(); i++) { cout << newArr[i] << endl; } return 0; } depending on the requested space complexity you don't have to sort the chars inside the string. there are only 26 chars in the alphabet. so, you can have a map or an int array with 26 counters. each counter i will say how many times the char 'a' + i appears in the string. then iterate once over the string incrementing the specific counters and in the end display the map or array. Show More Responses For the previous answer, you should not assume that the characters are alpha only. You should plan to have to accomodate for all possible chars, which simply means you have an array of size 256.

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

Sep 1, 2010
 Given two lists, A and B, of sizes n and k, respectively, describe an algorithm to determine the intersection, C, of the two lists. What is the complexity of your algorithm? (The obvious solution is O(n*k)). Can you describe a solution that is faster? (An optimized solution can do it in O(n+k)). 4 Answers The obvious solution compares each element of list A with each element of list B, searching for intersection. The optimized solution utilizes a hash table. A[5] = {3,5,6,9,10} B[6] = {2,3,4,6,9,10} C[6] // Declare maximum size among two arrays Steps: ====== 1. Sort Array A[] and B[] 2. Compare A[aindex] == B[bindex] , == IF TRUE, ADD TO C[] == aindex++, bindex++ recursive Call to method again with new aindex,bindex 3. IF A[aindex] > B[bindex] , bindex++ recursive Call to method again with aindex, new bindex 4. IF A[aindex] < B[bindex] , aindex++ recursive Call to method again with new aindex, bindex Suresh's approach will not get O(N+K) complexity. Sorting individual list itself will cost O(nlogn) plus O(n+k) in merge sort. I think hash code will get O(n+k) complexity. Show More Responses Dynamic programming, see longest common subsequence

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

Dec 23, 2011
 unlimited supply of coins of different demoninations. pick min number of coins to get given amount. 4 Answers standard dp algo prob PHP solution: ============ 25,'dime'=>10,'nickel'=>5,'penny'=>1); while (\$total \$value) { if (\$value <= \$amt) { return \$name; } } throw new Exception("No denomination found less than \$amt"); } // in Java int[] denom={10000,5000,2000,1000,500,100,50,25,10,5,1}; int amountInCents = 34200; int coinCount = 0; int i=0; while(amountInCents>0){ coinCount = coinCount+( amountInCents/denom[i]); amountInCents=amountInCents % denom[i]; System.out.println(amountInCents); i++; } System.out.println("min of coins is "+coinCount); Show More Responses Here is the solution using dynamic programming - bottom up approach. // For denomination the answer is // The denomications are 4,3,1 . // THe rows are denominations and columns are amount. // // [[0, 1, 2, 1, 1, 2, 3, 2, 2, 3, 4, 3, 3, 4, 5], // [0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6], // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]] int[] denom={4,3,1} int n=denom.length; C = new int[n+1][amount]; for(int i=0;i=0;i--){ for(int amt=0;amt

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

Apr 11, 2012
 Find the length of the longest palindrom in a given string 4 Answers Only think of a n-square solution with two loops public class LongestPalindrome { public static void main(String args[]){ String arr="aaa"; String res=""; int ptr1=0; int ptr2=arr.length(); int center=0; for(int i=0;i=res.length()) res=arr.substring(ptr1,ptr2+1); if(ptr1-1>=0 && ptr2+1<=arr.length()-1) { ptr1=ptr1-1; ptr2=ptr2+1; } else break; } you can add extra conditions to check for when the length is less than 3 Show More Responses The above does not account for palindromes with an even length. Use indices as follows: center = i/2; left = center - 1; right = (i+1)/2; for(int i = 2; i < s*arr.length() - 1; i++) ...

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

Mar 26, 2009
 I got questions like "Given a dictionary of words, how do you calculate the anagrams for a new word". 4 Answers One answer was to precalculate a 26 element array for each dictionary word where an array element represented how many occurences of the corresponding letter of the alphabet occured in that word. You wouldn't. A new word would not appear in the dictionary. One way to do this would be to take each word in a dictionary and sort it and store it as a key in a hash. the values will be all the words that map to this one, stored as a list. Show More Responses Store all anagrams for the new word in a 2-dimensional array (column 1 = anagram, column 2 = flag). Compare each element in column 1 with words in the dictionary until found. If found, flag = good anagram, else flag = bad anagram! Just a guess. Suggestions please.

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

Oct 22, 2009
 Determine the first non-repeated character in a word. For example, in abbcaf it should return c. Do this in O(n) time with O(1) space. 4 Answers public char findFirstSolo(String input){ List[] buckets = new List[ alphabet.size ]; for(char c in input){ List curr = buckets[c]; // get appropriate bucket curr.add(c.index); // add index to list } int earliestIndex = infinity; for(List bucket in buckets){ if(bucket.size == 1){ if(bucket[0].index < earliestIndex){ earliestIndex = bucket[0].index; } } } return input.charAt(earliestIndex); } does O(1) mean, I can use a fixed 256 size array? public static char findFirstSolo(String input){ int[] letters = new int[26]; int pos = 0; for(char c : input.toCharArray()){ ++pos; if (letters[c - 'a'] == 0) letters[c - 'a'] = pos; else letters[c - 'a'] = Integer.MAX_VALUE; } char firstSolo = (char)0; int earliestIndex = Integer.MAX_VALUE; for (int i = 0; i < 26; ++i) { if (letters[i] < earliestIndex && letters[i] != 0) { earliestIndex = letters[i]; firstSolo = (char) ('a' + i); } } return firstSolo; } Show More Responses Since the alphabet is not dependent on n, it is O(1) char firstNonRepeated(String input) { int letters = new int[26]; for(char c : input.toCharArray()) letters[c-'a'] ++; // assuming initialized to 0 for(char c : input.toCharArray()) if (letters[c-'a'] < 2) return c; }
5160 of 3,476 Interview Questions

More