Amazon Coding Question - Insert Delete GetRandom O(1)

🎧 Join the community Discord: https://discord.gg/aVWsAaaCtT
💰 Support me on Patreon: https://www.patreon.com/michaelmuinos
🔗Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos
📂Follow me on Github: https://github.com/MichaelMuinos

Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: https://algoswithmichael.com

For this video, I go over the popular coding interview problem "Insert Delete GetRandom O(1)" found on the LeetCode platform. This problem is asked at many tech companies including Amazon, Bloomberg, Facebook, Oracle, and Twitter. This coding question is a design problem that tests your knowledge of the arraylist and map data structures.

We have to implement three different functions: insert, remove, and get random. Insert will take a value and insert it inside of a data structure. Remove will take a value and remove it from the data structure. Get random will return a random element from our data structure where each element must have an equal probability of being chosen.

The time complexity of the optimal approach will be O(1) constant time since we are using a map to store the elements with their appropriate indices and only removing the last element in our arraylist. The space complexity will be linear where N is the number of entries we have in our map and list.

Видео Amazon Coding Question - Insert Delete GetRandom O(1) канала AlgosWithMichael