Randomly partition array into k segments
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given a list of integers and an integer k representing the number of segments, write a function that randomly partitions the list into k non-empty segments and returns them as a list of lists. Explain your approach, discuss its time and space complexity, and describe how you would test the randomness of your solution.
Quick Answer: This question evaluates algorithm design, randomization techniques, and time/space complexity analysis within the Coding & Algorithms domain, focusing on partitioning an array into random non-empty segments.
Given an integer array nums, an integer k (1 <= k <= len(nums)), and a 32-bit unsigned integer seed, return a uniformly random partition of nums into k non-empty contiguous segments. Model the partition as placing k-1 cuts among the n-1 gaps between elements, uniformly over all C(n-1, k-1) choices. For reproducibility, use exactly the following PRNG and sampling method:
- PRNG: 32-bit linear congruential generator (LCG). State is initialized as seed mod 2^32. Each draw sets state = (1664525 * state + 1013904223) mod 2^32 and returns state.
- To draw a uniform integer in [0, m-1], use rejection sampling: let M = 2^32 and limit = (M // m) * m. Repeatedly draw r until r < limit, then return r % m.
- To choose k-1 distinct cut positions uniformly from [1, n-1], use Floyd's algorithm: iterate j from (n-1)-(k-1)+1 to (n-1), pick t uniformly in [1, j]; if t is already chosen, include j; otherwise include t. Sort the selected positions and cut after those indices to form segments.
Constraints
- 1 <= len(nums) <= 100000
- 1 <= k <= len(nums)
- -10^9 <= nums[i] <= 10^9
- 0 <= seed < 2^32
- Output must be k non-empty contiguous subarrays whose concatenation equals nums
Hints
- Reduce the problem to choosing k-1 distinct cut positions among n-1 gaps.
- Use a seeded PRNG to make the output deterministic for testing.
- Floyd's algorithm samples without replacement in O(k) time and O(k) space.
- After selecting cuts, sort them and slice the array accordingly.
- To test randomness quality, run many trials and apply frequency checks (e.g., chi-square) over cut positions.