一亩三分地论坛

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

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

Snapchat电面。。感觉要跪

[复制链接] |试试Instant~ |关注本帖
wangmengcathy 发表于 2016-4-22 10:09:30 | 显示全部楼层 |阅读模式

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

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

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

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

第一道题是print 2d array diagonally top-down, e.g.-google 1point3acres
[[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。
. 鍥磋鎴戜滑@1point 3 acres
第二道,先问知不知道anagram,两个string怎么判断是不是anagram,楼主迅速说了开128或者256空间那个,以为要问原题了。。。结果 并不是。。-google 1point3acres
问题是给一个source string和pattern string,求有没有任意一个source string的substring和pattern string互为anagram,返回true or false。让用O(n)。。当时觉得有点蒙,我擦怎么O(n)啊。。光比较就要n的复杂度了何况还要slice window。。反正是后来苦思冥想半天总算是想到了。。楼主解法是用另外一个diff map存不对应关系,key是frequency不同的characters,value是对应的difference,source多value正,pattern为负,然后slice window,没slice一位,更新diff表,每有一个value变空了从map中删除那个entry,diff map为空则说明找到了一个匹配的window返回true。。。此法时间复杂即O(n)。。空间O(n)

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



评分

2

查看全部评分

tcomein2009 发表于 2016-4-22 13:38:10 | 显示全部楼层
楼主相当厉害!
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26个大小的int array (这个依然是constant,记录每个字亩出现次数)。pattern string也做这么一个
然后每次移动都比较pattern string的int array。比较也算constant吧
回复 支持 反对

使用道具 举报

waikai 发表于 2016-4-22 14:15:14 | 显示全部楼层
tcomein2009 发表于 2016-4-22 13:38
楼主相当厉害!. From 1point 3acres bbs
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26 ...
. 1point 3acres 璁哄潧
这是时间复杂度应该是O(mn),m是pattern的长度。开Array的同时应该也要像楼主一样更新一个diff。diff为0的时返回true。这样时间复杂度就会使O(m+n)。空间复杂度也是constant
回复 支持 反对

使用道具 举报

 楼主| wangmengcathy 发表于 2016-4-22 23:38:47 | 显示全部楼层
tcomein2009 发表于 2016-4-22 13:38
楼主相当厉害!. 1point 3acres 璁哄潧
第二题是不是可以只开一个和pattern string相同的windows,然后向右移动,同时更新一个26 ...

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

使用道具 举报

jy_121 发表于 2016-4-23 00:27:44 | 显示全部楼层
第二题就是lc的Minimum Window Substring的变形吧
回复 支持 反对

使用道具 举报

windream1991 发表于 2016-4-23 07:35:33 | 显示全部楼层
看楼主snapchat面了两次?
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-4 00:23:41 | 显示全部楼层
Remove 掉可能会有问题 单独用一个counter记比较好
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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