Mock Coding Interview Simulation

1// Mock interview example: Design an iterator for a 2D matrix
2// that traverses in spiral order
3
4// Step 1: Understand — I need to traverse a matrix in spiral order
5// and return elements one at a time via next() and hasNext()
6
7// Step 2: Plan — Pre-compute the spiral order in the constructor,
8// then iterate through the precomputed list. Alternative: maintain
9// boundaries and compute on-the-fly (more complex but O(1) space).
10
11// Step 3: Code
12class SpiralIterator(matrix: Array<IntArray>) : Iterator<Int> {
13    private val elements = mutableListOf<Int>()
14    private var index = 0
15    
16    init {
17        if (matrix.isNotEmpty() && matrix[0].isNotEmpty()) {
18            var top = 0
19            var bottom = matrix.size - 1
20            var left = 0
21            var right = matrix[0].size - 1
22            
23            while (top <= bottom && left <= right) {
24                // Right
25                for (col in left..right) elements.add(matrix[top][col])
26                top++
27                // Down
28                for (row in top..bottom) elements.add(matrix[row][right])
29                right--
30                // Left
31                if (top <= bottom) {
32                    for (col in right downTo left) elements.add(matrix[bottom][col])
33                    bottom--
34                }
35                // Up
36                if (left <= right) {
37                    for (row in bottom downTo top) elements.add(matrix[row][left])
38                    left++
39                }
40            }
41        }
42    }
43    
44    override fun hasNext(): Boolean = index < elements.size
45    override fun next(): Int {
46        if (!hasNext()) throw NoSuchElementException()
47        return elements[index++]
48    }
49}
50
51// Step 4: Test
52// Input: [[1,2,3],[4,5,6],[7,8,9]]
53// Expected: 1,2,3,6,9,8,7,4,5
54// Edge: empty matrix → hasNext() = false
55// Edge: single row → 1,2,3
56// Edge: single column → 1,4,7
57
58// Step 5: Discuss
59// Time: O(m*n) constructor, O(1) next/hasNext
60// Space: O(m*n) for stored elements
61// Trade-off: Could compute on-the-fly with O(1) space but more complex