# Software Engineering Interview Questions in San Jose, CA

Software engineering interview questions shared by candidates

## Top Interview Questions

### Software Engineer at Facebook was asked...

Given an array of integers, now we want to erase all 0's (can be other value), and we want the result array condensed, meaning no empty cell in the array. 16 Answers#include #include void main() { clrscr(); int i,j,k.a[20]; cout>n; cout>a[i]; } cout<<"entered array is"; for(i=0;i Assuming that the array is named iArray and the unwanted number is named delthis. I think this should work: public condense(int[] iArray, int delthis){ ArrayList iList = new ArrayList(); for (int i=0; i Test on Java 6: public Integer[] condense(int[] iArray, Integer delThis){ ArrayList iList = new ArrayList(); for (int i=0; i Show More Responses void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1+1; } test on gcc void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; arr[p2] = 0; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1; } #include using namespace std; int main() { int a[] = { 0,2,3,0,4,0,5,0,0,0}; int i,nz = 0; for(i = 0; i<=9 ; i++) { if (a[i] == 0) nz++; else a[i-nz] = a[i]; } for(i = 0; i <=9-nz ; i++) cout << a[i]<<" "; return 0; } Python: ------------- s = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] for k in xrange(len(s), 0, -1): if not s[k-1]: s.pop(k-1) -------------- after: [1, 2, 4, 5, 1, 1, 7, 8, 2, 4, 5, 1, 2, 8, 5, 6, 8] void erase(int arr[], int sz, int errasedVal) { int i = 0, j = -1; while(i < sz && j < sz) { if(arr[i] == errasedVal && j == -1) j = i; else if(arr[i] != errasedVal && j != -1) { cout << arr[i]<< " " << j << endl; swap(arr[i], arr[j]); j++; while(arr[j] != errasedVal && j < sz) j++; } i++; } } void RemoveZeros(vector& input) { int p1 = 0, p2 = 0; int len = input.size(); while (p1 < len && p2 < len) { while(input[p1] == 0) { ++p1; } input[p2++] = input[p1++]; } input.resize(p2); for (int i = 0; i < p2; ++i) { cout << input[i] << endl; } } @Bikash is my favorite answer because it uses constant space, unlike some of the above answers. Objective-C NSArray *input = @[@2, @3, @1, @2, @0, @2, @0, @1, @3, @1, @2, @0]; input = [input objectsAtIndexes:[input indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) { return ![obj isEqualToNumber:@0]; }]]; ----------------------- output:(2, 3, 1, 2, 2, 1, 3, 1, 2) def eraseDigit(aList, aDigit): theResult = [int(''.join([x for x in str(X) if x != str(aDigit)])) for X in aList] return theResult theList = [432, 4409, 85, 6887, 87, 1386] theDigit = 8 print eraseDigit(theList, theDigit) import java.util.Arrays; public class facebook1 { public static void main(String[] args) { int [] givenArray = new int[] {3,4,45,5,0,3,0,32,4,5,40,23,0,43,0,0,43,2,4}; int rightPointer = givenArray.length -1; for(int leftPointer = 0; leftPointer 0; i--){ if(givenArray[i] == 0){ int [] tempArray = new int[givenArray.length-1]; System.arraycopy(givenArray, 0, tempArray, 0, givenArray.length-1); givenArray = tempArray; } } System.out.println(Arrays.toString(givenArray)); } } Show More Responses Here is a short python solution: a = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] a = [x for x in a if x != 0] Completely trivial in C#. The only thing to note about the solution is that it does not do the replacement "in place" and returns a new array. But that was not specified as a constraint in the question. int[] RemoveZeros(IEnumerable input) { return input.Where(x => x != 0).ToArray(); } // This is erase/remove idiom one liner. Too much code with C. std::vector v; v.erase(std::remove(v.begin(), v.end(), 0), v.end()); |

### Software Engineer at Google was asked...

Write a function to get maximum consecutive sum of integers from an array. 12 AnswersSour code: int LargestSubSum(int[] arr) { int maxSum = 0;//this is value to return int tempSum = 0;//this is to keep track of current sum. check Q16 for more details for(int i=0; i0)//still can be part of the final largest sum's part { tempSum += arr[i]; if(tempSum>maxSum) maxSum = tempSum; } else//this can be discarded as the possiblity being part for largest sum tempSum = 0;//reset } return maxSum;//do not forget to return } I also made a video to demo the whole process to solve this problem including a test case at http://youtu.be/Q7Rf79mLs7M public static int recursiveMaxSum(int set [], int index){ if(index==set.length) return 0; if(set[index] < 0) return rMaxSum(set, ++index); return set[index] + rMaxSum(set, ++index); } Penguin: Try this case {5,-1,2,-2} the max sum is 5-1+2=6. I am not sure why my reply (2nd reply) was tagged as not helpful, but that's the working code including a testing case. Show More Responses In Java public static int findMaxConsecutive(int[] arr){ int max =0; int temp = 0; for(int i=0; i function maxarr($arr, $len) { $maxsofar = 0; $maxendinghere = 0; foreach ($arr as $entry) { $maxendinghere = max(0, $maxendinghere + $entry); $maxsofar = max($maxendinghere, $maxsosfar); } } There is an easy recursive solution for this that runs in O(nlgn). Split the array in two, then the MCS (maximum consecutive sum) is the maximum of: MCS(first half), MCS(second half), or sum of consecutive numbers passing the middle point or SUM(maximum of numbers up to the end of first half, maximum of numbers from start of the second half) not sure that all these propositions are working in real cases : let's consider this array : t = [ -1,-2,10,11,-2,-1 ] none of your solutions seem to consider a sub sum that can be bounded inside the array. I feel like a solution with two iterators should fit. a function sum(int beg, int end, int* array) returning the sum between the indexes. and something like : int highestConsecutive(int* array){ int beg=0, end=len(array); int biggest_sum=-MAXINT; for(end=len(array);end>0;--end){ for(beg=0; beg < end; ++beg){ int s_btw=sum(beg,end); biggest_sum=s_btw; } } return biggest_sum; } should return the highest consecutive sum.... I've not tested it since I've juste been writing it here, but I think that it's on the way to a correct solution, and it seems to have something like an n*log(n) complexity. such a solution even allows you to return the indexes of the sum found... this have to be checked and optimized but still... oups ^^ there a lack in this code it seems :) , lack of the if(s_btw > biggest_sum) :) appologize for this ;) Contrary to all the solutions posted the correct solution runs in O(n) and Lilica posted the Python solution with a link to the Wikipedia source. There's also a easy C solution that any Java or .Net developer should be able to understand. Check the answer at https://goo.gl/BbWEO1 http://en.wikipedia.org/wiki/Maximum_subarray_problem def max_subarray(A): max_ending_here = max_so_far = 0 for x in A: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far Source:http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm |

Implement division without using multiplication or division. It should work most efficient and fast. 11 Answersexp(ln(a)-ln(b))=a/b What if one or both of a,b is less than zero. ln(x) for x < 0 is not defined. public class Solution { public static void main(String[] args){ int top=32; int bottom=4; int count=0; boolean negative=(top*bottom)=bottom){ top=top-bottom; count++; } System.out.print((negative)?"-":""+String.valueOf(count)+"..."+top); } } Show More Responses Obviously the interviewer would not allow us to use Math functions like exp, log etc. We are supposed to use the Long division method or the Newton Raphson method to find the quotient. Newton Raphson is the fastest but uses operator * (multiplication) though. http://stackoverflow.com/a/5284915 Python version that gives you an idea how it works: i = 0 while divisor = 0: if dividend >= divisor: dividend -= divisor result |= 1 >= 1 i-=1 plus some code to check for 0 and support negative values #Write a program to do division without division or multiplication 2 3 def division(dividend, divisor_initial): 4 divisor_final = divisor_initial 5 quotient = 1 6 while dividend - divisor_final > divisor_initial: 7 quotient += 1 8 divisor_final = divisor_final + divisor_initial 9 number = divisor_final - divisor_initial 10 remainder = dividend - divisor_final 11 return quotient,remainder 12 13 14 def main(): 15 print division( 101, 3) 16 17 18 if __name__ == "__main__": 19 main() can anyone post solution in java? // correcting previous answer int Divide(int divisor, int dividend) { int divisionCount; int tmp = dividend; if (tmp - divisor > 0) { tmp = tmp - divisor; divisionCount++; } // This will apply the correct sign to the quotient if ((divisor & 0x80000000) ^ (dividend & 0x80000000) != 0) { divisionCount = divisionCount | 80000000; } return divisionCount; } This solution rounds down to the nearest signed integer // Implement division without using multiplication or division. It should work most efficient and fast. int Divide(int divisor, int dividend) { int divisionCount; int tmp = dividend; if (tmp - divisor > 0) { tmp = tmp - divisor; divisionCount++; } // This will apply the correct sign to the quotient if ((divisor & 8) ^ (dividend & 8) != 0) { divisionCount = divisionCount | 8; } return divisionCount; } we can use bit shift operator. e.g. 4 is 100 in binary we want to divide 4 by 2 so right shift 4 by 1 bit 4>>1, so we get 010 which is 2. |

### Software Engineer at Facebook was asked...

Find the minimum depth of binary search tree 10 Answersisn't this? int mindepth(node* root) { if(root==NULL) return 0; return 1 + min(mindepth(root->left),mindepth(root->right)); } You wouldn't get an on-site interview with this answer. Your code is not optimal, although it looks short. Here is the trick: you don't have to traverse entire tree to find out the minimum. think about this example. L side of the root node has only one item, so the deep is 1, R side of the root has one million items. Why do you have to traverse through all one million nodes, if you can get the min from the L side right away? It can be solved using the previous recursive code and also can be solved using Breadth First Traversal, by starting the traversal from the root of the tree, and when reach a leaf then this is the min depth return the number of steps from the root to this leaf Show More Responses public int minDepth(Node root) { Map depthMap = new HashMap(); depthMap.put(root, 0); List toVisit = new ArrayList(); toVisit.add(root); while(!toVisit.isEmpty()) { Node curr = toVisit.remove(0); if(curr.getLeft() == null && curr.getRight() == null) { // first leaf node is the minimum depth return depthMap.get(curr); } else { if(curr.getLeft() != null) { depthMap.put(curr.getLeft, depthMap.get(curr) + 1); toVisit.add(curr.getLeft()); } if(curr.getRight() != null) { depthMap.put(curr.getRight(), depthMap.get(curr) + 1); toVisit.add(curr.getRigth()); } } } return -1; // not good } use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast! use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast! Someone said you need to pass 3 questions to be qualified to on-site... void mindepth(node* cur, int curdepth, int& best) { if(curdepth >= best) return; if(cur == null) { best = curdepth; return; } mindepth(cur->left, curdepth + 1, best); mindepth(cur->right, curdepth +1, best); } best = inf; mindepth(root, 0, best); public class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<div>q = new LinkedList<div>(); q.add(root); int enqueuedNum = 1; int visitedNum = 0; int lastLevelNum = 1; // initialized to be 1, whichever child tree node is null, then finish // the operation and return the current minDepth int minDepth = 1; while (true) { TreeNode n = q.poll(); visitedNum++; if (n.left != null) { q.add(n.left); enqueuedNum++; } if (n.right != null) { q.add(n.right); enqueuedNum++; } if (n.left == null || n.right == null) { return minDepth; } if (lastLevelNum == visitedNum) { lastLevelNum = enqueuedNum; minDepth++; } } } }</div></div> Use BFS to iterate the tree, keep track of the "level" you're currently at. When a childless node shows up, return the level number. Code: public static int MinDepth(Node root) { if (root==null) { return 0; } Queue queue = new LinkedList(); queue.add(root); queue.add(new Sentinel()); int depth = 1; while(!queue.isEmpty()){ Node current = queue.poll(); if (!(current instanceof Sentinel)) { if (current.left==null && current.right==null) { break; } else { if (current.left!=null) queue.add(current.left); if (current.right!=null) queue.add(current.right); } } else { depth++; if (!queue.isEmpty()) { queue.add(new Sentinel()); } } } return depth; } |

### Software Engineer at Google was asked...

Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array? 18 AnswersThe catch is to realize that if there is a cycle, it will result in an infinite loop What as the time and space complexity of the best solution? Can you do it in O(n) time and O(1) space? One possible solution is to keep a list for all visited positions. If we hit a position that is already in the list, we've detected a cycle. For this solution, time complexity is O(n) and space complexity is O(n). How to do this in O(n) time and O(1) space? Show More Responses use the contents of a position as an index into array and while traversing the contents, negate the contents after you visit it. if at any time you find the contents of a position as negative (given that every element points to the next element in array, you cannot have -ve numbers in array) this will run in o(n) with constant space e.g. array = [1,2,3,4,5,2] (zero based index) a[0]=1 go to a[1] and negate a[0] to -1 a[1]=2 go to a[2] and negate a[1] to -2 like this when you hit a[5] =2 and then you see a[2] = -3, which is already visited so there is a loop/cycle The problem is imprecisely stated. If every element a[i] contains a value that is an index into a (i.e. a value in the range 0..length(a)), then there *must* be at least 1 cycle, assuming a is of finite size. On the other hand, if a is allowed to contain values that are not valid indexes (negative, or >= length(a)), then it indeed takes some work to determine if a has cycles. So let's assume the latter. If a is allowed to contain negative values to start with, then the negate-as-you-see-it solution doesn't work. To determine if there is a cycle starting at any given element (isCycle(elemindex)) in O(1) space and O(n) time, you could walk 2 pointers starting at elemindex. One would go at normal speed (nextelem = a[thiselem]) and one would go at double speed (nextelem=a[a[thiselem]]). If the 2 pointers meet, isCycle() returns true. However, since you'd have to run isCycle(index) on every index to ask if there is a cycle *anywhere* in the array, this algorithm is O(n**2) in time. I'd have to ponder if there's an O(1) space / O(n) time algorithm for this... if the array is not "full," then it must contain sentinel values which represent NULL references. You could use Integer.MIN (in Java parlance) or just -a.length. this fixes the above criticism of the negate-as-you-see-it approach. What it doesn't fix is the fact that that the "graph" can be disconnected. for instance [1,2,NULL,4,5,1] a[0]->a[1]->a[2]->NULL a[3]->a[4]->a[5]->a[1]->a[2]->NULL in this case there are multiple references to element a[1], but it's not a cycle. I think you're stuck with the N^2 solution. Define two pointers One pointer move one step each time, The other pointer move two steps each time. If the pointers ever meet together (besides the start point) before one of the pointer reaches the end, then there is a loop. Otherwise, there isn't. This takes O(n) time and O(1) space. if there is a loop then that means that is a number repeated in the array. put the number in the array into a hashmap and compare the size of the hashmap to the size of the array. if less than there is a loop If you interpret the question strictly, then the answer is TRUE -- it always has a loop. Unless an element can point to nothing (with a negative index for instance) signaling that the iterator must terminate. Can some one explain the question ? If you have an array of integers then the ONLY interpretation of " ...each element points to the index of the next element" is the following array : a = [1,2,3,4,5,6,7 ...] . If that is the case - then what does it even mean to "have a cycle" ? Sort it and see if we have duplicates works too. Is that the full version of the question? The one I heard before said that we just have a limited memory resource. But because my version and the one mentioned above don't prohibit us to modify the given data, so I think we just need one variable and one pointer for this question. We assign the value of the first element in the array provided to our variable and pointer. Then we jump to the next element in the array and check if the value of that element is equal to the one in our variable. If not, assign the value of that element to the pointer and then change that value to the one we have in the variable. Jump to the next element by using the pointer and continue to do the same task like what we do with the previous element. The program will alert an infinite loop when it found there is an element with the same value in the variable. public void detectCycle(int[] arr,int n){ int slow=0,fast=arr[arr[slow]]; boolean flag=false; while(fast=n) System.out.println("Cycle not present in arr"); } Show More Responses "turn" & check the first The question is not clear . If each element's value is the next element's index then there'd be no cycle as mentioned above. I like the sets solution in terms of simplicity. To add to the possible solutions I propose hashing each index encountered with the value being the number of occurrences. Each time update the value of a key if it is already a 1 we've found a cycle. This should be O(n) for both time and space complexity. One doubt I have with the fast/slow double pointer solution is the assumption that the existence of a cycle has to send the fast pointer back exactly to where it eventually meets the slow pointer. In situations where this isn't true an additional condition should be if the slow pointer reaches the end before the fast. If an array starts at index 0 and it has value 2. If the index 2 has value 1 and index 1 has value 0. Then it would be cyclic array. Because it starts and ends in the same index 0. Multiple approaches are possible. If space of O(n) is allowed, add all pointers to a Set. If set size is less than array size, there is a cycle. If linear time and constant space is desired, start 2 pointers at index 0, First pointer is incremented by 1 index, second incremented by 2 indices. If end is reached by either pointer, no cycle. If fast pointer '.next' is every slow pointer, there is a cycle. How about incrementing a counter every time you follow a pointer and seeing if the final count is greater than the array length? If you've done more iterations than the array's length, that should indicate a cycle. |

### Software Engineer at Facebook was asked...

Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ). 11 AnswersSee Kadane's Algorithm. Sort the array in n log(n) and then start adding from right to left until the sum drops and thats your largest sum. def LargestSumSubArray(arr): sum = max_sum = 0 low_end = high_end = 0 tmp_low_end = 0 for i, a in enumerate(arr): sum += a print 'sum = %d max_sum = %d' % (sum, max_sum) if sum > max_sum: max_sum = sum high_end = i if tmp_low_end: low_end = tmp_low_end else: if a >= 0: if a > max_sum: low_end = high_end = i max_sum = sum = a else: sum = a tmp_low_end = i print '%d %d' % (low_end, high_end) return arr[low_end:high_end + 1] Show More Responses //find the largest sum subarray in an array of integers. (Better than O(n^2) ). // 0 1 2 3 4 5 6 7 8 9 10 11 12 $input = array(12, -23, 123, 12, 213123123, -23432, 1231231, 12, 12, 12, -34, -23423, 2123); $len = count($input); $temp = ls($input, 0, $len - 1); function ls($input, $start, $end) { if ($start == $end) { return array($input[$start], $start, $end); } else { $out = ls($input, $start, $end - 1); $lmax = $max = $out[0]; $i = $out[1]; $j = $out[2]; $sum = 0; for ($index = $end; $index > $out[2]; $index--) { $sum += $input[$index]; if ($sum > $lmax) { $lmax = $sum; $i = $index; $j = $end; } } $sum += $max; if ($sum > $lmax) { $max = $sum; $i = $out[1]; $j = $end; } else { $max = $lmax; } return array($max, $i, $j); } } Sort the array. {1,5,3,7,2,9} {1,2,3,5,7,9} Then largest sum can be given by {2,3,5,7,9} - leave a[0] :-) A dynamic programming can solve it with O(n). On the i-th step save inclusive and exclusive values with the next logic (A - input array): Inclusive(i) = Max(Inclusive(i-1), 0) + A[i] Exclusive(i) = Max(Inclusive(i-1), Exclusive(i-1)) C# example: class Item { public int Inclusive { get; set; } public int Exclusive { get; set; } } int[] input = new int[] {-3, 15, -10, 1, 5, 5, -15, 17}; Item prev = new Item { Inclusive = input[0], Exclusive = 0 }; for (int i = 1; i < input.Length; i++) { Item curr = new Item { Inclusive = Math.Max(prev.Inclusive, 0) + input[i], Exclusive = Math.Max(prev.Inclusive, prev.Exclusive) }; prev = curr; } Console.WriteLine(Math.Max(prev.Inclusive, prev.Exclusive)); Console.ReadKey(); #define MAX(_a, _b) ((_a) > (_b) ? (_a) : (_b)) static void find_max_subarray(const int *array, int num) { int currentSum = 0; int maxSum = 0; int begin = -1; int end = -1; int i; for (i = 0; i < num; i++) { currentSum = MAX(0, currentSum + array[i]); if (currentSum == array[i]) { begin = i; } maxSum = MAX(maxSum, currentSum); if (maxSum == currentSum) { end = i; } } printf("max_subarray_sum = %d -- begin=%d end=%d\n", maxSum, begin, end); } int maxSum(vector& S) { int max_sum = 0; int current_sum = 0; int positive = 0; for (size_t i = 0; i max_sum) { max_sum = current_sum; } if (positive) { return max_sum; } return -1; // return -1 if there is no positive set } depends on your definition, if it must be continuous, then DP, O(n) #include #include #include using namespace std; int main() { int input[9999]; int inputL = 0; while (true) { cin >> input[inputL]; if (999 == input[inputL]) break; inputL++; } for (int i = 1; i 0) input[i] += input[i-1]; int max = 0; for (int i = 0; i < inputL; i++) if (max < input[i]) max = input[i]; cout << max << endl; return 0; } /* -2 1 -3 4 -1 2 1 -5 4 999 -1 -41 -51 -5 -2 999 -1 0 999 0 999 1 0 2 -3 5 5 -5 999 */ otherwise simply scan, pick the positive ones, O(n) It shouldn't be that complicated. A dynamic programming can solve it easily with O(n) public static void findLargestSumSubArray(int[] arr){ if(arr == null) { System.out.println("NULL ARRAY"); } else if(arr.length == 1){ SortingFun.printArray(arr); } else{ int maxSum = 0; //the largest sub array sum so far int maxStart = -1; //start of the sub array with largest sum int maxEnd = -1; //end of the sub array with largest sum int largestNegativeVal = Integer.MIN_VALUE; //the smallest negative number so far int runStart = -1; //start of a run (a run starts with a positive number) int sum = 0; //the sum in the current run int i = 0; //runner index while(i largestNegativeVal){ largestNegativeVal = val; } //if it's a positive value and we are not in a run yet, set i as the start of a run if(val > 0 && runStart == -1) runStart = i; sum += val; //if the current value causes the sum to become negative, discard the sub array before i if(sum = 0){ int k = i; while(arr[k] maxSum){ maxSum = sum; maxStart = runStart; maxEnd = k; } } //reset run-related variables runStart = -1; sum = 0; } i++; }//end while //if we are still in a run, then discard all the trailing negative numbers. if the sum of the rum without //trailing negative numbers is larger than the current max, update current max if(runStart >= 0){ i--; while(arr[i] maxSum){ maxSum = sum; maxStart = runStart; maxEnd = i; } } if(maxStart >= 0){ SortingFun.printArray(Arrays.copyOfRange(arr, maxStart, maxEnd + 1)); } else{ int[] temp = new int[1]; temp[0] = largestNegativeVal; SortingFun.printArray(temp); } } } |

### Software Engineer at Facebook was asked...

Given a string, remove all the duplicate characters (not necessarily consecutive) 9 Answersvoid removeDuplicates(char *in, char *out) { bool seen[NUM_CHARS] = {false}; while (*p != 0) { if (seen[*p] == 0) { *out++ = *p; } seen[*p] = true; } } void remove_duplicate(char * str, int len) { bool appeared[NUM_CHARS]; memset(appeared, 0, sizeof(appeared)); int i = 0, j=0; while(i < n) { if(!appeared[str[i]]) { str[j] = str[i]; j ++; appeared[str[i]] = true; } i ++; } str[j] = '\0'; } I mean combine them Show More Responses store each characted in hashset and them combine each char has ASCII code number, so just XOR all those numbers together, duplicates will eliminate each other. public class Duplicates { public static String removeDuplicates(String str){ int[] chars = new int[26]; StringBuffer sb = new StringBuffer(); for(int i = 0; i < str.length(); i++){ int val = (int)str.charAt(i)-97; if(chars[val]==0){ chars[val]=1; sb.append(str.charAt(i)); } } return sb.toString(); } public static void main(String[] args){ String res = removeDuplicates("faaabook"); System.out.println(res); } } to the last two - just use a boolean array instead of a map or list like Interview Candidate void RemoveDuplicates(char[] arr, int length) { Map charMap = new Map(); int currenPosition = 0; for (int i=0;i public class StringRemove { private final String baseString = "abcdefghijklmnopqrstuvwxyz12345678910"; private final List finalMap = new ArrayList(); private StringBuffer sb = new StringBuffer(); private void findDup(){ for(int i=1 ; i <= baseString.length() ; i++) { String sLocal = baseString.substring(i-1, i); if(finalMap.contains(sLocal)){ finalMap.remove(sLocal); }else{ finalMap.add(sLocal); } } String s = finalMap.toString(); s = s.replace('[',' ').replace(']',' ').replace(',', ' ').replace(',', ' ').trim().replaceAll(" ", ""); System.out.println(s); } public static void main(String s[]){ StringRemove sr = new StringRemove(); sr.findDup(); } |

### Software Engineer at Google was asked...

Write a function to caculate the angle between hour and minute hand on a clock. 9 AnswersJust make sure u take account of the angle of hour hand public class Clock { /** * @param args */ public static void main(String[] args) { System.out.println(getAngle(2,11)); } public static double getAngle(int hours, int mins) { System.out.println(hours * 30.0 + 30.0*mins/60.0); System.out.println(mins*360/60); double angle = Math.abs((hours * 30 + 30.0*mins/60.0) - (mins*360.0/60.0)); return angle; } } Sorry Hasan, But I still don't think your code is correct. For example, if the time was 3:15, the angle should be 0 rather than 180 [ the output your code suggests. Similarly, if the time was 3:45, the angle should be 180 rather than 0 [ the output your code suggests. Why? because the question is the angle between the hour and the minute hand. I will post my solution soon. Its alot more complicated than people think! Show More Responses Think of it this way: First, you need to take the hour and do a modulo 12 on it, because there aren't 24 hours on a clock. Next, every minute, the minute hand moves by 6 degrees (360/60). Now, the hour hand does a complete rotation in 12 hours, that would be 30 degrees per hour (360 degrees / 12 hours) Of course, as the minute hand rotates beyond H:00, the hour hand keeps advancing, so we need to account for that. We know it takes 60 minutes for the hour hand to advance by 30 degrees, so the correction is (fraction of an hour) * 30 degrees. So the angle between 12 o'clock and the position of the hour hand (Ha) is: Hour = Hour % 12 -> handle values past noon Ha = 30*Hour -> position of the hour hand without correction Ha = Ha + (Minute / 60 * 30 degrees) -> correction for the position of the hour hand And the angle between noon and the minute hand (Ma) is: Ma = 360 degrees / 60 minutes * Minute And so the angle between the two hands is: Abs(Ha - Ma) For instance, for 14h20: Hour = 14 % 12 = 2 Ha = 30 * 2 = 60 (uncorrected) Ha = Ha + (20 / 60 * 30) = 70° Ma = 360 / 60 * 20 = 120° Angle between the two = 50° Whenever you have a problem like this one, try to draw it on the board, and pick easy values, for instance 6:30, which is obviously not 0°, but half of the angle that represents 5 minutes, and you'll end up figuring it out pretty quickly. function getAngle($h, $m) { $ha = $h * 30 + ((int) $m / 60) * 30; $ma = $m * 6; return abs($ma - $ha); } Is this the question asked at Google for real? It's not hard at all. Oz, Your code has some bugs... the corrected code is below: public class Clock { public static void main(String[] args) { System.err.println(getAngle(Integer.parseInt(args[0]),Integer.parseInt(args[1]))); } public static double getAngle(int hours, int mins) { double angle = Math.abs((hours * (360.0/12.0)) - ((60 - mins) / 5.0 * (360.0/12.0))); return angle % 360.0; } } Quick answers 1. I have no idea why. 2. I didn't see the question before but I solved it too quickly and he accused me. 3. Oops, this needs to be corrected. Just few thoughts on interview process: - why the interviewer attacks that way at beginning? - when u know the answer, i think it's sort of honesty to say you had read this question before; then the interviewer might ask different ques, or he might ask to see how do u code it - finally, why do you said "Received and Declined Offer", when you failed 2nd phone screen. No offense, just ask for correction. |

### Software Engineer at Google was asked...

Write a function that divides two numbers without using the divide '/' operator. 11 AnswersI had to use recursive subtraction or addition. But, I think I took too long a time to figure out the fastest code and I was typing it out in google docs while the interviewer was on the phone with me. I was nervous. It was my first ever interview. But, it was a heck of a experience. X * Y^(-1) One way is to iteratively count the number of times Xn = Xn-1 - Y >= Y. No recursion needed. Also, if Y is a power of 2, you can use a right-shift to get the answer...even faster. If the number space is sufficiently small, you can use a lookup table. Show More Responses int positionOfFirstAndOnlyBitSet(int m) { int pos = -1; int x = 0; for (; x > x) & 1) if (pos == -1) pos = x; else return -1; // found more than one bit } return pos; } int divide(int n, int m) { if (m == 1) return n; if (m == n) return 1; if (m > n) return 0; int pos = positionOfFirstAndOnlyBitSet(m); if (pos != -1) return n >> pos; // how manny times one can multiply m before going over n int x = 1; int mm = m; while (mm <= n) { mm += m; x++; } return x - 1; } assuming you want to be able to handle doubles, I like the idea of x * pow(y,-1.0); ... why make the answer more difficult for yourself than it needs to be? I got this question in facebook interview as well. You usually are not allowed to use floats, or pow(), or % And also you have to consider both +, - integers, so Steve M answer is not valid. public static int divide(int a, int b) { if(a < b) return 0; int div = b; int k = 1; while((div<<1) <= a) { div = div<<1; k = k<<1; } return k + (div == a ? 0 : divide(a-div,b)); } Victor, whats the complexity of your solution ? Binary search will work ? Let's say you need x/y. And only integral solution is needed i.e. 10/3 = 3 , not 3.33. This won't work if we need float as a result Pseudocode If x > 2) if mid*y == x : return mid if mid*y > x : hi = mid - 1 else: lo = mid + 1 return lo -------------------- Actually, it's quite simple. Recursively! function addTwo(x,y){ if (y === 0) { return x; } return addTwo( x ^ y, (x & y ) << 1); } addTwo(2,3) // 5 OR do it iteratively function addTwo(x, y) { // Iterate till there is no carry. while (y !== 0) { // Carry now contains common set bits of x and y. carry = x & y; // Sum of bits of x and y where at least one of the bits is not set. x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum. y = carry << 1; } return x; } int num; int div; int rem; // assume only positive numbers for(i=0; num>=0 ; num-=div) { i++; rem=num; } printf("\ni: %s%d rem:%d", i, rem ); |

### Software Engineer at Facebook was asked...

Write a function to tell if two line segments intersect or not. 9 AnswersI check slope, if parallel then check y-intersect, and see if ends of one line segment are between the ends of the other. If not parallel then check if ends of one line are on different sides of the other. However later I found that it will be much easier to use vector dot product. Maybe that's why I am rejected. Wtf if m1 = m2 the slopes are parallel, then it doesnt work. Interview Candidate is right..I would just solve for each equation and check where if the equations ever equal each other ( after seeing if slope is parallel) Calculate formula for each line. Determine intersection point and then determine if each segment overlaps the intersection point. You have to special-case the situations where the slope is infinite (vertical line) and where the slopes of the lines are the same. Show More Responses Here's the solution coded up. bool DoesIntersect(line one, line two) { float slopeOne = GetSlope(one); float slopeTwo = GetSlope(two); if (slopeOne == slopeTwo) { if (one.x1 == one.x2) { return true; } else { return false; } } float yInterceptOne = one.y1 - slopeOne*one.x1; float yInterceptTwo = two.y1 - slopOne*two.y1; float xIntersection = (yInterceptTwo - yInterceptOne)/(slopOne - slopeTwo); float minPointOne, maxPointOne; GetMinAndMax(one.x1, one.x2, &minPointOne, &maxPointOne); float minPointTwo, maxPointTwo; GetMinAndMax(two.x1, two.x2, &minPointTwo, &maxPointTwo); if ((xIntersection >= minPointOne && xInterSection = minPointTwo && xIntersection <= maxPointTwo)) { return true; } else { return false; } } float GetSlope(line theLine) { if (theLine.x1 == theLine.x2) { slope = 0; } else { slope = (theLine.y1 - theLine.y2)/(theLine.x1 - theLine.x2); } return slopeOne; } void GetMinAndMax(float one, float two, float* min, float* max) { if (one <= two) { *min = one; *max = two; } else { *min = two; *max = one; } } #include #include #include using namespace std; double f(double a0, double b0, double a1, double b1, double x, double y) { return (a1-a0)*y - (b1-b0)*x + a0*b1-a1*b0; } int main() { double x0, x1, y0, y1, x2, x3, y2, y3; cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; if (f(x0, y0, x1, y1, x2, y2)*f(x0, y0, x1, y1, x3, y3) <= 0 && f(x2, y2, x3, y3, x0, y0)*f(x2, y2, x3, y3, x1, y1) <= 0) cout << "yes" << endl; else cout << "no" << endl; return 0; } Why all this stuff. .Its asking about two line segments, not two straight lines. ASsume the line segment as an X axis range (X1,X2) and the other one has an x axis rage of (X3,X4). Then if these two ranges do not overlap, then the two line segments don't intersect. If they do overlap, check if the Y axis ranges overlap or not. If they don't overlap, then the two line sgements don't intersect. So simply, if either the x axis range or the y axis range of both lines don't overlap, then the two lines don't intersect... otherwise, they intersect.. simple right? No slope or stuff.. ActiveX answer is wrong.. this case will fail.. line(point(3, 1), point(9, 6)) and line(point(6, 3), point(9, 0)) your approach will return true.. while it should return false. This is my approach: 1. Get the slope of the two lines m1, and m2 2. If they are equal means they are parallel and return false 3. else compute b1, and b2 such that the first line equation is y = m1x+b1 and the second line equation y = m2x+b2 4. Compute the intersection point X, Y such that m1x+b1 = m2x+b2 this will lead us to finding x and then y 5. Check in the first line and the second line SEGMENTS that they include this point .. bool check(line l, point p) { double mnX = min(l.p1.x, l.p2.x); double mxX = max(l.p1.x, l.p2.x); if(!(mnX <= p.x && p.x <= mxX)) return false; return true; } bool lines_intersect(line l1, line l2) { double m1 = (l1.p1.y-l1.p2.y)/(l1.p1.x-l1.p2.x); double m2 = (l2.p1.y-l2.p2.y)/(l2.p1.x-l2.p2.x); if(fabs(m1-m2) <= 1e-9) return false; double b1 = l1.p1.y-(l1.p1.x)*m1; double b2 = l2.p1.y-(l2.p1.x)*m2; double intersectionX = (b1*-1+b2)/(m1-m2); double intersectionY = m1*intersectionX+b1; cout << intersectionX << " " << intersectionY << endl; if(check(l1, point(intersectionX, intersectionY)) && check(l2, point(intersectionX, intersectionY))) return true; return false; } A linear line is represented as y=mx+b or just to distinct points in the space. If the later case, assume the points are (x1, y1) and (x2, y2), then m=(y2-y1)/(x2-x1) and b can calculated easily. So, to lines y=m1x+b1 and y=m2x+b2 are intersected if m1 equals to m2. |

**21**–

**30**of

**6,126**Interview Questions

## See Interview Questions for Similar Jobs

- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Intern
- Software Engineer Intern
- Data Scientist
- Analyst
- Engineer
- Product Manager
- Software Engineer II
- Business Analyst
- Consultant
- Associate Software Engineer
- Staff Software Engineer
- Java Developer
- Director
- Project Manager
- Senior Software Developer
- Software Engineering Intern
- Software Engineer III