google 面经

第一个是个印度女生，让设计一个data structure，容纳n个数据，可以随时返回当前n个数据的中位数，而且一直在往结构里输入新整数。当加入一个新整数时，最早加入的整数要删除。
-一个minheap一个maxheap，同时用linkedlist维持输入输出顺序。
-问了如何处理各种异常输入，只回答了极值，空值，内存超了。
第二个是native小哥。给一个s

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

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

。
-bug3,stringbuilder在append的时候</br>没双//
-然后说优化。本来是双层循环，O(n^2);但是用trie tree就可以O(n);但是没时间实现了。

第二题可以这样做吗?
先找dict 里所有的string 在 s里的interval = [start, end], 思路可以用strstr 那题
然后merge 所有interval, 思路是merge interval 那题
然后取 merge 后的interval 对应的s 里面的substring,  前后加<br></br>, 对没有任何interval 对应的substring 直接加入结果当中
不知道并查集怎么做

oio14644 发表于 2017-2-28 11:13
第二题可以这样做吗?
先找dict 里所有的string 在 s里的interval = [start, end], 思路可以用strstr 那题
...

嗯嗯。你说的有道理。后来跟小伙伴讨论，他说也是你说的这样做。

dlh012 发表于 2017-3-1 04:39
嗯嗯。你说的有道理。后来跟小伙伴讨论，他说也是你说的这样做。

dict 有可能很大，不应该走这个方向，除非前提是dict有限。

第一题如何删除heap中最早加入的数据

jiaguofang 发表于 2017-3-7 04:59
第一题如何删除heap中最早加入的数据

priorityqueue有remove()

dlh012 发表于 2017-3-15 09:01
priorityqueue有remove()

remove是O(n)吧

jiaguofang 发表于 2017-3-16 00:23
remove是O(n)吧

貌似不是logN；但貌似java有个treemap可以支持logN；用python哭过，py的data structure少太多了

第一题怎么求中位数啊？中位数不是中间那个数的意思嘛，用minheap和maxheap怎么求啊，难道说这里的中位数是 (max+min)/2

jiaguofang 发表于 2017-3-16 00:23
remove是O(n)吧

当然是log（n）

删除的操作是被是删除节点和heap tree最后一个元素交换，删除最后一个节点，然后把交换过的节点上升或者下降。是log n的。