Senior software developer Interview Questions in San Jose, CA

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; }

//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.

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

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 }

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.

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.

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; }