Intern Software Engineering Interview Questions | Glassdoor

# Intern Software Engineering Interview Questions

1,054

Intern software engineering interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Dec 13, 2013
 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 b7 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 questionSee 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; idef 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 Development Engineering Intern at Amazon was asked...

Jun 10, 2012
 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-TreeShow More ResponsesDatabase indexes is a classic example

Mar 31, 2012
 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)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).Closed form solution. GGShow More Responsesint public(int n){ if(n == 0) return n; if(n == 1) return n; return (n-1)+(n-2); }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

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

Mar 20, 2012
 Implement integer division4 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 ResponsesI 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); }

Jul 5, 2012

Nov 6, 2012
 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#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 ResponsesAndddd I forgot negative number check. That's just a simple if(str[0] == '-') check.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 Truepublic boolean isInteger(String s) { if(s.indexOf('.') == -1) return false; if(s.indexOf('-') > 0) return false; return true; }

Nov 15, 2012
 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 => nwell normal case n comparisons Compare in pair and you have n-1 comparisons...Show More ResponsesMinimum 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 Engineering Intern at Yelp was asked...

Mar 7, 2013
 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)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 resultActually, 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?

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

May 17, 2012
 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.htmlTo 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 ResponsesSorting 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)