狗家面试挂经 求安慰米

第二题怎么根据给定的符号顺序建树啊？

xiaozhu 发表于 2018-7-12 09:02
那怎么确定跟是哪个符号呢  还有怎么确定乘除优先于加减啊

是这样得 这个题有两个输入 一个是中序遍历的string 一个是符号的顺序 按照优先顺序排，
我的做法是最外轮 先用一个循坏 找到最初的根 比如 “+ - * /” 那么先循环找到第一个加号
我特意确认了下 如果是一样的符号怎么处理 面试官说 你随便 一样的没有优先顺序
那么找到+了后
把0 到 +这个index - 1 传入 再把index + 1 到end传入dfs
再循环 还是按那个符号顺序找
dfs退出条件就是start == end
因为你每次都挑的是符号 而且把用过的index 跳过去了 所以不会重复回去挑
挑到最后只剩数字了

请问lz第三题具体怎么做的

浅漾 发表于 2018-7-13 01:09
是这样得 这个题有两个输入 一个是中序遍历的string 一个是符号的顺序 按照优先顺序排，
我的做法是最外 ...

哦哦 好的  我以为你只用了一个中序  就把树给还原了  哈哈哈  谢谢lz

xiaozhu 发表于 2018-7-13 02:29
哦哦 好的  我以为你只用了一个中序  就把树给还原了  哈哈哈  谢谢lz

同问楼主第三题，queue里面放 start的job， map用来做缓存吗？map就是放那些finished了，但是queue里面不是peek的task？

第三题的理解：
Queue存start job id, 存储顺序按照job start order。

e.g.
start(1, time1)
start(2, time2)
start(3, time3)
finish(2, time2)
finish(3, time3)
finish(1, time1)

Queue:
job 1, job 2, job 3

HashMap存finished job id, and log.
e.g.
finish(2, time2)
--- Map ->(2, time2), since queue.peek() ！= 2, 不打印
finish(3, time3)
--- Map ->(3, time3), since queue.peek() ！= 3, 不打印
finish(1, time1)
--- Map ->(1, time1), since queue.peek() == 1, 打印 1， queue.pop(),然后继续检查queue.peek == 2 在map中，打印2。。。继续pop，打印3

这个思路对吗？

感觉面得不错啊~难道一轮挂就会铁挂啊，要求真这么高么？过段时间也要去面了，很忐忑啊:(

楼主加油，感谢分享

aviva 发表于 2018-7-13 14:32
第三题的理解：
Queue存start job id, 存储顺序按照job start order。

对 字符限制 字符限制