# Software Intern Interview Questions

Software intern interview questions shared by candidates

## Top Interview Questions

### 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) |

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

Print out a binary tree level by level 6 AnswersRun breadth-first search using a queue. Add a null pointer to signify the end of each level. Are questions really this easy? No. That was my question for the first round. Second round questions are harder. At most companies, engineers interview recruits. So the difficulty of the question depends on which engineer is interviewing you. Show More Responses But whether they hire you or not depends on whether you are from an Ivy league university, right? Are you from one? ^ Yes you're right. Serious Comment: There is usually a large alumni base from the target schools, some of these target schools are ivies. Troll Comment: Yes. If you don't go to an ivy, you don't get hired. Tough luck. I'm not from an ivy league and I hold hired. But I've also started 2 companies with several clients, etc. You just have to be proactive. |

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= 20 for (i=0;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. |

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

Write a power function power(a , b) returns a^b 7 Answersint power (double a, int b) { for (int i = 1, i <= b, i++) { a *= a; } return a; } There are some conditions you are missing. What if b is <=0 ? The conditions made by the Hulu rep was to assume b > 0. However there is a better way to do this problem. Show More Responses long power(int a, int n) { if(n%2==0) return power(a,n/2)*power(a,n/2); else if (n%2==1&&n!=1) return power(a,n-1)*a; else //n==1 return a; } double power(int a, int n){ double res=1; while(n!=0){ if((n&1)==1) { if(n>0) res*=a; else res/=a; } a*=a; n /=2; } return res; } def power(a,b): if b is 1: return a return a * (power(a, b--)) double pow(int a,int b) { if(b0) { if(b%2==1) res*=a; a*=a; b>>1; } return res } |

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"< public class MatchTwoStrings { public static void main(String[] args) { String s = "F9ceboooooook"; String t = "F.cebo*k"; String td = ""; for(int i=0; i |

**21**–

**30**of

**1,398**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Intern
- Software Engineer Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer
- Software Engineering
- Data Scientist
- Software Engineer New Grad
- Engineering Intern
- Technology Analyst
- Engineering