Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

786

interview questions shared by candidates

## Algorithm Interview Questions

Sort: Relevance Popular Date

Aug 1, 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 Answers This 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.

Aug 29, 2009

### Software Development Engineer Intern at Amazon was asked...

May 15, 2009
 Given an array of integers, all but one of which appears an even number of times, find the one integer which appears an odd number of times. Upon completion, asked to improve the algorithm in terms of both time and space, eventually asked to do it in O(n) time and constant space. 4 Answers xor the entire array, all the integers which appear an even number of times will cancel eachother out int[] theArray = new int[]{1, 1, 2, 2, 3, 3, 3, 4, 4, 10, 10, 10, 10, 10, 11, 11, 12, 12}; Map theMap = new HashMap(); for (int i = 0; i mapKeys = theMap.keySet(); for(int keyInt : mapKeys) { if(theMap.get(keyInt) % 2 != 0) { System.out.println(keyInt + " occurs odd number of times"); } } } I was also asked this in 2010,march. Show More Responses XOR

### Software Development Engineer I at Microsoft was asked...

Jan 3, 2013
 Given a string of format '2+3*2-1', calculate and return the result. No parenthesis in the input, just integers and + - * / operators. Operator precedence has to be considered. Linear time complexity and minimal data structure use is preferred. 4 Answers I did 2 pass on input string. I also did two passes on the input string. I created the following helper classes: Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator). InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1". Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it. One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle. I used a different approach by making use of a queue: - parse the string, and push in the operands and operators onto a queue - evaluate the queue My general approach was this: - read in lhs, operator and rhs - if operator is "+" or "-", enqueue lhs and operator > if string is empty, we are done parsing --> enqueue rhs > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further - else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate. (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug) // Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression. string getCurr(string& str); int eval(string str) { if (str.empty()) return -1; // operand / operator queue std::queue q; // construct it char buf[5]; while (!str.empty()) { string lhs = getCurr(str), oper = getCurr(str), rhs = getCurr(str); // evaluate directly if (oper == "*") { int res = atoi(lhs.c_str()) * atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } // evaluate directly else if (oper == "/") { int res = atoi(lhs.c_str()) / atoi(rhs.c_str()); // restore the string str = itoa(res, buf, 10) + str; } else // "+" or "-" { q.push(lhs); q.push(oper); // finished parsing the expression if (str.empty()) q.push(rhs); else // restore the string str = rhs + str; } } // evaluate the queue int res, rhs; string oper; res = atoi(q.front().c_str()); q.pop(); while (!q.empty()) { oper = q.front(); q.pop(); rhs = atoi(q.front().c_str()); q.pop(); if (oper == "+") res += rhs; else // "-" res -= rhs; } return res; } string getCurr(string& str) { if (str.empty()) return ""; string curr(""); // operator if (str[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/') { curr += str[0]; str = str.substr(1); } else // a number { do { curr += str[0]; str = str.substr(1); } while (!str.empty() && str[0] >= '0' && str[0] <= '9'); } return curr; } Show More Responses Use 2 stacks. one for operands and one for operators. Keep pushing in operator as long as the newly pushed opertor has higher precedence than the "top of stack " operator. if not, pop out 2 operands and calculate result and again push it on stack

Sep 2, 2012
 Write a function that finds the square root of a decimal number. 4 Answers A binary search with a constraint for precision. We should also take care of the interval (0.00, 1.00). // iterative (function(n){ var lo=0; var hi=n; var tries=500; var prev; while(tries--){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr){ break; } prd>n ? hi=curr : lo=curr; prev=curr; } console.log(curr, curr*curr, 500-tries) })(64) // recursive with closure use (function(n){ var lo=0; var hi=n; var tries=500; var prev; function rec(){ var curr=hi-((hi-lo)/2); var prd=curr*curr; if(prd===n || prev==curr || !tries--){ return curr; } prd>n ? hi=curr : lo=curr; prev=curr; return rec() } var result = rec(); console.log(result, result*result, 500-tries) })(25) Show More Responses For the above, I would set my high to be the max(x, 1), Let say's one call any of your functions with 1/4, or with any 0 epsilon) && (epsilon 100) return; return guess; })

Feb 23, 2010
 How would you write a sort routine to ensure that identical elements in the input are maximally spread in the output? 4 Answers This is my opinion: First of all, understand what "maximally spread out" means - if we have an array of 4 identical elements, there are 4! = 24 permutations we can arrange the elements by. If we measure for each element the distance of its new position minus its old one (i.e. the number of "hops" the element made), and sum these measurements we get an idea of how well the permutation "mixed up" the array. However, there is more than one such maximal permutation, and so we need to choose the "maximally spread out" one. I think this is the one where the minimal amount of "hops" for any element is maximal, in the 4 elements array case - each element does 2 hops, i.e. [a b c d] turns into [c d a b]. In order to achieve this we can use a *stable* MergeSort, and when performing the last merge (e.g. between [a b] and [c d]), we simply choose to perform this specific merge with preference for items from the right array and not the left one. (all through the recursions levels of the operation we stayed stable, meaning we preferred to initially place elements from the left array, this time we do the opposite). We can accomplish this by giving an extra boolean parameter for the recursion, the top level gets it as 'true' and invokes all other levels with it being 'false'. ... This is just my opinion :) I am confused for more than one reason. First, "sort" usually means "arranged in ascending or descending order". In sorted output the identical elements are right next to each other, not "maximally spread out"! Or do I miss something? If your "sort" means "any arrangement that follows certain rules", then you should mention what these rules, besides identical elements in the input being maximally spread out. Is there some ordering of non-identical elements? probably dynamic programming question, o(n^2) for each item in input_array for i=0 to i=output_array.length if (item == output_array[i]) { swap_in_output_array(i, i-count) count++ } output_array.append(item) Show More Responses refer here http://stackoverflow.com/questions/17899312/disperse-duplicates-in-an-array

Feb 10, 2013

### Software Engineer at Yahoo was asked...

Nov 26, 2013
 fair, lot of position related tech questions. Given a string "Keyword" find whether the characters exist in a String "Target" in the same order but not necessarily next to each other Keyword cat aaa Target cbate abcde Output YES NO 4 Answers Both Longest Common Subsequence and Linear solution will work. int index = 0; for (int i = 0; i < target.length(); i++) { if target[i] = keyword[index]; index++; if (index == keyword) return true; } return false; ...how do you think to use iterative method....blah..recursive: - (BOOL)findString:(NSString *)keyword inMixedString:(NSString *)target { if(!keyword || !target) return NO; if([keyword length] == 0) return YES; if([target length] == 0) return NO; NSString *kLecter = [keyword substringWithRange:NSMakeRange(0, 1)]; NSString *tLecter = [target substringWithRange:NSMakeRange(0,1)]; if([kLecter isEqualToString:tLecter]) keyword = [keyword substringFromIndex:1]; return [self findString:keyword inMixedString:[target substringFromIndex:1]]; return NO; } Show More Responses obviously without return NO at the end

Jan 13, 2012