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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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)算法。 |
|
