google intern

两天前的背靠背，都不是常规题

第一轮是设计题，给你函数 int timerID = startTimer(int millseconds, Runnable run); cancelTimer(int timerID);  还有一个class sprite 有draw(int x, int y) function，功能是在一个画板上让你在x y这个坐标画出这个sprite
要求让你实现一个单线程a

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

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

回一个int, 比较int是否一样，显然不是小哥满意的答案。
狗家面试确实比较看运气，发个帖子求个好运吧。


补充内容 (2018-1-20 17:09):
居然过了hc, 之前觉得自己两轮都做的不完美...我面试时具体的做法晒在第二页了，希望能对大家有帮助吧

我昨天也面到了tree这个题，写的也是recursion的办法，面试官问能不能优化这个算法，我想了半天，他提示可以destroy这个tree，你函数的input不一定是root，然后我就说可以把input变成list of edges的形式，比如（A (B)(C))可以转化成[（A C）,(A B)]，如果tree是相似的，这个list of edges内容应该是相同的。不知道这个list of edges排序后能不能作为楼主这题的hash

第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)？然后T(node with no children) = O(1)这样子 4^(logN)然后N^2

第一题：我本科ee，很惭愧没有学过线程，面试时候我一听到thread就打开了geek for geek搜了一个线程的例子，然后面试时候照猫画虎写，面试完自己在家恶补了几天线程，发现自己照猫画虎写的居然对。。具体就是把自己实现的这个class 变成runnable的，然后在run 里 call start。 当时面试官问我想怎么做，我说我想用一个while loop, 然后用一个boolean值作为开关控制start跑不跑，他说不用这样子，直接在run里call start就可以了。然后在draw function里要实现实时更新月球的地址，我之前学过一点computer graphics, 要使一个object绕另一点转动的计算方法是：1平移至原点，2乘cos sin来绕原点旋转，3平移回去 。面试官没听太懂，但是他人很好，我写完代码后他手算了一下说这个看起来可行，然后他跟我介绍了他期望的方法是横竖平移，也是通过角度来计算x y各平移多少。具体计算角度就是用过了多少时间来计算，我说 java获取当前时间还要声明一个calendar对象，我们时间不多了我直接assume一个getCurrentTime()行吗？面试官说好的没问题。这一轮感觉一直被很好地引导着做题，特别感谢这位面试官。

第二题用BFS应该是 O(n)？

补充内容 (2018-1-5 06:02):
还有MD5 应该最小化conflict rate貌似

xh_pku 发表于 2018-1-5 06:01
第二题用BFS应该是 O(n)？

补充内容 (2018-1-5 06:02):

recursion做法应该是n方的，可能我题意描述的不确切吧，你可以上geek for geek搜索一下原题。

wsypeter 发表于 2018-1-5 06:17
recursion做法应该是n方的，可能我题意描述的不确切吧，你可以上geek for geek搜索一下原题。

是这个吗？：
https://www.geeksforgeeks.org/tree-isomorphism-problem/

dingshilun 发表于 2018-1-5 06:23
第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)？然后T(node with no ...

嗯 我觉得是的 ～ 那么 Hash怎么设计呢？

dingshilun 发表于 2018-1-5 06:23
第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)？然后T(node with no ...

对的紫薯紫薯紫薯

xh_pku 发表于 2018-1-5 06:26
嗯 我觉得是的 ～ 那么 Hash怎么设计呢？

粗略想了想，如果要保证完全正确，可以先把这棵树所有的同构体都计算出来然后serialize，然后根据字典序排序，随后将这整个字符串计算一个md5码。。。虽然很麻烦也不是完全正确=。=但是两个similar的树md5一定一样，

我二轮也是一个类似的题目
也是搞一个timestamp
超过时间范围就报错
不超过就输出map[key]
然后follow up一些复杂度了，频繁查找，怎么减少map大小之类的吹牛玩意

请问楼主，能说一下第一题怎么画sprite吗，要定义什么全局变量么