推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1429|回复: 20
收起左侧

google nyc onsite

[复制链接] |试试Instant~ |关注本帖
zyjdxtc 发表于 2017-7-11 10:32:50 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@Google - 内推 - Onsite |Other其他

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今天去谷歌nyc office面试了,总体来说运气不错,遇到了两个国人,题目也不怎么难,而且不知为何没有问到system design。。。不管怎样,希望最后能有offer,祝大家同样有好offer!
我用的python,大家不要鄙视我. from: 1point3acres.com/bbs


答案我就不详细写了,大家肯定都知道. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

1. 白人。
1.1 问一个数组里面最长的连续的递增数列的长度
1.2 如果是一个tree,不一定是binary tree,的最长的连续递增的序列的长度
     这一问我是用recursive dfs做的,然后被要求用iterative 做一下。

2. 白人。求两个整数的二进制有多少个不同的位数。。。
我说直接xor 然后用python 里bin 函数转化成字符串,数有几位是‘1’。。-google 1point3acres

后续要求:
2.1 不让用转化成字符串。我说那就一位一位的数,用 <<1做。-google 1point3acres
2.2 怎么更快?可以把这些preprocessing到一个array里,比如我存0~2^16的所有数字的2进制的1的位数在内存里,a xor b之后去这里查每16位的1就是了.
2.3 取多少8位 16位还是更多?粗略估算了占内存的多少,64位太大,32位合适,我说但具体好不好还得靠实际测试。
2.4 他说如果你测试发现用存32位的数据比16位的慢(不算preprocessing 时间),可能什么原因?我想了2分钟说没想出来,难道你内存坏了?。。。他笑了,说到时间了。。。大家知道啥原因吗?估计很简单,脑子堵了

3. 国人。. 1point 3acres 璁哄潧
问一个数组能否只改变一个数字,从而让他变成单调增的数组。.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如[3,3,2,2] 不可以,[1,2,5,3,3] 可以把5变成2或者3,可以。. visit 1point3acres.com for more.
这位兄弟面试过程中也很照顾我。感谢!

午餐由一个欧洲人带我参观。席间谈笑甚欢,他是cs博士,我说我物理博士,聊了聊学术道路的艰辛,以及谷歌概况。

4. 白人。
guess number,好像是以前的题?我没做过,还好跟leetcode上那个predict winner(或之类名字)的题很相似。. 1point3acres.com/bbs
给定一个范围,我要猜一个这个范围内的数字,每猜一个数,我要支付这个数字相同的钱,每次我猜之后,他的回答是大了,或者小了。问最后我最少付多少钱可以一定猜到这个数。
注意的是他的回答可能是变化的,只要不违反他之前的回答。
我设了一个dp 2D array,然后跟leetcode 做法predict winner相似。总而言之是我和他都要取对自己最有利的下一步。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
5. 国人。
给定一个函数f(x),由一段单调增一段单调减构成,比如抛物线。给定单调增的x的数组输入,要求输出单调增的y。
大概做法是从两端开始考虑,结果数组里填f(x),要注意区分抛物线(比如)开口向上向下的情况。期间还指导了我如何写出漂亮的程序结构,比如loop里少用些if条件。
我感觉这兄弟给我放水了,而且看着很亲切。之后留了几分钟我们用中文聊天的,我说听你有南方口音?结果竟是一个城市的,小兄弟比我还小2届,说了两句家乡话,痛快!




评分

2

查看全部评分

本帖被以下淘专辑推荐:

iker01 发表于 2017-7-11 11:03:44 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主你好!能问下你是在职跳槽吗?想了解下你是大概什么时候投的啊,是general的开发岗吗?
回复 支持 反对

使用道具 举报

iag 发表于 2017-7-11 11:39:39 | 显示全部楼层
关注一亩三分地微博:
Warald
1
  1. class Solution(object):
  2.     def lengthOfLIS(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int. 1point3acres.com/bbs
  6.         """
  7.         size = len(nums)
  8.         dp = []
  9.         for x in range(size):
  10.             low, high = 0, len(dp) - 1
  11.             while low <= high:
  12.                 mid = (low + high) / 2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.                 if dp[mid] >= nums[x]:-google 1point3acres
  14.                     high = mid - 1
  15.                 else:
  16.                     low = mid + 1
  17.             if low >= len(dp):
  18.                 dp.append(nums[x])
  19.             else:
  20.                 dp[low] = nums[x]
  21.         return len(dp)
复制代码
回复 支持 反对

使用道具 举报

 楼主| zyjdxtc 发表于 2017-7-11 20:25:18 | 显示全部楼层
iker01 发表于 2017-7-11 11:03
楼主你好!能问下你是在职跳槽吗?想了解下你是大概什么时候投的啊,是general的开发岗吗?
. 鍥磋鎴戜滑@1point 3 acres
我现在还是博后,按理说不是学生,但专业不对口,也没有公司工作经验,所以不知道是否算是在职跳槽
我是找朋友5月底内推的,后来六月中旬有hr联系我。应该是普通的general的岗位
回复 支持 反对

使用道具 举报

stealop 发表于 2017-7-11 23:26:22 | 显示全部楼层
第二题的思路应该就是 把两个是 做 xor 操作 然后 查找结果里面 1的 个数吧? 如果用 暴力法 一个 一个的  1<< 可能有有个bug 就是 如果是一个负数, 那么最左边的那位永远是 1, 那就无线循环了, 书上有一个解法就是 不停地 n  =  (n-1) & n, 直到n为 0, 复杂度就是 k (k是 1的 个数)
回复 支持 反对

使用道具 举报

jyttwc901231 发表于 2017-7-12 05:27:30 | 显示全部楼层
2.2 怎么更快?可以把这些preprocessing到一个array里,比如我存0~2^16的所有数字的2进制的1的位数在内存里,a xor b之后去这里查每16位的1就是了.

请问Lz,这意思是省去10进制转换成2进制那一步?
回复 支持 反对

使用道具 举报

fenghao 发表于 2017-7-12 19:15:41 | 显示全部楼层
jyttwc901231 发表于 2017-7-12 05:27. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2.2 怎么更快?可以把这些preprocessing到一个array里,比如我存0~2^16的所有数字的2进制的1的位数在内存里 ...

lz的意思是做index
回复 支持 反对

使用道具 举报

 楼主| zyjdxtc 发表于 2017-7-12 21:27:39 | 显示全部楼层
jyttwc901231 发表于 2017-7-12 05:27
2.2 怎么更快?可以把这些preprocessing到一个array里,比如我存0~2^16的所有数字的2进制的1的位数在内存里 ...

差不多,比如我存0~255(8bit) 整数的二进制的1的个数在数组里,然后a^b = 15,就直接从数组里读,从而省去10进制转化2进制的这一步。
回复 支持 反对

使用道具 举报

msu_HIDDEN 发表于 2017-7-12 21:28:06 | 显示全部楼层
2.4 和cpu缓存有关吧 你缓存太小 miss率高就会降低效率
回复 支持 反对

使用道具 举报

fenghao 发表于 2017-7-12 21:46:11 | 显示全部楼层
msu_HIDDEN 发表于 2017-7-12 21:28
2.4 和cpu缓存有关吧 你缓存太小 miss率高就会降低效率

主要还是内存,缓存肯定都放不下
回复 支持 反对

使用道具 举报

edyyy 发表于 2017-7-12 22:56:48 | 显示全部楼层
楼主 有卡了吗?我师兄也是博后 现在面试中。。。就是愁工作签证问题呢
回复 支持 反对

使用道具 举报

dojiangv 发表于 2017-7-13 00:14:56 | 显示全部楼层
狗狗又有人头了?
回复 支持 反对

使用道具 举报

 楼主| zyjdxtc 发表于 2017-7-13 03:21:29 | 显示全部楼层
edyyy 发表于 2017-7-12 22:56
楼主 有卡了吗?我师兄也是博后 现在面试中。。。就是愁工作签证问题呢

没有 抽不中滚蛋
回复 支持 反对

使用道具 举报

 楼主| zyjdxtc 发表于 2017-7-13 03:22:49 | 显示全部楼层
edyyy 发表于 2017-7-12 22:56
楼主 有卡了吗?我师兄也是博后 现在面试中。。。就是愁工作签证问题呢

没办法                        
回复 支持 反对

使用道具 举报

 楼主| zyjdxtc 发表于 2017-7-13 03:53:40 | 显示全部楼层
fenghao 发表于 2017-7-12 21:46
主要还是内存,缓存肯定都放不下

嗯 存32位的话,这里的整数他要求是8Byte的,所以要32G,他说内存给我64G,可以放下。所以还不知道是啥原因
回复 支持 反对

使用道具 举报

haifengc 发表于 2017-7-14 02:39:32 | 显示全部楼层
楼主能讲讲这一题吗

uess number,好像是以前的题?我没做过,还好跟leetcode上那个predict winner(或之类名字)的题很相似。.1point3acres缃
给定一个范围,我要猜一个这个范围内的数字,每猜一个数,我要支付这个数字相同的钱,每次我猜之后,他的回答是大了,或者小了。问最后我最少付多少钱可以一定猜到这个数。
注意的是他的回答可能是变化的,只要不违反他之前的回答。
我设了一个dp 2D array,然后跟leetcode 做法predict winner相似。总而言之是我和他都要取对自己最有利的下一步
. 鍥磋鎴戜滑@1point 3 acres

是不是才对的那个数字不收钱,
如果收钱,而且每次都对自己有利的,那最少的情况就是直接才那个数字啊,. 鍥磋鎴戜滑@1point 3 acres

可能是我题目理解错了,楼主你说说吗?谢谢
回复 支持 反对

使用道具 举报

DerekLH 发表于 6 天前 | 显示全部楼层
可能因为数组是连续地址存的,每次取的时候先从cache里取,然后碰巧发生了较大的碰撞. from: 1point3acres.com/bbs

补充内容 (2017-7-20 12:13):
因为cache从内存加载到cache里的时候也是一次加一排的
回复 支持 反对

使用道具 举报

jy_121 发表于 5 天前 | 显示全部楼层
问下楼主第三题当时是怎么回答的?谢谢
回复 支持 反对

使用道具 举报

knight0clk 发表于 5 天前 | 显示全部楼层
jy_121 发表于 2017-7-21 12:32. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
问下楼主第三题当时是怎么回答的?谢谢

第三题不就是扫描一下就出来答案了吗?发现invalid数字,总是变成和前一个相同,然后接着看下一个,这样处理
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-26 05:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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