Loler
BAN USER- 1 Answer Questions deleted by OP?
I have noticed that a couple of questions have been deleted. (One was a very new maximum product sub-array question, and one was a relatively new zig-zag of a 1-D array, which has a nice answer by showell).
- Loler March 10, 2013
It seems unlikely that the mods are deleting those, as those seemed like valid questions.
Is it possible that the OP deleted them after getting an answer? (Possibly homework and didn't want to get caught...).
Is there are a way to get back the questions (and the answers)? Prevent such things from happening in the future? (Eg. Don't allow a delete of a question after 2-3 answers have been posted).| Flag | PURGE
You missed 350.
Assuming it is a two pan balance, and we are allowed to place weight in any pan.
Each weight has 3 states: Left pan, not in any pan, Right pan.
Assign being in left pan as -1, and right pan as 1.
In each possible weighing, each weight w_i gets a coefficient a_i where a_i is -1, 0 or 1.
The weight that can be measured is the absolute value of a_1 w_1 + a_2 w_2 + ... + a_n w_n.
This gives us an algorithm.
Try to enumerate possible coefficients (a_1, a_2, .., a_n) and compute.
This can be done using the odometer trick, or if n is small enough, interpreting as a base 3 number.
This will visit each weight at least twice, but is asymptotically optimal in the worst case(the case when all weights are powers of 3, you will have Theta(3^n) possible measurements).
Here is quick python code
def generate_odometer(limits_list):
odometer_list = map(lambda x: 0, limits_list)
has_more = True
n = len(odometer_list)
while has_more:
yield odometer_list
has_more = False
for j in range(0,n):
limit = limits_list[j]
if odometer_list[j] < limit-1:
odometer_list[j] = odometer_list[j]+1
has_more = True
break
else:
odometer_list[j] = 0;
continue
def weights(lst):
feasible = {}
limits_list = map(lambda x:3, lst)
# 2 is treated as -1
for coeffs in generate_odometer(limits_list):
sum,idx = 0,0
for coeff in coeffs:
if coeff == 2:
sum -= lst[idx]
if coeff == 1:
sum += lst[idx]
idx += 1
if sum < 0:
sum = -sum
feasible[sum] = True
print feasible.keys()
def main():
weights([100,250])
weights([1,3,9,27])
if __name__ == "__main__":
main()
and here is the output
[0, 250, 100, 150, 350]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
@eugene: Yeah, I realized that you were probably thinking of something like that, after posting this. Of course, the one I posted trades time for space (space is O(n) if all we need is a stable sort), but makes an extra pass. If we store the list instead of a count, that is O(L+n) space.
- Loler March 10, 2013@HauntedGhost: Given the current info, you cannot do better than linear.
Are you sure of the question?
Perhaps they allowed preprocessing (like creating a Voronoi diagram) after which nearest point queries can be sub-linear, but you have to pay the Theta(n) cost (in fact, probably Theta(n log n) for Voronoi preprocessing).
There is a provable Omega(n) lower bound for this problem.
The idea being that you can create a matrix such that one of the main diagonals is an arbitrary given set. Querying for some member of that set in that matrix must take Omega(n) time in the worst case, for any algorithm.
For one such construction, given x_1, x_2, ... x_n place them in positions M[n][1], M[n-1][2], M[n-2][3],.., M[1][n] (M is matrix and M[i][j] is element of row i, column j).
Now chose Theta(n^2) numbers, all < min x_i, an arrange them so that the top left half of the matrix satisfies the condition, by filling row by and row, and starting with the smallest.
Similarly the bottom right right half can be filled to satify the properties.
Any element finding algorithm, must take Omega(n) in the worst case.
Yes, this question seems to be asking for an in-place merge algorithm.
Doing the insertion sort like steps, should work to give us an O(n^2) algorithm.
Getting an O(n) time merge algorithm is quite difficult, and research papers have been written about it (after being open for some time).
@Eugene: Ah! Good point. Thanks.
I will edit my answer to mention the interpretation it follows.
As to the other interpretation, I suppose rdx's solution works.
Treat each number as a 2-digit number in base n and use radix sort, one of the digits telling you which list the number belongs to, and the other the actual number. We can use a stable version of counting sort for the single digit sorting (which is what I suppose you were referring to?).
If needed you can avoid hashing by sorting the array and using the two pointers trick.
The decision problem (finding if there is at least one triple) is 3SUM hard. Getting a better than quadratic (like DashDash's solution) is an open problem.
Of course, this problem calls for enumerating all, so could go cubic!
@rdx: Eugene has convinced me that your interpretation is not as artificial as it seemed to me! Good solution, seems like it will work. +1 to your comment.
@Anonymous: What I meant to say was you don't really need L to be exactly n. It can be n+100, or 1000n. Counting sort requires bounded integers, why must that bound be same as the number of such integers? You can sort a million bits, for instance. We don't restrict to just two :-)
@vhmj1982: This is a reasonable solution. Not picking the root is a minor issue and can easily be corrected.
This way, for a balanced tree, insert/delete and getRandom all have O(log n) time.
Doing an inorder traversal will be O(n) time (btw, if you do decide to do inorder, you can save the array space of O(n) by using reservoir sampling).
@ywdong8809: The problem seems to imply that the binary tree implementation is in your hands, and so we expect the L/R will be available as a node field. Did you clarify this with the interviewer?
Yes, this is wrong. You never return the actual value in most cases. Though it is close to an answer which might work. But since you have no explanation whatsoever, I chose to downvote this. On the basis of the code alone(it is incorrect and you use static), this is enough to get a bad score on an interview.
The same question was asked a few days back, under Facebook.
You seem to be attempting to simulate an iterative in-order (in reverse) traversal using a list...
I guess one can beat that, by actually using a stack instead, where you get to pop off/reuse the stack data, thereby restricting the space usage to O(h) (height of tree), while your space usage is potentially Omega(n) (number of nodes in tree) (you only append to your 'stack').
Also, inspite of it being pseudo code, it looks quite ugly. So writing cleaner code which is easier to understand will better that, I suppose. (Perhaps not me, as I find most of my code ugly too)
@Anonymous: The question does not say the lists are already sorted.
Even if they were sorted, I am curious: what O(n) time algo do you have which can merge r lists (where r can be as large as n itself) which does not take into account the 1 to n bounds?
Sorry, have to give this answer a -1.
@Anonymous: I wish I could give your comment a -1, but that changes the order, so I will leave it at that.
A stable version of counting sort should cater to the two different interpretations of the problem we have seen so far:
1) Sort all into one big list
2) Sort each independently.
We solve 1), but include enough information in the output to solve 2)!
Maintain an array counts of size n for the counts. Increment counts[k] when you encounter k and then generate the sorted list at the end, by walking the input again(in order we got it), so that we can tag the output number with the list it came from. This way, the numbers are sorted, but we also know which list we got them from, which can be used to solve 2).
If the sum of the lengths of the lists is L, then this algorithm is O(L+n) time and O(L+n) space.
We don't exactly need n = L.
Sample python code. count_sort takes a list of lists, and returns a sorted list of tuples (number, list_number), sorting by number. sort_all just extracts the number and creates a big list. sort_single create a list of lists, and puts in number in the appropriate list using list_number.
def count_sort(lsts, n):
count_list = map(lambda x: 0, xrange(0,n+1))
list_id = 0
total_num = 0
for lst in lsts:
for k in lst:
count_list[k] += 1
total_num += 1
offset = 0
for i in xrange(1, n+1):
count = count_list[i]
count_list[i] = offset
offset += count
result = [0] * total_num
num_seen = map(lambda x: 0, xrange(0,n+1))
list_num = -1
for lst in lsts:
list_num += 1
for k in lst:
result[count_list[k] + num_seen[k]] = k,list_num
num_seen[k] += 1
return result
def sort_all(lsts,n,r):
return map (lambda x: x[0], count_sort(lsts,n))
def sort_single(lsts,n,r):
results_lst = []
for j in xrange(0,r):
results_lst.append([])
for k,list_num in count_sort(lsts,n):
results_lst[list_num].append(k)
return results_lst
def main():
lsts = [[2,3],[3,2,1],[2,2,2,1,1,1]]
print "Input", lsts
print "All", sort_all([[2,3],[3,2,1],[2,2,2,1,1,1]],3, 3)
print "Single", sort_single([[2,3],[3,2,1],[2,2,2,1,1,1]],3, 3)
if __name__ == "__main__":
main()
Output
Input [[2, 3], [3, 2, 1], [2, 2, 2, 1, 1, 1]]
All [1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]
Single [[2, 3], [1, 2, 3], [1, 1, 1, 2, 2, 2]]
--------------------------------------------------------------
- Loler March 06, 2013Going by numbers alone, that is actually an impressive performance.
Being able to do 3 questions in a ~45 min slot (specifically in a Google interview) is quite impressive.
But the fact that you even had a second phone interview probably means that there might have been something lacking in the first (does not look like an HR person was conducting that interview, but was it?).
So I would say (of course, no data to back it up), seems like an above average interview.
Good luck!
@zyfo2, when one talks about 'best' with conviction, it always makes me nervous :-)
The best depends on the circumstances and is not always clear. Even with a theta(n^2) vs theta(nlog n) algorithm, the quadratic one might be 'best' under the circumstances.
For this problem, say you had say fifteen 128bit integers for which you were looking for a particular subset sum. It might potentially be better to just enumerate all subsets, rather than go via the dynamic programming approach.
I downvoted this answer because it makes a wrong statement and just says check the wiki, which IMO, is a bad quality answer, with no scope of being corrected unless changed drastically...
As to the interviewer 'wanting' an answer, you seem to be mistaken. There is no specific 'correct' answer they (usually) look for. They try to look for how you plan and approach to solve the problem, and how the discussion goes.
Assuming by subsequence you actually meant _subarray_, an O(n) time algorithm is possible.
Traverse the array from left to right, and maintain a running sum of number of ones - number of zeroes.
You also have a hashtable keyed on the running sum, and which contains information regarding the number of times that running sum appears, and also the leftmost index for which that sum appears.
Note: Even though the code uses hashtable below, as Eugene pointed out, since the running_sum is between -n and n, we can always use an array, guaranteeing O(1) lookups.
Using this structure, we can compute the answers for both 1 and 2.
For instance, to compute the number, we check if the running sum appeared before. If it appeared k times before, then we get k new sub-arrays with equal number of zeroes and ones.
The max length uses the left most such idx.
Here is sample code in python (with random test cases). The O(n) method is named equal_count.
def equal_count(lst):
bits = [-1,1]
counts = {0: (1,-1)}
run_sum, total_count, max_len = 0,0,0
cur_idx = -1
for bit in lst:
cur_idx += 1
run_sum += bits[bit]
if run_sum in counts:
c, idx = counts[run_sum]
total_count += c
if cur_idx - idx > max_len:
max_len = cur_idx - idx
counts[run_sum] = c+1, idx
else:
counts[run_sum] = 1, cur_idx
return total_count, max_len
def equal_count_brute(lst):
n = len(lst)
total_count, max_len = 0,0
for i in range(0,n):
for j in range(i+1, n+1):
count = sum (map (lambda x: -1 if x == 0 else 1, lst[i:j]))
if count == 0:
total_count += 1
if j-i > max_len:
max_len = j-i
return total_count, max_len
def main():
lsts = [[0], [1], [1,1], [1,0], [1,0,1],[1,0,0,1], [0,1,0,1,0,1]]
for lst in lsts:
print equal_count(lst), equal_count_brute(lst)
if __name__ == "__main__":
main()
If you actually meant _subsequence_, then I suppose the problem is easier and more mathematical than programming.
Count the number of zeroes, and number of ones. Find the number of ways to pick r zeroes and r ones, and add up over possible r. The largest r (or rather 2r) will you give you the max length subsequence.
Interesting problem.
A simple approach is to just increment in small steps from x1 to x2. This is O(|x2-x1|) and potentially inefficent.
There is a more efficient binary-search like algorithm. The idea is to narrow down the interval in which the minimum lies.
Given current interval (x,y), compute two new points ((2x + y)/3, (x+2y)/3), call it (a,b).
if a and b are "equal" you return a.
Compute convex(a) and convex(b).
If convex(a) < convex(b), then b is surely in the increasing arm of the function.
Thus you can pick (x,b) as the new search interval.
if convex(a) > convex(b), then a is surely in the decreasing arm of the function. You can pick (a,y) as the new search interval.
if convex(a) == convex(b), we can pick either (x,b) or (a,y).
Thus we have an O(log (|x2 -x1|) time algorithm, as we cut a fixed fraction of the interval each time.
Here is sample python (neither exemplary, nor properly tested)
def minima(x,y, f):
err = 0.00000000000000000001
a,b = (2.0*x + y)/3.0, (x+2.0*y)/3.0
if b-a < err:
return a
delta = f(a) - f(b)
if delta*delta < err*err:
return minima(x,b,f)
if delta < 0:
return minima(x,b,f)
if delta > 0:
return minima(a,y,f)
return b
def square(x):
return x*x;
minima(-1.0,1.0, square)
@Bevan: I am curious. Subset sum is NP-Complete even if the numbers are all positive. What algo do you have?
btw, if you do have an algorithm for positive numbers, you can use it for negative numbers (just add a large enough positive number to each, and also put a constraint on the size of the set, and run multiple times for different sizes).
Since we are looking for the deepest node(I misread the question, which only asks for the depth, not the node itself, but will leave this here), doing a depth first search might be preferable, considering space complexity, as the time complexity will be similar, as compared to doing a breadth first search. And writing the code for a recursive version of dfs might be easier.
Assume root is at depth 1 (this assumption matters, and needs to be clarified with the interviewer).
We do a dfs, and keep track of the level and a possible candidate node (and its depth). Possible code (C/C++ like).
Tree * FindOddDeep(Tree * root) {
uint depth=1; // unsigned int
Tree *result = NULL;
unsigned int result_depth = 0;
FODHelper(root, depth, *result, result_depth);
return result;
}
void FODHelper
(Tree *root, uint &depth, Tree ** pResult, uint &result_depth) {
if (root == NULL) {return;}
// A leaf node
if (root->left == NULL && root->right == NULL) {
if (depth % 2 == 1) { // odd depth
if (depth > result_depth) { // deeper than current candidate
*pResult = root;
result_depth = depth;
}
}
return;
}
depth++;
FODHelper(root->left, depth, pResult, result_depth);
FODHelper(root->right, depth, pResult, result_depth);
depth--;
}
@kz: We cannot dispute assumptions like that :-) They will be dictated by the needs of the requirements (or the interviewer in this case), which we don't have access to.
I just stated that to prefer reverse inorder over inorder. That is all.
In any case, if we don't know the total number of nodes in the tree, doing a reverse inorder will be more efficient than counting the nodes and then doing an inorder traversal to find the (n-k)^th smallest.
I have updated the original post to not talk of any assumptions at all.
@Frank. If characters can repeat, you can maintain the difference in counts (between the window and the target string) and this idea would essentially work. Once a character count becomes zero, that means the window has the exact number required for that character (as we are maintaining difference). You can move it to a different set.
To check if a window matches, just check the length of the different set.
This is O(n) time (n is the length of the larger string).
@Jean: If you say yes here is your product, and give a solution without clarifying anything, then there is no guess, you will get rejected.
You have to clarify the problem further, and that is not possible because Bevan just copied and pasted from glassdoor, giving no chance to try and asking clarifying questions.
I am not claiming that if some ambiguous question is given you throw up your hands claiming nonsense etc (not sure how in the world you came to that interpretation). In any case, you need to have the guts to call crap for what it is...
Anyway, pointless discussion...
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
Rep
@nik: That is not the core idea. The core idea is just recursion! You are just complicating something that is quite simple.
- Loler March 13, 2013@Paul:
Imagine sum was a blackbox. You used that and now have the result for the subtree rooted at the left child, and the subtree rooted at the right child.
Given those values, can you give the result for the subtree rooted at the root?
For a similar example, consider computing the height of a tree.
Given the heights of the left and right subtree, can you give the height of the whole tree?
Now, can you translate that to a recursive method?