An LSM tree flushes immutable, sorted files called SSTables. The same key can exist in several files, and deletion is represented by a tombstone until compaction has hidden every older copy.
Design an SSTableCompactor class:
SSTableCompactor() creates a stateless compactor.int[][] compact(int[][] older, int[][] newer) merges two SSTables into one sorted result.
Each row is [key, value]. Keys within each segment are unique and sorted in ascending order. The newer segment takes precedence:
- When a key exists in both segments, keep the newer row.
- A newer value of
-1 is a tombstone; remove that key from the output. - Preserve live keys that occur in only one segment.
Example 1:
Input:
Output:
Explanation: Key 3 takes its newer value, key 4 is inserted, and keys 1 and 5 carry through.
Example 2:
Input:
Output:
Explanation: The newer tombstone hides the older value for key 2.
Constraints
0 <= older.length, newer.length <= 10^5- Every row has exactly two integers:
[key, value]. - Keys are unique within a segment and sorted in strictly increasing order.
- Older values are not
-1; a newer value of -1 is a tombstone. - All keys and live values fit in signed 32-bit integers.
- At most
100 calls are made to compact.
Compact Two SSTableshard