May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2924|回复: 17
收起左侧

狗家6月onsite经验分享。。。

[复制链接] |试试Instant~ |关注本帖
dianhua1560 发表于 2016-6-11 16:30:16 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google狗家6月onsite经验分享。。。 - 内推 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚面完onsite,上来跟大家分享一下。

过程和其他onsite一样,上午2个45分钟面试,中午和员工吃饭,下午再2个45分钟。

第一个面试:warmup问题,给一个string,找出第一个不重复的character。没啥难度,直接第二题。给一个list of strings, 比如['chips', 'chocolate', 'orange', 'cake'], return ['chi', 'cho', 'o', 'ca']。意思就是找出可以uniquely表达每个string最短的prefix。给回的list里的prefix的顺序不重要。我当时的想法是先sort,然后值得注意的地方是第一次当两个string的第一个character不一样的时候。

第二个面试:有一个shadow。上来问network的问题,accessing a single page, loading forever, what could be the issue and solution? 第二题,假设有一个social network,找出其中一个人的第k层的所有的朋友。例子,A和B是朋友,B和C是朋友,那么A的第一层朋友有B,第二层朋友有C。直接bfs解,node的structure自己写。

第三个面试:上来问bfs的一个题,bfs是怎么运作的,怎么用bfs找出从一个node到另外一个node的最短的一个path。完了之后问A* algorithm,因为自己简历上写了之前project有用过。。。这里有点懵,1年前学的东西,完全没准备,随便瞎聊了几句。之后的题是 implement an encode function。decode的func已经给了,input是string,output也是string。decode是如果看见一个数字然后又看见‘x',那么在output里加上这个数字数量’x'后面的char。例子,input = "4xe", output = "eeee"; input = "abc10xq", output = "abcqqqqqqqqqq"。encode func应该尽量减少output的长度,然后保证decode出来的string是encode之前的string。最后的encode func应该保证不会有任何不同的input最后encode完有一样的output。

第四个面试:问andriod的面板parttern和普通数字密码,哪个更secure?然后问了leetcode的351,改了一下,最后return value是list of all possible patterns。. Waral 鍗氬鏈夋洿澶氭枃绔,

希望大家面试顺利!!!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

handsomecool 发表于 2016-6-12 06:15:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Trie好像快一些,build trie只要n*L的时间,sort则要nlog(n) * L ,  (n是单词个数,L是平均长度,sort的话每次比较也要花L的时间所以是Nlog(N)*L ) , 但是用trie要多用空间,sort则不用。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

每个单词生成unique时我觉得不用remove, 可以这样做:
. visit 1point3acres.com for more.
    在trie中沿着该单词从上往下一个字母一个字母走,一旦发现下面没有分支,就定下来,得到的就是最短的unique表达。

这样生成每个单词的unique表达是O(L), 一共是O(n*L) , 这一步也比较快。
. more info on 1point3acres.com
举个例子:. visit 1point3acres.com for more.

['chips', 'chocolate', 'orange', 'cake'], return ['chi', 'cho', 'o', 'ca']

               root
             /      \
           c          o
         /   \         \
       a     h          r
      /      /  \         \
    k       i    o         a
  /        /      \
e       p          c
    .... ....

从这个树里我们可以看到chips这个单词在i这个节点开始,每个level只有一个节点,所以chips应该return chi ;
. Waral 鍗氬鏈夋洿澶氭枃绔,可以看到chocolate 这个单词从o这个节点开始,每个level只有一个节点,所以chocolate应该return cho

大概就是这个意思。


. from: 1point3acres.com/bbs

补充内容 (2016-6-12 06:20):
这样比不断加长prefix来test是否unique快,不断加长来判断的话要O(L^2)。
回复 支持 2 反对 0

使用道具 举报

snowwolf 发表于 2016-6-11 16:46:16 | 显示全部楼层
关注一亩三分地微博:
Warald
竟然还问非算法的问题,好厉害
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-6-11 23:54:10 | 显示全部楼层
accessing a single page, loading forever, what could be the issue and solution? 求大神解答
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 02:07:11 | 显示全部楼层
snowwolf 发表于 2016-6-11 16:46
-google 1point3acres竟然还问非算法的问题,好厉害
. 1point 3acres 璁哄潧
可能跟我简历上的经验也有关系。我以前做过devops的intern,学校里也拿过类似的课。
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 02:09:52 | 显示全部楼层
mkcing 发表于 2016-6-11 23:54
accessing a single page, loading forever, what could be the issue and solution? 求大神解答

这个说实话就是看你能不能说了。我觉得没有正确答案,别太离谱就行了。我当时说的是跟server traffic有关,或者跟中间proxy有关,或者跟database的容量和indexing有关。把懂得沾边的都说了一遍
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-12 03:07:05 | 显示全部楼层
拿offer的节奏啊,祝好~
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-6-12 05:14:35 | 显示全部楼层
第一面的第二题trie可以做吗?
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 05:35:37 | 显示全部楼层
hidden_track 发表于 2016-6-12 05:14
第一面的第二题trie可以做吗?

具体点?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-6-12 05:51:39 | 显示全部楼层
有点小麻烦,先把所有其他的字符串insert到Trie里,然后就是对每一个字符串, 先把当前字符串从Trie里remove, 然后遍历当前字符串的所有prefix, 调用startsWith一直到return false最后在把当前的字符串insert回去,继续遍历后面的字符串,求问楼主当时用了什么方法做的?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-6-12 06:25:07 | 显示全部楼层
handsomecool 发表于 2016-6-12 06:15
Trie好像快一些,build trie只要n*L的时间,sort则要nlog(n) * L ,  (n是单词个数,L是平均长度,sort的话 ...

举个反例,两个单词chi 和 chip这个方法怎么区分chi和chip呢?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-12 06:45:33 | 显示全部楼层
hidden_track 发表于 2016-6-12 06:25
举个反例,两个单词chi 和 chip这个方法怎么区分chi和chip呢?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
trie的每个node有一个flag是用来判断这个node是不是一个valid end of word还是只是某一个更长的word的路径上的节点对吧。在我刚才描述的步骤中可以这样来判断:
. 鍥磋鎴戜滑@1point 3 acres
string getUniqueRepresentation(string &word, int pos, TrieNode* n){

         if(pos == word.length()-1) //如果已经到了这个单词的最后一个字母,直接return整个单词 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                return word;. From 1point 3acres bbs
         if(n->children.size()==1&&!n->valid())//如果下面只有一个节点,且当前节点不是某单词的最后一个字母. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                return word.substr(0, pos+1);

         // 否则继续往下找
         return getUniqueRepresentation(word, pos+1, n->children[word[pos]] );
}

补充内容 (2016-6-12 06:46):. 1point 3acres 璁哄潧
其实你如果不问我都没想到这种情况。
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 06:55:03 | 显示全部楼层
handsomecool 发表于 2016-6-12 06:45
trie的每个node有一个flag是用来判断这个node是不是一个valid end of word还是只是某一个更长的word的路 ...

感觉这题可能是考trie的,但是当时没忘那边想。。。
回复 支持 反对

使用道具 举报

 楼主| dianhua1560 发表于 2016-6-12 06:55:52 | 显示全部楼层
hidden_track 发表于 2016-6-12 05:51
有点小麻烦,先把所有其他的字符串insert到Trie里,然后就是对每一个字符串, 先把当前字符串从Trie里remove ...

我没想到trie。。。当时第一想法就是先sort 然后在找prefix。思路很简单,注意edge case就好了。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-12 07:01:39 | 显示全部楼层
dianhua1560 发表于 2016-6-12 06:55
感觉这题可能是考trie的,但是当时没忘那边想。。。

trie好像不是必须知道的,没事没事。
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-6-12 07:11:27 | 显示全部楼层
handsomecool 发表于 2016-6-12 06:45
trie的每个node有一个flag是用来判断这个node是不是一个valid end of word还是只是某一个更长的word的路 ...

感觉code还是有点小问题,比如说chip和chips。。c的children size 是1 并且c不是endWord...那难道要return c吗?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-12 07:28:03 | 显示全部楼层
hidden_track 发表于 2016-6-12 07:11
感觉code还是有点小问题,比如说chip和chips。。c的children size 是1 并且c不是endWord...那难道要retur ...

哦,我刚才没有理解,原来你是说字典里一共就只有chip和chips俩单词。 嗯。。。不太好办,我感觉可以在build trie的时候记录每个node被几个单词share,这样我们还是从上往下找,直到找到只被一个单词使用的node为止。
  1. <div>struct TrieNode {</div><div>    char c;</div><div>    unordered_map<char, TrieNode*> children;</div><div>    int share;</div><div>    bool isEndofWord;</div><div>}</div>
复制代码
比如你说的例子,建成的树是:
. 鍥磋鎴戜滑@1point 3 acres
              root               share            isEndOfWord. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                |
                C                   2                     F
                |
                H                   2                     F
                |
                I                    2                     F
                |
                P                    2                     T
                |
                S                    1                     T
-google 1point3acres
生成unique的那个function就不看children size了,看share是不是1.。。。这回应该行了? :)

回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-12 07:29:29 | 显示全部楼层
格式怎么乱了。。
  1. struct TrieNode {
  2.     char c;  . 鍥磋鎴戜滑@1point 3 acres
  3.     unordered_map<char, TrieNode*> children;
  4.     int share;
  5.     bool isEndofWord;
  6. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 21:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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