《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5190|回复: 33
收起左侧

Snapchat 跪经

[复制链接] |试试Instant~ |关注本帖
clfhaha1234 发表于 2016-9-14 09:43:42 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
据说Snapchat要上市了,感觉找人内推了一下


电面2道题:


1、给你一个(string,k)返回,从后往前数的第k的字符,k=0返回最后一个
快慢指针做就行,我应该没有做到bug free,目测哪儿写2了. 1point 3acres 璁哄潧

2、给你一个未排序的数组,问最短从这个数组的那一段开始排序即能让整个数组有序

比如(1,2,5,7,6,4,9),那么从 (5,7,6,4)这一段排序就足够了.鏈枃鍘熷垱鑷1point3acres璁哄潧
最坏情况O(N^2),最优情况O(N)时间O(1)空间. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


这2道题在算法上都没有太大问题,但是我在这次电面上犯了几个错误导致了最后的失败:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1、第一题虽然简单,但是容易出bug,如果在纸上画画,写几个case,应该能够更清楚.鏈枃鍘熷垱鑷1point3acres璁哄潧
2、面试最重要的不是做题,而是交流,你做出来不算数,还得让面试官理解,所以写的时候可以加注释,变量初始化不要太随意. 1point 3acres 璁哄潧
3、culture fit也是个问题,之前没用过snapchat,提问环节都提不出问题,比较尴尬

最后,果然得勤于刷题保持题感,多多面试才行啊. Waral 鍗氬鏈夋洿澶氭枃绔,
. 1point3acres.com/bbs

补充内容 (2016-9-14 12:04):
改正:第一题不是String,是链表,哈哈……

评分

4

查看全部评分

1370786136.1.3 发表于 2016-9-14 11:20:59 | 显示全部楼层
大家可以参考http://stackoverflow.com/questions/15855594/min-n-m-so-that-whole-array-will-be-sorted/15855670#15855670,据说之前Linkedin面过此题。
. visit 1point3acres.com for more.

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

kevinwangjk 发表于 2016-9-14 11:43:22 | 显示全部楼层
第二题扫两遍行吗?
从左到右扫一遍然后keep track of current high,找到最右边的index i such that current high != nums[i]
从右到左扫一遍然后keep track of current low,找到最左边的index j such that current low != nums[j]
然后j到i就是结果?
0 1 2 3 4 5 6
1,2,5,7,6,4,9
1,2,5,7,7,7,9 -> i = 5
1,2,4,4,4,4,9 -> j = 2
回复 支持 2 反对 0

使用道具 举报

774913744 发表于 2016-9-14 09:49:49 | 显示全部楼层
第二题如何做到O(1)空间?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-14 10:02:11 | 显示全部楼层
第二题就是类似插入排序啊
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 10:02:54 | 显示全部楼层
求问第二题, 如何O(N)时间,O(1)空间呀. 不用Stack嘛?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-14 10:22:24 | 显示全部楼层
小A要当码农 发表于 2016-9-14 10:02. From 1point 3acres bbs
求问第二题, 如何O(N)时间,O(1)空间呀. 不用Stack嘛?

最优情况就是说已经sorted了,insertion sort不就是O(N)么
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-14 10:28:58 | 显示全部楼层
pawprinter 发表于 2016-9-14 10:22.鐣欏璁哄潧-涓浜-涓夊垎鍦
最优情况就是说已经sorted了,insertion sort不就是O(N)么

感觉确实是用改编版的insertion sort就能,记录最后一个要换位置的index, 再记录其新位置的index 两者相减就是那一段
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-14 10:30:09 | 显示全部楼层
楼主,第一道题是在搞笑吗,s.charAt(s.length-1-k ) ?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-14 10:31:43 | 显示全部楼层
wtcupup 发表于 2016-9-14 10:28
感觉确实是用改编版的insertion sort就能,记录最后一个要换位置的index, 再记录其新位置的index 两者相 ...

大概就是这样,记录上个范围,然后再和当前的这个范围进行比较,有点merge的意思
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 11:01:28 | 显示全部楼层
wtcupup 发表于 2016-9-14 10:28
感觉确实是用改编版的insertion sort就能,记录最后一个要换位置的index, 再记录其新位置的index 两者相 ...

多谢, 还是没太懂啊。插入排序的话不应该就是O(n^2)么? .1point3acres缃
比如1,5,4,7,9,3这个数组。 该怎么扫,怎么插入才能O(n)呢?

补充内容 (2016-9-14 11:03):
不好意思,说错了。是1,5,4,0,9,3这个case
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-14 11:27:54 | 显示全部楼层
774913744 发表于 2016-9-14 09:49
第二题如何做到O(1)空间?

I guess: two pointer.
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-14 11:46:16 | 显示全部楼层
For Problem 1, if it asks for the k th char from end in a string s, shouldn't it be simply return s[s.length()-1-k] ? (assuming k <= s.length()-1)  
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 11:50:08 | 显示全部楼层
kevinwangjk 发表于 2016-9-14 11:43
第二题扫两遍行吗?
从左到右扫一遍然后keep track of current high,找到最右边的index i such that curr ...

你这样的话没有办法保证i - j之间 没有比 i左边的小的, 没有比j右边的大的呀。。 比如1,5,4,0,7,6这个case
回复 支持 反对

使用道具 举报

kevinwangjk 发表于 2016-9-14 12:01:14 | 显示全部楼层
小A要当码农 发表于 2016-9-14 11:50
你这样的话没有办法保证i - j之间 没有比 i左边的小的, 没有比j右边的大的呀。。 比如1,5,4,0,7,6这个ca ...

你这个case我的给的答案是 i = 5, j = 0,不对吗?
回复 支持 反对

使用道具 举报

 楼主| clfhaha1234 发表于 2016-9-14 12:04:34 | 显示全部楼层
wtcupup 发表于 2016-9-14 10:30
楼主,第一道题是在搞笑吗,s.charAt(s.length-1-k ) ?

啊哈哈,是链表,抱歉抱歉
回复 支持 反对

使用道具 举报

 楼主| clfhaha1234 发表于 2016-9-14 12:06:20 | 显示全部楼层
小A要当码农 发表于 2016-9-14 11:01
多谢, 还是没太懂啊。插入排序的话不应该就是O(n^2)么?
比如1,5,4,7,9,3这个数组。 该怎么扫, ...

lx已经有人回复了哈,类似于stack的思想,但由于是找中间连续的一段来排序,所以用双point维护前后各扫一遍就行了
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-14 12:12:51 | 显示全部楼层
For Problem 2, it is equivalent to find index L < R in vector<int> a, such that L is the min index such that a[L] is not the min of any a after it and R is the max index such that a[R] is not the max of any a before it. Then the starting and ending index of the shortest unsorted subarray will be from L to R. The worst time complexity is O(n^2) and space complexity is O(1).

  1. vector<int> findShortestUnsortedPart(vector<int>& a) {
  2.   // function to check whether a[idx] <= any a[i] after it
    . From 1point 3acres bbs
  3.   auto isMin = [](vector<int>& a, int idx) {
  4.     int n = a.size();
  5.     if (idx < 0 || idx >= n) return false;
  6.     for (int i = idx+1; i < n; i++) if (a[idx] > a[i]) return false;    . 1point3acres.com/bbs
  7.     return true;
  8.   }
  9.   // function to check whether a[idx] >= any a[i] before it
  10.   auto isMax = [](vector<int>& a, int idx) {
  11.     int n = a.size();
  12.     if (idx < 0 || idx >= n) return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.     for (int i = 0; i < idx; i++) if (a[idx] < a[i]) return false;   
  14.     return true;
  15.   }
  16. . Waral 鍗氬鏈夋洿澶氭枃绔,


  17.   int L = 0;
  18.   while (L < a.size()) {
  19.     if (isMin(a, L)) L++;
  20.     else break;
  21.   }
  22.   if (L == a.size()) return make_pair(0,0,) // entire array is sorted


  23.   int R = a.size() - 1;. visit 1point3acres.com for more.
  24.   while (R >= 0) {
  25.     if (isMax(a, R)) R--;
  26.     else break;
  27.   }. From 1point 3acres bbs
  28.   return make_pair(L, R);
  29. }
复制代码
回复 支持 反对

使用道具 举报

xh_pku 发表于 2016-9-15 07:18:47 | 显示全部楼层
第二题不是O(n)很好解吗??
回复 支持 反对

使用道具 举报

 楼主| clfhaha1234 发表于 2016-9-15 07:46:38 | 显示全部楼层
zzgzzm 发表于 2016-9-14 12:12. visit 1point3acres.com for more.
For Problem 2, it is equivalent to find index L < R in vector a, such that L is the min index such t ...

ls你 isMin是o(n),外层循环也是n,岂不是写成了n^2的算法了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 21:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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