# Software Intern Interview Questions

Software intern interview questions shared by candidates

## Top Interview Questions

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

Implement integer division without using / or %. Questions about running time. Can you do it faster? 6 AnswersOptimal running time: O(log n) Binary search Here's an implementation that works -- any ideas on how to make it go faster? public static void divide_without_slash_or_mod(int num, int divisor) { int factor = 0; int remainder = num; System.out.println("Number = " + num + " divisor = " + divisor); while(remainder >= divisor) { remainder -= divisor; factor++; } System.out.println(" remainder = " + remainder + " factor = " + factor ); } Show More Responses D(Divisor), N(Divident) low = 0, high = INT_MAX/D while(low N) high = mid - 1; else low = mid + 1; } return -1; //No divisor Here is the Java implementation of implementing division with O(log n) time complexity (actually, this solution is using divide operator). public static void divide(int dividend, int divisor) { int mid, low = 0, high = Integer.MAX_VALUE / divisor; while(low dividend) { high = mid-1; } else { low = mid +1; } } } |

Write a function in Java that will take a sorted array of ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation. 5 Answerscreate temp array; starting from the second element copy the i'th char if input[i-1] != input[i] return temp oh efficiency is O(n) you can't create a temp array because you don't know the size until after you process. you could count the number of dupes in one pass, then allocate the array, then do the compacting. or you could allocate the array equal to the size of the original and accept that some elements will be null (or -1, or whatever). or you could use some dynamic data structure like an ArrayList to build the compacted list and convert it to an array at the end (ArrayList.toArray(...)). regardless, it's still O(n) and uses 2x the memory. makes me think there's a more elegant solution though. Show More Responses do bitwise XOR of consecutive numbers. When the xor is 0, you know the number is duplicate. It will require single pass thru the array to identify number of duplicates in the array. you can also use 2 index, at the beginning they both = 0, then you will have a previous and a next, if previous value = next value increment next index until next value != previous value then increment previous index by 1 and assign "next value" to it and so forth until you "next index reach the end of the array and then increment all previous index assigning null or -1. O(n) without using 2x memory. Anyway, I hope it is not too confusing, its late but I hope you got the big picture. |

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

Traverse a binary there so that the order returned is ordered from smallest to greatest. 5 AnswersIn order binary tree traversal void inorder (Node * root){ if (root) { inorder(root->left) coutvalue; inorder(root->right) } } This is a binary tree, not a binary search tree. Thus, in order traversal may not work. Show More Responses If it isn't a binary search tree, then just traverse the tree in any which way and put the elements into a min heap. Then iteratively pop the min off the top to return smallest to greatest. Traversal would take O(n), building the min heap is also O(n), and popping min off n times is also O(n) so total is O(n). each popping takes logn. hence O(ologn) |

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

**21**–

**30**of

**1,408**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Intern
- Software Engineering Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer
- Software Engineering
- Data Scientist
- Technology Analyst
- Product Manager
- Engineering
- Analyst