有很多同学跟领扣🐱反馈
Palantir面试简直一绝
不但薪资股权远超一线大厂，面试还包吃包住！
就连跪面后，都有HR主动联系复盘

这么好的公司，错过了可就没有啦！
其实Palantir的面试非常看重算法和coding能力，这里将一道Palantir面试真题，分享给大家👇
LintCode 1318

包含重复值吗？III

题目描述
给定一个整数数组，找出数组中是否有两个不同的索引i和j，使得nums [i]和nums [j]之间差的绝对值最多为t，同时i和j之间差的绝对值最多为k。

扫码免费做题
↓↓↓
样例1：
输入: nums = [1,3,1], k = 1, t = 1

输出: false

解释:

nums[2] = 1, nums[1] = 3, nums[1] - nums[2] = 2 > t

nums[0] = 1, nums[2] = 1, nums[1] - nums[2] = 0 < t,

2 - 0 = 2 > k
样例2：
输入: nums = [1,3,1], k = 1, t = 2

输出: true

解释:

nums[2] = 1, nums[1] = 3, nums[1] - nums[2] = 2 = t,

2 - 1 = 1 = k
解题思路
用map维护数字的位置，然后扫一遍数组进行求解。
源代码
publicclassSolution{/*** @param nums: the given array* @param k: the given k* @param t: the given t* @return: whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.*/privatelonggetID(long i, long w){return i < 0 ? (i + 1) / w - 1 : i / w;}publicbooleancontainsNearbyAlmostDuplicate(int[] nums, int k, int t){// Write your code hereif (t < 0) {returnfalse;}Map<Long, Long> d = new HashMap<>();long w = (long)t + 1;for (int i = 0; i < nums.length; ++i) {long m = getID(nums[i], w);if (d.containsKey(m)) {returntrue;}if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w) {returntrue;}if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w) {returntrue;}d.put(m, (long)nums[i]);if (i >= k) {d.remove(getID(nums[i - k], w));}}returnfalse;}}
点击【阅读原文】，查看领扣原题。
继续阅读
阅读原文
关键词
数组
数字
题目
思路
之间