这是我在 Google 面试中的一个经历。在面试中，面试官给了我一个有趣的编程任务，目的是考察我的数据结构和算法能力，以及如何在实际工程中优化性能的能力。以下是我在面试中的具体解题过程和思路。

Your task is to write a function that given a distance d and a stream of floating point values received one at a time, checks for groups of three values that are within at most d distance.
As values are received they should be stored in memory.
Whenever any group is found meeting the distance criteria, return the three values and remove them from memory.

面经记录

问题描述：

面试官给了我一个任务：写一个函数，给定一个距离 d 和一个流式接收的浮点数Array，检查是否存在任意三个值的距离在 d 以内。如果找到这样的三个值，就返回这三个值并从内存中删除它们。

理解和讨论：

我首先确认了几个关键点：

1. d 是表示数值之间的距离。
2. Array是一个一个进入的。
3. 一旦找到满足条件的三个数，就要从内存中移除这三个数。

我举了一个例子来确认我的理解：如果 d 是3，那么序列 [2, 3, 4] 就满足条件，因为任意两个数之间的距离都在 3 以内；但是序列 [2, 5, 8] 不满足条件，因为虽然 2 和 5 之间的距离在 3 以内，5 和 8 之间的距离在 3 以内，但 2 和 8 之间的距离超过了 3。

最简单的方法：

我首先提出了一个简单的方法，即将所有数字记录在一个数组中，然后每次接收到一个数字时，用嵌套循环检查所有可能的三元组。这种方法的时间复杂度是 O(n^2)。

面试官同意这个思路，并让我实现这个方法。

python复制代码def find_triplet_within_distance(d, stream):
    memory = []
    
    def check_triplets():
        n = len(memory)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if abs(memory[i] - memory[j]) <= d and abs(memory[j] - memory[k]) <= d and abs(memory[i] - memory[k]) <= d:
                        return [memory[i], memory[j], memory[k]]
        return None

    for value in stream:
        memory.append(value)
        triplet = check_triplets()
        if triplet:
            # Remove the triplet from memory
            memory.remove(triplet[0])
            memory.remove(triplet[1])
            memory.remove(triplet[2])
            return triplet
    return None

# Example usage
d = 3
stream = [1.0, 2.0, 4.0, 5.0, 7.0, 8.0]
result = find_triplet_within_distance(d, stream)
print(result)  # Output should be [2.0, 4.0, 5.0] or [4.0, 5.0, 7.0] depending on order

性能优化：

为了提高性能，我提出了优化方案，即保持数组有序，这样我们可以使用二分查找来插入新数字，并用双指针方法检查是否存在满足条件的三元组。这样可以将时间复杂度降低到 O(n log n)。

面试官同意这个优化方案，并让我实现这个方法。

python复制代码from bisect import bisect_left, insort

def find_triplet_within_distance_optimized(d, stream):
    memory = []
    
    def check_triplets(index):
        left, right = index - 1, index + 1
        while left >= 0 and abs(memory[index] - memory[left]) <= d:
            while right < len(memory) and abs(memory[right] - memory[left]) <= d:
                if abs(memory[index] - memory[right]) <= d:
                    return [memory[left], memory[index], memory[right]]
                right += 1
            left -= 1
        return None

    for value in stream:
        pos = bisect_left(memory, value)
        insort(memory, value)
        triplet = check_triplets(pos)
        if triplet:
            # Remove the triplet from memory
            for val in triplet:
                memory.remove(val)
            return triplet
    return None

# Example usage
d = 3
stream = [1.0, 2.0, 4.0, 5.0, 7.0, 8.0]
result = find_triplet_within_distance_optimized(d, stream)
print(result)  # Output should be [2.0, 4.0, 5.0] or [4.0, 5.0, 7.0] depending on order

总结：

通过这个过程，我展示了从最简单的方法到优化方案的思路。面试官对我的理解和实现过程表示满意，并指出了这道题目考察的是候选人的数据结构和算法能力，以及在实际工程中如何优化性能的能力。

By following these steps, you will be able to answer each of the questions accurately. If you have any further questions or need additional clarification, feel free to ask!

After utilizing our interview assistance service, the candidate successfully passed this round of interviews. We look forward to the next set of interview questions together!

If you are interested in our services, feel free to leave us a message for consultation at any time.

经过我们的面试辅助服务，候选人顺利通过了本轮面试，我们一起期待下一次的面试题目吧~

如果您对我们的服务感兴趣，随时留言咨询我们。