数组Snapshot

14417335

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

kaipeng21

第二种

您好！
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 220 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

testwe

简单的写了下数组的。基本思想是：

维护一个version num，TakeSnapshot时加1
数组的每个元素是一个{since_version, value} 的vector （保存的其实是the value since a version的信息）
Get，O(log(那个元素不同版本的个数))，二分查找到想要的since_version即可，我这里用的是upper_bound的结果减1
Set，O(1)。看看那个位置最新的version，如果和当前version相等，直接覆盖；否则append

#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;
template <typename ValueType>
class VersionedArray {
public:
using Version = size_t;
// default_val is the default value when an element doesn't exist.
explicit VersionedArray(size_t size, ValueType default_val)
: v_(size), default_val_(default_val) {}
void Set(size_t pos, ValueType val) {
assert(pos < v_.size());
if (v_[pos].empty() || v_[pos].back().first != ver_) {
v_[pos].push_back({ver_, val});
} else {
v_[pos].back().second = val;
}
}
int Get(size_t pos, Version ver) {
assert(pos < v_.size());
if (v_[pos].empty()) {
return default_val_;
}
// Find a version > ver, then the previous version is what we want.
auto it = upper_bound(
v_[pos].begin(), v_[pos].end(), make_pair(ver, -1),
[](const pair<Version, int>& v1, const pair<Version, int>& v2) {
return v1.first < v2.first;
});
if (it == v_[pos].begin()) {
return default_val_;
}
return prev(it)->second;
}
void TakeSnapshot() { ver_++; }
Version LatestVersion() const { return ver_; }
private:
vector<vector<pair<Version, ValueType>>> v_;
Version ver_ = 0;
const ValueType default_val_; // Default value when an element doesn't exist.
};
int main(int, char*[]) {
constexpr int NOT_FOUND = numeric_limits<int>::min();
VersionedArray<int> va(10, NOT_FOUND);
va.Set(0, 0);
assert(va.Get(0, va.LatestVersion()) == 0);
assert(va.Get(1, va.LatestVersion()) == NOT_FOUND);
va.TakeSnapshot(); // Now latest version is 1
va.Set(0, 10);
va.Set(1, 11);
va.Set(1, 111);
assert(va.Get(0, 0) == 0);
assert(va.Get(0, 1) == 10);
assert(va.Get(1, 0) == NOT_FOUND);
assert(va.Get(1, 1) == 111);
va.Set(1, 1111);
va.TakeSnapshot(); // Now latest version is 2
va.TakeSnapshot(); // Now latest version is 3
va.TakeSnapshot(); // Now latest version is 4
assert(va.Get(0, 0) == 0);
assert(va.Get(0, 1) == 10);
assert(va.Get(0, 2) == 10);
assert(va.Get(0, 3) == 10);
assert(va.Get(0, 4) == 10);
assert(va.Get(1, 0) == NOT_FOUND);
assert(va.Get(1, 1) == 1111);
assert(va.Get(1, 2) == 1111);
assert(va.Get(1, 3) == 1111);
assert(va.Get(1, 4) == 1111);
return 0;
}

复制代码

补充内容 (2019-4-18 01:34):
Followup的map，和数组相比，基本类似

补充内容 (2019-4-18 01:35):
刚才补充了一句话，原来能高亮的代码排版全乱了。麻烦版主看到了帮忙修改一下代码的格式。

西风瘦马1912

请问楼主，输入的是什么东西？不同的version是什么意思？

14417335

西风瘦马1912 发表于 2019-3-3 10:06
请问楼主，输入的是什么东西？不同的version是什么意思？

举个例子吧：

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

步惊云

提示: 作者被禁止或删除内容自动屏蔽

Warald

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

14417335

增加一个followup，Snapshot Map

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

magicsets

关于Snapshot Map我写了一份参考代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) {
SnapshottableMap map = new SnapshottableMap();
Snapshot s0 = map.createSnapshot();
map.put("name", "John");
map.put("country", "UK");
Snapshot s1 = map.createSnapshot();
Assert(s1.get("name").equals("John"));
Assert(s1.get("country").equals("UK"));
map.put("name", "Marta");
Snapshot s2 = map.createSnapshot();
Assert(s2.get("name").equals("Marta"));
Assert(s2.get("country").equals("UK"));
Assert(s1.get("name").equals("John"));
Assert(s0.get("name") == null);
map.put("label", "AAA");
map.put("label", "BBB");
Snapshot s3 = map.createSnapshot();
Assert(s3.get("label").equals("BBB"));
System.out.println("--------\n" + s1.toDebugString() + "--------\n");
// --------
// country: UK
// name: John
// --------
System.out.println("--------\n" + s2.toDebugString() + "--------\n");
// --------
// country: UK
// name: Marta
// --------
System.out.println("--------\n" + s3.toDebugString() + "--------\n");
// --------
// country: UK
// name: Marta
// label: BBB
// --------
}
private static void Assert(boolean value) {
if (!value) {
throw new RuntimeException("");
}
}
}
// Snapshot只存version number和主map的引用
class Snapshot {
private int snapshotVersion;
private SnapshottableMap map;
public Snapshot(int version, SnapshottableMap map) {
this.snapshotVersion = version;
this.map = map;
}
public String get(String key) {
return map.get(key, snapshotVersion);
}
public String toDebugString() {
return map.toDebugString(snapshotVersion);
}
}
// SnapshottableMap的实现
class SnapshottableMap {
private int lastestVersion = 0;
private List<Snapshot> snapshots = new ArrayList<>();
private Map<String, ValueHistory> storage = new HashMap<>();
public void put(String key, String value) {
ValueHistory history = storage.get(key);
if (history == null) {
history = new ValueHistory();
storage.put(key, history);
}
history.put(value, lastestVersion);
}
public String get(String key) {
return get(key, lastestVersion);
}
// 微量级时间的create snapshot
public Snapshot createSnapshot() {
Snapshot snapshot = new Snapshot(lastestVersion++, this);
snapshots.add(snapshot);
return snapshot;
}
public List<Snapshot> getSnapshots() {
return snapshots;
}
public String get(String key, int version) {
ValueHistory history = storage.get(key);
if (history == null) {
return null;
}
return history.get(version);
}
// 打印某一个version的所有值用于调试
public String toDebugString(int version) {
StringBuilder sb = new StringBuilder();
for (String key : storage.keySet()) {
final String value = get(key, version);
if (value != null) {
sb.append(key + ": " + value + "\n");
}
}
return sb.toString();
}
}
class ValueHistory {
// 代码逻辑保证slots中version号码一定是有序的
private ArrayList<ValueSlot> slots = new ArrayList<>();
public void put(String value, int version) {
// 修改最后一个version或者是添加新version
if (!slots.isEmpty()) {
ValueSlot lastSlot = slots.get(slots.size() - 1);
if (lastSlot.getVersion() == version) {
lastSlot.SetValue(value);
return;
}
}
slots.add(new ValueSlot(version, value));
}
public String get(int version) {
// 二分查找version
int index = Collections.binarySearch(slots, version);
if (index < 0) {
if (index == -1) {
return null;
}
// 不存在指定version，但是有之前的version
index = -index - 2;
}
return slots.get(index).getValue();
}
}
class ValueSlot implements Comparable<Integer> {
private int version;
private String value;
public ValueSlot(int version, String value) {
this.version = version;
this.value = value;
}
public int getVersion() {
return version;
}
public void SetValue(String newValue) {
value = newValue;
}
public String getValue() {
return value;
}
@Override
public int compareTo(Integer other) {
return version - other;
}
}

复制代码

liaohs49

用的list，然后binary search搜索。
优化了空间。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class SnapHashMap<K, V> {
class VersionedValue {
public V val;
public int ver;
public VersionedValue(int ver, V val) {
this.ver = ver;
this.val = val;
}
}
private HashMap<K, ArrayList<VersionedValue>> map;
private int version = 0;
public SnapHashMap() {
map = new HashMap<K, ArrayList<VersionedValue>>();
}
public int snap() {
return this.version++;
}
public V getVerVal(K key, int ver) {
if (ver >= this.version) {
return null;
}
ArrayList<VersionedValue> verVals = map.get(key);
if (verVals.get(0).ver > ver) {
return null;
}
if (verVals.get(verVals.size() - 1).ver < ver) {
return verVals.get(verVals.size() - 1).val;
}
// binary search ver
return binarySearch(verVals, ver);
}
// find equal or biggest ver smaller than target version
public V binarySearch(List<VersionedValue> list, int targetVer) {
int left = 0, right = list.size() - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (list.get(mid).ver > targetVer) {
right = mid;
} else if (list.get(mid).ver < targetVer) {
left = mid;
} else {
return list.get(mid).val;
}
}
return list.get(left).val;
}
public void put(K key, V value) {
if (!map.containsKey(key)) {
VersionedValue verVal = new VersionedValue(this.version, value);
ArrayList<VersionedValue> initVerVals = new ArrayList<VersionedValue>();
initVerVals.add(verVal);
map.put(key, initVerVals);
} else {
ArrayList<VersionedValue> verVals = map.get(key);
// check if is new version
if (verVals.get(verVals.size() - 1).ver == this.version) { // if ver exist
verVals.get(verVals.size() - 1).val = value;
} else { // if ver not exist, then add
verVals.add(new VersionedValue(this.version, value));
}
}
}
public V get(K key) {
ArrayList<VersionedValue> verVals = map.get(key);
return verVals.get(verVals.size() - 1).val;
}
public static void main(String[] args) {
SnapHashMap<Integer, Integer> map = new SnapHashMap<>();
map.put(1, 11);
System.out.println("ver " + map.snap());
map.put(1, 12);
map.put(2, 23);
System.out.println("ver " + map.snap());
map.put(1, 14);
System.out.println("val " + map.get(1));
System.out.println("ver val " + map.getVerVal(2, 0));
System.out.println("ver val " + map.getVerVal(2, 1));
}
}

复制代码

霍建华

提示: 作者被禁止或删除内容自动屏蔽

BridgeHUHX

implement 4 interfaces for class Snapshot, 面之前没见过，后来好像看到是高频题，不知道怎么才是最佳。如果用数组，每次snapshot增加时复制，实现容易，get O(1), set O(n)，空间复杂度不好。估计不是面试官想要的。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限或查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[高频题] 数组Snapshot

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

评分

google snapshot

评分

浏览过的版块