← Riot Games Interview Insights

Riot Games·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Jan 2025Remote

Summary

Got an OA from Riot Games for a Software Engineer role back in January. One coding question, pretty straightforward if you know your way around sets.

Questions Asked (1)

Q1

Given a Sudoku row as a vector of integers (values 0-9, where 0 means empty), return all digits from 1 to 9 that are missing from the row. Non-zero values are guaranteed to be unique.

Algorithms & Data Structures
Author's notes

Pretty clean problem once you see it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose an efficient solution using a boolean array or set to track seen digits. Walk through the algorithm step-by-step, analyze time and space complexity, and discuss potential optimizations or alternative approaches.

Pro tip: Mention that since the row is guaranteed to have unique non-zero values, you can use a simple boolean array of size 10 for O(1) lookups, and highlight that this approach is optimal for a single row. Also, briefly discuss how this could scale to validating an entire Sudoku board.

1. Understand the problem

Restate the problem in your own words and confirm assumptions: the row has 9 elements, values 0-9, 0 means empty, non-zero values are unique. Ask clarifying questions if needed.

2. Choose data structure

Decide on a data structure to track which digits 1-9 are present. A boolean array of size 10 or a hash set are both suitable; explain your choice.

3. Design algorithm

Iterate through the row, marking each non-zero digit as seen. Then iterate from 1 to 9 and collect digits that are not marked.

4. Analyze complexity

State that the algorithm runs in O(n) time and O(1) space (since n=9 is constant), and explain why this is optimal.

5. Discuss edge cases and extensions

Mention edge cases like all digits present (return empty list) or all zeros (return 1-9). Optionally, discuss how to extend to validate a full Sudoku board.

Key Points to Mention

  • Use a boolean array of size 10 for O(1) membership checks.
  • Time complexity: O(n) where n is the number of elements (9).
  • Space complexity: O(1) since the array size is fixed.
  • Edge cases: empty row (all zeros), full row (no missing digits).
  • Alternative: use a set or bit manipulation for tracking.
  • Scalability: adapting the approach to check rows, columns, and subgrids in a full Sudoku.

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