一亩三分地论坛

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

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

狗家昂赛特

[复制链接] |试试Instant~ |关注本帖
SidneyFan 发表于 2016-11-18 04:39:36 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
因为snapchat家的面筋一发就有昂赛特了。。所以也发个狗家的吧。。从地里也学习到了好多东西,回报回报。。。求不被发现。。准备:LC一百四十道狗家题刷了两遍。

上周昂赛特,遇到了史上最难题吧。。

第一轮:topological sort。我写了上百遍了(DFS wik版本),但是华人大叔没太看懂为什么有两个visited set,所以解释了好久。

第二轮:
int[][]矩阵,求是否满足性质:左上角到右下角的斜线上的值都要相等。比如(0,1)(1,2),(2,3)这些要相等。
小伙伴告诉过我这题,所以我知道follow up是矩阵很大,每次只能读一行怎么办,所以我一开始就写了两行两行比较的算法,面试小哥有点蒙蒙,依然也给了这个follow up,秒了。然后还剩二十多分钟,小哥就给了第二个follow up:现在一行都太大没法读进来,但是可以允许算法不是100%准确的。然后我也不知道为什么灵光闪现,想起来大四的时候跟实验室同学聊天知道的一个压缩矩阵保持feature的方法,然后给出了:每次取出matrix的一小块,算一个signiture(比如乘一个vector就能压缩到一维向量),然后整个矩阵就可以压缩,保持一定的feature,最后用前面的算法做,有False positive,但是满足性质的matrix一定是返回True的。小哥说每次读一小块太昂贵了(因为有不同行,从disk的一个条带上读的话跨越太多), 只能一行一行读,每次读一小点。我说那就能读多少读多少(比如读N),signiture简单乘上一个固定的vector(大小N)压缩成一个int就好了,这样整个大矩阵也可以每行一点一点压缩(每行压缩的时候要有offset,因为是斜着比较的),如果压缩一次不够的话,还可以递归压缩,直到内存足够读入一行为止。最后小哥让我写代码,写完表示非常非常非常满意。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第三轮:LC394,剩十分钟follow up是反过来encode,求最短encode(跟我说前面那个是warm up,这才是真题)。懵逼,给了个贪心+memory的算法(代码非常乱),也不知道能不能得到最优解。没做出来。。。最后结束的时候她说这题很难很难,让我don't worry,用DP做(分析题目的时候我试了一下,她没有hint所以我没继续下去),然后我才想到用dp[k][i][j]做应该可以。。。但也没时间写了。。


第四轮:这题真是前所未见的,白人面试官,带一个非常可爱的华裔小帅哥shadow。题目:double[][]矩阵,值表示高度,所以是一个3D的地图。现在无限远处平行光射入(任何角度),求矩阵上那些点被遮盖住了。
懵逼。开始各种分析,我以为是设计题,就3D阴影建模。正要开始写class的时候,然后得到hint:从每个cell看向太阳方向,所以想到现在2D上,对一条光路ax+by=0,求哪些cell相交(这个挺难算的,在hint和反复的question下,我最后给出了三条平行线算计算相交cell,面试官表示肯定)。然后跟面试官negotiate得到只需要考虑中心点被覆盖,同时相交cell之间的距离就近似成中心点的距离(因为要计算tanA*distance(p1,p2)得到高度)。。。。总之到最后是给出了一个算法,写了一点点中间步骤的代码,但是整个代码是没写的。结束的时候考官问我感觉怎么样,我说没有想到是这种数学题,他说我们希望看到你分析这个题然后写成代码的整个过程,我说可惜我还是没写完代码呀,他点点头说嗯(我就觉得完蛋了)。最后朋友圈大神说这是计算机图形学最后几章的问题,什么z buff scan算法。。。。

好的就这样,等待HR反馈。。。。我个人觉得已经发挥我所有实力了,但感觉依然有风险。。第三轮followup不好,第四轮只分析出来算法没写出代码。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

linjin 发表于 2016-11-19 13:34:49 | 显示全部楼层
抄来的

#include <cstdio> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
#include <list>
using namespace std;
#define MAXN 102
int dp[MAXN][MAXN];
char str[MAXN];
bool check(int l, int p, int r) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
{
    int len = p-l+1;   //也就是尝试把[l, r]压缩成若干个[l, p]的重复
    if((r-p)%len != 0)return false;
    for(int i = p+1; i <= r; i++)
        if(str[i] != str[(i-l)%len+l])return false;
    return true;
}

.鐣欏璁哄潧-涓浜-涓夊垎鍦int main()
{
    memset(dp, 0x3f, sizeof(dp));
    scanf("%s", str+1);
    int slen = strlen(str+1);
    for(int i = 1; i <= slen; i++)dp[i][i] = 1;
    for(int len = 2; len <= slen; len++). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    {
        for(int i = 1; i + len - 1 <= slen; i++)
        {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            int j = i+len-1;
            for(int k = i; k < j; k++). 1point3acres.com/bbs
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);  //这个是套路. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if(check(i, k, j))   // if I can compress str[i][j]-google 1point3acres
                {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                    int t = dp[i][k] + 2;   // ( ) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    int b = (j-k)/(k-i+1)+1;  //n of 'n( )'
                    while(b)
                    {
                        b /= 10;
                        t++;
                    }
                    dp[i][j] = min(dp[i][j], t); // 如果压缩了更好
                }
            }
        }
    }
    printf("%d\n", dp[1][slen]);
    return 0;-google 1point3acres
}
回复 支持 1 反对 0

使用道具 举报

chestnut9919 发表于 2016-11-18 04:52:32 | 显示全部楼层
第三轮那个跟我一样,原来只是个warm up啊。。怪不得我HC挂了
回复 支持 反对

使用道具 举报

Griffith♂Guts 发表于 2016-11-18 05:58:33 | 显示全部楼层
最后一轮竟然考gpu算法。玩游戏的知道关了阴影特效会流畅很多就知道这个复杂度挺高的了。
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 06:04:27 | 显示全部楼层
chestnut9919 发表于 2016-11-18 04:52
第三轮那个跟我一样,原来只是个warm up啊。。怪不得我HC挂了

T T那我凶多吉少了。。。是个亚裔姐姐。。。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-11-18 06:09:31 | 显示全部楼层
SidneyFan 发表于 2016-11-18 06:04
T T那我凶多吉少了。。。是个亚裔姐姐。。。

我的是个非洲小哥 你起码还问到了followup 我写完根本没时间了 还是很有希望的
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-18 06:17:56 | 显示全部楼层
第三轮的dp思路能不能分享下? 这题想了好几天了... 没有头绪呀
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 06:27:37 | 显示全部楼层
catinclay 发表于 2016-11-18 06:17
第三轮的dp思路能不能分享下? 这题想了好几天了... 没有头绪呀

我觉得brute force都很难想。。主要是S[i..j)加上S[j]的时候,要往回check是不是可以encode挺麻烦的。。我当时想的是从j到i检查,每次算[k,j]是不是S[i,k)的结尾的substring。。这样复杂度非常高。。但也没想到别的办法。。。dp[k][j]是这样想的,k代表pattern的长度,一段一段的去检查(因为可以压缩的pattern是相连的),但是也没想出具体要怎么算。。
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 06:28:26 | 显示全部楼层
chestnut9919 发表于 2016-11-18 06:09
我的是个非洲小哥 你起码还问到了followup 我写完根本没时间了 还是很有希望的

我看到你的帖子了!rotation多好啊!!!
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-11-18 06:39:53 | 显示全部楼层
SidneyFan 发表于 2016-11-18 06:28
我看到你的帖子了!rotation多好啊!!!

好啥啊这都是HC挂了的被扔过去,还是祝你过HC。
回复 支持 反对

使用道具 举报

披着马甲的菠菜 发表于 2016-11-18 08:25:59 | 显示全部楼层
加油小可爱~哈哈哈

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 08:30:10 | 显示全部楼层
. from: 1point3acres.com/bbs
卧槽这是谁。。
回复 支持 反对

使用道具 举报

披着马甲的菠菜 发表于 2016-11-18 08:31:23 | 显示全部楼层
SidneyFan 发表于 2016-11-18 08:30. 1point 3acres 璁哄潧
卧槽这是谁。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你的名字太好认了。。。嘎的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

fay19 发表于 2016-11-18 10:11:03 | 显示全部楼层
求问楼主,第三题的follow up的话,如果是输入是“accaccacc",输出应该是3[a2[c]]还是3[acc]呢,第二个其实更短一些~~~
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-18 10:29:17 | 显示全部楼层
披着马甲的菠菜 发表于 2016-11-18 08:31
你的名字太好认了。。。嘎的

层主你好,求保佑!
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 12:06:41 | 显示全部楼层
fay19 发表于 2016-11-18 10:11
求问楼主,第三题的follow up的话,如果是输入是“accaccacc",输出应该是3[a2[c]]还是3[acc]呢,第二个其实 ...

第二个,要包括中括号的长度
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-18 12:38:17 | 显示全部楼层
Bless LZ.
感觉都好难啊。。。
回复 支持 反对

使用道具 举报

fay19 发表于 2016-11-18 12:59:31 | 显示全部楼层
SidneyFan 发表于 2016-11-18 12:06
第二个,要包括中括号的长度

感谢楼主,那这样的话dfs是可以做出来的,我前几天看到别的人的面经有这个题,今天刚写了一个dfs的,test了几个case可以过,dp的话感觉不知道怎么定义状态哎,楼主有想法吗?
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 13:20:05 | 显示全部楼层
fay19 发表于 2016-11-18 12:59
感谢楼主,那这样的话dfs是可以做出来的,我前几天看到别的人的面经有这个题,今天刚写了一个dfs的,test ...

backtracking吗。。复杂度呢?
回复 支持 反对

使用道具 举报

 楼主| SidneyFan 发表于 2016-11-18 13:22:03 | 显示全部楼层
fay19 发表于 2016-11-18 12:59
感谢楼主,那这样的话dfs是可以做出来的,我前几天看到别的人的面经有这个题,今天刚写了一个dfs的,test ...

dfs加一个memory储存见过的string大概就变成dp了吧
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-18 13:32:43 | 显示全部楼层
SidneyFan 发表于 2016-11-18 13:22
dfs加一个memory储存见过的string大概就变成dp了吧

求楼主细说一下记忆化搜索的思路呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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