G 面经+加面

1.      Inbox team的年轻白人

类似LC361， enemy变成light，求光线最强值；

follow up1：light的光有范围，e.g.超过两格会消失. Solution：分别算出left，right，up，down，用queue store行列上的光照范围

follow up2：每盏light范围不一样肿么办，用PriorityQueue代替Queue

2.      Design 年轻白人

Telescope system on moon， 有100 telescopes， 天文学家可以用它们拍照观测，每个观测任务可能会要couple hours

和地球通信只能用radio signal，latency会很高；设计系统manage Telescopes, 要fault tolerant，任务调度，deploy update

思路：类似long distance data center的manage， moon上多台app server负责控制telescope，每台server会与地球的master用radio作为heartbeat通信；

如何deployupdate时，选一台active server发送file，然后分chunk，在moon上peer to peer的用gossip传播update

<

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

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

licate id是取average，而且输出还是要sorted by value，

思路：用map，给出two pass NlgN做法，不满意要求onepass；

用binary search的话，因为arraylist 会移动elements，复杂度不理想； linkedlist需要scan才能拿到对应index的element 还是不理想；最后面试官说他是有one-pass NlgN做法的

回报地里，跪求G的offer~~

补充内容 (2016-12-10 15:20):
收到offer了

zyoppy008 发表于 2016-12-2 16:44
不懂你第一题follow up的做法 为啥那样做 直接拿个count计左边的长度 知道左右加起来的和 就可以求右边的长 ...

followup1：你说的很接近，不过细节上，例如算left光亮值时，从左到右scan，每遇到light时，把colulmn Index + 光照range 塞入Queue中，每移动一格，倒要check 当前col index > queue.peek() ,如果是的话，要pop，之后left 光照强度 就等于queue.size()了；然后right up down都一样的做法

followup2：每盏灯range不同，就不能塞到queue里面了，因为后面来的灯有可能先弹出；需要把colulmn Index + 光照range 塞到priority queue里

2.&nbsp; &nbsp;&nbsp; &nbsp;在工作10多年的老白男
一个class Node {int id, int val},
两个Node list, List<Node> n1, List<Node> n2, n1,n2是按val 排序的，且n1,n2各自id没有duplicate， 但n1 n2 之间可能存在duplicate
写merge(n1, n2) 类似merge two sorted list, 但是发现id duplicate就只取其中一个，用Set就搞定了
Followup：这才是真正的题目，duplicate id是取average，而且输出还是要sorted by value，
思路：用map，给出two pass NlgN做法，不满意要求onepass；
用binary search的话，因为arraylist 会移动elements，复杂度不理想； linkedlist需要scan才能拿到对应index的element 还是不理想；最后面试官说他是有one-pass NlgN做法的

这题用map+list可解，类似lru cache,如果有dup  id，找到list节点，一路冒泡swap过去就好了。

不懂你第一题follow up的做法 为啥那样做 直接拿个count计左边的长度 知道左右加起来的和 就可以求右边的长度 然后后范围比较呀 follow up 2呢

Treemap 加hashmap啊

同问第一题 没太 get 到用 queue 和 PriorityQueue 的原因在哪儿，我的理解，不是建一个 matrix，然后遍历每个元素，对 每个发光的点的四周做 +1 操作不就 OK 了么，不知道我理解的对不对

补充内容 (2016-12-3 09:11):
知道了 用楼主的方法，只需要一张Map统计我们需要统计的点就可以了，而不是我那样建一个N^2的矩阵。

另外，碰见Light后，上下左右的遍历+1也不需要了，直接利用Queue中的元素size，即可获知当前的光照址，O（1）

2008 发表于 2016-12-2 21:25
这题用map+list可解，类似lru cache,如果有dup  id，找到list节点，一路冒泡swap过去就好了。

双向链表 + Map ?

mmliu 发表于 2016-12-2 22:44
双向链表 + Map ?

对，
map: id=>list iterator
doubly linked list: struct(id, value, count)

when add new <id, value> check map first,
if does not have, append list, then insert map;
if has, find list node, update value, (count*oldValue+ newValue)/(count+1), then swap with left node or right node until the value are sorted again.

2008 发表于 2016-12-2 23:47
对，
map: id=&gt;list iterator
doubly linked list: struct(id, value, count)

你这复杂度根本就不行 楼主说了

2008 发表于 2016-12-2 23:47
对，
map: id=>list iterator
doubly linked list: struct(id, value, count)

我当时也试图用LRU类似做法，然而lru，每个node都是插入到tail，每次操作可以O(1); 这个要先判断插入位置，无论用arraylist还是linkedlist都比较蛋疼
也试图维护一个binary search tree(treemap类似的)，不过因为输入merge为list，这样还是算two-pass吧，不清楚