Software Development Engineer Intern Interview Questions | Glassdoor

# Software Development Engineer Intern Interview Questions

307

Software development engineer intern interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

### Software Development Engineer Intern at Microsoft was asked...

Mar 18, 2009
 Connect Four is a game where two players take turns dropping their color discs into a vertically suspended grid. The game ends when a player adds a disc to the playing grid that connects four discs of their color. The connected discs can be in a horizontal, vertical or diagonal line. Write a function to be called after every turn that returns true if the game is over (and false otherwise).3 AnswersThere are many ways to solve this, especially since you're not given any other details about the code architecture. Note that checking for four connected discs horizontally, vertically and diagonally is very similar, but varies in the direction. This is a good hint that it should be a method taking a parameter specifying the direction.The ask for a function, but how about a class and a method in order to explain some of my thinking (I think in Python nowadays) class Game: def __init__(self, w, h): self.w = w self.h = h self.board = [] # WxH (ColxRow) array ... def get_rows(self): ... def get_columns(self): ... def get_diagonals(self): ... def done(self): in_a_row = 0 lastdot = -1 for (c,r) in self.get_columns() + self.get_rows() + self.get_diagonals(): if self.board[c,r] is not None and self.board[c,r] == lastdot: in_a_row = in_a_row + 1 if in_a_row == 4: return True # TODO: perhaps return the dot instead? else: lastdot = self.board[c,r] in_a_row = 0 return Falses-The ask-They ask-g

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

Aug 27, 2012
 Is it possible to sort using linear time a file with lots of numbers that contain duplicates, when there are no limits of resources or space?3 AnswersIt is possible, just use a hash map in the first pass, and then on the second pass store it in a one dimensional array.if space is not a problem, create a integer array with size equal to the range of numbers. initialize all to 0. Then do array[number]++ for each number in fileuse bucket sort.. if stability is not the issue. or use counting sort

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

May 25, 2012
 Given a string of Rs and Gs, design an algorithm to produce a string with Rs in the front and Gs after that. The number of flips from Rs to Gs or otherwise should be minimum. The number of Rs and Gs in the end need not be same as that in the beginning, however the length of the entire string should be the same. 5 AnswersRegarding the R&G problem... couldn't you just scan the string keeping a count and then regurgitate the values? Essentially you could achieve an O(N) solution. for (int i = 0; i < inputString.size(); i++) { if ("R" == inputString.charAt(i)) { System.out.print("R"); else ++count; } for (int i = 0; i < count; i++) { System.out.print("G"); } -------- Alternatively I suppose you could swap all "R"s for 1, all "G"s for 0, calculate the binary value and then its a straight output. RGGGRRGRGGRRRR == 10001101001111 == 9039 == 8x1 = 8xR+6xG = 14char (initial length) Or am I misunderstanding the way you've explained the question.How about using Merge Sort? It would be done in O(nlogn).I think the interviewer's intent is to use the idea of counting sort; keep one pointer from head tracking Rs, another pointer from tail tracking Gs; moving forward the head pointer until reach a G; then moving backward the tail pointer until reach a R; swap R and G; move on until the pointers meet;Show More Responsespublic static void test() { System.out.println(solution("RGRGRRRGGG".toCharArray())); } private static char[] solution(char[] input) { int i; int j = input.length - 1; for(i = 0; i < j; j--) { while (i < j && input[i] == 'R') { i++; } if(input[j] == 'R') { input[j] = input[i]; input[i] = 'R'; } } return input; }// Use partition Algorithm char ch[]=str.toCharArray(); int i=-1; char q='r',temp; for(int j=0;j

Jun 23, 2012

### Software Development Engineering Intern at Amazon was asked...

Jun 23, 2012
 Write a function that returns the depth of a tree.3 Answerspublic static int depth(Node root, int level) { if(root != null) { if(depth(root.right, level + 1) > depth(root.left, level + 1)) return depth(root.right, level + 1); else return depth(root.left, level + 1); } return level; }Slightly simplified :] (I think this works; not doubling up on the recursive calls either) public static int depth(Node root, int level) { if (root == null) return level-1; return Math.max(depth(root.right, level+1), depth(root.left, level+1)); }int finddepth(node_t* node) { if(node == NULL) return -1; else return 1 + MAX(finddepth(node->lchild), finddepth(node->rchild)); }

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

Jan 10, 2012
 in an array of characters find the character that is repeated the most3 AnswersPriority QueueCorrect me if I'm wrong, but is priority queue really the best way? I think efficiency ends up being O(nlogn) for PQ...inserting n elements into the queue (insert is O(logn)) then peeking. Using a hash table, it takes O(n) to insert the n elements and O(n) to find the max, resulting in O(n) efficiency.Okay actually building a heap is O(n) not O(nlogn). So both techniques take O(n). Priority queue might be a little better since it only requires one scan and peek is O(1), whereas the hash table method requires two scans through the array.

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

Jan 10, 2012
 Print the BST in level order3 AnswersBasic idea: perform a breadth first traversal of the tree. Every time you dequeue a node, print it. This will give a level order print in linear time.Recursive function that starts at the root and recursively prints the value of each left and right node, along with the level order. bstprint(node, count) { if (node == null) { return; } print count + ": " + node.value; //pseudocode for printing cause lazy bstprint(node.left, count + 1); bstprint(node.right, count + 1); } bstprint(root, 0); //initial callif not tree: return nodes=collections.deque([tree]) currentCount, nextCount = 1, 0 while len(nodes)!=0: currentNode=nodes.popleft() currentCount-=1 print currentNode.val, if currentNode.left: nodes.append(currentNode.left) nextCount+=1 if currentNode.right: nodes.append(currentNode.right) nextCount+=1 if currentCount==0: #finished printing current level print '\n', currentCount, nextCount = nextCount, currentCount

### Software Development Engineer Intern at Microsoft was asked...

Sep 26, 2012
 How would you sort an array if you had infinite RAM? Infinite memory?3 AnswersI would probably use counting sort. This is not generally used outside of sorting a bunch of integer numbers that fall within a small range precisely because it uses a lot of memory. For e.g., to sort number in the range of 1 to 10,000, you will need an array C[1...10,000]. It can be extended to sort a set of any kind of stuff that has total ordering relationship between them, and is O(n) time. Only down side is that memory used will be insane depending on the range of values whatever you are sorting will take.If no duplicates exist, create an infinite array, put each integer in the array by using the value of the integer as the index to put the value in the array, then read the array from left to right ignoring null values. N write + N read = O(n) time complexity.counting sort!

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

Jan 30, 2012
 Write a program that reverses the words in a sentence.4 AnswersI used a stack, pushing words onto it as I reached spaces.=0; \$index--) { \$result[strlen(\$word)-1 - \$index] = \$word[\$index]; } return implode("", \$result); } // O(n/2) times = O(n) times function reverse2(\$word) { \$temp = ""; if(strlen(\$word)%2 == 1) \$stop = strlen(\$word)/2; else \$stop = strlen(\$word)/2-1; for (\$index = 0; \$indexString[] temp; temp = input.split(" "); System.out.println("Array length : " + temp.length); for (int i = temp.length; i > 0; i--) System.out.print(temp[i-1] + " " ); System.out.println(""); }Show More Responsespublic static String reverseSentence(String a){ StringBuilder result = new StringBuilder(); Stack stack = new Stack(); String[] temp; temp = a.split(" "); for (String s : temp){ stack.push(s); } while(!stack.empty()){ result.append(stack.pop() + " "); } return result.toString(); }

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

Nov 5, 2013
 About the details, and interviewer will communicate with you when you are typing. 3 AnswersDivision - Divide A/B - repeatedly subtract B from A, until A < B. At which time print the number of subtractions as the quotient. The left over value in B, is the remainder.More efficient - http://www.prasannatech.net/2009/01/division-without-division-operator_24.htmlFor the sum case of digits try a binary search type approach: Let S be the sum we are searching for Sort the array - you can do this in n*Log(n) (see http://en.wikipedia.org/wiki/Sorting_algorithm) Here is where the binary search idea comes in Divide the sorted array into sub arrays A1 and A2. Take the mid elements of both sub arrays as pivots p1 and p2. This gives us 4 sub-sub arrays - In A1, we have the left of p1 as A11 to the right of p1 as A12. In A2, we have to the left of p2 as A21 and right of p2 as A22. If p1 + p2 > S then we look in A12 and A13, A11 and A13 and A11 and A12 If p1 + p2 < S look in A12 and A14
2130 of 307 Interview Questions