一亩三分地论坛

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

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

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

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

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

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

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

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。

希望大家面试顺利!!!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

本帖被以下淘专辑推荐:

handsomecool 发表于 2016-6-12 06:15:19 | 显示全部楼层
Trie好像快一些,build trie只要n*L的时间,sort则要nlog(n) * L ,  (n是单词个数,L是平均长度,sort的话每次比较也要花L的时间所以是Nlog(N)*L ) , 但是用trie要多用空间,sort则不用。

每个单词生成unique时我觉得不用remove, 可以这样做:

    在trie中沿着该单词从上往下一个字母一个字母走,一旦发现下面没有分支,就定下来,得到的就是最短的unique表达。

这样生成每个单词的unique表达是O(L), 一共是O(n*L) , 这一步也比较快。. 1point3acres.com/bbs

举个例子:
. From 1point 3acres bbs
['chips', 'chocolate', 'orange', 'cake'], return ['chi', 'cho', 'o', 'ca']

               root
             /      \
           c          o. from: 1point3acres.com/bbs
         /   \         \
       a     h          r
      /      /  \         \.1point3acres缃
    k       i    o         a
  /        /      \
e       p          c
    .... ....

从这个树里我们可以看到chips这个单词在i这个节点开始,每个level只有一个节点,所以chips应该return chi ;
可以看到chocolate 这个单词从o这个节点开始,每个level只有一个节点,所以chocolate应该return cho

大概就是这个意思。


. more info on 1point3acres.com

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

使用道具 举报

snowwolf 发表于 2016-6-11 16:46:16 | 显示全部楼层
竟然还问非算法的问题,好厉害
回复 支持 反对

使用道具 举报

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
竟然还问非算法的问题,好厉害

可能跟我简历上的经验也有关系。我以前做过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
. 1point 3acres 璁哄潧举个反例,两个单词chi 和 chip这个方法怎么区分chi和chip呢?

trie的每个node有一个flag是用来判断这个node是不是一个valid end of word还是只是某一个更长的word的路径上的节点对吧。在我刚才描述的步骤中可以这样来判断:. 1point 3acres 璁哄潧

string getUniqueRepresentation(string &word, int pos, TrieNode* n){

         if(pos == word.length()-1) //如果已经到了这个单词的最后一个字母,直接return整个单词
                return word;. 1point 3acres 璁哄潧
         if(n->children.size()==1&&!n->valid())//如果下面只有一个节点,且当前节点不是某单词的最后一个字母.鐣欏璁哄潧-涓浜-涓夊垎鍦
                return word.substr(0, pos+1);
. Waral 鍗氬鏈夋洿澶氭枃绔,
         // 否则继续往下找
         return getUniqueRepresentation(word, pos+1, n->children[word[pos]] );
}

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

使用道具 举报

 楼主| 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. 鍥磋鎴戜滑@1point 3 acres
trie的每个node有一个flag是用来判断这个node是不是一个valid end of word还是只是某一个更长的word的路 ...
. from: 1point3acres.com/bbs
感觉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>
复制代码
比如你说的例子,建成的树是:

              root               share            isEndOfWord
                |
                C                   2                     F. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                |.1point3acres缃
                H                   2                     F
                |
                I                    2                     F
                |
                P                    2                     T
                | .1point3acres缃
                S                    1                     T

生成unique的那个function就不看children size了,看share是不是1.。。。这回应该行了? :). Waral 鍗氬鏈夋洿澶氭枃绔,

回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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