谷狗加面3.1

刚结束的谷狗加面，听声音应该是个本土小姐姐，全程冷冷的不怎么爱说话。

第一题，sentence similarity，判断句子是否同义词，还好之前面经见过LC上也刷过，followup就是可以transitive。

第二题，给了两个function, start(id, start_time), stop(id, time)，分别表示给id赋值开始和结束时间，给了一堆这样子的操作（确保start小id的operation先出现，以及每个id最后都有start_time和stop_time），要求按start顺序print对应的id, start_time, stop_time，要求空间复杂度尽可能小，不能一股脑先全部记录再全部print。没见过这题，一开始理解错了以为很简单，后来说了几种思路，对面指出问题，才发现很麻烦。
e.g.，start(1, 1), start(2, 2), stop(2, 3), start(3, 4), stop(3, 5), stop(1,6)，print顺序是(1,1,6), (2, 2, 3), (3,4, 5) #(id, start_time, end_time)
start(1,1), stop(1,2), start(2,2), start(3,3), stop(2,4), stop(3, 5)，print顺序是(1,1,2), (2, 2, 4), (3, 3, 5)
我最后想的思路是用doubly linked list，当更新的id是linked list中的head，且start和end time都存在，才可以print然后看下一个。感觉大方向应该可行，但代码里需要处理的细节太多最后时间不够了，google doc里的代码肯定很多bug。希望大家畅所欲言看看大家这题怎么想的。

发出来攒个人品求通过，希望小姐姐能高抬贵手。这也是最后一次面试机会了，找工作这段时间经历各种冷暖，耗的时间也太久，这次如果挂了就只能回国了。

yzkst06100 发表于 2018-3-2 07:52
意思是一结束就print？

比如这个例子，start(1,1), stop(1,2), start(2,2), start(3,3), stop(2,4), stop(3, 5)。在stop(1,2)时候，id=1就可以print了，之后stop(2,4)时，id=2就可以print了。 stop(3, 5), id=3可以print。

再比如这个例子，start(1, 1), start(2, 2), stop(2, 3), start(3, 4), stop(3, 5), stop(1,6)，到stop(2,3)的时候，id=2已经存在start和end time了，但之前的id=1还不满足print的条件还没print，所以就要等着id=1 print之后才能print 2。

看起来跟“区间排序”挺类似的。其实是给定的是已经按照开始时间排好顺序的区间了，而且已经编好了号。感觉应该可以用queue（Python的话，deque更贴切一点）做吧。对每一个输入，如果是start，直接append，如果是stop，那么看看它的id是否跟queue的hea.id一样，如果一样，print，否则继续append。如果是print的话，需要继续check if head.id == end.id，print if ==, until queue is empty or invalid。

补充内容 (2018-3-4 01:57):
typo，hea.id应该是head.id

haohao188 发表于 2018-3-2 08:01
这不能够啊 一开始就print 第一个 （1，1）都不知道什么时候结束 怎么可能第一个就print它？

其他的即使满足print条件，但第一个还没print，其他的就要等着不能print。最后每个id都确定会有且只有一个start和end。最差的情况就是最后一步全部print，比如我的第一个例子。好的情况下有些id中间就可以print出去节省memory

同一个id可以被重复开始结束么？ like start 1，1， end 1，2 start1，3   end1，4这种情况咋办？

yzkst06100 发表于 2018-3-2 07:17
同一个id可以被重复开始结束么？ like start 1，1， end 1，2 start1，3   end1，4这种情况咋办？

不会出现这样的情况，每个id只有一次start和stop

Sebastian37019 发表于 2018-3-2 07:23
不会出现这样的情况，每个id只有一次start和stop

那就把 id 开始结束时间 封装一下？然后弄个heap ？

yzkst06100 发表于 2018-3-2 07:29
那就把 id 开始结束时间 封装一下？然后弄个heap ？

我一开始也考虑heap，但首先不是每个operation后都要print, 你不知道什么时候要print（满足start最小的id存在start和end，才print，start大的id满足条件了也不能print），其次heap里不方便更新中间id的start和end。

补充内容 (2018-3-2 07:44):
面试官说要优化space，不能等全部operation之后把保存记录全部信息按顺序print，要在每个id能print的时候尽早就print，难点就在这

Sebastian37019 发表于 2018-3-2 07:35
我一开始也考虑heap，但首先不是每个operation后都要print, 你不知道什么时候要print（满足start最小的id ...

意思是一结束就print？

Sebastian37019 发表于 2018-3-2 07:35
我一开始也考虑heap，但首先不是每个operation后都要print, 你不知道什么时候要print（满足start最小的id ...

这不能够啊 一开始就print 第一个 （1，1）都不知道什么时候结束 怎么可能第一个就print它？

今天也加面了。为楼主加油。同求一波人品。