p*******8 发帖数: 344 | 1 P家指palantir, pocket gems,不管能不能过,应该不打算继续面了,刚面的面经
palentir:
1)warm-up: 给定一个array,如果有duplicate,返回true,否则,false
2)改进一:如果存在duplicate元素间index的距离不超过k,返回true,否则,false
比如a[1]=a[3]=3, k=2,那么3-1=2 <=2, 返回true
比如a[1]=a[3]=3, k=1,那么3-1=2 > 1, 继续找
我用了HashMap记录每个元素的index,如果第二次遇到,比较当前index和前面记录
的值,满足条件就返回true,否则继续找,空间>O(N),被问能不能优化空间,没想出来
,提示说只要记录k个数字就行了,于是我用了个linked hash map,超过k个,自动踢出
最老的,表示可以,但有点overkill了
3)改进二:如果存在两个元素间index的距离不超过k,差的绝对值不超过l,返回true
,否则, false
比如a[1]=2, a[3]=3, k=2,l=3, 那么3-1=2 <=2(k), 3-2 < 3(l)返回true
同理,如果l=0, 继续找
写了个O(K*N)的算法,表示认可,问能不能弄个更快的,我表示没想法,然后问了
几个问题就完了
pocket gems:
同glassdoor上基本一样
1)反转字符串
2)binary tree的LCA
3)10瓶药片,一瓶重量不一样,一个称,用最少次数找出那瓶异常的
改进:可能是1瓶不正常,可能是2瓶不正常,怎么找
我想了个,分成两组,没组5瓶,标上1,3,5,7,9 如果是超出部分是其中一个数字,
证明这组一瓶不正常(两个奇数的和为偶数,所以只可能是一瓶不正常),要撑两次,
如果大于这个数字,说明两瓶不正常,再撑一次,也要两次
希望有要面的同学可以参考下 | p*****2 发帖数: 21240 | | c********t 发帖数: 5706 | 3 多谢!bless!
2)改进一:如果存在duplicate元素间index的距离不超过k,返回true,否则,false
两个指针+hashmap 可以吧
3)改进二:如果存在两个元素间index的距离不超过k,差的绝对值不超过l,返回true
,否则, false
两个指针+BST+ current min variable,应该能O(nlgk),但是太难写codes了,看有没
有更好的解法。
false
【在 p*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P家指palantir, pocket gems,不管能不能过,应该不打算继续面了,刚面的面经 : palentir: : 1)warm-up: 给定一个array,如果有duplicate,返回true,否则,false : 2)改进一:如果存在duplicate元素间index的距离不超过k,返回true,否则,false : 比如a[1]=a[3]=3, k=2,那么3-1=2 <=2, 返回true : 比如a[1]=a[3]=3, k=1,那么3-1=2 > 1, 继续找 : : 我用了HashMap记录每个元素的index,如果第二次遇到,比较当前index和前面记录 : 的值,满足条件就返回true,否则继续找,空间>O(N),被问能不能优化空间,没想出来 : ,提示说只要记录k个数字就行了,于是我用了个linked hash map,超过k个,自动踢出
| p*****p 发帖数: 379 | 4 随便写了下,可能有bug
1.
bool checkDup(int *a, int n) {
unordered_set set;
for (int i = 0; i < n; ++i) {
if (set.find(a[i]) == set.end()) {
set.insert(a[i]);
}
else {
return true;
}
}
return false;
}
2.
bool checkDup(int *a, int n, int k) {
list kCont;
unordered_set set;
for (int i = 0; i < n; ++i) {
if (set.find(a[i]) == set.end()) {
if (kCont.size() == k) {
set.erase(kCont.front());
kCont.pop_front();
}
kCont.push_back(a[i]);
set.insert(a[i]);
}
else {
return true;
}
}
return false;
}
3没想出什么好想法
false
【在 p*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P家指palantir, pocket gems,不管能不能过,应该不打算继续面了,刚面的面经 : palentir: : 1)warm-up: 给定一个array,如果有duplicate,返回true,否则,false : 2)改进一:如果存在duplicate元素间index的距离不超过k,返回true,否则,false : 比如a[1]=a[3]=3, k=2,那么3-1=2 <=2, 返回true : 比如a[1]=a[3]=3, k=1,那么3-1=2 > 1, 继续找 : : 我用了HashMap记录每个元素的index,如果第二次遇到,比较当前index和前面记录 : 的值,满足条件就返回true,否则继续找,空间>O(N),被问能不能优化空间,没想出来 : ,提示说只要记录k个数字就行了,于是我用了个linked hash map,超过k个,自动踢出
| h**i 发帖数: 431 | 5 那个不超过k的可以用heap达到O(Nlogk)
false
【在 p*******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : P家指palantir, pocket gems,不管能不能过,应该不打算继续面了,刚面的面经 : palentir: : 1)warm-up: 给定一个array,如果有duplicate,返回true,否则,false : 2)改进一:如果存在duplicate元素间index的距离不超过k,返回true,否则,false : 比如a[1]=a[3]=3, k=2,那么3-1=2 <=2, 返回true : 比如a[1]=a[3]=3, k=1,那么3-1=2 > 1, 继续找 : : 我用了HashMap记录每个元素的index,如果第二次遇到,比较当前index和前面记录 : 的值,满足条件就返回true,否则继续找,空间>O(N),被问能不能优化空间,没想出来 : ,提示说只要记录k个数字就行了,于是我用了个linked hash map,超过k个,自动踢出
| x*****0 发帖数: 452 | | d**u 发帖数: 1065 | 7 warm-up那题元素最大值是多少?如果小于n,有O(n)算法。 |
|