Amazon SDE I Interview Leetcode Question
Summary
I wanted to share a unique LeetCode-style question from my Amazon SDE I interview that I couldn't find elsewhere, hoping it helps others with their practice.
Full Experience
During my past interview experience for an SDE I role at Amazon, I encountered a rather interesting coding question. I'm sharing it here, paraphrased as accurately as possible, as I believe it presents a good challenge for interview preparation, especially since it wasn't readily available on LeetCode. I found the constraints on time and space particularly thought-provoking.
Interview Questions (1)
Suppose I have a list of intervals that is unsorted and non-overlapping (start, end), intervals, produce a random int within the intervals where each number in the interval has a uniform distribution.
Challenge: in O(n) time?
Bigger Challenge: in O(1) space?
Example:intervals = [(7,9),(3, 5)]Possible results include: [3,4,5,7,8,9] omit 6