All right boys, it's time for an interview programming question to get your brain fired up again:

All right boys, it's time for an interview programming question to get your brain fired up again:

You are given a grid of numbers, and you have to write a function that takes as input a two dimensional array and returns a single dimensional array that is all the diagonals in zig zag order.

In this example the input is [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]. And your code should produce the output [1, 2, 6, 11, 7, 3, 4, 8, 12, 16, 17, 13, 9, 5, 10, 14, 18, 19, 15, 20]. Use any programming language you like.

Attached: problem.jpg (500x300, 39.67K)

Other urls found in this thread:

en.wikipedia.org/wiki/Z-order_curve
gist.github.com/K-C-DaCosta/8458b12dde87c97b09d1bf7da4a5a47e
twitter.com/SFWRedditVideos

not doing your homework

It's not homework. I'm getting myself ready for interviews to get out of neetdom. Solved this one today, not as easy as it first seems.

Not writing the jpeg compressor for your homework.

en.wikipedia.org/wiki/Z-order_curve

this isn't interesting it's been solved already

thats not the same curve. Z-order is clearly recursive

ok here's my idea and tell me what you think. i didnt put down anything into code, just brainstormed
any 2D array will have x+y-1 number of diagonals in this problem, so i would loop that many times.
the loop would move along the pic related (just increment X, and if that would put it over max X then increment Y instead)
each loop id put the current diagonal in a temp array (always going from top right to bot left), every other time id swap the order of that temp array,
and at the end of the loop id concat that temp array to the 1D one.

Attached: e.png (390x295, 86.3K)

Algorithm is the following. Keep track of which direction you are walking in. Try to take one step in that direction.
If you bump into right edge, then take a step to the down instead and change directions
elseif you bump into top edge, then take a step to right and change firections.
elseif you bump into the bottom edge then take a step to the right and change directions
elseif you bump into left edge then take a step down and change directions.

that's good thinking, see if you can write out actual code that does it

I tried this first, it's a real pain in the ass to deal with edge cases. But maybe I'm too dumb to figure it out.

I'd do this with a state machine. first set is move right if possible otherwise down then goto second state. second state is move down and left if possible otherwise down and goto third state. third set is move up and right if possible otherwise go to first state.

Or something like that anyway

Fine... I'll hand it to you
def dothing(w, h):

def get_value(x, y):
return x + w * y + 1

x, y, d = 0, 0, 1

for _ in range(w * h):
yield get_value(x, y)
if d == 1 and x == w - 1:
y += 1
d = -1
elif d == 1 and y == 0:
x += 1
d = -1
elif d == -1 and y == h - 1:
x += 1
d = 1
elif d == -1 and x == 0:
y += 1
d = 1
else:
x += d
y -= d

print(list(dothing(5, 4)))

10 PRINT "[1, 2, 6, 11, 7, 3, 4, 8, 12, 16, 17, 13, 9, 5, 10, 14, 18, 19, 15, 20]"
20 GOTO 10

Attached: NAT-MF-ROYAL-LUCK-SUSPECT-1590818274760_17264287dc8_medium.jpg (540x405, 24.79K)

What language is this?

I tried making it stateless by swapping indexes (0,j)->(0,j) and using column parity to compute direction and starting point. Turns out that shit only works for square matrices or something. So i had to FORCE the matrix square before running the routine.

It wound up being messier than I imagined.

gist.github.com/K-C-DaCosta/8458b12dde87c97b09d1bf7da4a5a47e

Attached: sol.png (1858x2806, 568.78K)

hey, not bad. Although the input and output is different from what the question asks. I did a slightly different approach based on this property: if you sum the coordinates of every number on a diagonal, they add up to the same number. For example (0,3), (1, 2), (2, 1), and (3, 0) are one diagonal, and the sum of their indices is 3 . Rest is self explanatory:

def diags(matrix):
diagonal = []
n = len(matrix)
m = len(matrix[0])
up = True
indexsum = {}

for x in range(n):
for y in range(m):
if x + y not in indexsum:
indexsum[x + y] = []
indexsum[x + y].append(matrix[x][y])

for sum_of_indicies in range(0, m + n - 1):
if up:
for i in range(len(indexsum[sum_of_indicies])-1, -1, -1):
diagonal.append(indexsum[sum_of_indicies][i])
else:
for i in range(len(indexsum[sum_of_indicies])):
diagonal.append(indexsum[sum_of_indicies][i])

up = not up

return diagonal

print(diags([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]))

holy shit that is complicated

That is what happens when the first idea you come up with is bad idea and you run just with it to see where it goes.

t. the guy who posted that abomination.

BASIC

>Job interview
Too hard, next question.

alright i fixed this piece of shit.

I actually dont think it was a bad idea now that I think about it.

Basically it works by knowing that a transpose of a given the top row (0,j) of a square matrix (j,0) is the opposite end of the diagonal. You can use the column parity to start at (0,j) and (j,0) in a stateless fashion.

Problem is ... this only works for SQUARE matrices.

The solution is to FORCE the matrix to be square.
But there's another problem: It only prints upper triangular part of the square.

Solution is to DOUBLE the size of the "virtual matrix" in order to get the lower half of it.

Attached: sol_fixed.png (1512x2434, 436.71K)