# Software Engineer Intern Interview Questions

Software engineer intern interview questions shared by candidates

## Top Interview Questions

Write an algorithm to insert a new value into a circular sorted linked list. 4 Answerspublic void InsertCircular(List head, int value) { List current = head; if (value > head.value) { current = head; while(current.value < value && current.value < current.next.value) { current = current.next; } } else { while(current.value < current.next.value) { current = current.next; } //go to largest value while(current.next.value < value) { current = current.next; } } ListNode addedNode = new ListNode(value); addedNode.next = current.next; current.next = addedNode; } See more videos at youtube.com/user/programminginterivew http://www.youtube.com/user/programminginterview } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 struct Node { int val; Node * next; }; void List::insert(Node * n) { if(head == NULL) { head = n; n -> next = NULL return; } if(head -> val val) { n -> next = head; head = n; return; } while(tmp -> next != NULL && tmp -> next -> val val) { tmp = tmp -> next; } if(tmp - > next == NULL) { tmp -> next = n; n -> next = NULL; } else { n -> next = tmp -> next; tmp -> next = n; } return; } Show More Responses class Node { public: Node* next; int value; Node(int v) { value=v; next=NULL; } }; void InsertNode(Node* head, int value) { if(!head) { head=new Node(value); head=head->next; return; } Node* node=head; if(node->value>value)// Update head pointer { //trick is firstly insert after the head, then swap it Node*tmpNode= node->next; node->next= new Node(value); node->next->next=tmpNode; int tmp=node->next->value; node->next->value=node->value; node->value=tmp; return; } while(node->next!=head) { if(node->next->value>value) { Node*tmpNode=node->next; node->next=new Node(value); node->next->next=tmpNode; return; } node=node->next; } Node*tmpNode=node->next; node->next=new Node(value); node->next->next=tmpNode; return; } |

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

How can one implement a queue with only a stack implementation? 4 AnswersYou will need at least two stacks. public class Queue { private Stack inbox = new Stack(); private Stack outbox = new Stack(); public void queue(E item) { inbox.push(item); } public E dequeue() { if (outbox.isEmpty()) { while (!inbox.isEmpty()) { outbox.push(inbox.pop()); } } return outbox.pop(); } } you have double ended queue (Deque) and insertion and removal can be handled at both end either left or right. But if you want to implement Queue as stack, then restrict the operation at any one end either left. So Front and rear both become at the same end. Never mind my previous answer was wrong implementation. It is actually implementing stack using Queue. Show More Responses #include #include using namespace std; stack st1, st2; int pop( ) { if (!st1.empty()) { int t,t1; while(st1.size() != 1) { t = st1.top(); st1.pop(); st2.push(t); } t1 = st1.top(); st1.pop(); while(st2.size()) { t = st2.top(); st2.pop(); st1.push(t); } return t1; } } int main() { st1.push(2); st1.push(3); st1.push(4); st1.push(5); st1.push(6); cout<<pop()<<endl; cout<<pop()<<endl; cout<<pop()<<endl; cout<<pop()<<endl; cout<<pop()<<endl; cout<<pop()<<endl; return 0; } |

I was asked two questions. Q 1. You are given two version numbers of a software, like Version 10.3.4 and Version 10.3.41. Write a program to find out which of the version numbers are the latest. If version 1 is latest output -1, if version number 2 is latest output +1 else output 0 if same version. Both the version numbers are taken as string. He also asks to make the program of minimum time complexity as we can. At the end he also asked the difference between an iterative program and one with recurrence and their advantages and disadvantages. Q 2. Given two files with a list of application IDs (or some kind of data) stored in them , write a program to compare the data in the two files and output all the common data found in each. What data structure would you use and why ? Give a minimum time and space complexity algorithm. Why did you choose the particular data Structure or algorithm ? 5 Answers1. This was a little tricky. You have to check for the decimal place in both the versions and then Store that part of the string till the decimal place in a temporary variable and then convert them to integer and check which one is greater. You have to keep on doing that till you reach the end of the version numbers or till when you find the answer 2. In the second question you can use Linked lists and then Binary Search Algorithm. The interviewer will ask you the reason for this. Why not just delimit the string with "." Then you'll have an array of string numbers. Then loop with the array from 0 -> n (depending on how many decimals there was) and compare. Return when one is greater than the other. You will have to check if you get a index out of bounds if one has more decimals than the other. Over all, that should be in n time. As for #2. HashTable it. Also n time. Show More Responses If you are using c++, can't you just use the "compare" method that is built into the string class? Maybe not the best solution... the time complexity is O(n). public static void main(String[] args) { String ver1 = "10.22.7.3"; String ver2 = "10.22.8.4.1"; String split1[] = ver1.split("\\."); String split2[] = ver2.split("\\."); int max = split1.length > split2.length ? split1.length : split2.length; for (int i = 0; i i) { System.out.println(+1); break; } else if (split2.length i) { System.out.println(-1); break; } else { if (Integer.parseInt(split1[i]) > Integer.parseInt(split2[i])) { System.out.println(-1); break; } else if (Integer.parseInt(split1[i]) < Integer .parseInt(split2[i])) { System.out.println(+1); break; } } } } |

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

Implement integer division 4 Answerspublic class Solution { public void integerDivision(int num, int den){ int q=0,rem=0; while(num>=den){ num-=den; q++; } rem=num; System.out.println("Quotient "+q+" Remainder "+rem); } public static void main(String[] args) { Solution sol = new Solution(); sol.integerDivision(73, 9); } } public static int division(int a, int b) { if (a b) { int q = 1; int c = b; while ((b = b > 1; while ((a = a - b) >= c) { q++; } return q; } else { return 0; } } Minor correction public static int division(int a, int b) { if (a b) { int q = 1; int c = b; while ((b = b > 1; while ((a = a - b) >= c) { q++; } return q; } else { return 0; } } Show More Responses I hope this will be helpful int divFunc(int* num,int* den,int* rem) { int q = 1; int backupNum = *num; int backupDen = *den; while((backupDen = backupDen >=1; backupNum = backupNum - backupDen; *num = backupNum; *rem = backupNum; return q; } void divide(num,den) { int q=0,r=0; while(num>den) { q = q + divFunc(&num,&den,&r); } printf("Q = %d\t R = %d\n",q,r); } |

Write a function to determine if a string is an integer. 6 AnswersJava version: boolean checkInt(String s){ try{ Integer.parseInt(s) } catch(NumberFormatException e){ return False;} return True; } Java version without try/catch: public static boolean isInt(String s){ for (int i=0; i<s.length;i++){ if (!Character.isDigit(s.charAt(i)){return False;} } return True; } Python version: def check_int(s): a = "1234567890" for c in s: if c not in a: return False return True #include #include int main(){ string str = ""; int len = str.length(); for (int i=0;i57){ return 0; } } return 1; } Actually my previous answer is incomplete. I don't check for negative numbers, nor decimal points. #include #include bool checknumber(string str){ int len = strlen(str); if ( (len==0) || (!str) ) return false; if (str[len-1] == '.') return false; bool flag = false; for (int i=0; i57){ return false; } if (str[i] =='.'){ if (flag){ return false; } flag = true } } } return 1; } Show More Responses Andddd I forgot negative number check. That's just a simple if(str[0] == '-') check. public boolean isInteger(String s) { if(s.indexOf('.') == -1) return false; if(s.indexOf('-') > 0) return false; return true; } def is_digit(thing): if not isinstance(thing, basestring): return ValueError('Argument needs to be of instance basestring.') # Be nice and strip whitespace. thing = thing.strip() # If there is nothing there, bail. if thing == '': return False # If there is more than 1 decimal, bail. if thing.count('.') > 1: return False # Sort of a special case. If the number is a negative, just strip it out. if thing.startswith('-'): # Do another strip. We are explicitly allowing for space after the negative. thing = thing[1:].lstrip() # If there are characters left over after all valid characters were stripped, # then something is invalid. if re.sub(VALID_RE, '', thing) != '': return False return True |

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

Given an unsorted array, extract the max and min value using the least number of comparison. 4 Answersf(1)=1 f(2)=f(1)+1=2 f(3)=f(2)+f(1)+1=4 ... var min, max, arr = [3,4,2,7,1,9]; for(i in arr){ //n-iterations min = Math.min( arr[i], arr[i+1], min ); //2 comparisons max = Math.max( arr[i], arr[i+1], max ); //2 comparisons } //4n => n well normal case n comparisons Compare in pair and you have n-1 comparisons... Show More Responses Minimum number of comparisons is 3n/2. The strategy is to go through the elements in pairs, and compare the smaller one to the minimum, and the bigger one to the maximum. This is 3 comparisons, done n/2 times in total, for 3n/2 running time. Working code in python: import random import sys r = [random.randint(1,100) for i in range(31)] print r mini = r[0] maxi = r[0] start = 0 if len(r) % 2 != 0: start = 1 for i in range(start,len(r)-1,2): n1 = r[i] n2 = r[i+1] # Exactly 3 comparisons each time if(n1 < n2): mini = min(n1,mini) maxi = max(n2,maxi) else: mini = min(n2,mini) maxi = max(n1,maxi) print mini print maxi |

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

Given a string write a function which prints all the subsets of the string. Now make the function to return only unique solutions. For example if they give you "abc" you print out a ab abc ac b bc c Now for the unique solution constraint, if they give you "aba" the output should be: a ab aba b 7 AnswersThere is a divide & conquer strategy with this problem. Divide string into two halves. Recursively print the string on left and then on right. Finally, for each string on left, combine it with every string on the right. (Note this will not give the unique solution.) To obtain the unique solution, a simple way is to use a set to keep track of every substrings we have constructed. If element is already in the set, we simply not add it. In the end, we print out every element in the set. Maybe there is a better way without using extra memory. What about counting the number of each character in a string? for "aba" we have a-2, b - 1. now recursive solution which takes charecter, for a we choose 0a, 1a, and 2a and push to the 'b' where take 0b or 1b. now we have "", "a","aa","ab","b". all subsets + empty one. @Allen: The interviewer specified that he wants a recursive solution and you are not allowed to use extra memory. Note: The interviewer gave me a big hint: "What happens if you sort the array and simply generate all the subsets?" Show More Responses @Marius: what do you mean by "sort the array"? There is no array in the question See this link and view discuss session for solution to unique subsets https://oj.leetcode.com/problems/subsets-ii/ So this requires subsets to be printed and not substrings; ordering of characters doesn't matter. So sort the characters and generate unique subsets. import java.util.Arrays; import java.util.Scanner; public class UniqueSubsetGenerator { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter string : "); final String masterWord = in.nextLine(); char[] word = masterWord.toCharArray(); Arrays.sort(word); generateUniqueSubsets(word, 0, ""); } } private static void generateUniqueSubsets(char[] word, int start, String prefix) { //System.out.println("start " + start + " prefix " + prefix); if (start >= word.length) { System.out.println(prefix); return; } char ch = word[start]; int count = 1; for (int i=start+1; i<word.length; i++) { if (word[i] == ch) { count++; } else { break; } } String next = ""; for (int i=0; i<=count; i++) { generateUniqueSubsets(word, start+count, prefix+next); next = next + ch; } } } def uniqueSubsets(inpStr): inpStr = sorted(inpStr) subSets = [] uniqueSubsetsHelper(subSets, "", 0, inpStr) return subSets def uniqueSubsetsHelper(subSets, currSet, index, inpStr): if index == len(inpStr): subSets.append(currSet) if index >= len(inpStr): return charLen = getLen(index, inpStr) for i in range(charLen + 1): posSet = currSet + inpStr[index] * i uniqueSubsetsHelper(subSets, posSet, index + charLen, inpStr) def getLen(index, inpStr): currChar = inpStr[index] currLen = 0 while index < len(inpStr): if inpStr[index] == currChar: currLen += 1 else: return currLen index += 1 return currLen |

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

Given a number n, give me a function that returns the nth fibonacci number. Running time, space complexity, iterative vs. recursive. 5 AnswersLet me give you a recursive & not-efficient solution to get n th fibonacci number. public int findNthFib(int n) { return (n < 2 ? n : (findNthFib(n-1)+findNthFib(n-2)); } This short method will recursively return fib number. However, running time is very awful! it's O(2^n) = exponential time. it will quickly become a non-usable method after n = 30~40. There is another quick and elegant linear time solution, but I want the next person to present that in here. (if you google it, you can find it easily) Closed form solution. GG int public(int n){ if(n == 0) return n; if(n == 1) return n; return (n-1)+(n-2); } Show More Responses public class fib { public static void main(String args[]){ int n=12; int counter=2; int[] arr = new int[n+1]; arr[0]=1; arr[1]=1; while(counter<n+1){ arr[counter]=arr[counter-1]+arr[counter-2]; counter++; } System.out.print("answer is "); System.out.print(arr[n-1]); } } unsigned long long fibonacci(unsigned long long n) { unsigned long long c = 0; unsigned long long i = 1; unsigned long long j = 0; unsigned long long nfib = -1; while (c < n) { i = i + j; c++; if(c == n) { nfib = i; cout << i << " "; break; } j = j + i; c++; if(c == n) { nfib = j; //break; } cout << i << " " << j << " "; } cout << endl << nfib; return nfib; } Time complexity O(N/2). |

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

Assuming a preexisting list of 100 words, how would you efficiently see if a word received from input is an anagram of any of the 100 words? 4 AnswersFirst Sort 100 words and keep the hash of sorted words.. Now when you recieve a word, SOrt it and check if Hash contains that key. O(nlogn) Where n is length of String. Hi I think you can take a look at the most efficient algorithm for this question in this link www.crackeasily.com/2012/01/find-whether-2-strings-are-anagrams.html To say what MW said more clearly: If you sort words that are the same anagram they will always look the same. Example: "god" and "dog" both look like "dgo". So you sort the input word, then you iterate through the list of 100 words, and while looking at each word sort that word. compare if the input and that word are the same. If they are then you have found an anagram. if you made it to the end of the list and you haven't found an anagram then an anagram does not exist in the list. Show More Responses Sorting takes O(nLogn) average time. This can be further improved by counting characters in the strings. So, for the given string calculate count of each character in an array [256]. For each word in the list, check if it contains the same count for its characters and return that word. Complexity O(n) |

Can you think of an example of a scenario where you would want to use a tree with more degrees of branching than a binary tree? 4 AnswersIf you need to represent a company's personal structure. For example, one president is trailed by more than just two vice presidents and it will span.... Great example for this: modeling a dictionary of possible words. I.e. a->g->r works because aggregate but a->g->(g) wouldn't because the second g wouldn't exist in the tree (no words begin or are formed with the string "agg"). I've actually received this in an Amazon interview where I was asked to model the game Boggle. B-Tree Show More Responses Database indexes is a classic example |

**31**–

**40**of

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