<
查看: 3867|回复: 6
收起左侧

Snapchat电面。。感觉要跪

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (83)
 
 
0% (0)    👎

2016(4-6月) 码农类General 硕士 全职@Snapchat - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
下午刚面的。。。妈蛋墨菲效应我也是醉了。。。面试的是个中国大哥 之前还找帮内推过 我真的是醉了。。。。
上题。

第一道题是print 2d array diagonally top-down, e.g.
[[1,2,3,4], [5,6,7,8], [9,10,11,12]] => 1, 2 5, 3 6 9, 4 7 10, 8 11, 12
题外话:这道题其实隐隐约约面经里我记得有人写过zigzag打印应该就是这个。。楼主地里电面面经看得到的都自己写了,准备了了洋洋洒洒近两千行的面经代码,唯独那道当时觉得年代久而且觉得现场也能秒就没写。。就那一道。。。
然后当时心情就坏了。。开始扣着写吧 一开始竟然还开了一个大小相同的数组存访问过没有,空间复杂度O(n)的。。。果断写完等着被优化,冥想半天从上边和右边开始向左下输出就好了,no space。

第二道,先问知不知道anagram,两个string怎么判断是不是anagram,楼主迅速说了开128或者256空间那个,以为要问原题了。。。结果 并不是。。
问题是给一个source string和pattern string,求有没有任意一个source string的substri
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
更新diff表,每有一个value变空了从map中删除那个entry,diff map为空则说明找到了一个匹配的window返回true。。。此法时间复杂即O(n)。。空间O(n)

然而最后代码跑的通但还是有点bug。。。求国人大哥网开一面给放过。。。



评分

参与人数 2大米 +45 收起 理由
何打发123 + 5 感谢分享!
candy_shmily + 40

查看全部评分


上一篇:Onsite Uber 加面接着跪
下一篇:亚马逊 实习
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
楼主相当厉害!
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26个大小的int array (这个依然是constant,记录每个字亩出现次数)。pattern string也做这么一个
然后每次移动都比较pattern string的int array。比较也算constant吧
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (338)
 
 
0% (1)    👎
tcomein2009 发表于 2016-4-22 13:38
楼主相当厉害!
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26 ...

这是时间复杂度应该是O(mn),m是pattern的长度。开Array的同时应该也要像楼主一样更新一个diff。diff为0的时返回true。这样时间复杂度就会使O(m+n)。空间复杂度也是constant
回复

使用道具 举报

 楼主| wangmengcathy 2016-4-22 23:38:47 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (83)
 
 
0% (0)    👎
tcomein2009 发表于 2016-4-22 13:38
楼主相当厉害!
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26 ...

哦对忘了说了,LZ之所以用map是因为面试官特意强调假设有无数多种字符。。可能他就想让用hashmap来搞吧
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (223)
 
 
2% (5)    👎
第二题就是lc的Minimum Window Substring的变形吧
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (147)
 
 
0% (0)    👎
看楼主snapchat面了两次?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (198)
 
 
1% (4)    👎
Remove 掉可能会有问题 单独用一个counter记比较好
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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