Google Onsite 12月新鲜面经

代同学发Google Onsite面经
1.        mine sweeping问题，要求初始化棋盘和完成点击更新棋盘状态
2.        一棵树，每个node可能有多个childnode（不止两个

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

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

个json文件的plaintext是不是一样。也就是去掉逗号，冒号后纯文本是不是一样。

sunnyroom 发表于 2016-12-17 01:33
同问，json就是字符串。
一个一个字符比较就可以了吧。
不知道这题考什么

你说的是第五轮把。就是去掉json的'{',',','"'这些字符和换行符后，剩下的字符串是一样的。他先用StringBuilder 递归获得整个字符串，然后比较两个字符串是否相等。后来面试官问如果没有那么大空间怎么办，方法Stack用DFS，每处理一次存到queue中，比较两个queue共同的prefix是否相同，不一样直接返回False.

工图新一 发表于 2016-12-14 05:26
第二轮是不是先要遍历一遍数，看树种最大的children数目，将2叉树做法变成n叉树做法？

我觉得不用，直接按照深度遍历来存树，把子节点们想办法group起来就行，比如用括号。
例如对树：
     0
   / | \
  1  2  3
|  / \
4 5   6
serialize 成 0(1(4())2(5()6())3())，然后deserialize就用个栈重建就行。

weii 发表于 2016-12-24 14:49
LZ 请问第四题是拓扑排序吗？next指针是指向多个子节点吗？
然后能不能补充一下第五题的细节？多谢多谢！ ...

第四题是拓扑排序。每个Node只有一个Next指针，指向list中另一个Node. 要求存在环的话throw exception.
这道题没有写很久，后来聊了一下实现Google DOC 这样一个共享文档client, server 各需要怎么设计。室友是用流的方法实现的。

第三轮说的不太清楚。第一轮求详细

zyoppy008 发表于 2016-12-13 15:36
第三轮说的不太清楚。第一轮求详细

第四轮 说错了

想问第二轮的思路~

第二轮是不是先要遍历一遍数，看树种最大的children数目，将2叉树做法变成n叉树做法？

zyoppy008 发表于 2016-12-13 16:33
第四轮 说错了

同问，json就是字符串。
一个一个字符比较就可以了吧。
不知道这题考什么

请问楼主，除了算法题有面其他内容嘛，比如数据结构/Java/OOD的小问答题，以及简历project~

http://www.geeksforgeeks.org/serialize-deserialize-n-ary-tree/
这个可以？

小A要当码农 发表于 2016-12-24 09:45
http://www.geeksforgeeks.org/serialize-deserialize-n-ary-tree/
这个可以？

行，但是如果value是数字的话还需要一个delimiter