亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 500|回复: 1
收起左侧

Thumbtack phone interview: amicable numbers + longest collatz sequence

[复制链接] |试试Instant~ |关注本帖
larry514 发表于 2017-7-1 07:31:53 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Thumbtack - 网上海投 - 技术电面 |Other其他

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

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

x
上午刚面的。一道新题,一道听说过没见过的题。.1point3acres缃

1. Amicable Numbers:
定义:https://en.wikipedia.org/wiki/Amicable_numbers
220: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284: 1 + 2 + 4 + 71 + 142 = 220. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
找出 10000 以下所有的 pair: (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368).
暴力做的,面试官也没说啥。注意跳过自己跟自己的情况,比如 6 = 1 + 2 + 3 = 6。. from: 1point3acres.com/bbs

2. Longest Collatz Sequence
定义:https://en.wikipedia.org/wiki/Collatz_conjecture

Simply put, for positive integer n > 1,
if (n % 2 == 1) {
  n = 3 * n + 1;
}
else {
  n = n / 2;
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
n finally will be 1.-google 1point3acres

例子:
n = 12: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1 -> 9 steps
n = 19: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 -> 20 steps
要求找出 n < 1,000,000 最长的序列。. Waral 鍗氬鏈夋洿澶氭枃绔,
没做完,时间不够了。直接搜太慢,面试官要求优化。应该用记忆化搜索吧?记录下遇到过的情况。比如上面的例子里,n = 12 时遇到 s(10) = 6, 算 n = 19 时,再遇到 10 可以直接得到 6. 不知道面试官还有啥别的要求不。看面经时知道有这题,但不知道具体是啥,感觉考的也不多。呃。。。. From 1point 3acres bbs

再来一些从其它面经看到的题目。phone & onsite 都算进去了。
https://leetcode.com/problems/im ... -tree/#/description  // 貌似需要返回所有满足条件的单词,不是有没有。
https://leetcode.com/problems/mi ... tring/#/description
https://leetcode.com/problems/line-reflection/#/solutions. more info on 1point3acres.com
https://leetcode.com/problems/se ... -tree/#/description  // 貌似是 n-way .
https://leetcode.com/problems/fi ... drome/#/description
https://leetcode.com/problems/ev ... ation/#/description
还有一道 GetMean(), GetMedian() in O(1) time & space 看到好几次。貌似能得到常数空间和时间是因为输入的数都在 [0, 999], 开个 1000 的数组就当常数了。跟 https://leetcode.com/problems/fi ... tream/#/description 不太一样,这题空间不是常数。没考过,具体不知道了。

在 CodePair 上写的,45 分钟。我用的是 C++ , 面试官要求把答案写成 class , 自己写 main(), 编译并且通过。头文件需要自己加。当场编译运行还挺吓人呢,报错就是一惊。。。

面经里反复就是这些算法题,貌似有题库呢?我信,把这些题都写了,那些没有原题的就自己在电脑上写写测测,结果。。。呃。。。

预祝各位找到理想的工作。
专业抛光核弹头 发表于 2017-9-20 08:54:10 | 显示全部楼层
谢谢分享, 周五电面
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-18 23:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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