小众lyft昂赛

kqxqx 发表于 2017-12-13 01:03
block/rollback是不是这样的意思：

BLOCK --> mark beginning of the block

有顺序， 我当时用的是nested list,就是每次有block就加一个list在最后，有操作就加在这个list里，去除就删掉最后一个，其实用stack比较好。我有工作经验。

volibear 发表于 2017-12-13 03:33
有顺序， 我当时用的是nested list,就是每次有block就加一个list在最后，有操作就加在这个list里，去除就 ...

nested list的数据结构你是当场写的么？这也有不少代码吧

再问一个外nested block的问题，比如：
BLOCK
X
BLOCK
Y
COMMIT
Z
ROLLBACK

这样执行完后，X和Z肯定被rollback了，Y呢？是不是Y就不需要被rollback了？

sterlanUSA 发表于 2017-12-10 10:45
能说一下block 和rollback 是不是以API形式出现的？也就是block(...) 可以看做是一个transaction执行一系 ...

input是这样的， 不支持parallelism， commit和rollback是主动的

kqxqx 发表于 2017-12-13 03:54
nested list的数据结构你是当场写的么？这也有不少代码吧

再问一个外nested block的问题，比如：

当场写的，Y不需要rollback

1hr coding的时候三哥是不在屋子里的，说没写完有可能是一小时以后他回来，我又写了5-6mins才停下来，大家这个地方注意下吧

kqxqx 发表于 2017-12-13 01:04
你是new grad么？好像最近Lyft没有new grad的head count了，地理不少人的面试都被取消了

not new grad.

volibear 发表于 2017-12-13 04:55
当场写的，Y不需要rollback

我想了一下，我原来的理解好像有点问题，我觉得这样来理解比较好实现

BLOCK --> mark beginning of the block
X         --> do nothing
Y         --> do nothing
...
COMMIT --> mark end of the block, do operations X, Y,  ...

BLOCK --> mark beginning of the block
X         --> do nothing
Y         --> do nothing
...
ROLLBACK --> mark end of the block, no operations

如果这样的话，我觉得可以用一个链表来记录所有的在block里面的操作，每次嵌入一个block，就先把block里面的操作加到链表末尾， list<pair<string,value>> 即可，然后把该block开始的位置push到一个 stack<list<pair<string,value>>::iterator>里，等到了commit/rollback的时候，从stack里pop出该block的起始位置，如果是commit就遍历那段链表，执行那些操作后删除，如果是rollback就直接删除，这样的话就不需要写 nested list的数据结构了

如果是按照原先的理解的话，
BLOCK --> mark beginning of the block
X         --> do operation X: set/unset
Y         --> do operation Y: set/unset
...
COMMIT --> mark end of the block

BLOCK --> mark beginning of the block
X         --> do operation X: set/unset
Y         --> do operation Y: set/unset
...
ROLLBACK --> mark end of the block, and reverse operation X, Y, ...

rollback那个操作还挺难实现的，因为得记住block开始前的kv store状态，不是简单地reverse每个operation就行

不知道面试官给你的是哪个要求？

volibear 发表于 2017-12-13 03:33
有顺序， 我当时用的是nested list,就是每次有block就加一个list在最后，有操作就加在这个list里，去除就 ...

楼主几年工作经验？地里其他的在职跳槽的好像是 90分钟上机 + 2轮design + 1轮manager聊天，你这个略有不同

johnnywsd 发表于 2017-12-13 14:32

这写的驴唇不对马嘴的根本不对啊。。

volibear 发表于 2017-12-13 03:33
有顺序， 我当时用的是nested list,就是每次有block就加一个list在最后，有操作就加在这个list里，去除就 ...

请问用stack怎么实现呢？比如说每次begin的时候都会有一个transaction block, 这个block可能会有很多的commands/operations，这里我有点迷茫，怎么区分stack里不同的block啊。  
用nested list我能理解，List<List<Operation>> list, 每一个block就相当于一个List<Operation> tempList, 在这个block里每智行一个command， 就tempList.add(Operation).  新的一个block就相当于list.add(new ArrayList<>())