# Software Engineer Intern Interview Questions

Software engineer intern interview questions shared by candidates

## Top Interview Questions

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

### Software Engineer Intern at PayPal was asked...

n= 20 for (i=0;i<n; i--) print i the question was to change or replace a only one character in for loop to print 20 times. 5 Answersit has to do with decrement or condition clause in for loop n= 20 for (i=0;-i<n; i--) print i n= 20 for (i=0;i<n; n--) print i Show More Responses add 4 in front of the 0 (in i=0); so it becomes i=40; i < n (which is 20); i-- changing i-- to n-- is a correct answer. adding 4 in front of i=0 would work, but does not satisfy the condition "change or replace a character" as it adds a character instead. |

Output a single linked list in reverse, in linear time and constant space, and recursively 5 Answersvoid recursive_reverse(nodeptr inlist) { if (inlist->next == NULL) { printf(" %d ", inlist->value); return; } recursive_reverse(inlist->next); printf(" %d ", inlist->value); } here it is a java code for reversing a linked list recursively Node reverse(Node head) { return reverse(head,null); } Node reverse(Node head,Node tail) { Node tmp = head.next; head.next = tail; tail = head; if (tmp == null) return head; head = tmp; return reverse(head,tail); } void revis(Node*node, Node* ptr){ if(node==null)return; revis(node->next,node); node->next=ptr; } Show More Responses Reversing it recursively always needs at least O(n) space in memory. def reverse(lst): if not lst or len(lst) == 1: return lst else: return reverse(lst[1:]) + [lst[0]] |

Given a list of "threads", which contain 2 variables - starting and ending times - implement a function that will return all running threads at some time t. Optimize it. (faster than O(n) ) 7 AnswersWe need to pre process this, Given the thread timings, we can create a int array of size max(endtimings) - min(start timings) and add 1 from array[start] to array[end] for each thread. Now, given a certain time, you can just lookup in the array, which takes O(1) time. The above solution will work and will be efficient in terms of time. But the amount of storage required is going to be massive, especially since thread timings are going to be generally specified in precision of milliseconds and can potentially run for a long time. A more optimal solution in terms of space could be dividing the time between min(start) and max(end) in ranges and then store the corresponding threads for each range. Since a thread can cover a range fully or partially, we will need to store the start time and end time corresponding to each thread. The ranges can be decided based on the trade-off that is required between time and space efficiency. When size of ranges is 1, the solution will effectively turn into the one mentioned above. I believe the best solution is as follows: You iterate through each thread and make note of where it starts and where it ends. You store this information in a sort of object that holds a time, the number of the thread, and whether or not the thread started or ended. Sort this list of objects based on time. You have essentially divided your space into time ranges based on the start/stop times of threads. Now we create some array of lists that has it's size set to the number of objects we created, BUT DO NOT fill this array with the objects! The array will be used to keep track of which threads are running in each time range. Iterate through the objects you made, filling up the lists in the array as you go. Example: Thread durations: 1: |---------| 2: |---| 3: |-------| Final array: {(1),(1,2),(1),(1,3),(3),null} Now you can do O(logn) lookup in the array with a basic binary search on the time ranges. The result in the array is what threads are running at that time. Show More Responses Glassdoor formatted the picture so it is useless. Here is attempt 2: 1: |---------|......... 2: ... |---|............. 3: ............|-------| @Jake The solution's pre-process can be faster. You can just store all times in an array, along with whether each time is a start/end time. The you can just traverse the array. This means that you don't need to figure out, for each discrete period in time, what threads are running. that could be pretty inefficient. try using interval tree https://en.wikipedia.org/wiki/Interval_tree. You can then traverse the tree and find all timeranges that overlaps with given time t. The complexity is O(log n + m) where m is the number of results. you might also divide overlaping timeranges into non-overlaping ranges. To each non-overlaping range assignlist of ranges that used overlaps there. Sample solution is here: http://stackoverflow.com/questions/628837/how-to-divide-a-set-of-overlapping-ranges-into-non-overlapping-ranges Then you can lookup the non-overlaping range that overlaps your given time t. Return list of ranges that used to overlaps there. You can do this with binary search (log n). |

Say you have a single-column table of entries of variable size. Implement this table to also contain methods to lengthen one cell, cut a cell shorter, and to return which cell we're pointing at if given a certain distance from the beginning of the table. All methods need to be fast (assume a single-column table with many many entries). 6 AnswersOne way to do this is to use the doubly linked list. Assuming lengthening and cutting short a cell happens only at the end of the table, then both operations can be done easily and quickly on a D.L.List. Not sure what the interviewer meant by distance from beginning of the table... like number of bytes from the beginning of the table and he wants the cell number? For example, if each cell has length 5, and the user clicks on 13 from the top, then you need to let the user know he has clicked on cell 3. This operation needs to be fast. The search function needs to be doable in less than linear time, and so do inserts and deletes Show More Responses binary indexed trees link list of link lists An dynamically allocated array that can be resized.. |

### Software Engineer Intern at Facebook was asked...

Write a function in language of your choice that takes in two strings, and returns true if they match. Constraints are as follows: String 1, the text to match to, will be alphabets and digits. String 2, the pattern, will be alphabets, digits, '.' and '*'. '.' means either alphabet or digit will be considered as a "match". "*" means the previous character is repeat 0 or more # of times. For example: Text: Facebook Pattern: F.cebo*k returns true 8 AnswersNOTE : I didn't really get the part of : "*" means the previous character is repeat 0 or more # of times. If it can be repeated 0 or more times, that means it's always true... I might have misunderstood this part. This is the code considering '*' and '.' are exactly the same. bool myStringCompare(char* string1, char* string2){ bool match=false; for(int i=0; string1[i] != '\0' && string2[i]!='\0'; i++) { bool condition1 = string1[i]==string2[i]; bool condition2 = (string1[i]=='*' || string1[i]=='.') && (isalpha((int)string2[i]) || isdigit((int)string2[i])); bool condition3 = (string2[i]=='*' || string2[i]=='.') && (isalpha((int)string1[i]) || isdigit((int)string1[i])); if(condition1 || condition2 || condition3) match=true; else{ match=false; break; } } return match; } I have used '#' instead of '*' . this code goes according to the rule that '#' gives 0 or more number of prev character value. #include #include #include bool ifMatch(std::string text, std::string pattern) { int tlen = text.length(); int plen = pattern.length(); std::string output = ""; char prev = '\0'; int k = 0; for(int i=0; i< plen && k < tlen; i++) { char textc = text[k]; char patternc = pattern[i]; if(patternc == '#') { if(prev == '\0') prev = '#'; else if(prev == text[k]) { output = output + prev; k++; } } else if(patternc == '.') { prev = textc; output = output + text[k]; k++; } else if(textc == patternc) { output = output + textc; prev = textc; k++; } else prev = pattern[i]; } std::cout << output << std::endl; if(strcmp(text.c_str(),output.c_str())==0) return true; return false; } int main() { ifMatch("facebook","#m#f.cn#bo#k"); } #include using namespace std; bool regex_match(string s1, string s2); int main() { if(regex_match("facebook", ".*.")) { cout << "Pattern Matched!" << endl; } else { cout << "Pattern Not Matched!" << endl; } return 0; } bool regex_match(string s1, string s2) { char c1, c2; int s2i = 0; for(int i = 0; i < s1.length(); i++) { c1 = s1[i]; c2 = s2[s2i]; if(c2 == '.') { s2i++; continue; } if(c2 == '*') { c2 = s2[s2i - 1]; bool done = true; c1 = s1[i - 1]; for(int j = i; j < s1.length(); j++) { c1 = s1[j]; if(c2 != '.' && c1 != c2) { done = false; i = j - 1; break; } } if(done) { break; } } else if(c1 != c2) { return false; } s2i++; } if(s2i < s2.length()) { for(int j = s2i + 1; j < s2.length(); j++) { if(s2[j] != '*') { return false; } } } else { return true; } return true; } Show More Responses #include #include using namespace std; bool regex_match(string s1, string s2); int main() { string strs[10] = {"facebook", "f.cebo*k", "*", ".*", "facebo.*", "facebo.*k", ".*.", "", " ", ".....o*."}; for(int i = 0; i q; for(int i = 0; i < s1.length(); i++) { q.push(s1[i]); } char last_char; for(int i = 0; i < s2.length(); i++) { if(q.empty()) { return false; } char c1 = q.front(); q.pop(); if(last_char == '\0') { last_char = c1; } if(c1 == '.') { last_char = c1; continue; } if(c1 == '*') { if(last_char == '.' || last_char == '*') { last_char = c1; break; } bool done = true; for(int j = i; j < s2.length(); j++) { if(s2[j] != last_char) { done = false; i = j - 1; break; } } if(done) { last_char = c1; break; } } else if(c1 != s2[i]) { return false; } last_char = c1; } if(!q.empty()) { while(!q.empty()) { if(q.front() != '*') { return false; } q.pop(); } } return true; } boolean accepts(char* pattern, char* s) { if (!pattern || !s) return 0; if (0 == *pattern) return (0 == *s); if ((strlen(pattern) > 1) && (pattern[1] == '*')) { return (match(pattern, s) && accepts(pattern, s+1)) || accepts(pattern+2,s); } else { return (match(pattern, s) && accepts(pattern+1, s+1)); } } boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } @Rahul: a small bug there (matching the '*' rather than the '.'): boolean match(char* pattern, char* s) { return ((*pattern == '*') || (*pattern == *s)); } should be: boolean match(char* pattern, char* s) { return ((*pattern == '.') || (*pattern == *s)); } Other thoughts: -- "if ((strlen(pattern) > 1)" is redundant since "if (!pattern[1] =='*')" takes care of it. (and I'd generally avoid a strlen in either a loop or recursive call) -- This solution ends up with a stack depth that is equal to the length of the target string -- far from ideal. #include using namespace std; bool match(string s1, string s2) { bool matching = true; char c1 = s1.at(0), c2 = s2.at(0); unsigned int i = 0, j = 0; while(matching && (i 0 && c1 == s1.at(i - 1)) { i++; } else if(c2 != c1) { matching = false; } i++; j++; } return matching; } int main() { bool m = match("faceboooooook", "f.cebo*.k"); if(m) { cout<<"matching"<<endl; } else { cout<<"not matching"<<endl; } return 0; } public class MatchTwoStrings { public static void main(String[] args) { String s = "F9ceboooooook"; String t = "F.cebo*k"; String td = ""; for(int i=0; i<t.length(); i++) { char ch = t.charAt(i); if(ch == '.') { td += "[\\d|\\w]"; }else { td += ch; } } System.out.println(td); System.out.println(s.matches(td)); } } |

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

### Software Engineering Intern at Yelp was asked...

You have two arrays with N integers in them. Merge those arrays using a recursive algorithm so that the integers in the final array are sorted. 6 AnswersIsn't this essentially mergesort? how to solve it? def funky(arrOne, arrTwo, arrThree, indexOne, indexTwo, indexThree): if(indexOne >= len(arrOne) and indexTwo >= len(arrTwo)): return arrThree if(not(arrOne[indexOne] in arrTwo)): arrThree.append(arrOne[indexOne]) if(not(arrTwo[indexOne] in arrOne)): arrThree.append(arrTwo[indexTwo]) indexOne = indexOne + 1 indexTwo = indexTwo + 1 funky(arrOne, arrTwo, arrThree, indexOne, indexTwo, indexThree) Show More Responses @Dung Pham you are right it is mergesort def merge(a1, a2): """ it is mergesort with unusual interface 2x Array on input """ return _merge(a1 + a2) def _merge(seq): if len(seq) = a_size: out.extend(b[b_i:]) break else: out.append(b[b_i]) b_i += 1 if b_i >= b_size: out.extend(a[a_i:]) break return out if __name__ == "__main__": got = merge([1,10,2,4], [12,1,9,7]) print(got) Actually, merge sort will require an extra O(m + n) space to store the temporary merged array. Probably it's better to concatenate two arrays then do quick sort? def merge(nums_1, nums_2): result = [] if len(nums_1) == 0: result.extend(nums_2) return result if len(nums_2) == 0: result.extend(nums_1) return result if nums_1[0] < nums_2[0]: result.append(nums_1[0]) result.extend(merge(nums_1[1:], nums_2)) else: result.append(nums_2[0]) result.extend(merge(nums_1, nums_2[1:])) return result |

**21**–

**30**of

**1,050**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