booking.com缤客上海面经

缘起

有几年，我每年都会去市场上面试几场，了解一下就业市场的形势，探讨一下最新的技术，有利无弊。所以积累了较多的面经，但是booking.com缤客是比较特别的一家，印象特别深刻。
一是时机。那时候刚从网易出来，想试试外企的机会，缤客是我面的第一家外企。
二是流程。他们的面试非常严谨，也很人性化，对我熟悉外企流程起了很大作用。
缤客面试经历跌宕起伏，虽然最终没去成，但其面试经历为我后来去其他外企乃至出国，奠定了基础，所以详细追记。

过程

1. V2EX论坛推荐

V2EX论坛在国内的技术论坛里面算比较有特色的论坛，那阵子对我帮助很大，有一半面试机会都来自陌生坛友的推荐，感谢senryxie帮忙推荐到缤客，也很快有回音，邀请面试。

2. 做hackerrank的题目（类似于leetcode，但是对方的题目比较难）

一共4道，前2道是leetcode容易级别的问题，我花了30分钟

后2到是结合了他们业务的题目，至少是leetcode中级以上的难度，关键是时间很紧！！一共才75分钟，加上第一次接触这类形式，时间分配上也不合理，结果我没有做完。我有点不甘心，申请重试，理由是Internet Connection Fail，新分配的4题难度也和上次都差不多，结果4道都做完，其中前2道完全测试通过，后2道有部分测试案例未通过。

回头看，缤客对编码题目的要求是比较高的，这里已经埋下了伏笔。

3. 五一节后HR沟通，其中5.8日全程HR英语面试

我记得用英语差不多聊了一个小时，讲讲过去的经历，之前我在国外学校的见闻，对将来工作的规划，以及为什么来缤客。聊下来感觉HR很专业，增加对缤客的好感。

4. 电话面试（主要是leetcode类似的编码题）

5月10日 booking.com的charles代码面试，时间复杂度O（n）
事后反馈：

• make clear事先沟通很好，方案经过讨论，不是一头扎进去；
• 有优化的概念；
• 时间复杂度概念清晰；
• 问题是漏了一个边界值修改条件

5. 现场面试

5月15日现场面试

booking是全程编码和算法且有英文，

• 第一面是他们的系统设计，设计一个弹窗系统，里面是他们的浏览同一个地点同一个旅馆的竞拍人数，

• 第二面是fitting，里面提到ab testing，

• 第三面是coding，流量过滤，因为边界条件判断和时间复杂度判断问题导致red flag

事后第二天，booking马上反馈我结果了，反馈速度很快，这个很赞

---

复盘

booking沟通：系统设计和fitting都过了，特别是系统设计很难得，因为挂在这个的人多，但是提到我比较依赖网易的工具，另外对session不太了解；coding挂了，编码过程中沟通之类的还是好的，手写代码也比较清晰规范，但是面试官反馈过程中边界条件有考虑不周之处，且事后复检时发现特定条件下有个死循环

我努力回忆了下现场点评并没有提到死循环问题，但当时在现场面试官帮助下，我将时间复杂度从O(n平方)提升到O(n)是有的。我赶紧找LeetCode上类似一题，按昨天面试现场的氛围和时间要求复盘一下。

题目要求：

凭记忆，当时题目要求是设计并实现一个流量控制的核心程序函数，核心的要求是根据网页访问请求的特征值（比如IP和端口），做一个滑动时间窗口（比如5分钟）内的流量控制，要求每个特征值在这个滑动时间窗口内不得超过n个。

我当时的思路（主要就是两个数据结构）：

1. 所谓滑动时间窗口，就是老的删掉，新的纳入。所以我用了一个Java的双向队列LinkedList，过期的老的访问请求，从队列头部删除；新进来的请求，加入到队列尾部。

2. 题目要求对每个特征值的请求，统计其时间窗口内的访问次数，所以我用了HashMap，主键是特征值，属性是访问次数，每当有新的请求进来，会检查是否有过期的老请求，删除；而新的请求，根据特征值看看其单位时间内请求次数是否超标

Leetcode上类似题目

今天正好在Leetcode上看到一道题，和面试题很像，只是Leetcode题目是统计滑动窗口内的平均值，题意更简单，不需要用HashMap，用上第一个数据结构LinkedList就可以了；滑动窗口是长度不是时间，相对也更简单

题目描述：346. 数据流中的移动平均值

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。例子如下：

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

因为面试过有思路，所以这个题目做的还是很顺手，实现代码如下：

class MovingAverage {
    

    //这题类似我在booking.com面试时做的

    Deque<Integer> dq;

    double avg;

    int size; 

    

    /** Initialize your data structure here. */

    public MovingAverage(int size) {
    

        this.dq = new LinkedList<>();

        this.size = size;

        this.avg = 0;

    }

    

    public double next(int val) {
    

        int len = dq.size();

        if (len < size) {
    

            dq.addLast(val);

            avg = (avg*len+val)/(len+1);

        } else {
    

            int rmval = dq.removeFirst();

            dq.addLast(val);

            avg = (avg*len-rmval+val)/len;

        }

        return avg;

    }

}

实际运行效果：

---

各个外企的Java面经（paytm wework mc booking ebay farfetch）.md