📣 4th of July限时特惠: VIP通行证立减$68
回复: 31
跳转到指定楼层
上一主题 下一主题
收起左侧

google intern

全局:

2018(1-3月) 码农类General 硕士 实习@google - 内推 - 技术电面  | | Other | 其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

第一轮是设计题,给你函数 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, 之前觉得自己两轮都做的不完美...我面试时具体的做法晒在第二页了,希望能对大家有帮助吧

评分

参与人数 5大米 +26 收起 理由
浴火擎灯 + 5 wangzhejiayou
forbread + 3 很有用的信息!
reliveinfire + 3 很有用的信息!
二院老同志 + 5 很有用的信息!
xh_pku + 10 很有用的信息!

查看全部评分


上一篇:Mulesoft intern hr面 有没有面过的大佬求经验
下一篇:Yelp OA-01/04/2018

本帖被以下淘专辑推荐:

全局:
我昨天也面到了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
回复

使用道具 举报

推荐
dingshilun 2018-1-5 06:23:31 | 只看该作者
全局:
第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)?然后T(node with no children) = O(1)这样子 4^(logN)然后N^2
回复

使用道具 举报

推荐
 楼主| wsypeter 2018-1-20 17:05:40 | 只看该作者
全局:
第一题:我本科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()行吗?面试官说好的没问题。这一轮感觉一直被很好地引导着做题,特别感谢这位面试官。
回复

使用道具 举报

🔗
xh_pku 2018-1-5 06:01:05 | 只看该作者
全局:
第二题用BFS应该是 O(n)?

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

使用道具 举报

🔗
 楼主| wsypeter 2018-1-5 06:17:00 | 只看该作者
全局:
xh_pku 发表于 2018-1-5 06:01
第二题用BFS应该是 O(n)?

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

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

使用道具 举报

🔗
xh_pku 2018-1-5 06:21:53 | 只看该作者
全局:
wsypeter 发表于 2018-1-5 06:17
recursion做法应该是n方的,可能我题意描述的不确切吧,你可以上geek for geek搜索一下原题。

是这个吗?:
https://www.geeksforgeeks.org/tree-isomorphism-problem/
回复

使用道具 举报

🔗
xh_pku 2018-1-5 06:26:42 | 只看该作者
全局:
dingshilun 发表于 2018-1-5 06:23
第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)?然后T(node with no ...

嗯 我觉得是的 ~ 那么 Hash怎么设计呢?
回复

使用道具 举报

🔗
 楼主| wsypeter 2018-1-5 06:41:18 | 只看该作者
全局:
dingshilun 发表于 2018-1-5 06:23
第二轮那个复杂度是T(root) = 4*(T(subtree of root))+C这样的形式吧(假设完全二叉树)?然后T(node with no ...

对的紫薯紫薯紫薯
回复

使用道具 举报

🔗
dingshilun 2018-1-5 06:45:44 | 只看该作者
全局:
xh_pku 发表于 2018-1-5 06:26
嗯 我觉得是的 ~ 那么 Hash怎么设计呢?

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

使用道具 举报

🔗
空空道友 2018-1-5 06:49:32 | 只看该作者
全局:
我二轮也是一个类似的题目
也是搞一个timestamp
超过时间范围就报错
不超过就输出map[key]
然后follow up一些复杂度了,频繁查找,怎么减少map大小之类的吹牛玩意
回复

使用道具 举报

🔗
wjw779 2018-1-5 07:01:51 | 只看该作者
全局:
请问楼主,能说一下第一题怎么画sprite吗,要定义什么全局变量么
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表