# Software Engineering Interview Questions in San Jose, CA

Software engineering interview questions shared by candidates

## Top Interview Questions

### Software Engineering Intern at Google was asked...

how would you find the shortest path between two nodes in a social network? 7 Answersdo breadth first search from both ends at the same time. Keep a set of all nodes that each has reached. When the sets have any element in common, there is a path. Does the above method have any advantage over the method in which we do bfs from one node of the nodes and stop when the other node is reached? BFS from both sides is massively faster than just doing BFS from one. Suppose each person has k friends and that the two nodes are d apart. BFS from one node is O(k^d). BFS from both nodes is O(k^(d/2)) -- the exponent is half as big. To put some example numbers on it, if each person has 100 friends and they are 10 apart, then BFS from one node takes 10^20 operations, whereas BFS from both nodes is 2*100^5= 200 billion operations. BFS from one node is intractable. BFS from both nodes is slow, but tractable. Show More Responses How about using Dijkstra's shortest path algorithm? Isn't that more efficient than a bfs? If you only care about the distance between two nodes and every edge length is 1 (both of which are true in this problem), then Dijkstra's shortest path algorithm basically is breadth first search (and BFS from both sides is faster than a simple BFS). If that doesn't make sense, then explain how http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode is different from a breadth first search in this case and I will clarify. Aren't you ignoring the time taken for checking for a common element in the two sets (which will be O(k^d))? Checking for set inclusion is constant time (assuming a reasonable hashset). Thus, it is O(1) to know whether or not a node that I add to one side's fringe is already in the other side's fringe. Does that make sense? |

### Senior Software Engineer at Google was asked...

what's wrong with the following code : <template type T > T accumulate ( vector<T> in) { T total = in[0]; for (int i =0; i < in.length() ; i++) { total = total + in[i]; } return T } 7 Answers1. The big bug in[0] is accumulated twice. 2. empty vector ... The solution or 1 and 2 : total = T(); 3. input vector need to be const & 4. Better return the value as a &T in the argument list rather than as the ret value T can also be a string for example ! or some class that is expensive to copy. I.e. void accumulate(const vector & , T &total) 5. For string this function sucks and better a template specialization for string is preferred. 6 (? ) total += in[j] . Much more effective if T is not primitive type . On the other hand should ask if += is defined for the required T . 7. Not a big thing but passing in const_forward_iterators is nicer (This one I thought only afterward ) 8. I think the most important thing, after doing 1-7 the function will be exactly as the accumulate from algorithm.h ( as I said I missed few knock outs in this interview) .size not .length return T? Show More Responses Right - should be "return total;", though I'd agree with most of the comments made by the Interview Candidate. Can elements of a Vector be accessed array style...? I thought it was a Iterable Collection. In addition to what is suggested by the candidate: - If you are going to hand-write iteration, do it with const_iterators instead of an index into the vector - Prefer ++i instead of i++. The post-increment operator is defined in terms of the pre-increment operator and is less efficient since a copy of the original value needs to be made and returned Re: #6. If += is not defined, define it! operator+ should be defined in terms of operator+=. I'd just like to point out that you signed a non-disclosure when you interviewed (as everybody does), so it's pretty unethical of you to post actual interview questions here. You're explicitly asked not to post or talk about the actual questions. |

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

Write a function that computes log2() using sqrt(). 7 AnswersSolution might be: from math import sqrt def log2(x): if x <= 2: return 1 y = sqrt(x) if (y*y != x): return log2(x / 2) + 1 else: return 2*log2(y) Note that algorithm rounds roughly the logarithms of non 2-base numbers. This can be improved. Used formulas: log ab = loga + logb, eg: log32 = log16 + log2 loga^2 = 2 loga To clarify a little bit more: Let x be 2^k number. If k is odd, we can divide by 2 and add 1. The recurrence goes on with this odd/even loop. As clearly can be seen, complexity is O(logn). Improvement: The division might be changed to increase the precision with handling the remainder. This code doesnt work .. it will return 4 for log2(10), log2(12) etc .. until log2(16) : public static double log2(double num) { if(num<=2) return 1; double y = Math.sqrt(num); if(y*y == num) { return (2*log2(y)); } else { return (log2(num/2)+1); } } Specifically I think return log2(x / 2) + 1 is true for all odd and even ..I wonder if sqrt is used only because it has been asked to be used .. can you please explain your approach again ? Thanks Show More Responses Notice Log2(1+y) = y/ln(2) = 1.442695*y (when x is very small) So the solution is: when x >= 2, divide x, until 1 Use binary search: err = 1e-06 def log2(n): x, y = 0, 1 while y >1, y while rx-lx > err: mx = (lx + rx) / 2.0 my = math.sqrt(ly * ry) if abs(my-n) < err: return mx elif n < my: rx, ry = mx, my else: lx, ly = mx, my return lx ln(1+x) = x(6+x)/(6+4x) (see http://www.nezumi.demon.co.uk/consult/logx.htm) So, log2(1+x) = (x(6+x)/(6+4x))/ln(2) Using Sumer Cip's code and modifying it a bit: def log2(x): if x <= 2: z = x-1 return (1.442695*z*(6+z)/(6+4*z)) else: y = sqrt(x) return 2*log2(y) #include #include using namespace std; double log2(double x, double precision) { if(x > x) { cout << log2(x, 0.00000005) << endl; } } |

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

Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number. For example, from array 1, 1, 2, 3, 3, 1 You should get 2, 1, 1, 2, 2, 3, 1, 1 Write a program to solve this problem. 7 Answersint[] Reformat(int[] original, int length) { LinkedList list = new LinkedList(); int currentCount; for(int i=0;i function numberArray( $arr ){ $a = array(); $number = null; $c = -1; foreach( $arr as $v ){ if( $v != $number ){ if( $number ){ $a[] = $c; $a[] = $number; } $number = $v; $c = 1; } else { ++$c; } } if( $c > 0 ){ $a[] = $c; $a[] = $number; } return $a; } var_export( numberArray( array( 1,1,2,3,3,1 ) ) ); $val) { echo $val . "\t"; } echo " \n"; } ?> Show More Responses working in php: sizeof($list)-2) || ($list[$i]!=$list[$i+1])){ $result[]=$count; for($j=0;$j vector reformat(int arr[], int size) { vector res; int j, count = 0; for(int i = 0; i < size; ) { cout << i << endl; count = 0; for(j = i; j < size; j++) { if(arr[j] != arr[i]) break; count++; } res.push_back(count); res.push_back(arr[i]); i = j; } return res; } int i=0; int j=1; ArrayList array=new ArrayList(); while(i @Anonymous: Your inner while loop will cause an out-of-bounds exception to be thrown when your scanning hits the end of the array. Your while loop will try to access givenArr[i+j] even when j increments to the point that surpasses the length of the array. You need while((i+j) != givenArr.length ... ) |

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

Find Kth smallest element in a BST. 8 Answerspublic Integer kthSmallestNode(Node root, int k){ if(k list = new ArrayList(); doInOrderTraverse(this.root, k, list); if(list.size() >= k){ return list.get(k-1); } return null; } private void doInOrderTraverse(Node n, int max, ArrayList list){ if(n == null || list.size() >= max) return; doInOrderTraverse(n.left, max, list); if(list.isEmpty() || n.data != list.get(list.size() - 1)){ list.add(new Integer(n.data)); } doInOrderTraverse(n.right, max, list); } Perform in-order traversal of the BST and stop when K nodes have been visited. If you can modify the tree to include how many nodes it has under each side, you can get a O(log n) algorithm. Otherwise, I think in-order will do. Show More Responses Aren't the above algorithms O(lg (n) + k) runtime since it takes lg n time to get to the smallest element, then you build up the in order search until the size of the list is k? Two solutions along with code are demonstrated here: http://www.geeksforgeeks.org/archives/10379 1 void Traverse(Node* current, int* num) { 2 Traverse(current->left, num); 3 *num += 1; 4 if (*num == k) { 5 print current->data; 6 } 7 Traverse(current->right, num); 8 } 9 10 int n = 0; 11 Traverse(root, &n); I like Anonymous's solution. However, I think the recursive function can be made more efficient and complete as follows: void InorderWalk(Node *node, int& num, int k) { if (node != NULL) { InorderWalk(node->left, num, k); if (num right, num, k); } } DFS. int find_kth_bst(bst_node* b, int cnt, int k) { if(b == NULL || cnt >= k) return cnt; int left = find_kth_bst(b->lft, cnt, k), right = 0; if(left+1 == k) { cout val rt, left+1, k); return right; } |

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

Given a binary tree, write a function to find the length of the longest path in the tree. 8 AnswersDepth of Tree ... Use Queue if you want to do iteratively, else use recursion and get the depth. As I understood the question, It is required to get the longest path in a binary tree not a the max depth of the tree, it is required to get longest path in the tree between two nodes, which can be solved recursively by getting the max depth in the left and max depth in the right, and return the max between maxDepthLeft + maxDepthRight and previousSolution The stumbling block here is that for each node, there are *two* things that must be done and two values that must be returned - the node must first figure out what is the longest path it sees (which is simply the sum of the max depth on each side) and it must also report the max depth for it's sub-tree so that it's parent node can figure out what is the longest path *it* can see and if the longest path instead passes though *it* instead of being somewhere in it's left and right subtrees. So each invocation of the function must return a pair - the longest path in that subtree and the max depth of that subtree. In this way, the first call (for root) can get the longest path so far for the left and right subtrees and also the max depths for each side. Then, it can be decided if the longest path is through the root or is in its left subtree or in its right subtree. Show More Responses Define a BST.depth function, call it on the left and on the right subtree, then add the two depths + 2 for the (root.left, root.right) path length. Do a dfs from the root to find a vertex that is most distant from the root and call it x. Call a dfs from x to find the most distant vertex from x and return it. i think we can compute the height of the left sub tree and the height of the right sub tree, then add them together def get_height_and_max_dist(root) if root.left or root.right: left_height, left_max = get_height_and_max_dist(root->left) right_height, right_max = get_height_and_max_dist(root->right) return max( left_height, right_height), max(left_height+ right_height, left_max, right_max) else: return 1, 0 max_height, max_distance = get_height_and_max_dist(root) I don't think we can just find height of left and right subtrees and add together + 2. It's possible that there is an even longer path that exists in the left subtree itself. For example, there could be no right subtree at all and only a left subtree which branches out in both the right and left directions. The path with its center at the left subtree would be longer than left+right. |

### Software Engineer at Google was asked...

Imagine dropping a Rubik's Cube into a bucket of paint. How many of the cubes will get paint on them? 7 Answers20, 8 corners, 8 middle edges, 4 centers. the cube in the middle does not get painted. 26, or all of them. since the rubik's cube is as a 3x3 and the core is basically none existent, this is only if all the individual cubes are actually cubes. but since each individual piece is not actually a cube, but a puzzle piece that is cube like, you can technically say 1 cube gets paint on it. the whole rubik's cube 26: 8 corners, 12 middle edges, 6 centers. middle cube does not get paint. 3x3x3-1 Show More Responses OK, now what's the answer for a 4x4x4 cube? What about the general nxnxn case? total number of cubes - number of cubes in the middle = N x N x N - ( (N - 2) x (N - 2) x (N - 2) ) = N^3 - (N-2)^3 for a 4x4x4 cube: 4^3 - 2^3 = 64 total number of cubes - 8 cubes in the middle = 56 Zero. Neither the rubik's cube nor any of its components is actually a cube. Have any of you people ever disassembled a Rubik's cube? There are no cubes on the inside, just the assembly to hold and manipulate the exterior together. |

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

Given set of coins and each coin has its unique probability to be head up, say double[] probs stores the probability values for all coins, print out all different cases and accordingly probability. 8 AnswersPermutation + probability, not difficult. @interview Candidate: Very smart answer dude! very very smart... :P public static void calculatePossibility(int n) { long total = (int)Math.pow(2, n); System.out.printf("%d facing up, possiblity=%3.2f%%\n",0, (100.0*1/total)); double p = 1; for (int i=1;i<=n;i++) { p = p*(n-i+1)/i; System.out.printf("%d facing up, possiblity=%3.2f%%\n",i,100*p/total); } Show More Responses #include #include #include using namespace std; map > > dp; double total = 0.0; int cnt = 0; vector > get_prob(vector prob, int indx) { if(indx >= prob.size()) return vector >(1); else if(dp[indx].size() != 0) return dp[indx]; cnt ++; vector > nxt = get_prob(prob, indx+1); vector > cur; cout prob; for(int i = 0; i > vec = get_prob(prob, 0); long double p = 1.0, total = 0.0; for(int i = 0; i < vec.size(); i++) { p = 1.0; for(int j = 0; j < vec[i].size(); j++) { cout << vec[i][j] << " "; p *= vec[i][j] ? prob[j] : (1-prob[j]); } total += p; cout << " Prob = " << p << endl; } cout << "Total prob should be 1 : " << total << endl; } public void printLevel(TreeNode root) { if (root == null) { return; } Queue<div>q = new LinkedList<div>(); q.add(root); int enqueuedNum = 1; int lastLevelNum = 1; int visitedNum = 0; while (!q.isEmpty()) { TreeNode n = q.poll(); System.out.print(n.x + " "); visitedNum++; if (n.left != null) { q.add(n.left); enqueuedNum++; } if (n.right != null) { q.add(n.right); enqueuedNum++; } if (visitedNum == lastLevelNum) { lastLevelNum = enqueuedNum; System.out.println(); } } }</div></div> #include #include #include class CoinsProbability { const double *prob; double totalProb; unsigned long counter; vector headsUp; void init(const double probArr[], size_t n) { prob = probArr; totalProb = 0.; counter = 0; headsUp.resize(n); } void printStates() { for(vector::const_reverse_iterator i=headsUp.rbegin(); i != headsUp.rend(); ++i) cout << (*i ? "up " : "down "); } void calcProb(int currIdx, double currentProb) { if(currIdx < 0) { cout << std::setw(12) << counter++ << ": " ; totalProb += currentProb; printStates(); cout << "| Probability= " << currentProb << endl; return; } headsUp[currIdx] = true; calcProb(currIdx-1, currentProb * prob[currIdx]); headsUp[currIdx] = false; calcProb(currIdx-1, currentProb * (1. - prob[currIdx])); } public: CoinsProbability() : prob(NULL), totalProb(0.), counter(0) {} double printAllProbabilities(const double probArr[], int size) { init(probArr, size); calcProb(size-1, 1.); return totalProb; } }; int main(int argc, const char * argv[]) { srand((unsigned)time(NULL)); double probs[TEST_PROB_NUM]; for(int i=0; i forgot to copy/paste... double inline drand() { return (double)rand() / (double)(RAND_MAX); }; const unsigned TEST_PROB_NUM = 10; static double pCoins[] = { 0.5, 0.6, 0.3, 0.8 }; static double sum = 0; static void print_all(const int *coins, int numCoins, const char *pfx, double p0) { char str[64]; double pc; if (numCoins == 0) { printf(" - %s (p=%.3f)\n", pfx, p0); sum += p0; return; } pc = pCoins[coins[0]]; snprintf(str, sizeof str, "%sH", pfx); print_all(coins + 1, numCoins - 1, str, p0 * pc); snprintf(str, sizeof str, "%sT", pfx); print_all(coins + 1, numCoins - 1, str, p0 * (1 - pc)); } int main(int argc, char **argv) { int coins[] = { 0, 1, 1, 3, 2, 0 }; int numCoins = 6; print_all(coins, numCoins, "", 1.0); printf("sum=%0.3f\n", sum); return 0; } |

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

Given an array, print the largest subarray that has elements in an increasing order 9 AnswersPretty easy really Algorithm: Lets say the input array is: 1 2 3 -4 4 5 6 7 8 9 0 1. Start with the first element and keep on increasing the count and index till you hit an element that is less than the previous element. In the above case -4 < 3, hence count =3, so store it in maxCount and LastIndex = index + 1 - count So, until this point 1 2 3 is the largest subarray. 2. Again start from -4, with index = 3 and count = 0 and keep on increasing the index and count till you hit an element which is less than the previous element. Here 0 < 9, hence you stop and compare the new count with the maxCount to see which is greater. Similarly, keep on following this till you hit the end of the array. Complexity - O(n) Sid's solution is not for longest increasing subsequence problem the best answer would be O(nlgn) Show More Responses Classic NP problem. No easy solution for this. Time complexity could be very high B: really?, it has an O(n) solution. def conseq(arr): cur_start,cur_end,cur_size=0,0,1 max_start,max_end,max_size=0,0,0 n=len(arr) if n==0: return (0,0,0) for i in range(1,n): if arr[i]>arr[i-1]: cur_size+=1 cur_end=i else: cur_start=i cur_end=i cur_size=1 if cur_size> max_size: max_size=cur_size max_start=cur_start max_end=cur_end return (max_size,max_start,max_end) All the above answers are incorrect except the one that pointed out it's an instance of Longest Increasing Subsequence. The standard dynamic programming algorithm is O(n^2). There is a more complex solution that runs in O(n lg n). Google for the answers. We only need the longest contiguous subsequence, so it can be done in linear time like in Sid's solution. This is dynamic programming Very common and good question. I found this post has a pretty insightful analysis https://goo.gl/88IpQJ |

### Senior Software Engineer at Google was asked...

Create a stack of numbers where the maximum number is always known. 10 AnswersCreate a separate stack for the maximums. maintain a sorted stack, the insert would look like insert(int p,stack s){ stack large; int top = s.peek(); while(top>s){ large.push(s.pop()); top = s.peek(); } s.push(p); while(!large.empty()){ s.push(large.pop()); } } sorry, typo while(top>p) Show More Responses I was asked of this question as well. I not sure how to implment a second stack in a way that the max number is always on top. I was asked of this question as well. I not sure how to implment a second stack in a way that the max number is always on top. To Job Seeker: The basic idea is that when a new number is being pushed onto the stack, you need to see if that number is greater than or equal to the current top of the maximums-stack. If it is, you push the number onto maximums-stack as well. Also, when pop is called, you look to see if the number being popped is equal to the number on the top of the maximums-stack. If it it, pop that stack as well. just saw this, i think u can just map your number into an object, that has both the maximum number, and the last number that you've pushed in just peek the stack before you push, compare the peek'd value 'vs' your new pushed number, then replace or update the max number as you see fit? if you're only allowed to push numbers into your stack, just push your number in the stack more than once (at-least three times) indicating that every value that you put in is a sequence of 2 numbers, and so, push another one (the 3rd, which will always be your maximum number) so on every 3 pushes, you've stored the maximum value, then everytime you push something in, just peek the last 3 values in the stack, knowing that the 2nd and 3rd value was probably the number you pushed in, and the first 1 was the max value it's funny Sort the array so that the numbers are in descending order this way you know for sure the first element is the maximum number. Maintain your Stack ADT like this: class Node { T data; T max; Node next; } class Stack { Node top; push(T value) { } } Maintain your Stack ADT like this: class Node { T data; T max; Node next; } class Stack { Node top; void push(T value) { Node node = new Node(); node.value = value; if(top == null) { node.max = value; } else { node.max = value.compareTo(top.max) > 1 ? value : top.max; } node.next = top; top = node; } T pop() { if(top == null) { return null; } T val = top.val; top = top.next; return val; } T max() { return top == null ? null : top.max; } } public static void main(String[] args) { Stack stack = new Stack(); stack.push(3); stack.push(2); stack.push(5); System.out.println(stack.max()); // 5 System.out.println(stack.pop()); // 5 System.out.println(stack.max()); // 3 System.out.println(stack.pop()); // 2 System.out.println(stack.max()); // 3 System.out.println(stack.pop()); // 3 } |

**41**–

**50**of

**6,122**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