# 408K

Software Engineer Intern interview questions shared by candidates

## Top Interview Questions

Sort: Relevance|Popular|Date
Software Engineer was asked...June 19, 2012

### You have a 100 coins laying flat on a table, each with a head side and a tail side. 10 of them are heads up, 90 are tails up. You can't feel, see or in any other way find out which side is up. Split the coins into two piles such that there are the same number of heads in each pile.

Split into two piles, one with 90 coins and the other with 10. Flip over every coin in the pile with 10 coins. Less

Pick 10 coins from the original 100 and put them in a separate pile. Then flip those 10 coins over. The two piles are now guaranteed to have the same number of heads. For a general solution of N heads and a total of M coins: 1.) Pick any N coins out of the original group and form a second pile. 2.) Flip the new pile of N coins over. Done. Example (N=2, M=6): Original group is HHTTTT (mixed randomly). Pick any two of these and flip them over. There are only three possible scenarios: 1: The two coins you picked are both tails. New groups are {HHTT} {TT} and when you flip the 2nd group you have {HHTT} and {HH}. 2.) The two coins you picked consist of one head and one tail. New groups are {HTTT} and {HT} and when you flip the 2nd group you have {HTTT} and {TH}. 3.) The two coins you picked are both heads. New groups are {TTTT} and {HH} and when you flip the 2nd group you have {TTTT} and {TT}. Less

### An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element.

1. calculate the sum of elements in array say SUM 2. sum of numbers 1 to 100 is(n* (n+1))/2 = 5050 when n==100 3. missing element is (5050-SUM) Less

Sum them and then subtract them from 5050. In general, if an array of size n - 1 elements has unique elements from 1 to n, then the missing element can be found by subtracting the sum of the elements in the array from sum(1 ... n) = n * (n + 1) / 2. Alternately, one could use a boolean array of length n with all values set to false and then for each value, set array[val - 1] to true. To find the missing value, scan through the array and find the index which is set to false. Return index + 1. This requires O(n) memory and two passes over an O(n) array (instead of constant memory and one pass), but has the advantage of actually allowing you to verify whether or not the input was well formed. Less

Read the question. Here are the steps to solve it: 1) find the sum of integers 1 to 100 2) subtract the sum of the 99 members of your set 3) the result is your missing element! Very satisfying! Less

### Write some pseudo code to raise a number to a power.

int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } Less

small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; } Less

double Power(int x, int y) { double ret = 1; double power = x; while (y &gt; 0) { if (y &amp; 1) { ret *= power; } power *= power; y &gt;&gt;= 1; } return ret; } Less

### Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division.

O(size of array) time &amp; space: First, realize that saying the element should be the product of all other numbers is like saying it is the product of all the numbers to the left, times the product of all the numbers to the right. This is the main idea. Call the original array A, with n elements. Index it with C notation, i.e. from A[0] to A[n - 1]. Create a new array B, also with n elements (can be uninitialized). Then, do this: Accumulator = 1 For i = 0 to n - 2: Accumulator *= A[i] B[i + 1] = Accumulator Accumulator = 1 For i = n - 1 down to 1: Accumulator *= A[i] B[i - 1] *= Accumulator Replace A with B It traverses A twice and executes 2n multiplicates, hence O(n) time It creates an array B with the same size as A, hence O(n) temporary space Less

Create two more arrays. One array contains the products of the elements going upward. That is, B[0] = A[0], B[1] = A[0] * A[1], B[2] = B[1] * A[2], and so on. The other array contains the products of the elements going down. That is, C[n] = A[n], C[n-1] = A[n] * A[n-1], and so on. Now A[i] is simply B[i-1] * C[i+1]. Less

Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i&lt; size; ++i) total *= A[i]; for(int i=0; i&lt; size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1) Less

### How many unique handshakes if each person in a group of 10 give handshakes out to each and every other individual. (a) 100 (b) 50 (c) 45 (d) 20 (e) 10

true, or 9+8+7+...+2+1

None of those answers are correct. The follow-up question should be are we assuming that each person is only using 1 hand? For example, if everyone is only giving handshakes left to left, or left to right or right to right or right to left? Granted left to right and right to left would be awkward. Less

45. Imagine it as a polygon of side 10. Or draw out triangle, square, pentagon, and see the pattern yourself, if you don't know the algorithm. Less

### Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this?

Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Less

Awesome!!

### What sort would you use if you required tight max time bounds and wanted highly regular performance.

Merge sort and heapsort are always guaranteed to be n*log(n). Quicksort is usually faster on the average but can be as bad as O(n^2), although with very low probability. Heapsort also does it sorting in-place, without needing an extra buffer, like mergesort. Lastly, heapsort is much easier to implement and understand than balancing trees mentioned by earlier posts. Less

That is so say, a "Balanced Tree Sort" is guaranteed to be O(n log n) always.

for something like this you generally want bubble sort or insertion sort. It's not about being fast it's about being consistent. Make it do exactly the same thing every time. Less

### What is a JavaScript callback function?

A callback function is a piece of JavaScript code that executes after the main function that the callback is attached to executes successfully. Less

udaykanth, I would say that a .forEach() would be the most common and most basic use of a callback function. I'm just writing this to help anyone that might have a hard time thinking up a quick example if the come across this question themselves. Example: var numArray = [ 1, 2, 3 ] ; numArray.forEach( function( i ) { console.log( arr[ i - 1 ] ) } ) ; // logs out // 1 // 2 // 3 Less

Is there a front end role at bloomberg. I guess your position must have been labelled software dev right? altho ur a dront end dev Less

### Implement a method to determine whether a string is a palindrome.

Take a string as function parameter. Copy this str value into a new var, then use .reverse() thereupon. Compare the reversed copy back against original string using turnery operator to set resVariable to "true" : "false". Return resVariable. Less

(Using .split(""), as well as .join(""))

const palindrome = (str) =&gt; str == str.reversed() palindrome('hello') // false palindrome('eve') // true Less