www.twitter.com /  HQ: San Francisco, CA

568 Interviews

3.1 Average

Sort: RelevancePopular Date

Dec 25, 2011
 Given n sets of choices: (1,2,3), (2,3,4), (4,5) You pick one element from each set of choices. Generate all possible picking.10 AnswersYou don't need depth-first or breadth-first.recursionwhy recursion? The following gives all possible pickings in list. A=[1,2,3]; B= [2,3,4], C=[4,5] list=[] for a in A: for b in B: for c in C: list.append([a,b,c])Show More ResponsesSorry about the ambiguity. n set of choices are given and we don't know them in advance. That was just an example..Okay then recursion is the way to go.In python its super easy list1 = [1,2,3] list2 = [2,3,4] list3 = [4,5] print [(x,y,z) for x in list1 for y in list2 for z in list3]public static void findAllPickings(List sets, int pos, String result) { if(pos == sets.size()) System.out.println(new String(result)); else { int[] currentSet = sets.get(pos); for(int i = 0; i < currentSet.length; i++) { String currentString = result + currentSet[i]; findAllPickings(sets, pos+1, currentString); } } }public List printPerm(List> lists, String prefix, List output) { if (prefix.length() == lists.size()) { output.add((T) prefix); } else { List currList = lists.get(prefix.length()); for (int i = 0; i < currList.size(); i++) { printPerm(lists, prefix + currList.get(i), output); } } return output; }public List printPerm(List> lists, String prefix, List output) { if (prefix.length() == lists.size()) { output.add((T) prefix); } else { List currList = lists.get(prefix.length()); for (int i = 0; i < currList.size(); i++) { printPerm(lists, prefix + currList.get(i), output); } } return output; }Backtracking is one of the solutions.

Mar 31, 2012
 Implement integer division without using / or %. Questions about running time. Can you do it faster?6 AnswersOptimal running time: O(log n)Binary searchHere's an implementation that works -- any ideas on how to make it go faster? public static void divide_without_slash_or_mod(int num, int divisor) { int factor = 0; int remainder = num; System.out.println("Number = " + num + " divisor = " + divisor); while(remainder >= divisor) { remainder -= divisor; factor++; } System.out.println(" remainder = " + remainder + " factor = " + factor ); }Show More ResponsesHere's an implementation that works -- any ideas on how to make it go faster? public static void divide_without_slash_or_mod(int num, int divisor) { int factor = 0; int remainder = num; System.out.println("Number = " + num + " divisor = " + divisor); while(remainder >= divisor) { remainder -= divisor; factor++; } System.out.println(" remainder = " + remainder + " factor = " + factor ); }D(Divisor), N(Divident) low = 0, high = INT_MAX/D while(low N) high = mid - 1; else low = mid + 1; } return -1; //No divisorHere is the Java implementation of implementing division with O(log n) time complexity (actually, this solution is using divide operator). public static void divide(int dividend, int divisor) { int mid, low = 0, high = Integer.MAX_VALUE / divisor; while(low dividend) { high = mid-1; } else { low = mid +1; } } }

Dec 30, 2011
 In a binary integer value tree, find the lowest level common ancestor of two values.7 AnswersNot binary search treeRecursive call.This is a very common question appeared on interview sites, books. The solution they provided is either inefficient or hard to understand. I worked out a simple idea: return {null, p, q, common ancestor} four type of values then the recursion will be very easy to write, and the code runs in log(n)Show More ResponsesTo Pegasus: Your idea won't work. Usually tree nodes do not contain a parent pointer unless specified. So the recursion is top down manner.Do the binary search for both elements at the same time...as soon as their paths diverge (i.e. you have to go left for one element and right for the other) save the node where it happened...this is the lowest common ancestor...however you should still carry out the recursion to verify that both values are indeed in the tree. Complexity is same as standard binary tree search, O(log n).Since it's not a binary search tree, you have to depth-first search the whole tree to find both nodes. When you find the nodes you save the path from the root to each. Then you just have to compare the two paths and find the last node in each that is the same. For instance, if the path to node G is A -> B -> C -> D -> G and the path to node H is A -> B -> E -> F -> H then the lowest common ancestor is B. Time complexity is O(n) where n is the number of nodes in the tree. Space complexity for a balanced tree is O(log(n)) since the paths can be the height of the tree.1) Search for the node1 from root. Keep track of its path in a list. Time complexity: O(n) 2) Repeat the same for another node. 3) Now remove the common nodes from both of the list. 4) The last node before the match is your result. Time complexity: O(n) Space complexity: O(n)

Mar 31, 2012
 Given a number n, give me a function that returns the nth fibonacci number. Running time, space complexity, iterative vs. recursive.5 AnswersLet me give you a recursive & not-efficient solution to get n th fibonacci number. public int findNthFib(int n) { return (n < 2 ? n : (findNthFib(n-1)+findNthFib(n-2)); } This short method will recursively return fib number. However, running time is very awful! it's O(2^n) = exponential time. it will quickly become a non-usable method after n = 30~40. There is another quick and elegant linear time solution, but I want the next person to present that in here. (if you google it, you can find it easily)unsigned long long fibonacci(unsigned long long n) { unsigned long long c = 0; unsigned long long i = 1; unsigned long long j = 0; unsigned long long nfib = -1; while (c < n) { i = i + j; c++; if(c == n) { nfib = i; cout << i << " "; break; } j = j + i; c++; if(c == n) { nfib = j; //break; } cout << i << " " << j << " "; } cout << endl << nfib; return nfib; } Time complexity O(N/2).Closed form solution. GGShow More Responsesint public(int n){ if(n == 0) return n; if(n == 1) return n; return (n-1)+(n-2); }public class fib { public static void main(String args[]){ int n=12; int counter=2; int[] arr = new int[n+1]; arr[0]=1; arr[1]=1; while(counter

Apr 8, 2012
 Given an array with all elements sorted on each individual row and column find the K-th smallest one4 AnswersTop left is the smallest one, obviously. Insert that, along with (0, 0), into a min heap. while less than k elements have been popped: pop the smallest element. Say it's coordinates are (i, j) Insert (i+1, j), (i, j+1) into the min heap. These are the possible next smallest numbers. The element at the root of the min-heap is the k-th smallest element now.Treat every row in the matrix as a separate stream of numbers. Merge the streams in an ordered way while decrementing k. When k is zero, your current element is the one in question.Walk through the matrix starting (0, 0). The comparisons happen between bottom and right values. If the right value is smaller than bottom, go to the bottom. If bottom is smaller than right, go right. Count every time you make a move. Do this until counter == K or you reach end of matrix.Show More ResponsesThe key feature of such a matrix is: The element at (m,n) should be the largest one in the sub matrix (0,0,m,n). So, the search should start from (0,N), then do zig-zag search based on the above feature.

Nov 17, 2013
 "Answer this question while I ignore you and then I'll criticize you for having not mentioned a solution...even though you did, which I ignored."2 AnswersDon't bother with Twitter.I think you should share the question being asked

Sep 5, 2012
 design a max stack using one stack, what are the language features that are missing in your favorite language, tree to a ordered doubly linked list2 Answershttp://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-onOne thing missing in Python that bugs me the most - Function/Method overloading! Argh!

Jun 24, 2011