5 ms·

I assume my code knows (or can readily find) the value of M and N. The max_height of the pyramid is ceil(M/2) + ceil(N/2). The height of every point in the matr

I assume my code knows (or can readily find) the value of M and N. The max_height of the pyramid is ceil(M/2) + ceil(N/2). The height of every point in the matrix can be readily calculated by taking its Manhattan Metric distance from the center. The equation is max_height - (floor(abs(i-M/2)) + floor(abs(j-N/2))). O(MN) operations are needed. The ceils and floors are there to deal with the case that M or N is even. I did this in my head so there may be off an off by one error which is easily remedied. I forget terminology. Object is an instance of a class right? Did I get the job?

jwilk 9y ago
> Manhattan Metric Nope. All border cells are supposed to be 0, but they have different Manhattan distances from the center. > Object is an instance of a class Correct.
- StevePerkins 9y ago
  The question statement above calls for border cells to have a height of "0 or 1". Perhaps to give the candidate some fudge-factor for matrices having an odd number height or width. I realize that this is a contrived testing problem, but to me a pyramid with zeros in the border cells sounds wrong. The area just beyond the border should be zero. Being within bounds of the pyramid intuitively should imply some non-zero height.
  - roel_v 9y ago
    Yeah borders being 0 is weird, but it's not material to the question, and for some reason someone once thought this was how it was supposed to work - I never cared about details like that.
SmallDeadGuy 9y ago
Actually, if your M/2 isn't integer division (which I assume is the case from your use of ceil around it first), your 5x5 pyramid would look like this: 23443 34554 45665 45665 34554 Using max_height - (abs(i - floor(M/2)) + abs(j - floor(N/2))) would give the properly-centered pyramid: 23432 34543 45654 34543 23432 Your max height should really be just max(ceil(M/2), ceil(N/2)) for a height of 3 going to 1 at the edges or floor(M/2) for 2 to 0. Using both Manhattan distances gives you an octagon-base pyramid (approximated to the square shape) when really you just want the max of both distances: max_height - max(abs(i - floor(M/2)), abs(j - floor(N/2))) gives: 11111 12221 12321 12221 11111 But this only works for square pyramids, using 3x5 you get: 12221 12321 12221 If you want a rectangle pyramid, use min manhattan distance from edge (don't need a max height then): 1 + min(i, N-i-1, j, M-j-1) gives: 11111 12221 11111 or for a 7x10 grid: 1111111111 1222222221 1233333321 1234444321 1233333321 1222222221 1111111111 Python 3 code for those who want to test themselves: N = 7 M = 10 for i in range(N): print("".join(str(1 + min(i,j,N-i-1,M-j-1)) for j in range(M)))
- IIAOPSW 9y ago
  This is what I get for trying to work it out in my head and be the first clever person to respond to OP. I like your code. very elegant solution with mins and such.
roel_v 9y ago
Well I would never interview in a style of 'get 5 answers right, you got the job'. So I can't quite tell from your answer :) But yeah that's generally what most working answers would end up like. One interesting aspect is that in some circumstances (I don't remember the details - one of my colleagues did some tests 10 years ago) it was faster to do it this way (iterate over all cells in order, so better cache locality) but in some it was better to 'draw rectangles' as it were, ie first put in all 1's, then all 2's and so on. Requires no floating point ops but more cache misses (iirc).

jwilk 9y ago

> Manhattan Metric Nope. All border cells are supposed to be 0, but they have different Manhattan distances from the center. > Object is an instance of a class Correct.

StevePerkins 9y ago
The question statement above calls for border cells to have a height of "0 or 1". Perhaps to give the candidate some fudge-factor for matrices having an odd number height or width. I realize that this is a contrived testing problem, but to me a pyramid with zeros in the border cells sounds wrong. The area just beyond the border should be zero. Being within bounds of the pyramid intuitively should imply some non-zero height.
- roel_v 9y ago
  Yeah borders being 0 is weird, but it's not material to the question, and for some reason someone once thought this was how it was supposed to work - I never cared about details like that.

SmallDeadGuy 9y ago

Actually, if your M/2 isn't integer division (which I assume is the case from your use of ceil around it first), your 5x5 pyramid would look like this: 23443 34554 45665 45665 34554 Using max_height - (abs(i - floor(M/2)) + abs(j - floor(N/2))) would give the properly-centered pyramid: 23432 34543 45654 34543 23432 Your max height should really be just max(ceil(M/2), ceil(N/2)) for a height of 3 going to 1 at the edges or floor(M/2) for 2 to 0. Using both Manhattan distances gives you an octagon-base pyramid (approximated to the square shape) when really you just want the max of both distances: max_height - max(abs(i - floor(M/2)), abs(j - floor(N/2))) gives: 11111 12221 12321 12221 11111 But this only works for square pyramids, using 3x5 you get: 12221 12321 12221 If you want a rectangle pyramid, use min manhattan distance from edge (don't need a max height then): 1 + min(i, N-i-1, j, M-j-1) gives: 11111 12221 11111 or for a 7x10 grid: 1111111111 1222222221 1233333321 1234444321 1233333321 1222222221 1111111111 Python 3 code for those who want to test themselves: N = 7 M = 10 for i in range(N): print("".join(str(1 + min(i,j,N-i-1,M-j-1)) for j in range(M)))

IIAOPSW 9y ago
This is what I get for trying to work it out in my head and be the first clever person to respond to OP. I like your code. very elegant solution with mins and such.

roel_v 9y ago

Well I would never interview in a style of 'get 5 answers right, you got the job'. So I can't quite tell from your answer :) But yeah that's generally what most working answers would end up like. One interesting aspect is that in some circumstances (I don't remember the details - one of my colleagues did some tests 10 years ago) it was faster to do it this way (iterate over all cells in order, so better cache locality) but in some it was better to 'draw rectangles' as it were, ie first put in all 1's, then all 2's and so on. Requires no floating point ops but more cache misses (iirc).