一亩三分地论坛

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

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

snapchat跪经

[复制链接] |试试Instant~ |关注本帖
andylitchi 发表于 2016-9-18 05:27:53 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 Onsite |Fail在职跳槽

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

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

x
之前面的snapchat 跪了,海滩挺美的,一堆抽大麻的
phone: LRU cahce
题目出的不是lru cache,是snapchat背景的题目,思路跟lru cache一样。电面要视频,有点奇怪。。。

onsite:
1. 国人大牛director
聊天+ coding
一堆数字,中间可以加 加号和乘号,求最大值,dp做

2.白人小胡子哥+国人小哥shadow
第三轮:做安卓端的小哥。问题是假定给个屏幕和一些屏幕坐标和渲染单个像素点的API,要求设计一个渲染class, 能实现当手指点下去的时候开始渲染,手指拖动过程中渲染以屏幕一角和手指作为对角线的一个长方形(这个长方形可以根据手指的运动扩大缩小),最终当手指离开屏幕的时候,以手指最后位置为准,留下most recent的那个长方形。小哥在整个过程中除了回答clarification以外一直不出声,edege case都是LZ一边写一边找出来的。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

抄的,同一个人 https://instant.1point3acres.com/thread/15352
.鐣欏璁哄潧-涓浜-涓夊垎鍦
跪在这轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鏈枃鍘熷垱鑷1point3acres璁哄潧
3.白人经理
给个2d数组给个起始点给个终止点,求路径,里面有障碍,dfs解

4.白人小哥
topology sort
题目背景是装软件按顺序装,软件之间有dependency,求一个合理的顺序。

全程要求现场编译出结果
wtcupup 发表于 2016-9-18 05:59:35 | 显示全部楼层
“抄的” 什么意思?snapchat onsite能现场google题目?
. From 1point 3acres bbs
补充内容 (2016-9-18 06:07):
ignore my post
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-18 06:30:38 | 显示全部楼层
snapchat提供wifi,可以让你当场上网查编程语言的reference。楼主这个是在职跳槽,没有面设计题?我的onsite除了第一轮面试官来得很晚只做了一个编程题外,后面三轮每轮都是两个题,一设计题一编程题。
回复 支持 反对

使用道具 举报

 楼主| andylitchi 发表于 2016-9-18 06:40:12 | 显示全部楼层
厉害的超人 发表于 2016-9-18 06:30
snapchat提供wifi,可以让你当场上网查编程语言的reference。楼主这个是在职跳槽,没有面设计题?我的onsit ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
在职,不知道为什么没有设计题,每轮都是先聊天,聊个20分钟再做题,最后顶多再来follow up
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-18 07:05:33 | 显示全部楼层
andylitchi 发表于 2016-9-17 14:40
在职,不知道为什么没有设计题,每轮都是先聊天,聊个20分钟再做题,最后顶多再来follow up

奇怪,面我的基本不聊天也不问snapchat的东西,完全没有背景问题和behavior问题。只有一轮我讲了两分钟以前做的东西他就忍不住要开始考编程题了。可以说每轮基本只花了一两分钟介绍一下他自己就开始做题了。由于是做两道题,做完后也没啥时间问其他的了。没想到snapchat的面试风格可以差这么大的啊
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-18 10:53:02 | 显示全部楼层
第一题:确认一下,给定的数组vector<int> arr顺序是不能改变的吧。let dp(i, k) be the max value calculated from sub array from a(i) with length k, then we need to find out dp(0,n). Use dp(i,k) = max ( dp(i,j)+dp(i+j,k-j) ) for j from 1 to k-1 and also take max with all product = a(i) *...a(i+k-1). 是这样吗?
回复 支持 反对

使用道具 举报

 楼主| andylitchi 发表于 2016-9-18 12:10:15 | 显示全部楼层
zzgzzm 发表于 2016-9-18 10:53 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题:确认一下,给定的数组vector arr顺序是不能改变的吧。let dp(i, k) be the max value calculated f ...
. visit 1point3acres.com for more.
对,我做的是dij是元素i到j,一个意思
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-18 21:10:45 | 显示全部楼层
请问那个渲染长方形,是给你底层的API当你当场真的把渲染实现出来,还是没有底层API,自己写了class然后写点小测试呢?
回复 支持 反对

使用道具 举报

 楼主| andylitchi 发表于 2016-9-19 01:50:37 | 显示全部楼层
hxtang 发表于 2016-9-18 21:10
请问那个渲染长方形,是给你底层的API当你当场真的把渲染实现出来,还是没有底层API,自己写了class然后写 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不好意思,我不记得了,你可以去链接里那个帖子问问
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-20 03:45:47 | 显示全部楼层
lz第一题能给个栗子吗?我理解是一堆digit 在里面加+ or *使得结果最大?怎么感觉好像什么都不加比较大……如果是一个valid数字的话(开头不为0)
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-20 03:59:25 | 显示全部楼层
请问楼主第一题数字中间可以不加任何符号嘛?
回复 支持 反对

使用道具 举报

 楼主| andylitchi 发表于 2016-9-20 07:15:50 | 显示全部楼层
小A要当码农 发表于 2016-9-20 03:59. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请问楼主第一题数字中间可以不加任何符号嘛?

不可以
字数字数字数
回复 支持 反对

使用道具 举报

qesss 发表于 2016-9-27 00:50:13 | 显示全部楼层
zzgzzm 发表于 2016-9-18 10:53
第一题:确认一下,给定的数组vector arr顺序是不能改变的吧。let dp(i, k) be the max value calculated f ...

这个貌似是正确的,但是复杂度好像比较高,O(n3)?

我想的办法是dp(i)表示到第i个数的值,dp(i) = max(dp(j) + a[j+1]*a[j+2]*...*a),也就是计算dp(i)时,枚举上一个加号的位置(从后往前数)。这个是O(n2)的。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-28 13:33:33 | 显示全部楼层
qesss 发表于 2016-9-27 00:50
这个貌似是正确的,但是复杂度好像比较高,O(n3)?

我想的办法是dp(i)表示到第i个数的值,dp(i) = max ...
. 1point 3acres 璁哄潧
Yes, you are right! Using 1D dp is enough (which yields O(n^2) time complexity only) by looking for the LAST plus sign (instead of any plus sign). Looking for the last plus signs requires only to calculate result from first a[0] to some a with fix starting point.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

stacies 发表于 2016-9-29 02:27:11 | 显示全部楼层
第一题能加括号么
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-9 12:06:38 | 显示全部楼层
zzgzzm 发表于 2016-9-28 13:33
Yes, you are right! Using 1D dp is enough (which yields O(n^2) time complexity only) by looking fo ...

这一题能不能LC282的解法呀,backtracking,把最后一个加上的数字传下去。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-9 12:09:08 | 显示全部楼层
请问楼主第二题啥思路呀。。。给的链接好像不对啊。。。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-10 06:49:31 | 显示全部楼层
小A要当码农 发表于 2016-10-9 12:06
这一题能不能LC282的解法呀,backtracking,把最后一个加上的数字传下去。。

The idea is similar to LC282. However, this problem has no target value. Let dp note the max value we could get from partial array of first several consecutive entries. Then the key is to check where should we insert the last "+" or not to use "+" at all (i.e., insert "*" for all positions).
  1. int getPlusMultiplyMax(vector<int>& a) {
  2.   int n = a.size();
  3.   if (n == 0) return INT_MIN; // default answer for empty array

  4.   // dp[i]: max value generated from a[0],...,a[i]  
  5.   vector<int> dp(n); dp[0] = a[0];
  6.   for (int i = 1; i < n; ++i) dp[i] = a[i]*dp[i-1];
  7.   for (int i = 1; i < n; ++i) {
  8.     int lastProduct = 1;
  9.     for (int j = i-1; j >= 0; j--) {
  10.       lastProduct *= a[j+1];
  11.       dp[i] = max(dp[j], dp[j] + lastProduct);
  12.     }
  13.   }
  14.   return dp[n-1];
  15. }
复制代码

补充内容 (2016-10-10 07:29):
Actually, I think this problem is easier than LC282 since we don't need to worry about matching target value or special treatment for "*" which is precedent to "+" operator in calculation.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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