Software Engineering Interview Questions in San Jose, CA | Glassdoor

# Software Engineering Interview Questions in San Jose, CA

6,122

Software engineering interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Oct 14, 2011

Jul 29, 2010
 what's wrong with the following code :

Apr 1, 2011
 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 ? ThanksShow More ResponsesNotice Log2(1+y) = y/ln(2) = 1.442695*y (when x is very small) So the solution is: when x >= 2, divide x, until 1Use 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 lxln(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; } }

Sep 21, 2011
 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;ifunction 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 Responsesworking in php: sizeof(\$list)-2) || (\$list[\$i]!=\$list[\$i+1])){ \$result[]=\$count; for(\$j=0;\$jvector 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 ... )

Jul 17, 2011
 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 ResponsesAren'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/103791 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; }

Dec 10, 2010
 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 previousSolutionThe 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 ResponsesDefine 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 togetherdef 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.

Jul 8, 2010
 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 cube26: 8 corners, 12 middle edges, 6 centers. middle cube does not get paint. 3x3x3-1Show More ResponsesOK, 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 = 56Zero. 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.

Dec 30, 2011
 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... :Ppublic 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