Source:
Problem 1.9

Problem Description:
Reserve a set of memory without initialization, meaning the data in there is random. Name the memory as ‘data’.
Design a mechanism to track and tell whether given index in data is initialized or not.

Algorithm 1:
1. Use a set data structure (naming it to initialized_set) to store initialized indices. Initially it is empty.
2. Write value to data[i]: need to initialized_set.add(i)
3. Access value at data[i]: need to check initialized_set.has(i)
Flaw: ops on initialized_set are O(logN).

Algorithm 2:
Purpose: to reduce op cost on initialized_set from O(logN) to O(N).
1. Use array initialized_arr to store initialized indices. Initially it has length of len(data).
2. Use array track_positions: track_positions[i] stores index in initialized_arr, i.e. initialized_arr[track_positions[i]] should equal to i if data[i] is initialized. Initially it has length of len(data).
3. Use a int variable ‘track’ to indicate (assert) initialized_set[0:track] is valid set.
4. Write value to data[i]: need to set initialized_arr[track] = i; track_positions[i] = track; track += 1.
5. Access value at data[i]: need to check initialized_arr[track_positions[i]] == i && track > track_positions[i]