The Zigzag Encoder

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

Middle rows are visited twice per pass: a rail-fence encoding lays the characters of a message s straight down num_rows rows and then diagonally back up to the top, repeating until the message runs out. Reading the rows top to bottom, each left to right, gives the encoded payload; with a single row there is no bend, so s comes back unchanged.

The message snakes its way across the rails.

Example 1

Input:

s = "PAYPALISHIRING", num_rows = 3

Output:

"PAHNAPLSIIGYIR"

Example 2

Input:

s = "PAYPALISHIRING", num_rows = 4

Output:

"PINALSIGYAHRPI"

Worked solution and explanation

The bounce is the whole problem

This is an index-reflection problem wearing a cipher costume. Everyone sees that characters get spread across rows and read back row by row; what separates candidates is noticing that the path does not wrap from the bottom to the top, it bounces. The row index climbs to num_rows - 1, then falls back toward 0, so one full cycle is 2 * num_rows - 2 characters long and every interior row gets hit twice. Reach for i % num_rows and you have encoded a grid, not a zigzag: every non-trivial case comes back scrambled.

Wrap (wrong)
row = i % num_rows sends rows 0, 1, 2, 0, 1, 2 for three rows. The middle row gets one character per cycle, and 'PAYPALISHIRING' encodes to the wrong string.
Bounce (right)
Rows go 0, 1, 2, 1, 0, 1, 2 for three rows. The cycle is four long, row 1 is visited on the way down and on the way back, and the output is 'PAHNAPLSIIGYIR'.

Building it

Step 1: Return early when nothing can bend

If num_rows <= 1 there is nothing to bounce between, and if num_rows >= len(s) every character sits alone on its own row. Both read back as s itself, so return it before any other work. The first guard also keeps the cycle length 2 * num_rows - 2 from ever being 0.

Step 2: Walk the rows and flip at both edges

One list per row, filled in a single pass. Carry current_row and a going_down flag; after placing a character, flip the flag at row 0 and at row num_rows - 1, then step one row in the current direction. The flip has to happen at BOTH boundaries, or the pointer walks off the end.

Step 3: Read the rows back in order

Join each row's characters, then join the rows top to bottom. Collecting into lists and joining once keeps the pass linear instead of rebuilding strings per character.

Row buckets with a direction flip
def zigzag_encode(s: str, num_rows: int) -> str:
    if num_rows <= 1 or num_rows >= len(s):
        return s
    rows = []
    for i in range(num_rows):
        rows.append([])
    current_row = 0
    going_down = True
    for ch in s:
        rows[current_row].append(ch)
        if current_row == 0:
            going_down = True
        elif current_row == num_rows - 1:
            going_down = False
        if going_down:
            current_row += 1
        else:
            current_row -= 1
    parts = []
    for row in rows:
        parts.append("".join(row))
    result = "".join(parts)
    return result

One pass over s, one join per row, then one final join.

Common follow-up questions