Senior software developer Interview Questions in San Jose, CA
senior software developer interview questions shared by candidates
Top Interview Questions
Senior Software Engineer at Facebook was asked...
Write some pseudo code to raise a number to a power. 11 Answerspretty trivial... int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; } Show More Responses In Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}" If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations. Because it uses dynamic programming and is lots more efficient than your algorithm. If the power is not integer, use ln and Taylor series If I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1. There is a way to do this in a logN way rather than N. 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); } This is from Programming pearls.. interesting way. 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; } # Solution for x ^ n with negative values of n as well. def square(x): return x * x def power(x, n): if x in (0, 1): return x if n == 0: return 1 if n < 0: x = 1.0 / x n = abs(n) # Even number if n % 2 == 0: return square(power(x, n/2)) # Odd number else: return x * power(x, n - 1) print ("0 ^ 0 = " + str(power(0, 0))) print ("0 ^ 1 = " + str(power(0, 1))) print ("10 ^ 0 = " + str(power(10, 0))) print ("2 ^ 2 = " + str(power(2, 2))) print ("2 ^ 3 = " + str(power(2, 3))) print ("3 ^ 3 = " + str(power(3, 3))) print ("2 ^ 8 = " + str(power(2, 8))) print ("2 ^ -1 = " + str(power(2, -1))) print ("2 ^ -2 = " + str(power(2, -2))) print ("2 ^ -8 = " + str(power(2, -8))) |
Senior Software Engineer at Google was asked...
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. 8 AnswersO(size of array) time & 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 # A Python solution (requires Python 2.5 or higher): def mult(arr, num): return reduce(lambda x,y: x*y if y!=num else x, arr) arr = [mult(arr,i) for i in arr] # O(n^2) time, O(n) space 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]. Show More Responses def without(numbers): lognums = [math.log10(n) for n in numbers] sumlogs = sum(lognums) return [math.pow(10, sumlogs-l) for l in lognums] 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< size; ++i) total *= A[i]; for(int i=0; i< 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) #include #define NUM 10 int main() { int i, j = 0; long int val = 1; long A[NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Store results in this so results do not interfere with multiplications long prod[NUM]; while(j < NUM) { for(i = 0; i < NUM; i++) { if(j != i) { val *= A[i]; } } prod[j] = val; i = 0; val = 1; j++; } for(i = 0; i < NUM; i++) printf("prod[%d]=%d\n", i, prod[i]); return 0; } void fill_array ( int* array, size ) { int i; int t1,t2; t1 = array[0]; array[0] = prod(1, size, array ); for(i = 1; i < size; i++){ t2 = array[i]; array[i] = prod(i, array.size(), array)*t1; t1 *= t2; } int prod(start, end, array){ int i; int val(1); for(i = start; i < end; i++ ) val *= array[i]; return val; } One or more comments have been removed. |
Senior Software Engineer at Google was asked...
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. 32 AnswersCreate a tree, where the leaf nodes are the initial values in the array. Given array A[1..n] create array B[1..n]= {1} // all elements =1 ; for (i=1; ij) B[i] *=A[j]; } } A=B; To husb: Your answer will work, but it's O(n^2) solution. Can you do better? Show More Responses Am I missing something? It can't be this easy: given array[0..n] int total = 0; for(int i=0; i<=n; i++) { total += array[i]; } for(int i=0; i<=n; i++) { array[i] = total-array[i]; } Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;) Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this given int array[1...n] int level_size = n/2; while(level_size != 1){//build the tree int new_array[1...level_size]; for ( int i=0; i left = array[i*2]; (and also from child to parent) new_array[i] -> right = array[i*2+1] new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product) } array= new_array; level_size /=2; } for(int i=0; iparent; if( parent->left == node){//find the other node under the parent brother = parent->right; } else{ brother = parent->left; } p *= brother; node = parent; } return p; } btw, it's O(n*logn) It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct[0] = array[0]; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array[0] = rightProduct[1]; array[n-1] = leftProduct[n-2]; for j=1; j < n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell. betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows? it looks to me can be done in order n time given the following relation: product[n] = product[n-1]*array[n-1]/array[n] for example we have array 2 3 4 5 6 product[0]=3*4*5*6 product[1]=2*4*5*6 array[0] = 2; array[1]=3 product[1]=product[0]*array[0]/array[1] 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< size; ++i) total *= A[i]; for(int i=0; i< 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) narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else.... narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot. You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array. void ArrayMult(int *A, int size) { runningProduct = 1; int *B = new int[size]; for(int i = 0; i = 0; --i) { B[i] *= runningProduct; runningProduct *= A[i]; } for(int i = 0; i < size; ++i) { A[i] = B[i]; } } Show More Responses <strong>Brutefoce Method : </strong> The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time. <strong>Other Solution : </strong> The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be : #include int main() { int n,i=0; scanf("%d",&n); int arr[n]; int brr[n]; int product = 1; for(i=0;i This solution will take O(n) time. The space complexity of this solution will be O(1). If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows." polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4. i.e. {A[0],A[1],A[2],A[3]} Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element. temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]} temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1} And then we will correspondingly multiply temp1 and temp2 and store in B. B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]} The C code to this solution will be : #include int main() { int n,i=0; scanf("%d",&n); int A[n],B[n]; int temp1[n], temp2[n]; for(i=0;i=0;i--) { temp2[i] = product; product *= A[i]; } for(i=0;i The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n). We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n) Not commentary nt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;i def solve(arr,n): product_arr=[1]*n product=1 for i in xrange(n): product_arr[i]*=product product*=arr[i] product=1 for i in xrange(n-1,-1,-1): product_arr[i]*=product product*=arr[i] return product_arr {{{ If A = {a0, a1, a2, ... an} Construct two arrays called left_p left product and right_p right product: left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1} right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1} prod_p[i] = left_p[i] * right_p[i]; }}} O(N) Solution!!! static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i < iArr.Length; i++) { total *= iArr[i]; } for (int i = 0; i < iArr.Length; i++) { iArr[i] = (int)(total * (1 / (double)iArr[i])); } } The answer I post above this uses division. Oops. Here is an answer without division static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Sorry, that last one didn't paste properly static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Show More Responses p = 1 g = 1 for x in nums: g = g* x + p p = p + x return g Way easy with a simple negative exponent var arr = [2,3,4,5] var prod = arr.reduce((a,b,arr)=>a*b) arr.map((x)=>Math.pow(x,-1)*prod) console.log(arr) //[60,40,30,24] I don't know if this is correct. But i think it is. I have done it with python def multiply(numbers,n): total = 1 for x in numbers: if x != n: total *= x return total a = [10, 3, 5, 6, 2] n = 4 prod = [] for i in a: re = multiply(a,i) prod.append(re) - create a binary tree with the values of array as leaf node - each parent is the product of its children - once the tree is formed, for each value/leaf traverse the tree to the top, each time multiplying the sibling -if tree construction time is ignored, this will take logn time for each calculation and nlogn time for all elements int[] array = new int[]{2,3,4,5}; int m = 1; int m2 = 1; int[] array1 = new int[array.length]; int[] array2 = new int[array.length]; for (int i = 0, j = array.length - 1; i < array.length; i++, j--) { m *= array[i]; array1[i] = m; m2 *= array[j]; array2[j] = m2; } for (int i = 0; i < array.length; i++) { if (i == 0) { System.out.println(array[i] + " " + m2 / array[i] + " " + array2[i + 1]); } else if (i == array.length - 1) { System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1]); } else { System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1] * array2[i + 1]); } } Of course, if allow more temp arrays it can be done in one iteration int[] array = new int[]{2, 3, 4, 6}; int m = 1; int m2 = 1; int[] array1 = new int[array.length]; int[] array2 = new int[array.length]; int[] array3 = new int[array.length]; int middle = array.length / 2; for (int i = 0, j = array.length - 1; i = middle) { if (i + 1 != array.length) { array3[i] = array1[i - 1] * array2[i + 1]; } else { array3[i] = array1[i - 1]; } if (j - 1 >= 0) { array3[j] = array1[j - 1] * array2[j + 1]; } else { array3[j] = array2[j + 1]; } } } for (int i = 0; i < array.length; i++) { System.out.println(array3[i] + "===" + m2 / array[i]); } Need help in writing Scala Program for multiplication of 2 elements of array and last element should not exceed 1000. Input Array:(1,3) Output: Array(1,3,3,9,27,243...) #include using namespace std; int main() { int y=1,a[23],i,k,s,t,b[76]; cout >s; for(i=0;i>a[i]; for(i=0;i #include using namespace std; int main() { int y=1,a[23],i,k,s,t,b[76]; cout >s; for(i=0;i>a[i]; for(i=0;i One or more comments have been removed. |
Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if $array[3,7] is 1 that means that 3 influences 7. An "influencer" is someone who influences every other person, but is not influenced by any other member. Given such an array, write a function to determine whether or not an "influencer" exists in the array. 12 AnswersThis was a tough one that forces you to consider how best to traverse the array and eliminate possibilities as soon as possible. Not_Influencers[n] = 0; //Make all elements 0 for (i = 0 ; i< n ; i++){ if(Not_Influencers[i] == 1) continue; row_sum = find_row_sum(a[i]); if(row_sum == n-1 && find_col_sum(i) == 0) return Found; for(j = i; j < i; j++) if (a[j] == 1) Not_Influencers[j] = 1; } X should be equal to Y, right? Show More Responses //if vec[i][j] == 0 then i is not an influence //if vec[i][j] == 1 then j is not an influence //so time complexity is O(n) bool find_influences(vector > &vec) { int n = vec.size(); vector not_influence(n); for (int i = 0; i = 0; --j) { if (!vec[i][j]) { break; } not_influence[j] = 1; } if (j < 0) { return true; } } not_influence[i] = 1; } return false; } Run a BFS or DFS. For each node keep going to influencer. Find a node which can be reach by all nodes. Sort of finding sink node. public static int influencer(final int[][] jobs, final int r, final int c) { int[] degree_in = new int[jobs.length]; int[] degree_out = new int[jobs.length]; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if(jobs[i][j] == 1) { // i influences j degree_out[i]++; degree_in[j]++; } } } for (int i = 0; i < r; ++i) { if (degree_out[i] == r - 1 && degree_in[i] == 0) { return i; } } return -1; } Consider the input as Graph given in adjaceny matrix representation. Find whether a semi-eulerian path is present in the graph or not. Take the XOR product of the original matrix with the transposed matrix and sum by row. If any row counts equal the rank then they are influencers. private static boolean hasInfluencer(int[][] matrix) { if (matrix == null) return false; if (matrix.length == 0) return false; boolean result = false; for (int i=0; i the XOR suggestion I think is incomplete. The condition sum(row_influencer) = 1 and sum(column_influencer) = N so a simple matrix multiplication with the transposed should give for the vector v[influencer] = N and v[N-influencer] = 1. I assume influencer influences himself. def find_influencer(matrix): for row in range(len(matrix)): following_none = not any(matrix[row]) if not following_none: continue all_following = True for r_no in range(len(matrix)): if not row == r_no: continue if not matrix[r_no][row]: all_following = False break if all_following: return row return -1 Here is a different view. Please comment if you find any issues with the logic. 1st. condition: An influencer can not be influenced by any one. Let's say the in a matrix of [x.y], there is an influencer with index 2. So, the column=2 (3rd column) in the matrix must be all 0s, since the influencer can not be influenced. Step 1: Find a column with all 0s. If found, remember the column index or there is no influencer. Let's say, it is m Second condition: An influencer must have influenced everyone. So, in our example: row=2 (third row) must be all 1s except for column=2, since influencer can not even influence self. Step 2: Check row=m and find that all values are 1 except for [m][m]. If found, we have an influencer. |
Senior Software Engineer at Google was asked...
Write a probability formula to tell how many bits will be changed when 1 is added to a 32 bit binary number. 11 AnswersThe probability of N bits being changed is (1/2)^N. The reason: the number of bits that will change depends on the position of the first zero that appears in the number. If the first zero is at the LSB, only one bit changes; if it is in the third position, the three bits upto the first zero change. Now, it boils down to the probability of finding the first zero. Assuming that the zeros and ones appear with equal probability in a given number, the probability of finding the first 0 in the Nth position is (1/2)^N. For more, look up the Geometric Random Variable. I think that you need to take into account that if you want to toggle 2 bits, you can only do if you flip bits from position 0..30. Toggling bit 31 is only going to toggle this bit no matter what. Therefore, you need to multiply (33-N)/32 to your proposed result, to keep this into account. @Mythreya's analysis is correct but incomplete. To get the expected value, you have to multiply the number of bits by their probability. Answer is Sigma{k/(2^k)} for k = 1 to 32. Show More Responses Using this approach, the answer is 2 bits will change on an average: https://answers.yahoo.com/question/index?qid=20110413165236AAU9tmO @Henry David Thoreau: The question is not asking for expected value, just the discrete density function. Also P(k=32) needs special handling. @Henry, no ... probability that at least 1 bit will change is (k/2^k); but, probability for all k bits to change, I guess, would still be 1/2^k. Right? And, k=0 to 31 !! k=1-32 p=k/2^(k-1) E(n) = 1 + E(n-1) / 2 where E(n) is the expected number of bit changes when 1 is added to an n-bit integer. E(1) = 1. E(2) = 1 + E(1) / 2 = 1.5. E(3) = 1 + E(2) / 2 = 1.75 We can verify it for n = 3. The possible values are as follows 000 -> 1 change 001 -> 2 change 010 -> 1 change 011-> 3 change 100-> 1 change 101-> 2 change 110-> 1 change 111-> 3 change Total changes: 14 Expected change = 14 / 8 = 1.75; answer is (2^1+2^2+2^3....2^32)/(32*(2^32)) If we just look at two bits - (b1,b2) f(b1) = { 1 b1=0; f(b2) if b1=1}, the probability of one bit changing is half. The probability of two bits changing is half * f(b2), which is half*half if b2=0 and half*half*f(b3) if b2=1. Therefore, for k=1-31 p(k) = 1/2^k and for p(k=32) = 1/2^k because when the 32nd bit flips there is nothing more to be done and the recursion stops |
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 } |
Senior Software Engineer at Apple was asked...
In a stream of integers from 1 to n, only one number will be repeated. How can you tell what that number is? 11 AnswersThis felt like a brain teaser question to me, and since I hadn't heard it before it took me a little while to come up with a solution that involved using a factorial function. You know n. S = n*(n+1)/2 is the sum of 1st n numbers. P = sum of the n+1 numbers you are provided with. Finding P given an array of n+1 integers can be done in O(n). P - S is the repeated integer. Heres an explanation, http://www.techinterview.org/post/526329049/sum-it-up Show More Responses int sum = 0; int xorSum = 0; for(int i =0 ; i < n; i++) { sum += input[i]; xorSum ^= input[i] } return (sum - xorSum)/2; Mat, try 1,2,2,3: 1+2+2+3= 8 1^2^2^3= 2 (8-2)/2=3?2 A hash table would resolve the question with O(n) Add to HashSet. It will return true if it exists. If you're writing it in ruby def find_repeat(numbers) numbers.length.times{|n| return numbers[n] if numbers[n] != n } end lmao, ok everyone getting a little craycray, why not just simply this.... int prev << stream; while (stream) { int curr << stream; if curr == prev return else prev = curr; } (sum_of_numbers - (n*(n-1)/2)) Add each integer to the map if it doesn’t already exist as key if it’s exists then it is a repeated number. |
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. |
Senior Software Engineer at Google was asked...
Implement a base 3 adder which takes two strings as input and returns a string 6 Answers// sum : null terminated pre-allocated large enough string char *addBase3(const char *a, const char *b, char *sum) { char oldsum[20] = ""; // stacking characters would be much better than this const int alen = strlen(a); const int blen = strlen(b); int retainer = 0; int apos, aval; int bpos, bval; int partsum; int pos; for(pos = 1; pos = 3) { retainer = 1; partsum = 3 - partsum; } else { retainer = 0; } strcpy(oldsum, sum); sprintf(sum, "%d%s", partsum, oldsum); } if (retainer) { strcpy(oldsum, sum); sprintf(sum, "%d%s", retainer, oldsum); } return sum; } if allowed, converting base 3 to base 2, then adding and converting back is better // sum : null terminated pre-allocated large enough string char *addBase3(const char *a, const char *b, char *sum) { char oldsum[20] = ""; // stacking characters would be much better than this const int alen = strlen(a); const int blen = strlen(b); int retainer = 0; int apos, aval; int bpos, bval; int partsum; int pos; for(pos = 1; pos = 3) { retainer = 1; partsum = 3 - partsum; } else { retainer = 0; } strcpy(oldsum, sum); sprintf(sum, "%d%s", partsum, oldsum); } if (retainer) { strcpy(oldsum, sum); sprintf(sum, "%d%s", retainer, oldsum); } return sum; } Show More Responses public class Test1 { public static void main(String[] args) { System.out.println(new Test1().add("21", "22")); //prints 120 } int toInt(String str) throws NumberFormatException { int result = 0; for (int index = 0; index 2) { throw new NumberFormatException(); } result = result * 3 + i; } return result; } String toStr(int i) throws NumberFormatException { StringBuffer sb = new StringBuffer(); while (i > 0) { sb.insert(0, i % 3); i /= 3; } return sb.length() == 0 ? "0" : sb.toString(); } String add(String str1, String str2) throws NumberFormatException { return toStr(toInt(str1) + toInt(str2)); } } base3DigitAdd(char lhs, char rhs, char &extra, char &carry,char &sum) { int s = (lhs - '0') + (rhs - '0') + (extra - '0'); carry = (s/3) + '0'; sum = (s%3) + '0'; } base3Add(const string &lhs, const string &rhs, string &result) { string::const_iterator il = lhs.end(); string::const_iterator ir = rhs.end(); result.clear(); char carry = '0'; char digit = '0'; while((il != lhs.begin()) || (ir != rhs.begin()) { char l = (il != lhs.begin) ? (*(il - 1)) : '0'; char r = (ir != rhs.begin) ? (*(ir - 1)) : '0'; base3DigitAdd(l, r, carry, carry, digit); result.push_front(digit); if (il != lhs.begin()) { --il; } if (ir != rhs.begin()) { --ir; } } if (carry != '0') { result.push_front(carry); } } string base3Add(const string & in1, const string & in2) { int i1 = atoi(in1.c_str()); int i2 = atoi(in2.c_str()); int carry = 0; char buff[2]; string result; while(i1 != 0 || i2 != 0 || carry != 0) { int i1p = i1 % 10; int i2p = i2 % 10; int total = i1p + i2p + carry; itoa(total % 3, buff, 10); result.push_back(buff[0]); carry = total / 3; i1 /= 10; i2 /= 10; } reverse(result.begin(), result.end()); return result; } |
Search a sorted array for the first element larger than k 7 AnswersUse binary search algorithm since array is sorted. #!/usr/bin/env python """Search a sorted array for the first element larger than k. """ def srch(list1, srchItem): """Perform Binary search and find the first element that is larger than the arg srchItem @list1: The sorted list @srchItem: The element to be searched for finding next greater value than that """ len1 = len(list1) startIdx = 0 stopIdx = len1 - 1 stop = False # saveIdx the index of the lowest value in the sorted list saveIdx = -1 while not stop and startIdx >= 0 and stopIdx srchItem: # found greater item, but the previous one also could be greater stopIdx = midIdx - 1 saveIdx = midIdx elif list1[midIdx] srchItem: saveIdx = startIdx break elif startIdx >= len1 or stopIdx < 0: break if saveIdx == -1: return -1 # not found return list1[saveIdx] def testAll(): testList = [3, 6, 9, 34, 67] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) # test for result to be the 1ast item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 68) print 'Result: %d' %srch(testList, 68) # test for result to be the ist item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 1) print 'Result: %d' %srch(testList, 1) # item not in the iist testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 70) print 'Result: %d' %srch(testList, 70) if __name__ == '__main__': testAll() //Run time complexity is logn public class FirstGreatestNumberThanK { public int prepareFirstGrtst(int[] a, int k) { return firstGrtst(a, 0, a.length - 1, k); } public int firstGrtst(int[] a, int start, int end, int k) { if (end == start + 1) { if (a[start] > k) return a[start]; else return a[end]; } else { int mid = (start + end) / 2; if (k == a[mid]) return a[mid + 1]; if (k > a[mid]) { start = mid; return firstGrtst(a, start, end, k); } else { end = mid; return firstGrtst(a, start, end, k); } } } public static void main( String[] args){ FirstGreatestNumberThanK f = new FirstGreatestNumberThanK(); // int[] a = {2,4,6,8,9,12,14,16}; // even length int[] a = {2,4,6,8,9,12,14}; // odd length // System.out.println(f.prepareFirstGrtst(a, 11)); // System.out.println(f.prepareFirstGrtst(a, 3)); // System.out.println(f.prepareFirstGrtst(a, 7)); // System.out.println(f.prepareFirstGrtst(a, 15)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 14)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 4)); System.out.println(f.prepareFirstGrtst(a, 12)); System.out.println(f.prepareFirstGrtst(a, 2)); } } Show More Responses def find_greater(aList, item): high = len(aList) low = 0 while low < high: mid = (high + low) // 2 if item < aList[mid]: high = mid else: low = mid + 1 return aList[low] arr = [1,5,6,8,10,56] n=int(raw_input("Enter a number:")) if n in arr and arr.index(n) != len(arr)-1: print arr[arr.index(n)+1] else: print "Element not present in the list or index out or range" public int firstLargerNum(int[] sortedArr, int k){ if(sortedArr == null || sortedArr.length < 1){ throw new IllegalArgumentException("Wrong set"); } int low = 0; int high = sortedArr.length; int searchedNum = 0; while(low One or more comments have been removed. |
See Interview Questions for Similar Jobs
- Software Engineer
- Software Developer
- Software Development Engineer
- Staff Software Engineer
- Director
- Principal Software Engineer
- Senior Software Developer
- Product Manager
- Software Engineer III
- Senior Software Development Engineer
- Software Engineer II
- Data Scientist
- Intern
- Project Manager
- Vice President
- Manager
- Software Development Engineer II
- Engineering Manager
- Engineer
- Java Developer