Amazon SDE I Interview Leetcode Question
- Posted
- 7 Jul 2020
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.
How it went
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.
Questions asked (1)
- 01
Random Number from Unsorted, Non-Overlapping Intervals
Data Structures & Algorithms
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