Senior software developer Interview Questions in United States | Glassdoor.co.in

# Senior software developer Interview Questions in United States

11,720

senior software developer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

13 Jul 2009

### Senior Software Engineer at Goldman Sachs was asked...

14 Apr 2018

1 Aug 2013
 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; ithe 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 -1Here 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.

2 Jan 2014
 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 responsesUsing 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

18 Jul 2010
 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 responsesIn 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 seriesIf 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)))

13 Jul 2009
 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 responsesI 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 funnySort 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...

21 Apr 2011
 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-upShow more responsesint 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?2A 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 } endlmao, 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.

1 Mar 2012