TikTok·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

TikTok coding round for a Software Engineer role. One problem, matrix-based, and the catch was they explicitly told you not to just flatten and sort. That constraint is where things get interesting or, depending on how you think, stressful.

Questions Asked (1)

Given an n x m matrix where every row and column is sorted in non-decreasing order, find the k-th smallest element. You must do better than flattening the whole matrix and sorting it.

Algorithms & Data Structures

Author's notes

The 'do better than full sort' constraint is the whole problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search on the value range to find the k-th smallest element, counting how many elements are ≤ mid in O(n+m) time. Alternatively, use a min-heap to merge the sorted rows and extract k elements. Discuss trade-offs and optimize for the given constraints.

Pro tip: Clarify constraints upfront (e.g., matrix size, k range) to choose the best approach. Mention that the binary search method is O((n+m) log(max-min)) and the heap method is O(k log n), and pick based on expected k.

1. Clarify constraints and edge cases

Ask about matrix dimensions, value ranges, and whether k is 1-indexed. Discuss edge cases like k=1, k=n*m, or empty matrix.

2. Propose binary search on value range

Explain that you can binary search the answer between the smallest and largest elements. For each mid, count elements ≤ mid in O(n+m) by starting from the bottom-left corner.

3. Detail the counting function

Describe how to count elements ≤ mid: start at bottom-left, move up if current > mid, else move right and add (current row index + 1) to count. This leverages row and column sorting.

4. Discuss alternative heap approach

Mention using a min-heap to merge rows: push first element of each row, then pop and push next from same row k times. Compare time and space complexity with binary search.

5. Analyze complexity and choose

State time and space complexities for both methods. Recommend binary search for large k or when value range is small, and heap for small k. Code the chosen solution.

Key Points to Mention

Binary search on value range with O(n+m) counting per step
Counting elements ≤ mid using staircase search from bottom-left
Min-heap approach for merging sorted rows
Time complexity: O((n+m) log(max-min)) vs O(k log n)
Space complexity: O(1) for binary search, O(n) for heap
Handling duplicates and ensuring k-th smallest definition

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.