### Posts from the “Algorithm” Category

Stuck at storyboarding of animated film n not know how to fix the issue.

Next: just draw. Draw anything you like. Then you’ll come up with the idea

Design a data structure that supports all following operations in average O(1) time.

1. `insert(val)`: Inserts an item val to the set if not already present.
2. `remove(val)`: Removes an item val from the set if present.
3. `getRandom`: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Discussion:

In C++, containers supporting insert with O(1) are vector, list, unordered_map, and unordered_set.

Containers remove by value with O(1) are unordered_map, unordered_set.

Container supporting random access is vector.

So, we can use vector AND unordered_set or unordered_map for the three functions. Then unordered_set or unordered_map? We have to use vector to store the values for the sake of random access with O(1). And a hash container (unordered_set, or unordered_map) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so unordered_map wins: reference the same value in the vector by the value’s position.

insert and random access can easily being done with O(1) for vector and unordered_map. But for remove, it affects the unordered_map‘s reference in the vector. The instinct is removing the value from the vector by getting its position from unordered_map. But this will decrease the positions of all descending elements in the vector, which affects the references of the unordered_map. The time complexity could be up to linear O(n) if we do position update in the unordered_map, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the vector, and updating the last element’s value in the unordered_map with the new position.  exactly O(1) on average.

This is a LeetCode problem:

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

It is not hard to come out a solution with O(m + n) or O(log(m + n)), but it’s really tricky to deal with boundary conditions.

A O(log(m + n)) solution should use something like binary search. I referenced an answer in the discussion board, and wrote my O(log(m + n)) solution. The idea is to make the median index as the k of the k-lowest search problem. For even length, the two median indices are (m + n + 1) >> 1 and (m + n + 2) >> 1; for odd length, (m + n + 1) >> 1 and (m + n + 2) >> 1 yield the same results! That’s really clever. With the median index, we find the k-lowest value in a recursion function. Here is the code: For the brute force solution, with O(m + n) complexity, we keep sorting the two arrays by comparing the current values until we reach the median index: 