一亩三分地论坛

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

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

Quora Square Snapchat Storm8 Shopkick 电面

[复制链接] |试试Instant~ |关注本帖
xelliotpenguin 发表于 2014-9-18 06:39:18 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Quora Square Snapchat Storm8 Shopkick - 网上海投 - 技术电面 |Other

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

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

x
Square skype [size=14.4444446563721px]面 60分钟 *2,有几道题目忘了
(1) 一个token stream, 统计这个stream里前k个出现最多的token。
(2) 一个social network, 判断a,b是不是朋友,要求constant time, 可以预处理。
(3) 一个 2 *4 的数组不重复包含1-8这些整数,有3种操作。

. 1point 3acres 璁哄潧
a) 上下两个row交换
b) 所有元素向右shift一个位置
c) 中间4个元素,顺时针旋转90度
现在随便给一个这样的数组,最小复员到1234,5678的步骤。

第一题 priority queue/min heap,
第二题 预处理用bfs把所有的cluster 算出来, a,b 是不是朋友看是不是在一个cluster酒行了。
第三题 同样bfs,只是要在为2*4 array写个hash function。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. Waral 鍗氬鏈夋洿澶氭枃绔,

. 1point3acres.com/bbs
Quora full-time 电面 45分钟:
(1)给定一个树和一个target, 打印出所有path that sums to the target, path可以开始在任何地方,停在任何地方。
  (2)  给定一个数组(整数)和一个target,  开始从数组中一个一个拿元素,有多少种不同的拿法使得和是target, 可以重复拿同一个元素,拿的顺序不一样算不同的拿法。

第一题没什么好说的,好多地方都有,leetcode上好像也有,很快写完,跑过了面试官给的test-case。
第二题楼主脑子昏了.. 一开始,
写了个
              f(A, j, target) = f(A, j, target-A[j]) + f(a, j-1, target) 的 recurrence, 分成用还是不用最后一个元素两种情况。


然后写了个recursive的算法。
面试官让我跑一下,一看是错的,我以为是base case 错了,看了半天也没发现问题。最后才发现这个recurence是错的,应该用score做index的一纬动态规划,每个位置[size=14.4444446563721px]loop整个input array。
只是说了说想法,来不及写了。。估计是跪了,发出来攒下人品。

Snapchat [size=14.4444446563721px]full-time 电面 45分钟:
[size=14.4444446563721px](1) Sudoku Checker
[size=14.4444446563721px](2) Implement Java ArrayList using Array.1point3acres缃
[size=14.4444446563721px]

[size=14.4444446563721px]Storm8 [size=14.4444446563721px] [size=14.4444446563721px]full-time 电面 45分钟:
(1) Search in Rotated Array, 经常面这道题。。
(2) 一些sorting algo, data structure 的runtime complexity。

Shopkick [size=14.4444446563721px] [size=14.4444446563721px]full-time 电面 45分钟:
[size=14.4444446563721px](1) 一个unsorted array里有多少对pair的位置是错误的? merge sort 里在merge 的时候统计位置错误的pair
[size=14.4444446563721px](2) objective c 里 automatic reference couting 是怎么运行的? 你如何implement(跪了,只知道counter到0 就free object)。. more info on 1point3acres.com





评分

5

查看全部评分

1guangnian 发表于 2014-9-19 00:44:12 | 显示全部楼层
lz,token stream那个题,需要记录每个token出现的次数吧,priority queue维护前k大的不同token,新来一个token的时候,如果它的次数可以放到priority queue里面,怎么保证它不在priority queue里面已经出现一次以上呢,需要额外一些操作么
回复 支持 反对

使用道具 举报

Interviwer 发表于 2014-9-19 00:55:05 | 显示全部楼层
Quora 的二是这样吗? 要是target太大怎么办,数组开的要很大怎么解决呢?
  1. int totalNum(vector<int> A, int target) {
  2.     sort(A.begin(), A.end());
  3.     vector<int> num(target+1, 0);
  4.     num[0] = 1;
  5.     for(int i = 1; i <= num.size(); i ++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.         for(int j = 0; j < A.size(); j ++) {
  7.             if(A[j] <= i) {
  8.                 num[i] += num[i-A[j]];
  9.             }else {
  10.                 break;.1point3acres缃
  11.             }   
  12.         }   
  13.     }   
  14.     return num[target];
  15. }
复制代码
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-2 01:39:04 | 显示全部楼层
很好奇楼主quora第一题怎么做的, 我确定lc上的题不是这个。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-10-2 01:57:16 | 显示全部楼层
quora第二题很难。 如果能重复拿那么是完全背包, 如果拿的物件一样但是顺序不一样也算不同的话就不知道啥模型了。
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-10-2 08:18:45 | 显示全部楼层
我去。 这些题目我全部没有面过。。
回复 支持 反对

使用道具 举报

jackjiang2 发表于 2014-10-2 09:19:08 | 显示全部楼层
第一道题就不会  能补全一下题目 再说下思路么
回复 支持 反对

使用道具 举报

sevenfrost 发表于 2014-10-19 10:01:16 | 显示全部楼层
想问楼主都是如何拿到面试的呀
投了其中两个都很快被据了
回复 支持 反对

使用道具 举报

tktrung 发表于 2016-2-26 06:25:41 | 显示全部楼层
quora 第二题是不是leetcode上的combination sum ii啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 13:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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