Google实习电面

这个月初面的, 实习都是电面两轮, 第一个是白人小哥,第二个是国人.

First interview: Design a data structure that stores a dictionary and can return a list of words that has some input prefix.
LC: TrieT

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

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

t style="background-color:rgb(245, 246, 247)">



最近收到通知要再加面一轮电面 orz

jpeng7 发表于 2016-11-29 02:55
求问第一题的time/space complexity是什么呀？谢谢～

我当时好像是这样答的,不知道对不对:
Time
For insertion: O(m)
For insert everything O(mn)
Finding prefix O(s)

Space:
O(mn) worst case, no words share any prefix

nicklyz 发表于 2016-11-29 02:59
我当时好像是这样答的,不知道对不对:
Time
For insertion: O(m)

嗯，find prefix是o(s)没错，但是要找到所有有prefix前缀的words，是不是找完prefix之后还得遍历所有包含这个prefix的word？那样时间复杂度好像？？

jpeng7 发表于 2016-11-29 04:28
嗯，find prefix是o(s)没错，但是要找到所有有prefix前缀的words，是不是找完prefix之后还得遍历所有包含 ...

我当时好像是在每个Node存了个List 来存所有的words

Follow-up: if a dict has n words, average word length is m, input length is s, what's the time/space complexity? . 1point3acres.com/bbs

- what's the time/space complexity? thanks

leetcode 211, 153

求问楼主找内推了嘛？

changju0310 发表于 2016-11-28 11:56
求问楼主找内推了嘛？

没有, 好像是Google联系的我. 然后我就网申了. 好像实习一般都不需要内推都有面试.

求问第一题的time/space complexity是什么呀？谢谢～

请问楼主是面完多久以后收到的加面通知啊？