## eugene.yarovoi

BAN USERSince the sum_array already has k-consecutive column sums, checking k consecutive rows in the same column of sum_matrix is checking k * k squares in the original input. You consider the columns one at a time in step 2, keeping track of where you saw the maximum as you go from column to column.

It is O(MN) as promised.

(Edited to reflect that there are 2 parameters, M and N, and the input is not just N*N).

We can do this in O(MN). High level outline:

1. Use a sliding window approach to create an auxiliary "sum matrix" where sum_matrix[i][j] = sum (input_matrix[i][j] + input_matrix[i][j + 1] + ... input_matrix [i][j+ k - 1]. By "sliding window", I mean that we should exploit the fact that sum_matrix[i][j] = sum_matrix[i][j - 1] + input_matrix [i][j+ k - 1] - input_matrix[i][j-1]. This reuse of previous results will allow the computation of the sum matrix in O(MN) time. (The sum matrix is of size m * (n-k), to avoid going out of bounds)

2. Now, the sum_matrix represents sums of k consecutive columns in the same row. So the remaining problem now is to find where in sum_matrix we get a maximum sum if we sum k consecutive rows in the same column. This can be done by a similar sliding window approach, again in O(MN) time.

Now we're done. The algorithm can be designed to just return the max sum or also keep track of where it was found. Since both steps above are O(MN), the algo is O(MN) overall. I should also mention that O(MN) is optimal because that is how much data we have, and we must look at all the data at least once.

If you really must require a (fairly obvious) explanation for the downvote: I don't think this can be the solution we're looking for. While technically O(1), it could be horribly inefficient if the input array isn't all that large. Also why 8 GB? If it's two bits per number, it's 1 GB.

- eugene.yarovoi August 12, 2012That doesn't matter. Even if it's a checking condition, you're still traversing 5 nodes every time you do current.next.next.next.next.next

It can't reasonably be considered an approach that only makes a single pass.

@dc360: no, it's not traversing the tree in the same way. Copy and pasting from my other post:

"Think about it this way. If you wanted to find whether two people share a mutual friend, would you 1) do a set intersection on the two people's sets of friends or 2) find all of A's friends, find all the friends of each such friend, and check whether B is in this giant set? Choice 1 is much better."

but Derived classes can still instantiate the base class. And you can still use new.

See the discussion in some of the other answers for this question -- we covered this idea already.

What is rand()? And what am I supposed to think about when thinking about this?

- eugene.yarovoi August 10, 2012The issue is that the poster didn't read the problem.

- eugene.yarovoi August 10, 2012-1: I haven't tested your code for correctness (and it might well be correct), but there's some bad stuff going on in here. There are some major performance killers:

- Use of operations like soFar += "0". This is terrible practice because it recopies the entire string every time you do that. See kaioa DOT com/node/59 for one explanation

- Unnecessary use of recursion for something that easily could have been done with iteration. This is particularly bad given that the maximum height of the recursive call stack is order O(B).

- More complex code logic and more checks than necessary. For example the decimal point could have been added once prior to entering the recursion so that all the associated checks aren't done every time you call divide().

Because of how you manage your strings, your algo will be at worst O(B^2) instead of being O(B).

@Raj: That's not correct. If you have two variables and you traverse the list once with each of them, that's two passes. It doesn't happen in the time of one pass as you suggested. The logic above isn't considerably faster than doing two passes.

- eugene.yarovoi August 10, 2012Good argument, cobra. It's always good to design your code to be easy to change. With your approach the value 5 would probably be one parameter passed to the queue in one place in the code.

One small correction: you need to be inserting elements into the queue even as you traverse to the 5th node.

So here you're traversing twice, aren't you? Once for each of the two pointers you have.

- eugene.yarovoi August 10, 2012No, because you would need to allocate new storage. A x B is only the same dimensions as B x A if A = B. You wouldn't be able to reuse the old storage in the case that you had an M x N matrix with M != N because the output would need to be N x M.

- eugene.yarovoi August 10, 2012I think the 3rd degree of connection was just used as an example. The algorithm should work for larger inputs too. See my response to careercup DOT com / question?id=14087784 for an algorithm that's considerably more efficient than BFS.

- eugene.yarovoi August 09, 2012Yes. This question has been asked on CareerCup before, and I explained the advantages of this approach. See my post in:

careercup DOT com / question?id=14087784

This is just one of the many tests you need to do. See Martin's response for one (out of many possible) examples of why your approach is woefully insufficient.

Some additional tests would be making sure there's no correlation between one number and the next, checking longest runs of ones and zeros, checking criteria like dimensional equi-distribution, and a zillion and one other tests. You can read about all of these on the Internet. This is a very nontrivial problem.

Same here. This question needs to be A LOT clearer before I'll attempt to answer it. What does killing an animal have anything to do with it?

- eugene.yarovoi August 09, 2012Agreed with madhu. You need to ensure you form a BST. You'd be right if that was not a constraint here.

- eugene.yarovoi August 08, 2012You haven't given a good rationale as to why it would be correct. Just because the most frequent elements are near the top, doesn't mean they're arranged in the most optimal way, or if they are, you should give a proof or at least an argument. I think that, generally speaking, when you post a solution to a non-trivial problem, the burden is on you to show that the solution is correct.

Try comparing your results with the results of the DP approach, whose optimality is easy to see and prove. You'll probably find cases where your trees are suboptimal.

You update the max to the current loop variable whenever a new minimum wasn't discovered. Whenever this runs max > min will also be true, so your logic means that whenever a new minimum isn't discovered, you will run maxProfit=A[i]-A[min]; But that's not correct. You can see how with that logic, maxProfit could be replaced with a smaller maxProfit in the next iteration.

- eugene.yarovoi August 06, 2012Hashcode in Java is not guaranteed to be related to the memory address; that's an implementation detail. Also, since you can't dereference arbitrary addresses in Java, knowing the address wouldn't help you.

- eugene.yarovoi August 06, 2012@amitdhaka: It's impossible. Just don't worry about it. Either you misunderstood the question or your interviewer's wrong (happens all the time -- they're ordinary people too). I guarantee that this is impossible.

- eugene.yarovoi August 06, 2012Selection sort is O(n^2) in the best, worst, and average case.

- eugene.yarovoi August 06, 2012This solution is preferable to external sorting if the heap can fit into memory. Something like external sorting (or Quickselect) will be needed if can't, however.

- eugene.yarovoi August 06, 2012It's perhaps worth noting this algorithm has degenerate cases that are O(n^2). It is not worst-case O(n). With some randomization, the degenerate cases can be made extremely improbable.

- eugene.yarovoi August 06, 2012Yep, this is correct.

The question says you only have one byte of storage space, so if you followed that strictly, you wouldn't be able to keep a variable like "range". Since it's impossible to solve the problem without having a counter like that, however, it's perfectly appropriate to ignore that requirement.

It's not correct, for the reason I mentioned. Take a dataset like the one I mentioned. Run cobra's algorithm. Then run the dynamic programming algorithm described by another response. Then observe how the dynamic programming solution yields a better expected time. This shows that cobra's algorithm isn't optimal.

- eugene.yarovoi August 05, 2012It's a stream, so you don't know that.

- eugene.yarovoi August 05, 2012Something's wrong. You should be getting O(n).

- eugene.yarovoi August 04, 2012You need to be able to store how many elements you've seen so far (which presumably can't fit into a byte) for this problem to be possible.

- eugene.yarovoi August 04, 2012cobra: that's not correct. Consider a tree whose inorder traversal is 1, 2, 3, 4, 5, 6, .., N and whose probabilities are, for instance, .01, .02, .03, .035, .... Strictly ascending probabilities with respect to the in-order traversal.Your idea would place N as the root, N-1 as its left child, N-2 as the left child of that, ... Your tree would be a linked list. This can be worse in the expectation than a more balanced tree even if the root of the balanced tree isn't the node that has the highest probability.

- eugene.yarovoi August 04, 2012We know absolutely nothing unless we just shot it dead.

- eugene.yarovoi August 04, 2012You say "first i thot eugene soln wud work, but ... ".

I haven't offered any solutions yet.

An important thing to note is that the strategy must work against any jump sequence. The monkey shouldn't be able to evade death even if it knows in advance the entire strategy of the hunter. This is necessary, because suppose there is some death evading sequence that a monkey can do that will counter a given sequence of shots from the hunter. Even if the monkey moves randomly, it has some chance of randomly choosing that sequence and not getting shot. Since you need a strategy that always succeeds, your strategy must be a strategy that succeeds against every possible sequence of moves from the monkey.

- eugene.yarovoi August 03, 2012You could look at both numbers, check the square of both, and pick the closer one.

- eugene.yarovoi August 03, 2012@notbad: the original appears correct to me. Your edit doesn't.

This approach does a good job of removing the K factor from the complexity, but O(n) is still expensive. Granted, you're forced into it here anyway since the data is in a linked list, so this might be a very reasonable solution for this situation. If we had an array we could do much better.

I didn't check your code for correctness, but the general approach makes sense. It is at worst O(NK). Still a relatvely far cry from being optimal. A more mathematical algorithm will produce something more like O(KlogN) (+ O(N) if you need to do it on a linked list instead of an array).

- eugene.yarovoi August 02, 2012OK, so this is still a rather naive solution. You're not making any optimizations that help you on large values of n, only on large values of k. This solution is still O(n) for fixed k.

- eugene.yarovoi August 02, 2012If you have a multiplication operator, you can use binary search in conjunction with multiplication to search for the quotient. Not necessarily the most efficient way though.

- eugene.yarovoi August 02, 2012My counter-question was "what is a dictionary?" Is it a dictionary in the natural language sense, or is it a dictionary in the data structure sense (key-value map / associative array)?

- eugene.yarovoi August 02, 2012You're missing the most important part: the conclusion. You need to say that you keep this recurrence going until you have T(1), so in your equality you want n / 2^k = 1, which implies n = 2^k or k = log base 2 of n. Substituting, you get T(n) = n *O(1) + n/2 +n4 +... = O(n) (by convergence of the sum of this series).

- eugene.yarovoi August 02, 2012I didn't leave the comment, but yes, there is a specific reason I completely agree. This is some horrifically ugly code.

- eugene.yarovoi August 02, 2012Dictionary can refer to one of two things. Either a collection of words, or a Map (associative array). Which one do you mean?

- eugene.yarovoi August 01, 2012The problem can be done by using a HashMap and a Queue using pretty much the same logic as the LinkedHashMap approach uses.

- eugene.yarovoi July 31, 2012No. This is exactly the approach discussed in the top-voted solution. There are still some problems with it. See the discussion there. The basic point is that subclasses are still able to instantiate instances of the base class.

- eugene.yarovoi July 29, 2012Try not to call people morons when you're wrong. Be right when you do that.

- eugene.yarovoi July 28, 2012Sure there are differences between classes based on mutability. Also, final doesn't make something immutable. This isn't const.

- eugene.yarovoi July 27, 2012I completely agree with this post. Even if you could cheat on the phone, there's no way you'll make it through the in-person interviews if you don't have the skills.

Still, using the web doesn't have to be cheating. Your interviewer could authorize it.

Using the Internet is only cheating if your interviewer hasn't authorized it. If you think that using a reference of some sort (e.g. a Javadoc) is reasonable for a particular problem, you can always ask if you can use the Internet. I've definitely had interviewers authorize me to do a search or pull up a reference.

- eugene.yarovoi July 26, 2012

Rep**Gayle L McDowell**, CEO at CareerCupGayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...

Rep**Loler**, Employee at Google

Rep

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

One problem: what if X has no set bits? This is possible. Consider c = a^b

- eugene.yarovoi August 12, 2012