# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

Make a program that writes a Binary Search Tree to a file. Now create a program that reads those files and recreates a Binary Search Tree. 5 AnswersThe BST should be read in > and save each values into a file. Its important that the tree is parsed in preorder- or regenerating tree will give a completely different tree. The solution by Jeevan is perfect. Inorder/Postorder - it is not possible to reconstruct the tree. calling insert(node), for every node read from file will re-create the original tree. Here's a code to do it: __________________________________________ #include #include "math.h" using namespace std; class BinaryTree { public: BinaryTree::BinaryTree(int v) : value(v) {left = NULL; right = NULL;}; int value; BinaryTree *left; BinaryTree *right; }; void dfs(BinaryTree *root, FILE *fp) { fprintf(fp, "%d|", root->value); if(root->left == NULL) fprintf(fp, "N|"); else dfs(root->left, fp); if(root->right == NULL) fprintf(fp, "N|"); else dfs(root->right, fp); } void serializeTree(BinaryTree *root) { FILE *fp = fopen("tree_serialized.txt", "w"); dfs(root, fp); fclose(fp); } BinaryTree* dfs_r(FILE *fp) { fpos_t position; fgetpos (fp, &position); char isN; fscanf(fp, "%c|", &isN); if(isN != 'N') { fsetpos(fp, &position); // integer, this node exists int value; fscanf(fp, "%d|", &value); BinaryTree *newroot = new BinaryTree(value); newroot->left = dfs_r(fp); newroot->right = dfs_r(fp); return newroot; } else { // no children // NULL already set by constructor return NULL; } } BinaryTree *deSerializeTree() { FILE *fp = fopen("tree_serialized.txt", "r"); BinaryTree *newT = dfs_r(fp); fclose(fp); return newT; } int main() { // Construct a binary tree BinaryTree root(4); BinaryTree n2(2); BinaryTree n6(6); BinaryTree n1(1); BinaryTree n3(3); root.left = &n2; root.right = &n6; n2.left = &n1; n2.right = &n3; // Serialize and de-serialize it serializeTree(&root); BinaryTree *newRoot = deSerializeTree(); return 0; } Show More Responses Preorder and postOrder are both correct. /*Java Code for Question - preOrder traversal is the way to go!*/ import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.LinkedList; import java.util.List; public class SimpleBinarySearchTree> implements Serializable { /** * */ private static final long serialVersionUID = 1L; Node root; private class Node implements Serializable{ T data; Node left; Node right; public Node(T data){ this.data=data; left=null; right=null; } } public SimpleBinarySearchTree(){ } public void add(T data){ root=addhelp(root,data); } private Node addhelp(Node node,T data){ if(node == null){ node=new Node(data); return node; } else if(node.data.compareTo(data) > 0){ node.left=addhelp(node.left,data); } else{ node.right= addhelp(node.right,data); } return node; } public void printPreOrder(){ printhelp(root); } private void printhelp(Node node){ if (node !=null){ System.out.println(node.data); printhelp(node.left); printhelp(node.right); } } public List preOrder() { List list = new LinkedList(); return preOrder(list,root); } /** * Helper method to list out items in BST in preOrder traversal * @param list the list of the items so far in preOrder traversal * @param curr the curr node being checked * @return list of items in BST in preOrder traversal */ private List preOrder(List list,Node curr){ if (curr != null){ list.add(curr.data); preOrder(list,curr.left); preOrder(list,curr.right); } return list; } public static void main(String args[]){ SimpleBinarySearchTree tree= new SimpleBinarySearchTree(); tree.add(6); tree.add(2); tree.add(8); tree.add(1); tree.add(3); tree.add(5); tree.add(9); SimpleBinarySearchTree tree2=null; try{ FileOutputStream fout = new FileOutputStream("/Users/Ore/Desktop/tree.ser"); ObjectOutputStream oos = new ObjectOutputStream(fout); oos.writeObject(tree); oos.close(); System.out.println("Done"); }catch(Exception ex){ ex.printStackTrace(); } try{ FileInputStream fin = new FileInputStream("/Users/Ore/Desktop/tree.ser"); ObjectInputStream ois = new ObjectInputStream(fin); tree2 = (SimpleBinarySearchTree) ois.readObject(); }catch(Exception ex){ ex.printStackTrace(); } List list = new LinkedList(); list=tree2.preOrder(); SimpleBinarySearchTree tree3= new SimpleBinarySearchTree(); for(int i=0;i<list.size();i++){ tree3.add(list.get(i)); } //tree3.printPreOrder(); System.out.println(tree.root.left.left.data); System.out.println(tree3.root.left.left.data); } } |

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

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); } } } |

Given a triangle, determine if its a scalene, equilateral, isosceles or neither... required knowledge of triangle properties, I learnt these properties about two decades ago so ofcourse I was fuzzy on the details, completely unexpected 4 Answerstesting use of ==, got a feeling he wanted to use bit level comparisons to compare sides lengths If the sides are all integers, then compare the length^2 instead of length to avoid the floating comparison; If the sides are floating numbers, then we need to set an epsilon to test. You'd better ask the interviewer about this. Asking this will definitely gives the interviewer better impression.... I believe :-) BTW, if you are given the sides instead of points, the condition to make an triangle is: a+b > c && b+c > a && c+a > b Show More Responses /* Q: Given a, b, c, determine if it can be the 3 sides of triangles, if yes determine if it's equilateral, isosceles, or scalene. */ #include #include #include using namespace std; // Use this in real world typedef enum { NONE = 0, EQUILATERAL = 1, ISOCELES = 2, SCALENE = 3 } TriangleType; double Epsilon = 1.0E-6; string GetTriangleType(double a, double b, double c) { if (a+b > c && b+c > a && c+a > b) { bool ab = (fabs(a-b) < Epsilon); bool bc = (fabs(b-c) < Epsilon); bool ca = (fabs(c-a) < Epsilon); if (ab && bc && ca) return "Equilateral"; if (ab || bc || ca) return "Isoceles"; return "Scalene"; } else { return "None"; } } int main() { cout << GetTriangleType(3, 3, 3) << endl; cout << GetTriangleType(3, 3, 5) << endl; cout << GetTriangleType(3, 4, 5) << endl; cout << GetTriangleType(3, 4, 7) << endl; return 0; } /* Output: Equilateral Isoceles Scalene None */ |

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

1) A puzzle to find 3 numbers in an array which summed to 0. 5 AnswersSort 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...

Given an array, put all repeated characters together. 4 Answerssimply 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. |

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

unlimited supply of coins of different demoninations. pick min number of coins to get given amount. 4 Answersstandard 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<amount;amt++){ if(amt <denom[i]){ C[i][amt]=C[i+1][amt]; }else{ C[i][amt]=1+C[i][amt-denom[i]]; } } } |

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

Find the length of the longest palindrom in a given string 4 AnswersOnly 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...

I got questions like "Given a dictionary of words, how do you calculate the anagrams for a new word". 4 AnswersOne 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...

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 Answerspublic 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; } |

**51**–

**60**of

**3,476**Interview Questions

## See Interview Questions for Similar Jobs

- Intern
- Software Engineer Intern
- Software Engineer
- Software Development Engineer
- Software Engineering Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer I
- Software Engineering
- Technology Analyst
- Program Manager
- Summer Analyst