snapchat跪经

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

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

2.白人小胡子哥+国人小哥shadow
第三轮：做安

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

45, 246, 247)">
跪在这轮

3.白人经理
给个2d数组给个起始点给个终止点，求路径，里面有障碍，dfs解

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

全程要求现场编译出结果

小A要当码农 发表于 2016-10-9 12:06
这一题能不能LC282的解法呀，backtracking，把最后一个加上的数字传下去。。

The idea is similar to LC282. However, this problem has no target value. Let dp[i] 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. 
   
5.   // dp[i]: max value generated from a[0],...,a[i]  
   
6.   vector<int> dp(n); dp[0] = a[0];
   
7.   for (int i = 1; i < n; ++i) dp[i] = a[i]*dp[i-1];
   
8.   for (int i = 1; i < n; ++i) {
   
9.     int lastProduct = 1;
   
10.     for (int j = i-1; j >= 0; j--) {
    
11.       lastProduct *= a[j+1];
    
12.       dp[i] = max(dp[j], dp[j] + lastProduct);
    
13.     }
    
14.   }
    
15.   return dp[n-1];
    
16. }

复制代码

补充内容 (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.

andylitchi 发表于 2016-9-17 14:40
在职，不知道为什么没有设计题，每轮都是先聊天，聊个20分钟再做题，最后顶多再来follow up

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

qesss 发表于 2016-9-27 00:50
这个貌似是正确的，但是复杂度好像比较高，O(n3)？

我想的办法是dp(i)表示到第i个数的值，dp(i) = max ...

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[i] with fix starting point.

“抄的” 什么意思？snapchat onsite能现场google题目？

补充内容 (2016-9-18 06:07):
ignore my post

snapchat提供wifi，可以让你当场上网查编程语言的reference。楼主这个是在职跳槽，没有面设计题？我的onsite除了第一轮面试官来得很晚只做了一个编程题外，后面三轮每轮都是两个题，一设计题一编程题。

厉害的超人 发表于 2016-9-18 06:30
snapchat提供wifi，可以让你当场上网查编程语言的reference。楼主这个是在职跳槽，没有面设计题？我的onsit ...

在职，不知道为什么没有设计题，每轮都是先聊天，聊个20分钟再做题，最后顶多再来follow up

第一题：确认一下，给定的数组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). 是这样吗？

zzgzzm 发表于 2016-9-18 10:53
第一题：确认一下，给定的数组vector arr顺序是不能改变的吧。let dp(i, k) be the max value calculated f ...

对，我做的是dij是元素i到j，一个意思

请问那个渲染长方形，是给你底层的API当你当场真的把渲染实现出来，还是没有底层API，自己写了class然后写点小测试呢？

hxtang 发表于 2016-9-18 21:10
请问那个渲染长方形，是给你底层的API当你当场真的把渲染实现出来，还是没有底层API，自己写了class然后写 ...

不好意思，我不记得了，你可以去链接里那个帖子问问

lz第一题能给个栗子吗？我理解是一堆digit 在里面加+ or *使得结果最大？怎么感觉好像什么都不加比较大……如果是一个valid数字的话（开头不为0）