一亩三分地论坛

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

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

Square两轮skype Interview的题目

[复制链接] |试试Instant~ |关注本帖
lanseyyu 发表于 2016-2-1 03:03:13 | 显示全部楼层 |阅读模式

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

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

x
最近刚面了两轮Square的intern,觉得这个公司的速度非常快,从投resume到开始面间隔一天,一面的结果当晚就给而且当天就约了二面的时间。可惜我挂在2面的题目上。
1面题目:-google 1point3acres
A)给出两个点的x,y坐标,求eucliend距离。
答案:会编程的人都能做...
B)给出一个array,每一个element是一个点的x,y坐标,求距离第一个点最近的K的点。
答案:
      解法1:我现场第一时间想到的就是用Heap,于是写了个min-heap + comparator(用来排序)。不过坏处就是time complexity和space complexity都略高。而且并不需要知道k个elements的顺序,有点浪费。
      解法2:  他问有没有更好的解法时候,我说可以用quickselect来做,这样更快更省space。

2面题目:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
A) 给出长度为n的int array和长度为n-1的char array(储存了一堆运算符),求运算结果
答案:loop+switch就行。
B)给定一个长度为nint array,要求使用每一个element进行加或者减,答案求得target. Waral 鍗氬鏈夋洿澶氭枃绔,
比如<1,2,3,4,5>, target15,那么答案就是1+2+3+4+5= 15
                          target5  答案可能是   1-2-3+4 +5 = 5
                                                     或者    1+2+3+4-5 = 5
要求求出所有可能的答案,且每个element必须用且只能用1次。
在面试的时候我想出了两种方法:
       解法1:只有n个数字,只能是正负,等同于求n个符号permutation,那么总有结果和target match。
       解法2:和maze solver相似,假设我们已经知道前n-1element的结果,那么我们可以轻松的知道如何使用最后一个element可以得到target或者根本不可能得到target
                     因此用Recursion写DFS。
       解法3:我大开脑洞想如果先求了整个array的和,用和减去target,得到相差的差值。那么证明1~n个element需要变成负数,0.5*difference = k个element的和,转化为n-sum问题。

我用了解法2,因为担心解法1太暴力。。。结果因为只有40分钟时间所以不知道在什么地方出了bug,过不了testcase。于是被淘汰。
我的心得,面试的时候先确保一定对,再追求更好的解法。
我觉得总体难度一般,祝大家好运!
lillian0 发表于 2016-2-1 03:17:17 | 显示全部楼层
我被挂简历
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-1 04:17:02 | 显示全部楼层
請問樓主是網頭嗎?
回复 支持 反对

使用道具 举报

 楼主| lanseyyu 发表于 2016-2-1 08:26:09 | 显示全部楼层
frank11118 发表于 2016-2-1 04:17
請問樓主是網頭嗎?

对,是海投的,所以才意外这么快就有回复。
1月10号投的,12号recruiter联系我预约了20号的面试。面试完当晚预约了26号的面试,29号被拒绝。
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-1 08:42:19 | 显示全部楼层
lanseyyu 发表于 2016-2-1 08:26
对,是海投的,所以才意外这么快就有回复。
1月10号投的,12号recruiter联系我预约了20号的面试。面试完 ...

樓主應該是大神 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我網路上投
jobVite 顯示好久 in process 仍舊沒消息
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-1 08:42:31 | 显示全部楼层
lanseyyu 发表于 2016-2-1 08:26
对,是海投的,所以才意外这么快就有回复。
1月10号投的,12号recruiter联系我预约了20号的面试。面试完 ...

樓主應該是大神
-google 1point3acres我網路上投
jobVite 顯示好久 in process 仍舊沒消息
回复 支持 反对

使用道具 举报

 楼主| lanseyyu 发表于 2016-2-1 08:50:58 | 显示全部楼层
lillian0 发表于 2016-2-1 03:17. Waral 鍗氬鏈夋洿澶氭枃绔,
我被挂简历

你和LX的头像好配!
回复 支持 反对

使用道具 举报

lillian0 发表于 2016-2-1 13:16:47 | 显示全部楼层
lanseyyu 发表于 2016-2-1 08:50
你和LX的头像好配!

哈??????????
回复 支持 反对

使用道具 举报

wcyz666 发表于 2016-2-1 13:53:31 | 显示全部楼层
就其他题难度而言,我怀疑他真的是让你暴力permutation的。。。

补充内容 (2016-2-1 13:56):
其实我个人觉得方法1和2的时间复杂度是一样的,都是O(2^n),楼主怎么看
回复 支持 反对

使用道具 举报

 楼主| lanseyyu 发表于 2016-2-1 21:15:37 | 显示全部楼层
wcyz666 发表于 2016-2-1 13:53
就其他题难度而言,我怀疑他真的是让你暴力permutation的。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-2-1 13:56):

对,这个避免不了。包括方法3也是。。。所以其实真的是做permutation毕竟第一问已经develop func来算结果,但我有种臭清高觉得permutation有点无脑。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 01:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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