Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
## Square
一个在 TC 进行的一小时面对面面试,过关后择日 Skype 面试。
### 感受
原本是最想去的公司,因为他们有大量的服务是用 Ruby 写的,只可惜第一个 Skype 面试弄砸了,甚至连还有木有后续面试都不知道 T T 最傻的是居然栽在了反转单词这种问题上 o_o 当时思路十分不清晰,调试 OBOE 时大脑一片空白 T T 后来又有其他公司问同样的问题,很轻鬆的就做出来了 = =
有趣的是 Square 内部有「Ruby is bad」这样的文化,理由当然还是因为 Ruby 服务器的吞吐量-代价比较低,所以 Square 的性能关键的、对吞吐量十分敏感的服务都是用 Java 写的,但需要高度可维护性以及开发效率的服务都是 Ruby 服务。面试官也是一个 Rubist,他说公司可以儘量安排 Ruby 的任务给我,但由于技术栈的特性他们不能保证我永远不需要碰其它语言。
### 问题
- 用纯 C 原地反转字符串中的字符(原地意即带破坏性质的算法)。
- 用纯 C 原地反转字符串中以空格符分隔的单词。
- 实现一个最小化交易次数的账务系统的核心逻辑。输入是不同个体之间相互欠款的额度,输出是最小化交易次数后不同个体需要做出的最终交易额度。例如:甲欠乙三钱,乙欠丙五钱,丙欠甲一钱,那麽最终最优的交易方桉可能是:丙向甲收取二钱,再向乙收取二钱,如此总交易次数便从三次减至两次。
## Twitter
一个在 TC 进行的一小时面对面面试,过关后择日进行一小时电面,电面过关后会有最后三个四十五分钟的连续的 Skype 面试。
### 感受
三个连续 Skype 面试那天有两个面试官都因为临时有紧急会议放了我鸽子,于是当天只做了一个,后来第二天只重新排了一个 Skype 面试就过关了。问题都不算太难,但面试过程确实很长(一共五个面试,我运气好只做了四个)。实习每小时 $39.5,每月提供 $1000 的住宿补贴,可加班,加班费按 1.5 倍工资算。Revenue 队是目前整个公司里用 Ruby 用的最多的队伍,最符合我的兴趣,所以最后是这个队伍给了工作邀请。
### 问题
- 一个二维网格,每一格是一个单元。每个单元可以被一单元的方块佔据,也可以被一单元的水佔据,也可以没有被任何物质佔据。现已知不同的单元被重叠起来形成条状的方块佔据(类似条形统计图的佈局,即不会出现中空的条),假设此网格是一三维场景的横截面且水受重力影响,问在保证不溢出的情况下最多可往这些方块中间灌注多少单元的水?(注:网格边缘不算作容器一壁。)例如:
00001000000
10001000010
10001001010
10101111011
其中 0 表示没有任何物质,1 表示方块,若以 * 表示水,此例中最多可容纳 12 个单元的水:
00001000000
1***1000010
1***1**1*10
1*1*1111*11
- 计算一个二进制整数中为 1 的位的个数。此问有一对数阶解法及一常数阶解法。
- 移除数组中重複(相等)的元素。两种解法,分别在时间与空间複杂度中有不同取捨。
- 写一个函数将字符串中所有的英文单词翻译为儿童黑话( Pig Latin)。翻译方法是把单词的第一个字母放到单词最后,然后再加上「ay」这个词尾。如果单词只有一个字母,那就保持原样。
- 用程序检测一个数字是否是「快乐数」。一个数 N 快乐与否和一个序列的收敛性有关,这个序列的初始数为 N,而后一个数是总是前一个数的所有十进制位的平方和。如果这个序列最后收敛到 1(因为 1 的所有十进制位的平方和还是 1,所以序列会一直重複下去),那麽 N 就是快乐的;如果这个序列最终并不收敛到 1 且重複了之前出现过的元素,那 N 就是悲伤的。
- 实现一个针对二叉搜索树的模煳二叉搜索,即在进行普通的二叉搜索时如果没有找到想要搜索的值,那就返回最靠近搜索值的存在的节点键值,并保证这个值和搜索值相差不超过一个给定的模煳范围,如果没有在模煳范围内的值则返回空值(null、nil、None)。比如一个二叉搜索树中包含 1、2、5、6 这几个键,当调用者进行模煳二叉搜索时,如果给定模煳范围是 999,那麽尝试搜索 -32 会返回 1,搜索 2 会返回 2,搜索 4 会返回 5,搜索 199 会返回 6,搜索 99999 会返回空值。
- 从前端到后端设计一个图片上传的 Web 服务。由于上传图片涉及到对图片进行预处理(裁剪为不同尺寸,创建略缩图等)以及调用云储存的 API 等耗时操作,整个过程应该与 HTTP 响应异步进行,在后台通过某种机制(比如异步的任务队列)处理。因此,前端还需要一个轮询(polling)服务用来查询上传状态(当然,如果不需要支持遗留客户端,可以直接用 WebSocket 推送上传进度的消息到客户端)。图片本身存在云端,但图片 ID 和系统中其它数据(比如用户)的关係则存储在关係数据库中。面试时需要给出 MVC 式的伪代码模拟上述过程(我用的 Rails)。
## Google
两个连续的在 TC 进行的四十五分钟的面对面面试(即总长度九十分钟),过关后招聘官会将你的信息在公司内部传播,如果有某个工程师(Google 称之为「主方」、「host」)觉得你适合加入他们小队并研发某个实习项目,那就会再进行一论来自主方的面试,有多少个不同队伍的工程师对你感兴趣就会有多少个这样的面试。主方面试的主要目的是给你介绍主方的队伍以及实习项目,大部分时候都只会问你本身的背景和经验以及你对项目的兴趣,而不会再设技术关卡让你闯。
### 感受
前两个技术面试中遇到的问题相较其他加州的 IT 巨头给的问题来说算简单的了,所以个人感觉决定能否去 Google 工作的关键因素还是个人本身的技能与经验是否够多、够宽、够深,是否能鹤立鸡群,因为这决定了你能否拿到前两个「海选」面试以及来自主方的面试,而面试本身相信大部分人都能过。一旦拿到主方面试,去 Google 工作的事基本上就算是板上钉钉了。我这次拿到两个主方面试(山景城和滑铁卢的两个),都没有被问到技术问题,但招聘官说少数主方确实还会再问一些技术问题以免所用非人,但几率很小。
这次被匹配到两个实习项目——山景城的是一个 Google Research 的内部审查工具,用于内部员工审查即将发佈的论文;滑铁卢的是 Gmail 的移动平台 Web 前端以及 iOS 前端。前者主要是用 Go,后者主要是 JavaScript、Google Closure。
### 问题
鉴于旻少之前曾收到来自 Google 招聘官的不要公开面试问题的请求,具体的问题就不公开了(保险起见,虽然我没收到这样的请求),笼统地说就是树的各种运算和深度、宽度优先之类的搜索问题。
## LinkedIn
两个四十五分钟的分两天在 TC 进行的淘汰制面对面面试。
### 感受
个人感觉 LinkedIn 的面试是这学期所有面试里做得最好的,但最后招聘官发了一封 email 说他们「暂时不打算发工作工作邀请,下学期如果你还感兴趣的话请一定重新申请」云云,估计是由于没有对我感兴趣的队伍,这个有点像申请 Google 工作时的没有匹配的主方的情况。尼玛当时还以为必定有工作邀请,收到那封 email 的时候顿时感觉不会再爱了……
### 问题
- 通过一棵唯一的二叉树的(以列表形式提供的)先序遍曆路径与中序遍曆路径重建该二叉树。如:
先序遍曆:[7, 3, 2, 4, 6, 1, 5]
中序遍曆:[4, 2, 6, 3, 1, 5, 7]
由以上两种遍曆路径可重建出一棵唯一的二叉树(即不会有两棵不相等的树有相同的先序与中序遍曆序列):
7
/
3
/ \
2 1
/ \ \
4 6 5
- 在不使用牛顿法或泰勒展开式的情况下计算一个双精度浮点数的立方根近似值,使得其误差在给出的容许范围内。
- 实现一个函数,测试一个图是否为二分图(即点色数为二,可以二色为顶点染色)。
- 计算阶乘结果中末尾的零的数量。例如:5! = 120,末尾零的数量为一;10! = 3628800,末尾零的数量为二。要求不溢出,无须计算实际阶乘结果。
## Dropbox
两个四十五分钟的分两天进行的淘汰制的面对面面试,过关后另择日 Skype 面试。
### 感受
个人感觉 Dropbox 最有意思的项目是在 iOS 上通过逆向工程的手段(将代码注入外部进程、拦截本地 API 调用等)在 Finder 这样的图形介面中注入 Dropbox 的各种窗口小部件,因为苹果没有开放任何官方的 API 实现这样的功能。连微软都提供了 CreateRemoteThread 这样的 API 方便程序员注入代码,苹果开发环境的开放度令人咋舌,不过确实是练习逆向开发的好木桩。最后一个面试做得不好,所以最后没拿到邀请。
### 问题
- 输入两棵相等的N叉树(结构相等,所有节点键值相等)及第一棵树中某个节点的引用,输出第二棵树中相等节点(键值相等,而非对象身份或内存地址份相等)的引用。假设有两棵相等但内存身份不同的树结构如下:
5
/ | \
9 6 7
/ |
11 5
\
77
输入就是两棵树的引用以及第一棵树中 77 这个节点的引用,而输出就是在第二棵树 77 这个节点的引用。
输入两棵树,在第一棵树中搜索等同于第二颗树的子树,并返回所有相等子树的数量。比如以下两棵树:
5
/ | \
9 6 7
/ \
6 5
\ / \
5 2 3
/ \
2 3
6
\
5
/ \
2 3
在第一棵树中搜索第二棵树,最后返回 2。
- 活动资源分配问题,类似不相交区等经典贪心算法问题。已知不同活动的开始时间和结束时间,求最少能把这些活动分为多少组使得每组中的活动时间不冲突。实际应用:活动需要在一个房间中进行,时间上不冲突的活动可以先后使用同一个房间,而问题就是如何儘量降低房间资源佔用(最小化需要的房间数量)。如有以下活动区间:
[1, 4], [3, 5], [4, 6], [6, 7], [1, 9], [10, 11], [6, 10]
那麽最优解就是分为 3 组,具体的安排可能是 [1, 4], [4, 6], [6, 7], [10, 11] 在一个房间,[3, 5], [6, 10] 在一个房间,[1, 9] 在一个房间。
- 实现一个(有条目上限的) 使用最近未使用(LRU)的替换算法的缓存机制。
- 在一个目录树中找到所有内容相同的文件,并返回一个列表的列表,其中每个列表是相同内容的文件集合。
- 如果需要考虑符号链接与硬链接,以上算法需要注意什麽问题?
- 如果针对超大目录树进行优化?
- 如何针对超大文件进行优化,避免不必要的 I/O?
## FutureAdvisor
一个45分钟的电话面试。
### 感受
一个不错的用 Rails 的 startup,旗舰产品是一个针对个人理财的 Web 应用,顾名思义。
### 问题
用两种不同的方式计算斐波那契序列的第 n 项,即实现函数 fib(n) -> integer。
如果知道 n 的上限,最快的返回第 n 个斐波那契数的方法是什麽(此法通用于所有序列,比如质数序列)?
## Foursquare
两个四十五分钟的淘汰制电面。
### 感受
在纽约和三藩两个地方有办公室,但三藩那个很小,由于本身就不怎麽想去纽约所以对 Foursquare 的兴趣也不大。面试只做了一个就被拒了,估计是由于在写硬币问题时我最后只求出了最少的硬币枚数,返回哪种面值的硬币分别用了多少枚的部分没能写完。
### 问题
- 高层语言(比如 Ruby、Python)和底层语言(C、C++)在内存管理上有什麽区别和优劣?
- 当代的垃圾回收器(GC)大致可分为基于追踪的和基于引用计数的两种方桉。基于引用计数的方桉相对于基于追踪的方桉有什麽劣势?
- 你最喜欢的编程语言是什麽?如果你有能力改变这个语言的三个方面,你会改哪三个方面?
- 内存模型中栈和堆的区别以及各自的优劣是什麽?
- 已知不同硬币面值(不一定是目前实际存在的货币面值),要求用最少的硬币数量凑够某一零钱值,并返回每个面值的硬币分别用了多少枚。这是一个经典的动态规划问题,在某些特殊的硬币面值组合下可以通过贪心算法正确解出,但不适用于任意面值。比如面值分别为 1、4、6 的硬币凑 8,贪心算法求得一枚 6 和两枚 1,但实际最优解法是两枚 4。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.