google onsite

cszeus

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

1. longest substring with at most m distinct characters。问了一堆怎么优化。最后面试官问我是不是见过这题，我说见过

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

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

2))这样的表达式，就是 7 +（8*9）+（12* （1+2））

都在面经里看过，感觉大家已经快把题库都穷尽了

cszeus

hyliu0000 发表于 2015-12-9 02:09
楼主啊，能不能详细说说你是怎么做的？
我先说下我的：
定义两个pointer left ，right

maxLen = 0
dic = {}
end = start = 0
while end < len(s):
if ch in dic or len(dic) < m:
 dic[ch] = end
else:
 maxLen = max(maxLen,end-start)
 # find minimum index in dic and its ch, O(m)
 start = index+1
 dic.pop(ch)
end += 1

大致是这样，当你有m个字母，并且出现m+1个字母的时候，你要试图删掉某个字母吧？我就找m个字母里面，出现最早的那个。

比如， ababac, m = 2
当出现c时，字典里面有{"b":3,"a":4}. 我只记录某个字母最后一次出现的位置。现在我可以知道，最后一个b出现在位置3，从位置4开始，只有m-1个字母。

然后这个地方，找到b，要扫一遍这个table。但是如果用OrderDict结合LRU cache的思想，每次更新一个字母的位置时，把它放到字典的最后，你就知道，字典中第一个，永远是我要找的那个。

补充内容 (2015-12-9 02:53):
这个字典会变成： {"a":0}, {"a":0,"b":1}, {"b":1,"a":2},{"a":2,"b":3}......m很大，你就看看出这个好处了

hyliu0000

cszeus 发表于 2015-12-9 01:00
只要存m个字母，每个字母最后出现的位置。然后找删除哪个的时候，扫一遍这个table，cost O(m)。但是如果 ...

楼主啊，能不能详细说说你是怎么做的？
我先说下我的：
定义两个pointer left ，right
定义hashmap<char, int> map
int maxLength = Integer.MAX_VALUE;
while(right < n)
map[char] ++
if(map.size() > m)
 left ++;
 map[char at left] -- ;
 maxLength = max(maxLength, right - left);
right ++;
maxLength = max(maxLength, right - left);
return maxLength

cszeus

ssross 发表于 2015-12-6 02:29
楼主能不能说下具体第三题？能不能说下设计的数据结构长啥样？
非常感谢！bless LZ！

就是树的结构啊，DOM就是个树啊。每个node有个children list，表示子节点。因为有可能有text的，我用的方法是把text也放到一个特殊的node里。

比如<html>hello world</html> 就是：
<html>
<text> hello </text>
world 
</html>

litJordan

楼主能不能说下具体第三题？能不能说下设计的数据结构长啥样？
非常感谢！bless LZ！

queeniejing

LZ在哪里面的只有4轮吗

litJordan

cszeus 发表于 2015-12-6 02:34
就是树的结构啊，DOM就是个树啊。每个node有个children list，表示子节点。因为有可能有text的，我用的方 ...

什么叫把test放到一个特殊的node里？

我design的是这样的不知道有没有问题:
class Node {
List<Node> children;
String text;
boolean inTag; // means if the node is in a tag
}
楼主设计的跟我有什么不一样嘛？

还想问下第一题我看到别人的面经里也有过。有个followup是如果给的input是stream怎么办？不知道LZ有没有问到。

cszeus

queeniejing 发表于 2015-12-6 05:17
LZ在哪里面的只有4轮吗

mountain view, 4轮

cszeus

ssross 发表于 2015-12-6 05:28
什么叫把test放到一个特殊的node里？

我design的是这样的不知道有没有问题:

因为可能是

hello world,也有可能是 hello world

text出现的位置不一定，所以把他也当做node处理。你那个结构，你知道text是在哪里么？

cszeus

ssross 发表于 2015-12-6 05:28
什么叫把test放到一个特殊的node里？

我design的是这样的不知道有没有问题:

并没有问stream的follow up。我不知道你怎么做，反正我会记录字母出现的位置。是不是stream，我觉得没有什么不同

hyliu0000

楼主，第一题需要怎么优化啊？是不是就是两个指针＋ hashmap？第二轮需要给出dp的解吗？最后一题是不是就用一个stack就ok了啊？遇到＋－＊／就放倒stack里面，遇到）或者结尾了就pop，然后计算。楼主你是怎么做的？

cszeus

hyliu0000 发表于 2015-12-6 07:56
楼主，第一题需要怎么优化啊？是不是就是两个指针＋ hashmap？第二轮需要给出dp的解吗？最后一题是不是 ...

第一题主要了优化数据结构，讨论了用堆，BST，python里的OrderedDict的可行性。第二轮NP-hard，我不觉得有dp，就是要你暴力解，然后根据他给的特殊条件，优化下。最后一题我用的stack

google onsite

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

浏览过的版块