两个P家电面面经# JobHunting - 待字闺中
p*8
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 如果是超出部分是其中一个数字，
证明这组一瓶不正常（两个奇数的和为偶数，所以只可能是一瓶不正常），要撑两次，
如果大于这个数字，说明两瓶不正常，再撑一次，也要两次
希望有要面的同学可以参考下
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 如果是超出部分是其中一个数字，
证明这组一瓶不正常（两个奇数的和为偶数，所以只可能是一瓶不正常），要撑两次，
如果大于这个数字，说明两瓶不正常，再撑一次，也要两次
希望有要面的同学可以参考下
