Designing with History
Editorial
Every snapshot a full copy
Snapshot Array asks for an array you can change, freeze as a numbered snapshot, and read later as it was in any snapshot. The obvious way keeps a copy of the whole array for every snap. Here it is beside one that keeps only each cell's changes, on the same calls: 1,000 rounds of one set and one snap on 5,000 cells, then 5,000 reads at random snapshots:
import bisect
import time
CELLS, SNAPS, GETS = 5000, 1000, 5000
class CopySnapshots: # the whole array copied at every snap
def __init__(self, length):
self.cells, self.copies = [0] * length, []
def set(self, index, val):
self.cells[index] = val
def snap(self):
self.copies.append(self.cells[:])
return len(self.copies) - 1
def get(self, index, snap_id):
return self.copies[snap_id][index]
def stored(self):
return sum(len(c) for c in self.copies)
class HistorySnapshots: # each cell keeps only its changes, in snap order
def __init__(self, length):
self.snap_ids = [[] for _ in range(length)]
self.values = [[] for _ in range(length)]
self.snap_id = 0
def set(self, index, val):
ids, vals = self.snap_ids[index], self.values[index]
if ids and ids[-1] == self.snap_id: # set twice in one snap: the later value wins
vals[-1] = val
else:
ids.append(self.snap_id)
vals.append(val)
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
i = bisect.bisect_right(self.snap_ids[index], snap_id) - 1 # the last change at or before snap_id
return self.values[index][i] if i >= 0 else 0
def stored(self):
return sum(len(v) for v in self.values)
def run(kind): # the same calls in every language: a set and a snap, a thousand times
start, x, total = time.perf_counter(), 7, 0
s = kind(CELLS)
for _ in range(SNAPS):
x = x * 48271 % 2147483647
index = x % CELLS
x = x * 48271 % 2147483647
s.set(index, x % 1000)
s.snap()
for _ in range(GETS):
x = x * 48271 % 2147483647
index = x % CELLS
x = x * 48271 % 2147483647
total += s.get(index, x % SNAPS)
ms = (time.perf_counter() - start) * 1000
print(f"{kind.__name__:16} {s.stored():>7} values stored, reads add up to {total}, {ms:.0f} ms")
run(CopySnapshots)
run(HistorySnapshots)
# CopySnapshots 5000000 values stored, reads add up to 235499, 30 ms
# HistorySnapshots 1000 values stored, reads add up to 235499, 4 msimport java.util.*;
public class Main {
static final int CELLS = 5000, SNAPS = 1000, GETS = 5000;
interface Snapshots {
void set(int index, int val);
int snap();
int get(int index, int snapId);
long stored();
}
static class CopySnapshots implements Snapshots { // the whole array copied at every snap
final int[] cells;
final List<int[]> copies = new ArrayList<>();
CopySnapshots(int length) { cells = new int[length]; }
public void set(int index, int val) { cells[index] = val; }
public int snap() {
copies.add(cells.clone());
return copies.size() - 1;
}
public int get(int index, int snapId) { return copies.get(snapId)[index]; }
public long stored() { return (long) copies.size() * cells.length; }
}
static class HistorySnapshots implements Snapshots { // each cell keeps only its changes, in snap order
final List<List<Integer>> snapIds = new ArrayList<>(), values = new ArrayList<>();
int snapId = 0;
HistorySnapshots(int length) {
for (int i = 0; i < length; i++) {
snapIds.add(new ArrayList<>());
values.add(new ArrayList<>());
}
}
public void set(int index, int val) {
List<Integer> ids = snapIds.get(index), vals = values.get(index);
if (!ids.isEmpty() && ids.get(ids.size() - 1) == snapId) vals.set(vals.size() - 1, val); // set twice in one snap
else {
ids.add(snapId);
vals.add(val);
}
}
public int snap() { return snapId++; }
public int get(int index, int snapId) {
List<Integer> ids = snapIds.get(index);
int lo = 0, hi = ids.size(); // the first change after snapId
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ids.get(mid) <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? values.get(index).get(lo - 1) : 0; // the one before it is the last at or before
}
public long stored() {
long n = 0;
for (List<Integer> v : values) n += v.size();
return n;
}
}
static void run(String name, Snapshots s) { // the same calls in every language: a set and a snap, a thousand times
long start = System.nanoTime(), x = 7, total = 0;
for (int k = 0; k < SNAPS; k++) {
x = x * 48271 % 2147483647;
int index = (int) (x % CELLS);
x = x * 48271 % 2147483647;
s.set(index, (int) (x % 1000));
s.snap();
}
for (int k = 0; k < GETS; k++) {
x = x * 48271 % 2147483647;
int index = (int) (x % CELLS);
x = x * 48271 % 2147483647;
total += s.get(index, (int) (x % SNAPS));
}
long ms = (System.nanoTime() - start) / 1000000;
System.out.printf("%-16s %7d values stored, reads add up to %d, %d ms%n", name, s.stored(), total, ms);
}
public static void main(String[] args) {
run("CopySnapshots", new CopySnapshots(CELLS));
run("HistorySnapshots", new HistorySnapshots(CELLS));
}
}
// CopySnapshots 5000000 values stored, reads add up to 235499, 24 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 3 ms#include <bits/stdc++.h>
using namespace std;
const int CELLS = 5000, SNAPS = 1000, GETS = 5000;
struct CopySnapshots { // the whole array copied at every snap
vector<int> cells;
vector<vector<int>> copies;
CopySnapshots(int length) : cells(length) {}
void set(int index, int val) { cells[index] = val; }
int snap() {
copies.push_back(cells);
return copies.size() - 1;
}
int get(int index, int snapId) { return copies[snapId][index]; }
long long stored() { return (long long) copies.size() * cells.size(); }
};
struct HistorySnapshots { // each cell keeps only its changes, in snap order
vector<vector<int>> snapIds, values;
int snapId = 0;
HistorySnapshots(int length) : snapIds(length), values(length) {}
void set(int index, int val) {
auto &ids = snapIds[index], &vals = values[index];
if (!ids.empty() && ids.back() == snapId) vals.back() = val; // set twice in one snap: the later value wins
else {
ids.push_back(snapId);
vals.push_back(val);
}
}
int snap() { return snapId++; }
int get(int index, int snapId) {
auto& ids = snapIds[index];
int i = upper_bound(ids.begin(), ids.end(), snapId) - ids.begin() - 1; // the last change at or before snapId
return i >= 0 ? values[index][i] : 0;
}
long long stored() {
long long n = 0;
for (auto& v : values) n += v.size();
return n;
}
};
template <class Snapshots> void run(const char* name) { // the same calls in every language: a set and a snap, a thousand times
auto start = chrono::steady_clock::now();
long long x = 7, total = 0;
Snapshots s(CELLS);
for (int k = 0; k < SNAPS; k++) {
x = x * 48271 % 2147483647;
int index = x % CELLS;
x = x * 48271 % 2147483647;
s.set(index, x % 1000);
s.snap();
}
for (int k = 0; k < GETS; k++) {
x = x * 48271 % 2147483647;
int index = x % CELLS;
x = x * 48271 % 2147483647;
total += s.get(index, x % SNAPS);
}
long long ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
printf("%-16s %7lld values stored, reads add up to %lld, %lld ms\n", name, s.stored(), total, ms);
}
int main() {
run<CopySnapshots>("CopySnapshots");
run<HistorySnapshots>("HistorySnapshots");
}
// CopySnapshots 5000000 values stored, reads add up to 235499, 12 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 0 msconst CELLS = 5000, SNAPS = 1000, GETS = 5000;
class CopySnapshots { // the whole array copied at every snap
constructor(length) {
this.cells = new Array(length).fill(0);
this.copies = [];
}
set(index, val) { this.cells[index] = val; }
snap() {
this.copies.push(this.cells.slice());
return this.copies.length - 1;
}
get(index, snapId) { return this.copies[snapId][index]; }
stored() { return this.copies.length * this.cells.length; }
}
class HistorySnapshots { // each cell keeps only its changes, in snap order
constructor(length) {
this.snapIds = Array.from({ length }, () => []);
this.values = Array.from({ length }, () => []);
this.snapId = 0;
}
set(index, val) {
const ids = this.snapIds[index], vals = this.values[index];
if (ids.length && ids[ids.length - 1] === this.snapId) vals[vals.length - 1] = val; // set twice in one snap
else {
ids.push(this.snapId);
vals.push(val);
}
}
snap() { return this.snapId++; }
get(index, snapId) {
const ids = this.snapIds[index];
let lo = 0, hi = ids.length; // the first change after snapId
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? this.values[index][lo - 1] : 0; // the one before it is the last at or before
}
stored() { return this.values.reduce((n, v) => n + v.length, 0); }
}
function run(Kind) { // the same calls in every language: a set and a snap, a thousand times
const start = performance.now();
let x = 7, total = 0;
const s = new Kind(CELLS);
for (let k = 0; k < SNAPS; k++) {
x = x * 48271 % 2147483647;
const index = x % CELLS;
x = x * 48271 % 2147483647;
s.set(index, x % 1000);
s.snap();
}
for (let k = 0; k < GETS; k++) {
x = x * 48271 % 2147483647;
const index = x % CELLS;
x = x * 48271 % 2147483647;
total += s.get(index, x % SNAPS);
}
const ms = Math.round(performance.now() - start);
console.log(`${Kind.name.padEnd(16)} ${String(s.stored()).padStart(7)} values stored, reads add up to ${total}, ${ms} ms`);
}
run(CopySnapshots);
run(HistorySnapshots);
// CopySnapshots 5000000 values stored, reads add up to 235499, 58 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 4 msconst CELLS = 5000, SNAPS = 1000, GETS = 5000;
interface Snapshots {
set(index: number, val: number): void;
snap(): number;
get(index: number, snapId: number): number;
stored(): number;
}
class CopySnapshots implements Snapshots { // the whole array copied at every snap
cells: number[];
copies: number[][] = [];
constructor(length: number) { this.cells = new Array(length).fill(0); }
set(index: number, val: number): void { this.cells[index] = val; }
snap(): number {
this.copies.push(this.cells.slice());
return this.copies.length - 1;
}
get(index: number, snapId: number): number { return this.copies[snapId][index]; }
stored(): number { return this.copies.length * this.cells.length; }
}
class HistorySnapshots implements Snapshots { // each cell keeps only its changes, in snap order
snapIds: number[][];
values: number[][];
snapId = 0;
constructor(length: number) {
this.snapIds = Array.from({ length }, () => []);
this.values = Array.from({ length }, () => []);
}
set(index: number, val: number): void {
const ids = this.snapIds[index], vals = this.values[index];
if (ids.length && ids[ids.length - 1] === this.snapId) vals[vals.length - 1] = val; // set twice in one snap
else {
ids.push(this.snapId);
vals.push(val);
}
}
snap(): number { return this.snapId++; }
get(index: number, snapId: number): number {
const ids = this.snapIds[index];
let lo = 0, hi = ids.length; // the first change after snapId
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? this.values[index][lo - 1] : 0; // the one before it is the last at or before
}
stored(): number { return this.values.reduce((n, v) => n + v.length, 0); }
}
function run(name: string, s: Snapshots): void { // the same calls in every language: a set and a snap, a thousand times
const start = performance.now();
let x = 7, total = 0;
for (let k = 0; k < SNAPS; k++) {
x = x * 48271 % 2147483647;
const index = x % CELLS;
x = x * 48271 % 2147483647;
s.set(index, x % 1000);
s.snap();
}
for (let k = 0; k < GETS; k++) {
x = x * 48271 % 2147483647;
const index = x % CELLS;
x = x * 48271 % 2147483647;
total += s.get(index, x % SNAPS);
}
const ms = Math.round(performance.now() - start);
console.log(`${name.padEnd(16)} ${String(s.stored()).padStart(7)} values stored, reads add up to ${total}, ${ms} ms`);
}
run("CopySnapshots", new CopySnapshots(CELLS));
run("HistorySnapshots", new HistorySnapshots(CELLS));
// CopySnapshots 5000000 values stored, reads add up to 235499, 59 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 3 msusing System;
using System.Collections.Generic;
using System.Diagnostics;
interface ISnapshots {
void Set(int index, int val);
int Snap();
int Get(int index, int snapId);
long Stored();
}
class CopySnapshots : ISnapshots { // the whole array copied at every snap
readonly int[] cells;
readonly List<int[]> copies = new List<int[]>();
public CopySnapshots(int length) { cells = new int[length]; }
public void Set(int index, int val) { cells[index] = val; }
public int Snap() {
copies.Add((int[]) cells.Clone());
return copies.Count - 1;
}
public int Get(int index, int snapId) => copies[snapId][index];
public long Stored() => (long) copies.Count * cells.Length;
}
class HistorySnapshots : ISnapshots { // each cell keeps only its changes, in snap order
readonly List<int>[] snapIds, values;
int snapId = 0;
public HistorySnapshots(int length) {
snapIds = new List<int>[length];
values = new List<int>[length];
for (int i = 0; i < length; i++) {
snapIds[i] = new List<int>();
values[i] = new List<int>();
}
}
public void Set(int index, int val) {
List<int> ids = snapIds[index], vals = values[index];
if (ids.Count > 0 && ids[ids.Count - 1] == snapId) vals[vals.Count - 1] = val; // set twice in one snap
else {
ids.Add(snapId);
vals.Add(val);
}
}
public int Snap() => snapId++;
public int Get(int index, int snapId) {
List<int> ids = snapIds[index];
int lo = 0, hi = ids.Count; // the first change after snapId
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? values[index][lo - 1] : 0; // the one before it is the last at or before
}
public long Stored() {
long n = 0;
foreach (var v in values) n += v.Count;
return n;
}
}
class Program {
const int CELLS = 5000, SNAPS = 1000, GETS = 5000;
static void Run(string name, ISnapshots s) { // the same calls in every language: a set and a snap, a thousand times
var watch = Stopwatch.StartNew();
long x = 7, total = 0;
for (int k = 0; k < SNAPS; k++) {
x = x * 48271 % 2147483647;
int index = (int) (x % CELLS);
x = x * 48271 % 2147483647;
s.Set(index, (int) (x % 1000));
s.Snap();
}
for (int k = 0; k < GETS; k++) {
x = x * 48271 % 2147483647;
int index = (int) (x % CELLS);
x = x * 48271 % 2147483647;
total += s.Get(index, (int) (x % SNAPS));
}
Console.WriteLine($"{name,-16} {s.Stored(),7} values stored, reads add up to {total}, {watch.ElapsedMilliseconds} ms");
}
static void Main() {
Run("CopySnapshots", new CopySnapshots(CELLS));
Run("HistorySnapshots", new HistorySnapshots(CELLS));
}
}
// CopySnapshots 5000000 values stored, reads add up to 235499, 19 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 1 mspackage main
import (
"fmt"
"sort"
"time"
)
const CELLS, SNAPS, GETS = 5000, 1000, 5000
type Snapshots interface {
Set(index, val int)
Snap() int
Get(index, snapID int) int
Stored() int
}
type CopySnapshots struct { // the whole array copied at every snap
cells []int
copies [][]int
}
func (s *CopySnapshots) Set(index, val int) { s.cells[index] = val }
func (s *CopySnapshots) Snap() int {
s.copies = append(s.copies, append([]int(nil), s.cells...))
return len(s.copies) - 1
}
func (s *CopySnapshots) Get(index, snapID int) int { return s.copies[snapID][index] }
func (s *CopySnapshots) Stored() int { return len(s.copies) * len(s.cells) }
type HistorySnapshots struct { // each cell keeps only its changes, in snap order
snapIDs, values [][]int
snapID int
}
func (s *HistorySnapshots) Set(index, val int) {
ids := s.snapIDs[index]
if len(ids) > 0 && ids[len(ids)-1] == s.snapID { // set twice in one snap: the later value wins
s.values[index][len(ids)-1] = val
return
}
s.snapIDs[index] = append(ids, s.snapID)
s.values[index] = append(s.values[index], val)
}
func (s *HistorySnapshots) Snap() int {
s.snapID++
return s.snapID - 1
}
func (s *HistorySnapshots) Get(index, snapID int) int {
ids := s.snapIDs[index]
i := sort.Search(len(ids), func(k int) bool { return ids[k] > snapID }) - 1 // the last change at or before snapID
if i < 0 {
return 0
}
return s.values[index][i]
}
func (s *HistorySnapshots) Stored() int {
n := 0
for _, v := range s.values {
n += len(v)
}
return n
}
func run(name string, s Snapshots) { // the same calls in every language: a set and a snap, a thousand times
start := time.Now()
x, total := int64(7), 0
for k := 0; k < SNAPS; k++ {
x = x * 48271 % 2147483647
index := int(x % CELLS)
x = x * 48271 % 2147483647
s.Set(index, int(x%1000))
s.Snap()
}
for k := 0; k < GETS; k++ {
x = x * 48271 % 2147483647
index := int(x % CELLS)
x = x * 48271 % 2147483647
total += s.Get(index, int(x%SNAPS))
}
fmt.Printf("%-16s %7d values stored, reads add up to %d, %d ms\n", name, s.Stored(), total, time.Since(start).Milliseconds())
}
func main() {
run("CopySnapshots", &CopySnapshots{cells: make([]int, CELLS)})
run("HistorySnapshots", &HistorySnapshots{snapIDs: make([][]int, CELLS), values: make([][]int, CELLS)})
}
// CopySnapshots 5000000 values stored, reads add up to 235499, 27 ms
// HistorySnapshots 1000 values stored, reads add up to 235499, 0 msBoth answered every read the same, the reads adding up to 235,499 in all seven languages. The copies stored 5,000,000 values, 5,000 for each snapshot, to keep 1,000 changes; the histories stored 1,000, one per set. The copies were also the slower: 30 against 4 ms in Python, 12 against 0 in C++, each snap copying 5,000 cells whatever changed.
The trouble is that a copy stores what didn't change, again and again. Write down only what changed, and when, and the past is still all there: to read a cell as it was, find its last change at or before that time. This lesson is that one idea in the designs that need it: values read at a time or a version, counts over a recent window, a history you walk back and forth, and a record that has to survive being written out.
A history per key, read with binary search
Time Based Key-Value Store keeps a value per key at each timestamp and asks for the value a key had at time t: the one set at the latest time at or before t. Keep, per key, its timestamps in a list and its values beside them. The timestamps arrive in increasing order, so the list is sorted without ever sorting it, and the read is one binary search for the last time at or before t, the last yes of Introduction to Binary Search. Beside it, the read people write by mistake, the first time at or after t:
import bisect
class TimeMap:
def __init__(self):
self.times = {} # key -> its timestamps, increasing as they're set
self.values = {} # key -> the value set at each of those times
def set(self, key, value, timestamp):
self.times.setdefault(key, []).append(timestamp)
self.values.setdefault(key, []).append(value)
def get(self, key, timestamp):
times = self.times.get(key, [])
i = bisect.bisect_right(times, timestamp) - 1 # the last time at or before timestamp
return self.values[key][i] if i >= 0 else ""
def get_next(self, key, timestamp): # the mistake: the first time at or after timestamp
times = self.times.get(key, [])
i = bisect.bisect_left(times, timestamp)
return self.values[key][i] if i < len(times) else ""
m = TimeMap()
for value, t in (("18C", 5), ("21C", 9), ("17C", 14)):
m.set("temp", value, t)
for t in (3, 5, 8, 9, 20):
print(f"get(temp, {t}) = {m.get('temp', t) or '(nothing)'}; the next version: {m.get_next('temp', t) or '(nothing)'}")
print(f"get(rain, 10) = {m.get('rain', 10) or '(nothing)'}")
# get(temp, 3) = (nothing); the next version: 18C
# get(temp, 5) = 18C; the next version: 18C
# get(temp, 8) = 18C; the next version: 21C
# get(temp, 9) = 21C; the next version: 21C
# get(temp, 20) = 17C; the next version: (nothing)
# get(rain, 10) = (nothing)import java.util.*;
public class Main {
static class TimeMap {
final Map<String, List<Integer>> times = new HashMap<>(); // key -> its timestamps, increasing as they're set
final Map<String, List<String>> values = new HashMap<>(); // key -> the value set at each of those times
void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
// the first index whose time is above t (orEqual: at or above t)
static int firstAbove(List<Integer> ts, int t, boolean orEqual) {
int lo = 0, hi = ts.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ts.get(mid) < t || (!orEqual && ts.get(mid) == t)) lo = mid + 1;
else hi = mid;
}
return lo;
}
String get(String key, int timestamp) {
List<Integer> ts = times.getOrDefault(key, List.of());
int i = firstAbove(ts, timestamp, false) - 1; // the last time at or before timestamp
return i >= 0 ? values.get(key).get(i) : "";
}
String getNext(String key, int timestamp) { // the mistake: the first time at or after timestamp
List<Integer> ts = times.getOrDefault(key, List.of());
int i = firstAbove(ts, timestamp, true);
return i < ts.size() ? values.get(key).get(i) : "";
}
}
static String shown(String s) { return s.isEmpty() ? "(nothing)" : s; }
public static void main(String[] args) {
TimeMap m = new TimeMap();
m.set("temp", "18C", 5);
m.set("temp", "21C", 9);
m.set("temp", "17C", 14);
for (int t : new int[] {3, 5, 8, 9, 20})
System.out.println("get(temp, " + t + ") = " + shown(m.get("temp", t)) + "; the next version: " + shown(m.getNext("temp", t)));
System.out.println("get(rain, 10) = " + shown(m.get("rain", 10)));
}
}
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)#include <bits/stdc++.h>
using namespace std;
class TimeMap {
public:
unordered_map<string, vector<int>> times; // key -> its timestamps, increasing as they're set
unordered_map<string, vector<string>> values; // key -> the value set at each of those times
void set(const string& key, const string& value, int timestamp) {
times[key].push_back(timestamp);
values[key].push_back(value);
}
string get(const string& key, int timestamp) {
auto it = times.find(key);
if (it == times.end()) return "";
auto& ts = it->second;
int i = upper_bound(ts.begin(), ts.end(), timestamp) - ts.begin() - 1; // the last time at or before timestamp
return i >= 0 ? values[key][i] : "";
}
string getNext(const string& key, int timestamp) { // the mistake: the first time at or after timestamp
auto it = times.find(key);
if (it == times.end()) return "";
auto& ts = it->second;
size_t i = lower_bound(ts.begin(), ts.end(), timestamp) - ts.begin();
return i < ts.size() ? values[key][i] : "";
}
};
string shown(const string& s) { return s.empty() ? "(nothing)" : s; }
int main() {
TimeMap m;
m.set("temp", "18C", 5);
m.set("temp", "21C", 9);
m.set("temp", "17C", 14);
for (int t : {3, 5, 8, 9, 20})
cout << "get(temp, " << t << ") = " << shown(m.get("temp", t)) << "; the next version: " << shown(m.getNext("temp", t)) << "\n";
cout << "get(rain, 10) = " << shown(m.get("rain", 10)) << "\n";
}
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)class TimeMap {
constructor() {
this.times = new Map(); // key -> its timestamps, increasing as they're set
this.values = new Map(); // key -> the value set at each of those times
}
set(key, value, timestamp) {
if (!this.times.has(key)) {
this.times.set(key, []);
this.values.set(key, []);
}
this.times.get(key).push(timestamp);
this.values.get(key).push(value);
}
static firstAbove(ts, t, orEqual) { // the first index whose time is above t (orEqual: at or above t)
let lo = 0, hi = ts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ts[mid] < t || (!orEqual && ts[mid] === t)) lo = mid + 1;
else hi = mid;
}
return lo;
}
get(key, timestamp) {
const ts = this.times.get(key) ?? [];
const i = TimeMap.firstAbove(ts, timestamp, false) - 1; // the last time at or before timestamp
return i >= 0 ? this.values.get(key)[i] : "";
}
getNext(key, timestamp) { // the mistake: the first time at or after timestamp
const ts = this.times.get(key) ?? [];
const i = TimeMap.firstAbove(ts, timestamp, true);
return i < ts.length ? this.values.get(key)[i] : "";
}
}
const shown = s => s || "(nothing)";
const m = new TimeMap();
for (const [value, t] of [["18C", 5], ["21C", 9], ["17C", 14]]) m.set("temp", value, t);
for (const t of [3, 5, 8, 9, 20])
console.log(`get(temp, ${t}) = ${shown(m.get("temp", t))}; the next version: ${shown(m.getNext("temp", t))}`);
console.log(`get(rain, 10) = ${shown(m.get("rain", 10))}`);
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)class TimeMap {
times = new Map<string, number[]>(); // key -> its timestamps, increasing as they're set
values = new Map<string, string[]>(); // key -> the value set at each of those times
set(key: string, value: string, timestamp: number): void {
if (!this.times.has(key)) {
this.times.set(key, []);
this.values.set(key, []);
}
this.times.get(key)!.push(timestamp);
this.values.get(key)!.push(value);
}
static firstAbove(ts: number[], t: number, orEqual: boolean): number { // the first index above t
let lo = 0, hi = ts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ts[mid] < t || (!orEqual && ts[mid] === t)) lo = mid + 1;
else hi = mid;
}
return lo;
}
get(key: string, timestamp: number): string {
const ts = this.times.get(key) ?? [];
const i = TimeMap.firstAbove(ts, timestamp, false) - 1; // the last time at or before timestamp
return i >= 0 ? this.values.get(key)![i] : "";
}
getNext(key: string, timestamp: number): string { // the mistake: the first time at or after timestamp
const ts = this.times.get(key) ?? [];
const i = TimeMap.firstAbove(ts, timestamp, true);
return i < ts.length ? this.values.get(key)![i] : "";
}
}
const shown = (s: string) => s || "(nothing)";
const m = new TimeMap();
const sets: [string, number][] = [["18C", 5], ["21C", 9], ["17C", 14]];
for (const [value, t] of sets) m.set("temp", value, t);
for (const t of [3, 5, 8, 9, 20])
console.log(`get(temp, ${t}) = ${shown(m.get("temp", t))}; the next version: ${shown(m.getNext("temp", t))}`);
console.log(`get(rain, 10) = ${shown(m.get("rain", 10))}`);
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)using System;
using System.Collections.Generic;
class TimeMap {
readonly Dictionary<string, List<int>> times = new Dictionary<string, List<int>>(); // key -> its timestamps
readonly Dictionary<string, List<string>> values = new Dictionary<string, List<string>>(); // and their values
public void Set(string key, string value, int timestamp) {
if (!times.ContainsKey(key)) {
times[key] = new List<int>();
values[key] = new List<string>();
}
times[key].Add(timestamp);
values[key].Add(value);
}
static int FirstAbove(List<int> ts, int t, bool orEqual) { // the first index above t (orEqual: at or above)
int lo = 0, hi = ts.Count;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ts[mid] < t || (!orEqual && ts[mid] == t)) lo = mid + 1;
else hi = mid;
}
return lo;
}
public string Get(string key, int timestamp) {
if (!times.TryGetValue(key, out var ts)) return "";
int i = FirstAbove(ts, timestamp, false) - 1; // the last time at or before timestamp
return i >= 0 ? values[key][i] : "";
}
public string GetNext(string key, int timestamp) { // the mistake: the first time at or after timestamp
if (!times.TryGetValue(key, out var ts)) return "";
int i = FirstAbove(ts, timestamp, true);
return i < ts.Count ? values[key][i] : "";
}
}
class Program {
static string Shown(string s) => s == "" ? "(nothing)" : s;
static void Main() {
var m = new TimeMap();
m.Set("temp", "18C", 5);
m.Set("temp", "21C", 9);
m.Set("temp", "17C", 14);
foreach (int t in new[] {3, 5, 8, 9, 20})
Console.WriteLine($"get(temp, {t}) = {Shown(m.Get("temp", t))}; the next version: {Shown(m.GetNext("temp", t))}");
Console.WriteLine($"get(rain, 10) = {Shown(m.Get("rain", 10))}");
}
}
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)package main
import (
"fmt"
"sort"
)
type TimeMap struct {
times map[string][]int // key -> its timestamps, increasing as they're set
values map[string][]string // key -> the value set at each of those times
}
func (m *TimeMap) Set(key, value string, timestamp int) {
m.times[key] = append(m.times[key], timestamp)
m.values[key] = append(m.values[key], value)
}
func (m *TimeMap) Get(key string, timestamp int) string {
ts := m.times[key]
i := sort.Search(len(ts), func(k int) bool { return ts[k] > timestamp }) - 1 // the last time at or before timestamp
if i < 0 {
return ""
}
return m.values[key][i]
}
func (m *TimeMap) GetNext(key string, timestamp int) string { // the mistake: the first time at or after timestamp
ts := m.times[key]
i := sort.Search(len(ts), func(k int) bool { return ts[k] >= timestamp })
if i == len(ts) {
return ""
}
return m.values[key][i]
}
func shown(s string) string {
if s == "" {
return "(nothing)"
}
return s
}
func main() {
m := &TimeMap{times: map[string][]int{}, values: map[string][]string{}}
m.Set("temp", "18C", 5)
m.Set("temp", "21C", 9)
m.Set("temp", "17C", 14)
for _, t := range []int{3, 5, 8, 9, 20} {
fmt.Printf("get(temp, %d) = %s; the next version: %s\n", t, shown(m.Get("temp", t)), shown(m.GetNext("temp", t)))
}
fmt.Printf("get(rain, 10) = %s\n", shown(m.Get("rain", 10)))
}
// get(temp, 3) = (nothing); the next version: 18C
// get(temp, 5) = 18C; the next version: 18C
// get(temp, 8) = 18C; the next version: 21C
// get(temp, 9) = 21C; the next version: 21C
// get(temp, 20) = 17C; the next version: (nothing)
// get(rain, 10) = (nothing)At t = 8 the temperature was still the one set at 5, 18C; the next version, 21C, wasn't set until 9. Reading the first time at or after t answers from the future, and before the first set it returns a value that didn't exist yet: at t = 3 it said 18C where the answer is nothing. At or before is bisect_right(times, t) - 1 in Python, upper_bound minus one in C++, the first index whose time is above t, minus one, in the others. A set is an append, O(1); a get is O(log k) for a key with k versions.
Snapshots without copies
Snapshot Array is the same idea with snapshot numbers in place of timestamps. Each cell keeps a list of (snap id, value) for the snaps it changed in. A set writes into the current snap: a new entry, or, when the cell has already changed in this snap, a replacement of its last one, since only the value at snap time counts. snap() hands out the current id and moves on. get(index, snap_id) is the binary search again, and a cell that never changed by then is still 0:
import bisect
class SnapshotArray:
def __init__(self, length):
self.snap_ids = [[] for _ in range(length)] # each cell's changes: the snap they were made in
self.values = [[] for _ in range(length)] # and the value
self.snap_id = 0
def set(self, index, val):
ids, vals = self.snap_ids[index], self.values[index]
if ids and ids[-1] == self.snap_id: # changed already in this snap: the later value wins
vals[-1] = val
else:
ids.append(self.snap_id)
vals.append(val)
def snap(self):
self.snap_id += 1
return self.snap_id - 1
def get(self, index, snap_id):
i = bisect.bisect_right(self.snap_ids[index], snap_id) - 1 # the last change at or before snap_id
return self.values[index][i] if i >= 0 else 0
a = SnapshotArray(4)
a.set(0, 5)
print("snap", a.snap())
a.set(0, 6)
a.set(2, 9)
a.set(2, 4) # twice in snap 1: 4 replaces 9
print("snap", a.snap())
a.set(0, 7)
print("snap", a.snap())
for i in (0, 2):
print(f"cell {i}:", " ".join(f"({s}, {v})" for s, v in zip(a.snap_ids[i], a.values[i])))
for index, snap_id in ((0, 0), (0, 1), (0, 2), (2, 0), (2, 1), (3, 2)):
print(f"get({index}, {snap_id}) = {a.get(index, snap_id)}")
# snap 0
# snap 1
# snap 2
# cell 0: (0, 5) (1, 6) (2, 7)
# cell 2: (1, 4)
# get(0, 0) = 5
# get(0, 1) = 6
# get(0, 2) = 7
# get(2, 0) = 0
# get(2, 1) = 4
# get(3, 2) = 0import java.util.*;
public class Main {
static class SnapshotArray {
final List<List<Integer>> snapIds = new ArrayList<>(), values = new ArrayList<>(); // each cell's changes
int snapId = 0;
SnapshotArray(int length) {
for (int i = 0; i < length; i++) {
snapIds.add(new ArrayList<>());
values.add(new ArrayList<>());
}
}
void set(int index, int val) {
List<Integer> ids = snapIds.get(index), vals = values.get(index);
if (!ids.isEmpty() && ids.get(ids.size() - 1) == snapId) vals.set(vals.size() - 1, val); // the later value wins
else {
ids.add(snapId);
vals.add(val);
}
}
int snap() { return snapId++; }
int get(int index, int snapId) {
List<Integer> ids = snapIds.get(index);
int lo = 0, hi = ids.size(); // the first change after snapId
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ids.get(mid) <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? values.get(index).get(lo - 1) : 0; // the one before it is the last at or before
}
}
public static void main(String[] args) {
SnapshotArray a = new SnapshotArray(4);
a.set(0, 5);
System.out.println("snap " + a.snap());
a.set(0, 6);
a.set(2, 9);
a.set(2, 4); // twice in snap 1: 4 replaces 9
System.out.println("snap " + a.snap());
a.set(0, 7);
System.out.println("snap " + a.snap());
for (int i : new int[] {0, 2}) {
StringJoiner line = new StringJoiner(" ", "cell " + i + ": ", "");
for (int k = 0; k < a.snapIds.get(i).size(); k++)
line.add("(" + a.snapIds.get(i).get(k) + ", " + a.values.get(i).get(k) + ")");
System.out.println(line);
}
int[][] reads = {{0, 0}, {0, 1}, {0, 2}, {2, 0}, {2, 1}, {3, 2}};
for (int[] r : reads) System.out.println("get(" + r[0] + ", " + r[1] + ") = " + a.get(r[0], r[1]));
}
}
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0#include <bits/stdc++.h>
using namespace std;
class SnapshotArray {
public:
vector<vector<int>> snapIds, values; // each cell's changes: the snap they were made in, and the value
int snapId = 0;
SnapshotArray(int length) : snapIds(length), values(length) {}
void set(int index, int val) {
auto &ids = snapIds[index], &vals = values[index];
if (!ids.empty() && ids.back() == snapId) vals.back() = val; // changed already in this snap: the later value wins
else {
ids.push_back(snapId);
vals.push_back(val);
}
}
int snap() { return snapId++; }
int get(int index, int snapId) {
auto& ids = snapIds[index];
int i = upper_bound(ids.begin(), ids.end(), snapId) - ids.begin() - 1; // the last change at or before snapId
return i >= 0 ? values[index][i] : 0;
}
};
int main() {
SnapshotArray a(4);
a.set(0, 5);
cout << "snap " << a.snap() << "\n";
a.set(0, 6);
a.set(2, 9);
a.set(2, 4); // twice in snap 1: 4 replaces 9
cout << "snap " << a.snap() << "\n";
a.set(0, 7);
cout << "snap " << a.snap() << "\n";
for (int i : {0, 2}) {
cout << "cell " << i << ":";
for (size_t k = 0; k < a.snapIds[i].size(); k++) cout << " (" << a.snapIds[i][k] << ", " << a.values[i][k] << ")";
cout << "\n";
}
for (auto [index, snapId] : vector<pair<int, int>>{{0, 0}, {0, 1}, {0, 2}, {2, 0}, {2, 1}, {3, 2}})
cout << "get(" << index << ", " << snapId << ") = " << a.get(index, snapId) << "\n";
}
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0class SnapshotArray {
constructor(length) {
this.snapIds = Array.from({ length }, () => []); // each cell's changes: the snap they were made in
this.values = Array.from({ length }, () => []); // and the value
this.snapId = 0;
}
set(index, val) {
const ids = this.snapIds[index], vals = this.values[index];
if (ids.length && ids[ids.length - 1] === this.snapId) vals[vals.length - 1] = val; // the later value wins
else {
ids.push(this.snapId);
vals.push(val);
}
}
snap() { return this.snapId++; }
get(index, snapId) {
const ids = this.snapIds[index];
let lo = 0, hi = ids.length; // the first change after snapId
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? this.values[index][lo - 1] : 0; // the one before it is the last at or before
}
}
const a = new SnapshotArray(4);
a.set(0, 5);
console.log("snap", a.snap());
a.set(0, 6);
a.set(2, 9);
a.set(2, 4); // twice in snap 1: 4 replaces 9
console.log("snap", a.snap());
a.set(0, 7);
console.log("snap", a.snap());
for (const i of [0, 2]) console.log(`cell ${i}:`, a.snapIds[i].map((s, k) => `(${s}, ${a.values[i][k]})`).join(" "));
for (const [index, snapId] of [[0, 0], [0, 1], [0, 2], [2, 0], [2, 1], [3, 2]])
console.log(`get(${index}, ${snapId}) = ${a.get(index, snapId)}`);
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0class SnapshotArray {
snapIds: number[][]; // each cell's changes: the snap they were made in
values: number[][]; // and the value
snapId = 0;
constructor(length: number) {
this.snapIds = Array.from({ length }, () => []);
this.values = Array.from({ length }, () => []);
}
set(index: number, val: number): void {
const ids = this.snapIds[index], vals = this.values[index];
if (ids.length && ids[ids.length - 1] === this.snapId) vals[vals.length - 1] = val; // the later value wins
else {
ids.push(this.snapId);
vals.push(val);
}
}
snap(): number { return this.snapId++; }
get(index: number, snapId: number): number {
const ids = this.snapIds[index];
let lo = 0, hi = ids.length; // the first change after snapId
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? this.values[index][lo - 1] : 0; // the one before it is the last at or before
}
}
const a = new SnapshotArray(4);
a.set(0, 5);
console.log("snap", a.snap());
a.set(0, 6);
a.set(2, 9);
a.set(2, 4); // twice in snap 1: 4 replaces 9
console.log("snap", a.snap());
a.set(0, 7);
console.log("snap", a.snap());
for (const i of [0, 2]) console.log(`cell ${i}:`, a.snapIds[i].map((s, k) => `(${s}, ${a.values[i][k]})`).join(" "));
const reads: [number, number][] = [[0, 0], [0, 1], [0, 2], [2, 0], [2, 1], [3, 2]];
for (const [index, snapId] of reads) console.log(`get(${index}, ${snapId}) = ${a.get(index, snapId)}`);
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0using System;
using System.Collections.Generic;
using System.Linq;
class SnapshotArray {
public readonly List<int>[] SnapIds, Values; // each cell's changes: the snap they were made in, and the value
int snapId = 0;
public SnapshotArray(int length) {
SnapIds = new List<int>[length];
Values = new List<int>[length];
for (int i = 0; i < length; i++) {
SnapIds[i] = new List<int>();
Values[i] = new List<int>();
}
}
public void Set(int index, int val) {
List<int> ids = SnapIds[index], vals = Values[index];
if (ids.Count > 0 && ids[ids.Count - 1] == snapId) vals[vals.Count - 1] = val; // the later value wins
else {
ids.Add(snapId);
vals.Add(val);
}
}
public int Snap() => snapId++;
public int Get(int index, int snapId) {
List<int> ids = SnapIds[index];
int lo = 0, hi = ids.Count; // the first change after snapId
while (lo < hi) {
int mid = (lo + hi) / 2;
if (ids[mid] <= snapId) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? Values[index][lo - 1] : 0; // the one before it is the last at or before
}
}
class Program {
static void Main() {
var a = new SnapshotArray(4);
a.Set(0, 5);
Console.WriteLine("snap " + a.Snap());
a.Set(0, 6);
a.Set(2, 9);
a.Set(2, 4); // twice in snap 1: 4 replaces 9
Console.WriteLine("snap " + a.Snap());
a.Set(0, 7);
Console.WriteLine("snap " + a.Snap());
foreach (int i in new[] {0, 2})
Console.WriteLine($"cell {i}: " + string.Join(" ", a.SnapIds[i].Select((s, k) => $"({s}, {a.Values[i][k]})")));
foreach (var (index, snapId) in new[] {(0, 0), (0, 1), (0, 2), (2, 0), (2, 1), (3, 2)})
Console.WriteLine($"get({index}, {snapId}) = {a.Get(index, snapId)}");
}
}
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0package main
import (
"fmt"
"sort"
)
type SnapshotArray struct {
snapIDs, values [][]int // each cell's changes: the snap they were made in, and the value
snapID int
}
func NewSnapshotArray(length int) *SnapshotArray {
return &SnapshotArray{snapIDs: make([][]int, length), values: make([][]int, length)}
}
func (a *SnapshotArray) Set(index, val int) {
ids := a.snapIDs[index]
if len(ids) > 0 && ids[len(ids)-1] == a.snapID { // changed already in this snap: the later value wins
a.values[index][len(ids)-1] = val
return
}
a.snapIDs[index] = append(ids, a.snapID)
a.values[index] = append(a.values[index], val)
}
func (a *SnapshotArray) Snap() int {
a.snapID++
return a.snapID - 1
}
func (a *SnapshotArray) Get(index, snapID int) int {
ids := a.snapIDs[index]
i := sort.Search(len(ids), func(k int) bool { return ids[k] > snapID }) - 1 // the last change at or before snapID
if i < 0 {
return 0
}
return a.values[index][i]
}
func main() {
a := NewSnapshotArray(4)
a.Set(0, 5)
fmt.Println("snap", a.Snap())
a.Set(0, 6)
a.Set(2, 9)
a.Set(2, 4) // twice in snap 1: 4 replaces 9
fmt.Println("snap", a.Snap())
a.Set(0, 7)
fmt.Println("snap", a.Snap())
for _, i := range []int{0, 2} {
line := fmt.Sprintf("cell %d:", i)
for k := range a.snapIDs[i] {
line += fmt.Sprintf(" (%d, %d)", a.snapIDs[i][k], a.values[i][k])
}
fmt.Println(line)
}
for _, r := range [][2]int{{0, 0}, {0, 1}, {0, 2}, {2, 0}, {2, 1}, {3, 2}} {
fmt.Printf("get(%d, %d) = %d\n", r[0], r[1], a.Get(r[0], r[1]))
}
}
// snap 0
// snap 1
// snap 2
// cell 0: (0, 5) (1, 6) (2, 7)
// cell 2: (1, 4)
// get(0, 0) = 5
// get(0, 1) = 6
// get(0, 2) = 7
// get(2, 0) = 0
// get(2, 1) = 4
// get(3, 2) = 0Cell 0 changed in every snap, (0, 5) (1, 6) (2, 7). Cell 2 was set to 9 and then to 4 in snap 1, and only the 4 was kept, (1, 4), so get(2, 0) found no change at or before snap 0 and answered 0. Cells 1 and 3 never changed and store nothing. Each set and snap is O(1), each get O(log c) for a cell with c changes, and memory grows with the sets, never with the snaps.
Snapshot and Read. Set some cells, take snapshots, then answer reads at old snapshots yourself: each read is a binary search on that cell's own history, and you pick which half to keep.
Counting what's recent
Design Hit Counter records hits and asks how many came in the last 300 seconds. The times arrive in order, so keep them in a queue, oldest first. A count first drops every time that is 300 seconds old or more, then reports what's left; each hit enters the queue once and leaves it once, so a call is O(1) on average:
from collections import deque
class HitCounter:
def __init__(self):
self.times = deque() # the hits of the last 300 seconds, oldest first
def hit(self, timestamp):
self.times.append(timestamp)
def get_hits(self, timestamp):
while self.times and self.times[0] <= timestamp - 300:
self.times.popleft() # 300 seconds old: it can never count again
return len(self.times)
c = HitCounter()
for t in (10, 10, 120, 299):
c.hit(t)
print("getHits(300) =", c.get_hits(300))
c.hit(305)
for t in (310, 420, 700):
print(f"getHits({t}) =", c.get_hits(t))
# getHits(300) = 4
# getHits(310) = 3
# getHits(420) = 2
# getHits(700) = 0import java.util.*;
public class Main {
static class HitCounter {
final Deque<Integer> times = new ArrayDeque<>(); // the hits of the last 300 seconds, oldest first
void hit(int timestamp) { times.addLast(timestamp); }
int getHits(int timestamp) {
while (!times.isEmpty() && times.peekFirst() <= timestamp - 300)
times.pollFirst(); // 300 seconds old: it can never count again
return times.size();
}
}
public static void main(String[] args) {
HitCounter c = new HitCounter();
for (int t : new int[] {10, 10, 120, 299}) c.hit(t);
System.out.println("getHits(300) = " + c.getHits(300));
c.hit(305);
for (int t : new int[] {310, 420, 700}) System.out.println("getHits(" + t + ") = " + c.getHits(t));
}
}
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0#include <bits/stdc++.h>
using namespace std;
class HitCounter {
deque<int> times; // the hits of the last 300 seconds, oldest first
public:
void hit(int timestamp) { times.push_back(timestamp); }
int getHits(int timestamp) {
while (!times.empty() && times.front() <= timestamp - 300)
times.pop_front(); // 300 seconds old: it can never count again
return times.size();
}
};
int main() {
HitCounter c;
for (int t : {10, 10, 120, 299}) c.hit(t);
cout << "getHits(300) = " << c.getHits(300) << "\n";
c.hit(305);
for (int t : {310, 420, 700}) cout << "getHits(" << t << ") = " << c.getHits(t) << "\n";
}
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0class HitCounter {
constructor() {
this.times = []; // the hits of the last 300 seconds, oldest first, from index head
this.head = 0;
}
hit(timestamp) { this.times.push(timestamp); }
getHits(timestamp) {
while (this.head < this.times.length && this.times[this.head] <= timestamp - 300)
this.head++; // 300 seconds old: it can never count again
return this.times.length - this.head;
}
}
const c = new HitCounter();
for (const t of [10, 10, 120, 299]) c.hit(t);
console.log("getHits(300) =", c.getHits(300));
c.hit(305);
for (const t of [310, 420, 700]) console.log(`getHits(${t}) =`, c.getHits(t));
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0class HitCounter {
times: number[] = []; // the hits of the last 300 seconds, oldest first, from index head
head = 0;
hit(timestamp: number): void { this.times.push(timestamp); }
getHits(timestamp: number): number {
while (this.head < this.times.length && this.times[this.head] <= timestamp - 300)
this.head++; // 300 seconds old: it can never count again
return this.times.length - this.head;
}
}
const c = new HitCounter();
for (const t of [10, 10, 120, 299]) c.hit(t);
console.log("getHits(300) =", c.getHits(300));
c.hit(305);
for (const t of [310, 420, 700]) console.log(`getHits(${t}) =`, c.getHits(t));
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0using System;
using System.Collections.Generic;
class HitCounter {
readonly Queue<int> times = new Queue<int>(); // the hits of the last 300 seconds, oldest first
public void Hit(int timestamp) => times.Enqueue(timestamp);
public int GetHits(int timestamp) {
while (times.Count > 0 && times.Peek() <= timestamp - 300)
times.Dequeue(); // 300 seconds old: it can never count again
return times.Count;
}
}
class Program {
static void Main() {
var c = new HitCounter();
foreach (int t in new[] {10, 10, 120, 299}) c.Hit(t);
Console.WriteLine("getHits(300) = " + c.GetHits(300));
c.Hit(305);
foreach (int t in new[] {310, 420, 700}) Console.WriteLine($"getHits({t}) = {c.GetHits(t)}");
}
}
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0package main
import "fmt"
type HitCounter struct {
times []int // the hits of the last 300 seconds, oldest first
}
func (c *HitCounter) Hit(timestamp int) { c.times = append(c.times, timestamp) }
func (c *HitCounter) GetHits(timestamp int) int {
for len(c.times) > 0 && c.times[0] <= timestamp-300 {
c.times = c.times[1:] // 300 seconds old: it can never count again
}
return len(c.times)
}
func main() {
c := &HitCounter{}
for _, t := range []int{10, 10, 120, 299} {
c.Hit(t)
}
fmt.Println("getHits(300) =", c.GetHits(300))
c.Hit(305)
for _, t := range []int{310, 420, 700} {
fmt.Printf("getHits(%d) = %d\n", t, c.GetHits(t))
}
}
// getHits(300) = 4
// getHits(310) = 3
// getHits(420) = 2
// getHits(700) = 0getHits(300) = 4: all four hits were less than 300 seconds old. At 310 the two hits at 10 were exactly 300 seconds old, so they left, and 3 were left; at 420 the hit at 120 went too, and at 700 nothing was. The queue is Introduction to Queues' queue, and the 300 seconds are a window that only moves forward, as in Introduction to Sliding Window.
With millions of hits a second, the queue holds every one of them. The follow-up's answer is 300 buckets, one per second of the window, at index t % 300: each holds the second it counts for and a count, and a bucket whose second is stale is reset before it's used. That's O(300) memory however many hits come.
Logger Rate Limiter needs even less history: for each message, only the time it may print again. A message prints at t if t has reached that time, which then becomes t + 10; a message refused changes nothing. The map keeps every message it has seen, so when memory matters, a queue of recent prints lets it drop the ones more than 10 seconds old.
A history you walk back and forth
Design Browser History opens a homepage, visits pages, and moves back and forward by some number of steps, never past either end. Keep the pages in an array with a cursor on the open one. back and forward move the cursor and clamp it. A visit writes the new page right after the cursor, and every page ahead of it is gone, the way a browser forgets your forward pages when you click a new link. Cutting them one by one would cost their number, so keep an end mark instead and move it:
class BrowserHistory:
def __init__(self, homepage):
self.pages = [homepage] # pages[:end] is the history; pages[at] is open
self.at, self.end = 0, 1
def visit(self, url):
self.at += 1
if self.at == len(self.pages):
self.pages.append(url)
else:
self.pages[self.at] = url
self.end = self.at + 1 # every forward page is cut off
def back(self, steps):
self.at = max(0, self.at - steps)
return self.pages[self.at]
def forward(self, steps):
self.at = min(self.end - 1, self.at + steps)
return self.pages[self.at]
def show(self):
return " ".join(f"[{p}]" if i == self.at else p for i, p in enumerate(self.pages[:self.end]))
b = BrowserHistory("home.org")
for url in ("a.org", "b.org", "c.org"):
b.visit(url)
print("after 3 visits:", b.show())
print("back(3) =", b.back(3), "|", b.show())
print("forward(1) =", b.forward(1), "|", b.show())
b.visit("d.org")
print("visit d.org:", b.show())
print("forward(2) =", b.forward(2), "|", b.show())
print("back(9) =", b.back(9), "|", b.show())
# after 3 visits: home.org a.org b.org [c.org]
# back(3) = home.org | [home.org] a.org b.org c.org
# forward(1) = a.org | home.org [a.org] b.org c.org
# visit d.org: home.org a.org [d.org]
# forward(2) = d.org | home.org a.org [d.org]
# back(9) = home.org | [home.org] a.org d.orgimport java.util.*;
public class Main {
static class BrowserHistory {
final List<String> pages = new ArrayList<>(); // pages up to end are the history; pages[at] is open
int at = 0, end = 1;
BrowserHistory(String homepage) { pages.add(homepage); }
void visit(String url) {
at++;
if (at == pages.size()) pages.add(url);
else pages.set(at, url);
end = at + 1; // every forward page is cut off
}
String back(int steps) {
at = Math.max(0, at - steps);
return pages.get(at);
}
String forward(int steps) {
at = Math.min(end - 1, at + steps);
return pages.get(at);
}
String show() {
StringJoiner s = new StringJoiner(" ");
for (int i = 0; i < end; i++) s.add(i == at ? "[" + pages.get(i) + "]" : pages.get(i));
return s.toString();
}
}
public static void main(String[] args) {
BrowserHistory b = new BrowserHistory("home.org");
for (String url : new String[] {"a.org", "b.org", "c.org"}) b.visit(url);
System.out.println("after 3 visits: " + b.show());
System.out.println("back(3) = " + b.back(3) + " | " + b.show());
System.out.println("forward(1) = " + b.forward(1) + " | " + b.show());
b.visit("d.org");
System.out.println("visit d.org: " + b.show());
System.out.println("forward(2) = " + b.forward(2) + " | " + b.show());
System.out.println("back(9) = " + b.back(9) + " | " + b.show());
}
}
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.org#include <bits/stdc++.h>
using namespace std;
class BrowserHistory {
vector<string> pages; // pages up to end are the history; pages[at] is open
int at = 0, end = 1;
public:
BrowserHistory(string homepage) : pages{homepage} {}
void visit(string url) {
at++;
if (at == (int) pages.size()) pages.push_back(url);
else pages[at] = url;
end = at + 1; // every forward page is cut off
}
string back(int steps) {
at = max(0, at - steps);
return pages[at];
}
string forward(int steps) {
at = min(end - 1, at + steps);
return pages[at];
}
string show() {
string s;
for (int i = 0; i < end; i++) s += (i ? " " : "") + (i == at ? "[" + pages[i] + "]" : pages[i]);
return s;
}
};
int main() {
BrowserHistory b("home.org");
for (string url : {"a.org", "b.org", "c.org"}) b.visit(url);
cout << "after 3 visits: " << b.show() << "\n";
string page = b.back(3);
cout << "back(3) = " << page << " | " << b.show() << "\n";
page = b.forward(1);
cout << "forward(1) = " << page << " | " << b.show() << "\n";
b.visit("d.org");
cout << "visit d.org: " << b.show() << "\n";
page = b.forward(2);
cout << "forward(2) = " << page << " | " << b.show() << "\n";
page = b.back(9);
cout << "back(9) = " << page << " | " << b.show() << "\n";
}
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.orgclass BrowserHistory {
constructor(homepage) {
this.pages = [homepage]; // pages up to end are the history; pages[at] is open
this.at = 0;
this.end = 1;
}
visit(url) {
this.at++;
this.pages[this.at] = url;
this.end = this.at + 1; // every forward page is cut off
}
back(steps) {
this.at = Math.max(0, this.at - steps);
return this.pages[this.at];
}
forward(steps) {
this.at = Math.min(this.end - 1, this.at + steps);
return this.pages[this.at];
}
show() {
return this.pages.slice(0, this.end).map((p, i) => (i === this.at ? `[${p}]` : p)).join(" ");
}
}
const b = new BrowserHistory("home.org");
for (const url of ["a.org", "b.org", "c.org"]) b.visit(url);
console.log("after 3 visits:", b.show());
console.log("back(3) =", b.back(3), "|", b.show());
console.log("forward(1) =", b.forward(1), "|", b.show());
b.visit("d.org");
console.log("visit d.org:", b.show());
console.log("forward(2) =", b.forward(2), "|", b.show());
console.log("back(9) =", b.back(9), "|", b.show());
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.orgclass BrowserHistory {
pages: string[]; // pages up to end are the history; pages[at] is open
at = 0;
end = 1;
constructor(homepage: string) { this.pages = [homepage]; }
visit(url: string): void {
this.at++;
this.pages[this.at] = url;
this.end = this.at + 1; // every forward page is cut off
}
back(steps: number): string {
this.at = Math.max(0, this.at - steps);
return this.pages[this.at];
}
forward(steps: number): string {
this.at = Math.min(this.end - 1, this.at + steps);
return this.pages[this.at];
}
show(): string {
return this.pages.slice(0, this.end).map((p, i) => (i === this.at ? `[${p}]` : p)).join(" ");
}
}
const b = new BrowserHistory("home.org");
for (const url of ["a.org", "b.org", "c.org"]) b.visit(url);
console.log("after 3 visits:", b.show());
console.log("back(3) =", b.back(3), "|", b.show());
console.log("forward(1) =", b.forward(1), "|", b.show());
b.visit("d.org");
console.log("visit d.org:", b.show());
console.log("forward(2) =", b.forward(2), "|", b.show());
console.log("back(9) =", b.back(9), "|", b.show());
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.orgusing System;
using System.Collections.Generic;
using System.Linq;
class BrowserHistory {
readonly List<string> pages = new List<string>(); // pages up to end are the history; pages[at] is open
int at = 0, end = 1;
public BrowserHistory(string homepage) { pages.Add(homepage); }
public void Visit(string url) {
at++;
if (at == pages.Count) pages.Add(url);
else pages[at] = url;
end = at + 1; // every forward page is cut off
}
public string Back(int steps) {
at = Math.Max(0, at - steps);
return pages[at];
}
public string Forward(int steps) {
at = Math.Min(end - 1, at + steps);
return pages[at];
}
public string Show() => string.Join(" ", pages.Take(end).Select((p, i) => i == at ? $"[{p}]" : p));
}
class Program {
static void Main() {
var b = new BrowserHistory("home.org");
foreach (string url in new[] {"a.org", "b.org", "c.org"}) b.Visit(url);
Console.WriteLine("after 3 visits: " + b.Show());
Console.WriteLine("back(3) = " + b.Back(3) + " | " + b.Show());
Console.WriteLine("forward(1) = " + b.Forward(1) + " | " + b.Show());
b.Visit("d.org");
Console.WriteLine("visit d.org: " + b.Show());
Console.WriteLine("forward(2) = " + b.Forward(2) + " | " + b.Show());
Console.WriteLine("back(9) = " + b.Back(9) + " | " + b.Show());
}
}
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.orgpackage main
import (
"fmt"
"strings"
)
type BrowserHistory struct {
pages []string // pages up to end are the history; pages[at] is open
at, end int
}
func (b *BrowserHistory) Visit(url string) {
b.at++
if b.at == len(b.pages) {
b.pages = append(b.pages, url)
} else {
b.pages[b.at] = url
}
b.end = b.at + 1 // every forward page is cut off
}
func (b *BrowserHistory) Back(steps int) string {
b.at = max(0, b.at-steps)
return b.pages[b.at]
}
func (b *BrowserHistory) Forward(steps int) string {
b.at = min(b.end-1, b.at+steps)
return b.pages[b.at]
}
func (b *BrowserHistory) Show() string {
parts := []string{}
for i, p := range b.pages[:b.end] {
if i == b.at {
p = "[" + p + "]"
}
parts = append(parts, p)
}
return strings.Join(parts, " ")
}
func main() {
b := &BrowserHistory{pages: []string{"home.org"}, end: 1}
for _, url := range []string{"a.org", "b.org", "c.org"} {
b.Visit(url)
}
fmt.Println("after 3 visits:", b.Show())
page := b.Back(3)
fmt.Println("back(3) =", page, "|", b.Show())
page = b.Forward(1)
fmt.Println("forward(1) =", page, "|", b.Show())
b.Visit("d.org")
fmt.Println("visit d.org:", b.Show())
page = b.Forward(2)
fmt.Println("forward(2) =", page, "|", b.Show())
page = b.Back(9)
fmt.Println("back(9) =", page, "|", b.Show())
}
// after 3 visits: home.org a.org b.org [c.org]
// back(3) = home.org | [home.org] a.org b.org c.org
// forward(1) = a.org | home.org [a.org] b.org c.org
// visit d.org: home.org a.org [d.org]
// forward(2) = d.org | home.org a.org [d.org]
// back(9) = home.org | [home.org] a.org d.orgAfter back(3) and forward(1) the open page was a.org, with b.org and c.org ahead. Visiting d.org wrote over b.org and moved the end back to just after it. c.org is still in the array, but past the end, so forward(2) stayed on d.org, and back(9) stopped at home.org. Every call is O(1). Two stacks, one for the pages behind and one for those ahead, give the same answers but move one page per step, O(steps) a call.
A length before every string
Encode and Decode Strings turns a list of strings into one string and back, and the strings can hold any character at all. A separator fails as soon as a string contains it. Writing each string's length and a # before it doesn't: the decoder reads the digits up to the first #, then takes exactly that many characters, whatever they are, # included:
def join_commas(strs): # the first idea: a separator between them
return ",".join(strs)
def split_commas(s):
return s.split(",")
def encode(strs): # each string's length, a '#', then the string as it is
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(s):
out, i = [], 0
while i < len(s):
j = s.index("#", i) # the length ends at the first '#' after i
n = int(s[i:j])
out.append(s[j + 1:j + 1 + n]) # then exactly n characters, whatever they are
i = j + 1 + n
return out
def show(strs):
return f"{len(strs)} strings: " + " ".join(f'"{s}"' for s in strs)
strs = ["2,3", "", "a#b", "5#"]
print("encoded:", encode(strs))
print("commas:", show(split_commas(join_commas(strs))))
print("length first:", show(decode(encode(strs))))
# encoded: 3#2,30#3#a#b2#5#
# commas: 5 strings: "2" "3" "" "a#b" "5#"
# length first: 4 strings: "2,3" "" "a#b" "5#"import java.util.*;
public class Main {
static String joinCommas(List<String> strs) { return String.join(",", strs); } // the first idea: a separator
static List<String> splitCommas(String s) { return Arrays.asList(s.split(",", -1)); }
static String encode(List<String> strs) { // each string's length, a '#', then the string as it is
StringBuilder sb = new StringBuilder();
for (String s : strs) sb.append(s.length()).append('#').append(s);
return sb.toString();
}
static List<String> decode(String s) {
List<String> out = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int j = s.indexOf('#', i); // the length ends at the first '#' after i
int n = Integer.parseInt(s.substring(i, j));
out.add(s.substring(j + 1, j + 1 + n)); // then exactly n characters, whatever they are
i = j + 1 + n;
}
return out;
}
static String show(List<String> strs) {
StringJoiner sj = new StringJoiner(" ", strs.size() + " strings: ", "");
for (String s : strs) sj.add("\"" + s + "\"");
return sj.toString();
}
public static void main(String[] args) {
List<String> strs = List.of("2,3", "", "a#b", "5#");
System.out.println("encoded: " + encode(strs));
System.out.println("commas: " + show(splitCommas(joinCommas(strs))));
System.out.println("length first: " + show(decode(encode(strs))));
}
}
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"#include <bits/stdc++.h>
using namespace std;
string joinCommas(const vector<string>& strs) { // the first idea: a separator between them
string s;
for (size_t i = 0; i < strs.size(); i++) s += (i ? "," : "") + strs[i];
return s;
}
vector<string> splitCommas(const string& s) {
vector<string> out(1);
for (char c : s) {
if (c == ',') out.push_back("");
else out.back() += c;
}
return out;
}
string encode(const vector<string>& strs) { // each string's length, a '#', then the string as it is
string s;
for (auto& x : strs) s += to_string(x.size()) + "#" + x;
return s;
}
vector<string> decode(const string& s) {
vector<string> out;
size_t i = 0;
while (i < s.size()) {
size_t j = s.find('#', i); // the length ends at the first '#' after i
int n = stoi(s.substr(i, j - i));
out.push_back(s.substr(j + 1, n)); // then exactly n characters, whatever they are
i = j + 1 + n;
}
return out;
}
string show(const vector<string>& strs) {
string s = to_string(strs.size()) + " strings:";
for (auto& x : strs) s += " \"" + x + "\"";
return s;
}
int main() {
vector<string> strs = {"2,3", "", "a#b", "5#"};
cout << "encoded: " << encode(strs) << "\n";
cout << "commas: " << show(splitCommas(joinCommas(strs))) << "\n";
cout << "length first: " << show(decode(encode(strs))) << "\n";
}
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"const joinCommas = strs => strs.join(","); // the first idea: a separator between them
const splitCommas = s => s.split(",");
function encode(strs) { // each string's length, a '#', then the string as it is
return strs.map(s => `${s.length}#${s}`).join("");
}
function decode(s) {
const out = [];
let i = 0;
while (i < s.length) {
const j = s.indexOf("#", i); // the length ends at the first '#' after i
const n = Number(s.slice(i, j));
out.push(s.slice(j + 1, j + 1 + n)); // then exactly n characters, whatever they are
i = j + 1 + n;
}
return out;
}
const show = strs => `${strs.length} strings: ` + strs.map(s => `"${s}"`).join(" ");
const strs = ["2,3", "", "a#b", "5#"];
console.log("encoded:", encode(strs));
console.log("commas:", show(splitCommas(joinCommas(strs))));
console.log("length first:", show(decode(encode(strs))));
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"const joinCommas = (strs: string[]): string => strs.join(","); // the first idea: a separator
const splitCommas = (s: string): string[] => s.split(",");
function encode(strs: string[]): string { // each string's length, a '#', then the string as it is
return strs.map(s => `${s.length}#${s}`).join("");
}
function decode(s: string): string[] {
const out: string[] = [];
let i = 0;
while (i < s.length) {
const j = s.indexOf("#", i); // the length ends at the first '#' after i
const n = Number(s.slice(i, j));
out.push(s.slice(j + 1, j + 1 + n)); // then exactly n characters, whatever they are
i = j + 1 + n;
}
return out;
}
const show = (strs: string[]): string => `${strs.length} strings: ` + strs.map(s => `"${s}"`).join(" ");
const strs = ["2,3", "", "a#b", "5#"];
console.log("encoded:", encode(strs));
console.log("commas:", show(splitCommas(joinCommas(strs))));
console.log("length first:", show(decode(encode(strs))));
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program {
static string JoinCommas(List<string> strs) => string.Join(",", strs); // the first idea: a separator
static List<string> SplitCommas(string s) => s.Split(',').ToList();
static string Encode(List<string> strs) { // each string's length, a '#', then the string as it is
var sb = new StringBuilder();
foreach (string s in strs) sb.Append(s.Length).Append('#').Append(s);
return sb.ToString();
}
static List<string> Decode(string s) {
var outList = new List<string>();
int i = 0;
while (i < s.Length) {
int j = s.IndexOf('#', i); // the length ends at the first '#' after i
int n = int.Parse(s.Substring(i, j - i));
outList.Add(s.Substring(j + 1, n)); // then exactly n characters, whatever they are
i = j + 1 + n;
}
return outList;
}
static string Show(List<string> strs) => $"{strs.Count} strings: " + string.Join(" ", strs.Select(s => $"\"{s}\""));
static void Main() {
var strs = new List<string> {"2,3", "", "a#b", "5#"};
Console.WriteLine("encoded: " + Encode(strs));
Console.WriteLine("commas: " + Show(SplitCommas(JoinCommas(strs))));
Console.WriteLine("length first: " + Show(Decode(Encode(strs))));
}
}
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"package main
import (
"fmt"
"strconv"
"strings"
)
func joinCommas(strs []string) string { return strings.Join(strs, ",") } // the first idea: a separator
func splitCommas(s string) []string { return strings.Split(s, ",") }
func encode(strs []string) string { // each string's length, a '#', then the string as it is
var sb strings.Builder
for _, s := range strs {
sb.WriteString(strconv.Itoa(len(s)) + "#" + s)
}
return sb.String()
}
func decode(s string) []string {
out := []string{}
for i := 0; i < len(s); {
j := i + strings.IndexByte(s[i:], '#') // the length ends at the first '#' after i
n, _ := strconv.Atoi(s[i:j])
out = append(out, s[j+1:j+1+n]) // then exactly n characters, whatever they are
i = j + 1 + n
}
return out
}
func show(strs []string) string {
quoted := []string{}
for _, s := range strs {
quoted = append(quoted, `"`+s+`"`)
}
return fmt.Sprintf("%d strings: %s", len(strs), strings.Join(quoted, " "))
}
func main() {
strs := []string{"2,3", "", "a#b", "5#"}
fmt.Println("encoded:", encode(strs))
fmt.Println("commas:", show(splitCommas(joinCommas(strs))))
fmt.Println("length first:", show(decode(encode(strs))))
}
// encoded: 3#2,30#3#a#b2#5#
// commas: 5 strings: "2" "3" "" "a#b" "5#"
// length first: 4 strings: "2,3" "" "a#b" "5#"Joined with commas, the four strings came back as five, since "2,3" split in two. With the lengths first, 3#2,30#3#a#b2#5# decoded to exactly the four, the # inside "a#b" and "5#" read as text because the decoder never looks for a # inside a string, only right after each length. Both directions are O(total length).
Spotting it
The clues: a value "at time t" or "as of snapshot k", "the most recent value at or before", versions, undo, back and forward; counts over "the last 5 minutes" or "the past 10 seconds"; "encode" and "decode", "serialize", a list that must come back exactly. Then ask what changed and when, and keep only that. Near misses:
- The newest value is all anyone reads: a plain hash map (Introduction to Hash Tables).
- Recency for eviction rather than reads of the past: Designing a Data Structure's LRU cache.
- The largest or smallest in a window that slides: Monotonic Deque: the Window's Maximum.
Mistakes that cost an interview
Reading the next version. The first time at or after t, bisect_left, where the answer is the last time at or before it, bisect_right minus one: in the run above, get(temp, 8) came back 21C, a value set at 9.
snap() handing out the next id. The snapshot just taken is the current id. Adding one first and returning the new value hands out ids one too high, so every later get(index, snap_id) reads the snapshot after the one it was given.
Copying on every snap. It answers right and costs a full copy per snap: the hook above stored 5,000,000 values to keep 1,000 changes.
A hit counter that keeps everything. Counting the hits newer than t − 300 in a list that's never trimmed gives the right number and grows forever; each count also walks the whole list.
A visit that keeps the forward pages. Appending the new page at the end instead of after the cursor leaves the old forward pages reachable: forward goes to a page the user left behind.
A separator inside a string. Any separator character can appear in a string; only a length, or an escape for the separator, keeps the strings apart.
Check yourself
Quiz
1 / 6Multiple choice
A TimeMap holds set(k, "a", 2), set(k, "b", 6) and set(k, "c", 11). What does get(k, 10) return?
Multiple choice
A Snapshot Array runs set(1, 4), snap(), set(1, 8), set(1, 2), snap(). What does get(1, 1) return?
Multiple choice
A HitCounter gets hit(5), hit(200), hit(305). What does getHits(305) return?
Multiple choice
BrowserHistory("x"), visit("y"), visit("z"), back(1), visit("w"). What does forward(1) return?
Multiple choice
With a length and a
# before each string, what does ["ab", "c#"] encode to?Multiple choice
Why can Snapshot Array's get binary search a cell's history without sorting it first?
Practice
In this section, easy to hard:
- Logger Rate Limiter: one time per message, when it may print again.
- Encode and Decode Strings: a length before every string.
- Time Based Key-Value Store: a history per key, read with the last time at or before t.
- Snapshot Array: a history per cell, replaced within a snap.
- Design Hit Counter: a queue of hit times, or 300 buckets.
- Design Browser History: an array, a cursor and an end mark.
Data Structure Design Quiz, at the end of this section, mixes both lessons.