← 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. Just one coding problem, pretty approachable if you know your basic set operations.

Questions Asked (1)

Q1

Given a Sudoku row as a list of integers (0 through 9, where 0 means empty), return all digits from 1 to 9 that are missing from the row.

Algorithms & Data Structures
Author's notes

Pretty straightforward once you see it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the row may contain duplicates and zeros, and that we need to return missing digits in any order. Use a boolean array or set to mark present digits, then collect the unmarked digits from 1 to 9. Alternatively, compute the sum of 1..9 and subtract the sum of unique non-zero digits, but that only works if no duplicates; so prefer the marking approach for robustness.

Pro tip: Mention that you would validate the input (e.g., length 9, values 0-9) and discuss trade-offs between using a boolean array (O(1) space) and a set (more flexible but higher constant). Also, note that duplicates don't affect the missing digits, so you can ignore them.

1. Understand the problem and constraints

Confirm that the row is length 9, values are 0-9, and 0 represents an empty cell. Clarify that duplicates may exist and should be ignored when determining missing digits.

2. Choose a data structure to track presence

Use a boolean array of size 10 (index 1-9) or a set to mark which digits are present. Iterate through the row and mark each non-zero digit.

3. Collect missing digits

Iterate from 1 to 9 and add any digit not marked as present to the result list.

4. Analyze complexity and edge cases

State that time complexity is O(n) where n=9 (constant), space O(1). Discuss edge cases: all digits present (empty result), all zeros (return 1-9), duplicates.

5. Test with examples

Walk through a sample row, e.g., [1,2,3,4,5,6,7,8,9] returns [], [0,0,0,0,0,0,0,0,0] returns [1..9], and [1,1,2,3,4,5,6,7,8] returns [9].

Key Points to Mention

  • Input validation: ensure row length is 9 and values are within 0-9.
  • Handling duplicates: duplicates do not affect the set of missing digits.
  • Time and space complexity: O(1) since the input size is fixed.
  • Choice of data structure: boolean array vs. set, and why boolean array is efficient here.
  • Edge cases: all digits present, all zeros, duplicates.
  • Alternative approaches: sum of 1..9 minus sum of unique digits (but note duplicates issue).

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