一亩三分地论坛

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

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

Snapchat 跪经

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

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

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

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

x
据说Snapchat要上市了,感觉找人内推了一下. visit 1point3acres.com for more.


电面2道题:


1、给你一个(string,k)返回,从后往前数的第k的字符,k=0返回最后一个
快慢指针做就行,我应该没有做到bug free,目测哪儿写2了
. visit 1point3acres.com for more.
2、给你一个未排序的数组,问最短从这个数组的那一段开始排序即能让整个数组有序

比如(1,2,5,7,6,4,9),那么从 (5,7,6,4)这一段排序就足够了-google 1point3acres
最坏情况O(N^2),最优情况O(N)时间O(1)空间


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

最后,果然得勤于刷题保持题感,多多面试才行啊
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (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面过此题。

评分

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]. 鍥磋鎴戜滑@1point 3 acres
然后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)空间?. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

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
求问第二题, 如何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)么?
比如1,5,4,7,9,3这个数组。 该怎么扫,怎么插入才能O(n)呢? .1point3acres缃
.1point3acres缃
补充内容 (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
  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;   
  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. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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


  24.   int R = a.size() - 1;
  25.   while (R >= 0) {
  26.     if (isMax(a, R)) R--;
  27.     else break;
  28.   }
  29.   return make_pair(L, R);
  30. }.1point3acres缃
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| clfhaha1234 发表于 2016-9-15 07:46:38 | 显示全部楼层
zzgzzm 发表于 2016-9-14 12:12. from: 1point3acres.com/bbs
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的算法了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地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

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