Coding Owl
BAN USERFinally some sane person who actually presents an algorithm instead of a truck load of cryptic code. Thank you!!
- Coding Owl February 21, 2015How about DP approach? Consider the right bottom cell. The only way it can belong to the maximum product is if it contributes to the maximum product itself. So with regard of matrix boundaries:
Ph = Product of A[i-3..i,j]
Pv = Product of A[i, j-3..j]
Pd = Product of A[i-3..i,j-3..j]
A[i,j] = max(Ph, Pv, Pd)
And BTW, does every coding monkey here seriously expect people to read truck load of code you manage to dump here? Get real people! You need to come up with an algorithm, not 3 pages of something that will take all evening to figure out.
Why would Adobe ask all these questions about Google?
- Coding Owl February 21, 2015Nothing is deleted -- they keep tracking you.
- Coding Owl February 21, 2015Read the problem -- binary search will give you nlogn failures in worst case, not 2.
- Coding Owl February 21, 2015
"Map-reduce" my eye! Use external merge sort -- no need for much memory. Two options - either put output to a new merged file and then make one pass over it, or do multiway merge of all created chunks, which will require a priority queue.
- Coding Owl February 21, 2015