Hash-Table

Intuition Create a map with the integer and the roman value of that integer, loop through the reversed array, treating the special cases (4 and 9) Approach Conver the number to a string then reverse it. Once reversed, create a base variable to store whether the digit is 1s, 10s, 100s, 1000s. Loop through each digit (d) getting the equivalent in roman: if d > 9 or d>4, return map[1*base] + map[(d+1)*base] if d > 5, store map[5*base], decrease d while d > 0 concat map[1*base] return stored roman Complexity Time complexity: O(n) ...

Intuition First thought was to use a dictionary(hashmap) to keep track of the items, however the random is an issue, since we need to convert the dictionary into a list to get a random item. Approach In order to achieve time complexity near O(1) we need to use two structures. One dictionary for fast deletion, and a list for fast randomization. The trick that makes the possible is to remove an element from a list in O(1), and this is achieved by u ...