Thumbtack OA 数据库实现

就是写一个简单内存数据库：
[img]http:/

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

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

觉都符合了它的Performance Requirement了， 不清楚如何跪的

我当时是类似这样过的：
俩hashmap A和B，A存updated name-value pairs，B存specific value count；再加一个string存reverse commands in a pending transaction。
set: 添加到A，更新B，同时append reverse command到string
unset: 调用set(null)
get: 直接返回A里的值
NUMEQUALTO: 直接返回B里的值
begin: string里append "|"
COMMIT: 直接清空string，其他啥也不管，如果string是空就返回false (NO TRANSACTION)
rollback，把string里的命令拿出来执行一遍，直到遇到"|"（此时调用set时不再添加reverse command到string里），有多个"|"就代表可以rollback多次，如果string是空就返回false

最后string类似："| UNSET a, SET b 8,| SET c 3，"

Time Complexity:
    SET/UNSET/GET/NUMEQUALTO/BEGIN/COMMIT O(1)
    ROLLBACK O(k), k is the number of commands in a transaction

pupuchan1116 发表于 2016-9-23 03:14
它这个OA有很多tricky的点，他给的test case不够的。我记得当初花了不少时间，把所有能想到的test case和边 ...

请问能讲一讲思路么？如果每个transition都maintain整个数据库，似乎内存消耗太大了，如果所有transition maintain一个temp db的话，rollback的时候就要go through all uncommit transitions, 又似乎与要求runtime与transition无关不符，所以还没想好

请问楼主这个OA可以用Java么？还是必须用C++ ？ rollback 的时候为什么要对countValues进行修改？没有commit的话不需要啊 ？

它这个OA有很多tricky的点，他给的test case不够的。我记得当初花了不少时间，把所有能想到的test case和边界条件都包含进去。在它后来已经不招人的情况下我都过了OA拿到面试，所以这道题我印象很深刻

lluo0204 发表于 2016-9-22 23:46
请问楼主这个OA可以用Java么？还是必须用C++ ？ rollback 的时候为什么要对countValues进行修改？没有commi ...

比如：
input:
SET A 10
begin
SET B 10
NUMEQUALTO 10

output
2

如果这样我rollback 的话，NUMEQUALTO 10就变回1了， 所以在rollback 的时候也得对conutValues进行修改的

luckyzzh1989 发表于 2016-9-23 03:37
比如：
input:
SET A 10

I see. 我觉得可能的原因是你每个transition都maintain整个db, 会不会内存消耗太大啊？

pupuchan1116 发表于 2016-9-23 03:14
它这个OA有很多tricky的点，他给的test case不够的。我记得当初花了不少时间，把所有能想到的test case和边 ...

能举几个corner case么？

厉害的超人 发表于 2016-9-23 04:38
我当时是类似这样过的：
俩hashmap A和B，A存updated name-value pairs，B存specific value count；再加一 ...

这个好，我刚才还在想把set前的值记录下来，记这个reverse command更方便了

wearless 发表于 2016-9-23 03:56
能举几个corner case么？

我有点忘了，我记得主要是在rolling back的地方，然后剩下的就是各种输入输出的有效性