一亩三分地论坛

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

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

4.12 google 电面

[复制链接] |试试Instant~ |关注本帖
mummymyth 发表于 2016-4-14 10:44:33 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
面试官应该是个白人小哥,上来也没聊简历,介绍了一下自己就开始做题了。. from: 1point3acres.com/bbs
不知道为什么,碰到的题特别简单,可能是妹子光环吧,奈何太紧张了外加本身自己水平就渣答的磕磕巴巴的,估计已跪

第一题上来让写个swap (我当时听到懵逼了一会儿完全不敢相信让写这么简单的东西。。。),就是把两个input的值换一下,问了一下小哥输入的type,小哥说随意,就写了个int的。
然后问怎么支持其他的type,我一开始还傻了吧唧的说那就再写一个函数换成新的input type,后来才反应过来说可以写template(语言选的c++),小哥说good, 那你写一下吧,然后我就又懵逼了,没写过啊。。。
如实告诉小哥并不知道语法,小哥说try your best,就随便写了一下。然后问有没有那种输入的type会造成编译报错的,这回彻底懵逼了。。。直接说不知道。我写的是最简单那种tmp=a; a=b; b=tmp; 求路过的大神有知道的告诉我一下答案。再然后问有没有那种输入的type这样搞非常的不efficient,回答说vector,因为没必要复制。小哥就给了个IntVector的class, 大概是
class IntVector{
int * buf;. 1point3acres.com/bbs
int size;
}
这样,问怎么改进。我一开始又傻了吧唧的只想到不要复制占空间,说一个个的换,小哥说你这样还是很耗时间啊,然后才想起来给的是个指针啊直接换指针不就好。。。然后换了指针就忘了还有一个size了,小哥提醒才想起来。

第二题是读了一段代码。输入是一个int的array和size, 两个array, 一个是从头加到当前的和,就是sum=nums[0]+nums[1]+...+nums,另一个是从尾巴开始加。用这俩找到一个index能把输入的array分成两部分让两边的和的差最小,返回index。先问的代码干嘛的,然后问能不能优化。我一开始想的是没必要用两个array一个就够了,小哥说好那你改吧,改完说还能不能再优化了, 想了想好像不用array,俩int记一下总和和加到当前的和就够了,然后就再改,这就已经是O(n)时间O(1)空间了就跟小哥说没法再优了。

第三题是给了一堆点(x_0,y_0)....(x_n,y_n)问怎么判断是不是关于任意vertical line 轴对称。没让写代码就说思路。我一开始不知道怎么以为点是按顺序的而且x是连着的,就说先找中间然后俩指针从中间往两头比y,小哥问你怎么找median,我天真的回答不是n/2那个点吗。。。(小哥内心一定是妈的智障脸)。然后发现给的点的值并没有任何顺序就开始崩了,想了半天怎么用O(n)找median,也没想出来,小哥表示听不懂你在碎碎念神马,曾经尝试着给了个例子,然并卵。。。我最后放弃了,就说先按x sort,然后从两边比y,然后忘记了x可能不对称了。。。经小哥提醒补充了还要看一下两边x的平均数是不是median。挂了电话想了会才想起来可以先找median,然后用hash table就可以是O(n)了。

想问一下大家,没见过的题,是先自己想好一个思路再开始讲呢还是想到哪讲到哪啊? 我是想把我脑子里在想什么都说出来但是渣口语小哥好几次都表示并不能听懂你在说神马, 而且想的时候还要同时想这个东西英语怎么说然后又说不清楚就越来越着急就更想不出来了。怎么样才能更清楚的表达自己的思路呢?



补充内容 (2016-4-15 09:46):
【i】怎么被吞了变斜体了。。。是sum【i】=num【0】+。。。+num【i】
路过的各位别光看题顺手来给楼主解个惑呗,这算是楼主第一个电面答的各种卡壳,楼主虚啊

评分

1

查看全部评分

houqingniao 发表于 2016-4-16 03:59:05 | 显示全部楼层
mummymyth 发表于 2016-4-15 21:19. From 1point 3acres bbs
是判断那堆点是否轴对称,如果是的话对称轴和median和x的平均应该是一样的吧

这样只有算平均就可以了吧, 跟median没关系吧
回复 支持 1 反对 0

使用道具 举报

woridage1 发表于 2016-4-15 20:25:17 | 显示全部楼层
把所有的点存到map<y,vector<x>> 中,同时累加x的和,求中轴线,然后遍历map,针对每个y的值取出他对应的所有x值,把每一组sum求中点,对比每组的中点是否和全部的中点相等,遍历一遍都相等就返回true。 求指教
回复 支持 1 反对 0

使用道具 举报

jerry_lin324 发表于 2016-4-14 21:20:50 | 显示全部楼层
楼主,第三题他的输入时一堆点和一条vertical line让你判断这对点是否关于这个line轴对称个,还是说给你了好几天vertical line,然后让你在里面找到一条。
回复 支持 反对

使用道具 举报

 楼主| mummymyth 发表于 2016-4-14 23:08:22 来自手机 | 显示全部楼层
jerry_lin324 发表于 2016-4-14 21:20
楼主,第三题他的输入时一堆点和一条vertical line让你判断这对点是否关于这个line轴对称个,还是说给你了 ...

输入就是一堆点,是判断这堆点是不是对称
回复 支持 反对

使用道具 举报

Hualiang 发表于 2016-4-15 01:49:05 | 显示全部楼层
可以把所有X加起来除2求对称轴吗?
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-4-15 04:59:49 | 显示全部楼层
第二题数组有负数就不好搞了吧,那样必须所有数据走一遍了
回复 支持 反对

使用道具 举报

 楼主| mummymyth 发表于 2016-4-15 05:18:23 来自手机 | 显示全部楼层
Hualiang 发表于 2016-4-15 01:49
可以把所有X加起来除2求对称轴吗?

就是点是对称的所以x加起来除2也不是对称轴吧,除非就两个点
回复 支持 反对

使用道具 举报

 楼主| mummymyth 发表于 2016-4-15 05:20:11 来自手机 | 显示全部楼层
kiviljc 发表于 2016-4-15 04:59
第二题数组有负数就不好搞了吧,那样必须所有数据走一遍了

有没有负数没关系吧,怎么着右半边的和都等于总和减去左半边的
回复 支持 反对

使用道具 举报

Hualiang 发表于 2016-4-15 08:50:32 | 显示全部楼层
mummymyth 发表于 2016-4-15 05:18. 1point 3acres 璁哄潧
就是点是对称的所以x加起来除2也不是对称轴吧,除非就两个点
. more info on 1point3acres.com
跟多少个点没关系呀, 比如(1,2) (3,2) (0, 5) (4, 6) 就是关于x=2对称的,就是可以把X所有加起来除以2.
回复 支持 反对

使用道具 举报

 楼主| mummymyth 发表于 2016-4-15 09:04:14 | 显示全部楼层
Hualiang 发表于 2016-4-15 08:50
跟多少个点没关系呀, 比如(1,2) (3,2) (0, 5) (4, 6) 就是关于x=2对称的,就是可以把X所有 ...

(1+3+4+0)/2=4呀,你是想说平均数吧,先假设平均数是对称轴再验证应该也可以
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-4-15 13:32:27 | 显示全部楼层
mummymyth 发表于 2016-4-15 09:04
(1+3+4+0)/2=4呀,你是想说平均数吧,先假设平均数是对称轴再验证应该也可以

是要轴对称 ?
还是找一条vertical line 把点分到两边, 使两边点 个数相等?
回复 支持 反对

使用道具 举报

 楼主| mummymyth 发表于 2016-4-15 21:19:39 来自手机 | 显示全部楼层
houqingniao 发表于 2016-4-15 13:32. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是要轴对称 ?
还是找一条vertical line 把点分到两边, 使两边点 个数相等?

是判断那堆点是否轴对称,如果是的话对称轴和median和x的平均应该是一样的吧
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-4-16 03:57:09 | 显示全部楼层
Hualiang 发表于 2016-4-15 08:50
跟多少个点没关系呀, 比如(1,2) (3,2) (0, 5) (4, 6) 就是关于x=2对称的,就是可以把X所有 ...

这怎么会关于x=2 对称, (0,5)跟(4,6)也不对称啊
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-4-16 03:59:30 | 显示全部楼层
woridage1 发表于 2016-4-15 20:25
把所有的点存到map 中,同时累加x的和,求中轴线,然后遍历map,针对每个y的值取出他对应的所有x值,把每一 ...
. visit 1point3acres.com for more.
同样的想法。。。
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-19 23:41:53 | 显示全部楼层
第三题能不能这么写:
HashSet<Point> set = new HashSet<Point>();
        for(Point p : Points) {
          if(set.contains(p的对称点)) {
             set.remove(p的对称点);
             continue;
          } else {
           set.add(p);
          }
        }
        
        if(set.isEmpty()) {
          return true;.1point3acres缃
        } else {
          for(Point p : set) {
            if(p.x != 给定的x) return false;
          }
          return true;. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
. visit 1point3acres.com for more.
具体类似two sum,遍历给定的points数组,用一个hashset记录每个点,如果当前点在set里找不到对称的点,就把当前点加入set;如果找到了对称点,就把这个对称点从set删除(同时当前点也不加入set)。 遍历完成后,如果set为空,说明所有点都有对称点了,就返回true。而set里面还有元素,还要判断这些元素是不是都在给定的那个vertical line上面,如果都在上面的话,也返回true;如果有任意一个不在vertical line上面,说明这个点没有找到对称点,就返回false

补充内容 (2016-4-19 23:44):
这个方法时间复杂度是O(n), 最差空间复杂度也是O(n),就是hashset的大小
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-22 03:33:46 | 显示全部楼层
yueliu2366 发表于 2016-4-19 23:41. 鍥磋鎴戜滑@1point 3 acres
第三题能不能这么写:
HashSet set = new HashSet();
        for(Point p : Points) {

这样的话在直线上的点在遍历时不放入不就可以了吗?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-22 04:15:06 | 显示全部楼层
jy_121 发表于 2016-4-22 03:33
这样的话在直线上的点在遍历时不放入不就可以了吗?

哦对,这样就不用最后再遍历一次了
回复 支持 反对

使用道具 举报

table 发表于 2016-5-21 11:32:09 | 显示全部楼层
楼主可以详细说一下第一题那个IntVector怎么个改进法吗?不太明白怎么个交换指针?
回复 支持 反对

使用道具 举报

nevets 发表于 2016-5-21 21:43:48 | 显示全部楼层
yueliu2366 发表于 2016-4-19 23:41
第三题能不能这么写:
HashSet set = new HashSet();
        for(Point p : Points) {

不知道我理解正确没有,但是对于任意两点,只要是x相同或者y相同都是对称点,但是整体不一定关于某条vertical line对成。。比如给任意两条平行于x轴的线段,你的算法应该会返回true,但实际上两条线段不一定关于某条垂直线平行。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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