一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1588|回复: 19
收起左侧

9.29 G家技术电面

[复制链接] |试试Instant~ |关注本帖
eming 发表于 2015-9-30 22:17:10 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 实习@Google - 网上海投 - 技术电面 |Other其他

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

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

x
昨天刚面完的,发到地里面攒人品……两个面试应该都是白人,因为面的是暑假的实习,两个面试给的题都不难,但是做出来以后会接着跟你讨论做优化。


第一个人的第一个题是给一个array/vector,里面是int,例如[2,3,8,9],然后让你写一个+1的算法,变成[2,3,9,0]。第二个题是有n个灯泡,让你写两个function,一个是 bool xisOn(int index); 第二个是 void Toggle(int start, int end); 然后写完以后跟你讨论如果n很大应该怎么样。

第二个人上来先问stack和queue的区别,然后接着问thread和process的区别...最后让写一个function去从不同国家中根据一个国家的人口数去抽取一个国家。

. 1point 3acres 璁哄潧
面完了问小哥feedback,白人小哥闭口不谈……希望会过吧,下个暑假就是本科最后一个暑假了,希望能找一个正儿八经的实习。


. from: 1point3acres.com/bbs

. from: 1point3acres.com/bbs

本帖被以下淘专辑推荐:

leixiang5 发表于 2015-9-30 22:24:13 | 显示全部楼层
feedback这事情。。貌似看人的。。有些人很好会暗示你会过。。我也在等我的feedback。。楼主一起加油!
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-30 22:32:09 | 显示全部楼层
求问第一题灯泡应该怎么优化呀?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 00:28:48 | 显示全部楼层
kelvinzhong 发表于 2015-9-30 22:32
求问第一题灯泡应该怎么优化呀?

应该是用Interval表示已经开的灯吧
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-10-1 00:30:48 | 显示全部楼层
wenqiang88 发表于 2015-10-1 00:28
. more info on 1point3acres.com应该是用Interval表示已经开的灯吧

那样会很复杂的吧,一旦开关次数了的话。。
回复 支持 反对

使用道具 举报

 楼主| eming 发表于 2015-10-1 00:51:38 | 显示全部楼层
kelvinzhong 发表于 2015-10-1 00:30
那样会很复杂的吧,一旦开关次数了的话。。

我说的是用一个map<pair<int, int>, bool>里面,pair是interval,bool表示开关…每过一段时间需要里面的interval merge一下,但是貌似并没优化多少
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-1 00:51:42 | 显示全部楼层
kelvinzhong 发表于 2015-10-1 00:30
那样会很复杂的吧,一旦开关次数了的话。。

但是应该比brute force要优,也许有更好的办法,期待后面大神的回答
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-1 06:01:59 | 显示全部楼层
第二题灯泡的有点没看到, toggle(start, end)是指将所有start到end的灯泡都开了嘛?
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-10-1 06:49:37 | 显示全部楼层
这题可以用BIT来优化,详见http://www.hawstein.com/posts/binary-indexed-trees.html最后面给的例子
回复 支持 反对

使用道具 举报

xnature 发表于 2015-10-9 04:40:01 | 显示全部楼层
mileschen2008 发表于 2015-10-1 06:01
第二题灯泡的有点没看到, toggle(start, end)是指将所有start到end的灯泡都开了嘛?

toggle是把开的变关的,关的变开的
回复 支持 反对

使用道具 举报

birdor 发表于 2015-10-9 05:22:18 | 显示全部楼层
一个同学碰到了灯泡题,花 15 分钟写了一个线段树的算法,但面试官表示不知道线段树是什么。于是他花了 30 分钟给面试官讲解线段树……
回复 支持 反对

使用道具 举报

xnature 发表于 2015-10-9 07:26:45 | 显示全部楼层
birdor 发表于 2015-10-9 05:22. from: 1point3acres.com/bbs
一个同学碰到了灯泡题,花 15 分钟写了一个线段树的算法,但面试官表示不知道线段树是什么。于是他花了 30  ...

可是面试时间不够实现一个线段树吧
回复 支持 反对

使用道具 举报

liberty_is_key 发表于 2015-10-9 07:50:33 | 显示全部楼层
求问Google是不是不严格要求“实习结束后还要返回学校”,我看的这条在preferred qualification但是不在minimum qualification里
回复 支持 反对

使用道具 举报

bensvage1989 发表于 2015-10-9 09:22:07 | 显示全部楼层
第一题写+1的算法是什么意思,求解释
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-9 10:15:03 | 显示全部楼层
birdor 发表于 2015-10-9 05:22
一个同学碰到了灯泡题,花 15 分钟写了一个线段树的算法,但面试官表示不知道线段树是什么。于是他花了 30  ...

feedback一定是genius~~
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-10-9 11:54:14 | 显示全部楼层
如果n很大,觉得可以用bitmap,每个bit表示一盏灯,不知对否。再就是toggle函数每次调用,不是对array操作,而是生成一个interval, 然后每次调用xisOn(index)的时候,看看index在多少interval里面,那么需要翻转多少次。当然可以用segment tree做,不过觉得空间消耗有点大,也可以sort之后二分查找。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-9 12:17:47 | 显示全部楼层
nothingtrouble 发表于 2015-10-8 22:54
如果n很大,觉得可以用bitmap,每个bit表示一盏灯,不知对否。再就是toggle函数每次调用,不是对array操作 ...

能讲讲,这道题具体在说什么吗?我连题意都没弄懂。
回复 支持 反对

使用道具 举报

xnature 发表于 2015-10-9 22:29:54 | 显示全部楼层
goo 发表于 2015-10-9 10:15
feedback一定是genius~~

一定是搞OI的
回复 支持 反对

使用道具 举报

chemsslu 发表于 2015-10-17 06:38:41 | 显示全部楼层
求问最后一个国家function的思路~
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-18 09:50:44 | 显示全部楼层
求问国家那一题是什么意思,能举个例子么
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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