# Software Development Engineer Intern Interview Questions

Software development engineer intern interview questions shared by candidates

## Top Interview Questions

Determine if an array from 1..n has a duplicate in constant time and space. 11 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate. ^^ Sorry, that's linear time *and* at best linear space, you fail. What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates. Show More Responses SUM(array) - (N(N+1)/2) = missing number. @Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4} I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap. I'm pretty sure OP posted something wrong there, and they were probably asking to do it in linear time and not constant. If it's constant, the way I would do it would be using a HashSet to check if the key (value in array) is contained, and if not add it to the set. If at any time I find an element that's already inside, return false; If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate. I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers |

To find and return the common node of two linked lists merged into a 'Y' shape. 13 Answershow did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8. For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9 5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same. Show More Responses @kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9 Can this be done using hash tables? Or is there anything more efficient? i think that kvr's answer is the best. @snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this 1 -2 -3 -4-7-8-9 x -x -x -x -x-o 12-13-14-5-6-8-9 (sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning. HASH TABLE seems the only efficient wt. 1. add each element's address (of the smallest list)and push it to the hash table. 2. start walking second list. 3. get element compar eits address with hash table if match is found in hash table, return 4. if list is not exhausted, go to step 2. 5. return NULL Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left. First reverse both list and find point where both gets diverged For Y condition the list could be List 1: 1->2->3->4->5->6 List 2: 7->8->9->4->5->6 So reverse list would be 6->5->4->3->2->1 6->5->4->9->8->7 now compare two list and move forward the position where you find next node of both are different is the point of merging Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better. Let's say L1 is the list starting with the lower number, and L2 is the other Set X = Head of L1 Set Y = Head of L2 While X <= Y Set X = Next(L1) End While If (X==Y) Return X Else While Y<=X Set Y = Next(L2) End While If X==Y Return X End If End If Repeat until you reach the end of either list. |

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 Answerspublic 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<<element[i] break } else { i=i+2 } } I dnt have any idea about its time complexity... Show More Responses This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer. public int returnNonRepeat(int[] input) { if(input.length < 3) return -1; else { int repeat = null; if(input[0] == input[1]) repeat = input[0]; else if(input[0] == input[2]) return input[1]; else return input[0]; for(int i = 2; i<input.length; i++) { if(input[i] != repeat) return input[i]; } } return -1; } Cant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) space only 2 possible solutions 1.) using sorting 2.) using additional space. which will be less than o(n) sub find_odd { my @a = @{$_[0]}; my ($i, $n); $n = $a[0]; for $i (1 .. $#a) { $n = $n ^ $a[$i]; } printf("number is %s\n", $n); } |

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 |

Write a function that takes in an array and repeats an integer that appears the most. 5 Answersif: Array [2][2][3][3][3][2][1][2][1] it should print [3] Confusing. In your example, 2 appears the most. Do you mean the integer that repeats the most consecutively? Cause that would be 3. Anyways, in either case, you can go through the array adding all the key-value pairs (number and times) to a hashmap and then access the hashmap in constant time. O(n). class FindMostOccurences { public static DictionaryEntry MostOccurences(int[] Array) { Hashtable ht = new Hashtable(); for (int i = 0; i Int32.Parse(de.Value.ToString())) { { de.Key = item.Key; de.Value = item.Value; } } } return de; } } Show More Responses Using map , i think one loop is sufficient. private static int mostReapeatingNumber(int[] is) { HashMap map = new HashMap(); int tempHighestCount = 0; int keyHighest = 0; for (int index=0; index tempHighestCount) { tempHighestCount = numCount; keyHighest = number; } } } return keyHighest; } I think there's no need to have a map. Just maintain variables prev_max_run, prev_max_num, prev_num, curr_num and curr_run. In the loop if the prev_num was equal to curr_num increment curr_run. When you find the num is different check curr_run with prev_run. If curr_run > prev_run, prev_max_num = curr_num. |

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

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

Write a program that sees if two binary trees are equal. 6 AnswersI utilized a depth-first traversal method, comparing the data within each node and recursively checking the left, then right child. Don't know if this works or not... value = $value; $this->left = $left; $this->right = $right; } // O(n) times inorder traversal function testEsqual($tree1,$tree2) { if($tree1->value ==null || $tree2->value==null) return false; if($tree1->value ==null && $tree2->value==null) return true; while($tree1->value!=null) { if($tree1->value == $tree2->value) { equal($tree1->left,$tree2->left); equal($tree1->right,$tree2->right); } else { return false; } } } } ?> How if we use in-order traversal? If my understanding is correct, two binary trees are equal if they contain the same elements (although at different positions in the tree) Show More Responses bool AreEqual(Node* node1, Node* node2) { if( (node1 == NULL && node2 != NULL) || (node2 == NULL && node1 != NULL ) return false; if(node1 == NULL && node2 == NULL) return true; if(node1->data != node2->data) return false; return( AreEqual(node1->left, node2->left) && AreEqual( node1->right, node2->right) }; int main(); { AreEqual(root1, root); }; The solution by kvr doesn't cover a case when node1->data and node2->data are equal. An additional if is required. fb, If if(node1->data != node2->data) is not true, what does that tell you *Is* true? |

Given an array of integers, all but one of which appears an even number of times, find the one integer which appears an odd number of times. Upon completion, asked to improve the algorithm in terms of both time and space, eventually asked to do it in O(n) time and constant space. 4 Answersxor the entire array, all the integers which appear an even number of times will cancel eachother out int[] theArray = new int[]{1, 1, 2, 2, 3, 3, 3, 4, 4, 10, 10, 10, 10, 10, 11, 11, 12, 12}; Map theMap = new HashMap(); for (int i = 0; i mapKeys = theMap.keySet(); for(int keyInt : mapKeys) { if(theMap.get(keyInt) % 2 != 0) { System.out.println(keyInt + " occurs odd number of times"); } } } I was also asked this in 2010,march. Show More Responses XOR |

**1**–

**10**of

**303**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