周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3173|回复: 17
收起左侧

google 2016全职电面面经

[复制链接] |试试Instant~
我的人缘0
primbo 发表于 2016-11-2 04:03:43 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩

2016(10-12月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
google电面 挂掉了,问题和这个链接里的一模一样,我回答的心路历程也和这个一样。有大神知道 面试官说的linear hashing是什么意思么?. more info on 1point3acres
http://stackoverflow.com/questio ... n-an-int-array-java

. visit 1point3acres for more.
补充内容 (2016-11-2 04:05):. From 1point 3acres bbs
前面的两种方法都不是面试官要的答案。

补充内容 (2016-11-2 10:00):
面试官说了,空间复杂度需要是O(1), 时间复杂度优于 O(n2)

评分

参与人数 1大米 +20 收起 理由
candy_shmily + 20

查看全部评分


上一篇:Microsoft phone 新鲜面筋
下一篇:新鲜的audible面经

本帖被以下淘专辑推荐:

我的人缘0
warriorbrant 发表于 2016-11-3 04:27:35 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  90% (40)
 
 
9% (4)  踩
primbo 发表于 2016-11-3 03:35
如果是1 到n之间的话怎么做? conting sort也要占用空间的啊。

我不知道这是不是叫linear hashing,就是把原数组当成hash数组
  1. public int helper(int[] array){
  2.    int len=array.length();
  3.    for(int i=0;i<len;i++){. from: 1point3acres
  4.        int tmp=Math.abs(array[i]);
  5.        if(array[tmp-1]<0)return tmp;
  6.        else array[tmp-1]*=-1;
  7.    }
  8.    return -1;-google 1point3acres
  9. }
复制代码
回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-2 04:04:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
找数组里面第一个重复的数字
回复

使用道具 举报

我的人缘0
elizabethxiazhi 发表于 2016-11-2 04:27:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (27)
 
 
0% (0)  踩
高票答案不可以么?不然linear probing? 开一个等size数组,h(x)+i是新的index, 插入是O(1),search找重复的的话h(x)+i (i=1,...,k).空间O(n),时间的话看hash 函数选择,最差O(n),平均O(1)。。。这个好像算法导论hash table实现有讲,不知道是不是面馆要的,遇上这种题目真是醉了 ...
回复

使用道具 举报

我的人缘0
shuiguo 发表于 2016-11-2 08:05:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (106)
 
 
2% (3)  踩
难道面试官想让你排序?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-2 10:00:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
shuiguo 发表于 2016-11-2 08:05
难道面试官想让你排序?

排序了找到的就不一定是第一个重复的了。不可以排序.留学论坛-一亩-三分地
回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-2 10:01:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
elizabethxiazhi 发表于 2016-11-2 04:27
高票答案不可以么?不然linear probing? 开一个等size数组,h(x)+i是新的index, 插入是O(1),search找重复的 ...

空间复杂度需要为O(1)
回复

使用道具 举报

我的人缘0
crir 发表于 2016-11-2 12:18:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
让走过的array有序,用binary search找到相邻数字然后insertion?
问题就是insertion的worst case会O(n2)

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
krystal1115 发表于 2016-11-2 12:35:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (19)
 
 
5% (1)  踩
数组中element的值有范围限制么
回复

使用道具 举报

我的人缘0
warriorbrant 发表于 2016-11-2 13:11:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (40)
 
 
9% (4)  踩
如果元素范围在1-n之间我知道咋做,n是length
回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-3 03:35:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
warriorbrant 发表于 2016-11-2 13:11
如果元素范围在1-n之间我知道咋做,n是length

如果是1 到n之间的话怎么做? conting sort也要占用空间的啊。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-3 08:09:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
warriorbrant 发表于 2016-11-3 04:27. visit 1point3acres for more.
我不知道这是不是叫linear hashing,就是把原数组当成hash数组

好强大。big cong,你这咋想出来的。
回复

使用道具 举报

我的人缘0
denev2004 发表于 2016-11-3 08:40:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (16)
 
 
11% (2)  踩
warriorbrant 发表于 2016-11-3 04:27
我不知道这是不是叫linear hashing,就是把原数组当成hash数组

what if tmp is huge....
回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-3 09:00:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
denev2004 发表于 2016-11-3 08:40.1point3acres网
what if tmp is huge....

it only works for number from 1 to n
回复

使用道具 举报

我的人缘0
aimboy 发表于 2016-11-3 09:18:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
回复

使用道具 举报

我的人缘0
warriorbrant 发表于 2016-11-3 09:33:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (40)
 
 
9% (4)  踩
primbo 发表于 2016-11-3 08:09
好强大。big cong,你这咋想出来的。
. from: 1point3acres
原来是pocketgem 面试题,leetcode也有了现在
回复

使用道具 举报

我的人缘0
warriorbrant 发表于 2016-11-3 09:37:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (40)
 
 
9% (4)  踩
primbo 发表于 2016-11-3 09:00
it only works for number from 1 to n

你的原题有范围限制吗,要没有还真不好做
回复

使用道具 举报

我的人缘0
 楼主| primbo 发表于 2016-11-3 10:02:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (56)
 
 
11% (7)  踩
warriorbrant 发表于 2016-11-3 09:37
你的原题有范围限制吗,要没有还真不好做

同学面的google的题,他没有听清,要没限制真的没法做了感觉。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-22 16:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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