Expedia面试经验|（校园实习）

Expedia参观了我们的校园，既有全职的，也有实习的，我当时坐在那里等待实习。这个过程包括一轮在线测试和三轮面试。

在线编码测试（1小时30分钟）

他们切断了0，测试是在HackerRank上进行的。

测试包括10个MCQ和2个编码问题。

MCQ围绕操作系统、面向对象、数据结构和算法展开。

编码问题如下：

1. 你总共有 N 你想要形成阶梯状的硬币 K -第四排一定有 K 硬币。鉴于 N ，找到 满的 可以形成的楼梯排。（即使是二进制搜索也给出了一些测试用例的TLE，只有O（1）解决方案可以通过所有测试用例）
2. 给定一条可以行驶无限多辆汽车的道路。道路索引从0到n开始。有m辆车的起始和结束索引以2个数组的形式给出。我们必须找到汽车从未行驶过的最大间隙。（这个问题也有很好的时间和记忆限制）

第一轮： 技术面试（1小时-1小时30分钟）

首先，她让我自我介绍，并告诉我一些简历中没有提到的事情。

然后问我一个编码问题：

给定一个经过排序和旋转的数组和一个元素，在一个完全排序的数组中查找该元素的索引。（这个问题涉及处理很多情况，找到数组是左旋转还是右旋转，然后找到旋转点，然后通过二进制搜索对给定元素进行索引。我被要求对所有这些进行编码）

当我写上述问题的代码时，她问我

• 什么是运行时和动态多态性？
• JAVA是一种完全面向对象的编程语言。
• 还有一些与操作系统有关的问题，我不记得了（我想这是为了检查你在多任务处理方面有多出色）

下一个问题是：

https://www.geeksforgeeks.org/find-the-number-occurring-odd-number-of-times/

求数组中出现奇数次的次数

（我给了她一个O（n^2）的解决方案，使用2个循环，一个O（n）中的解决方案，使用Hashmap和在O（n）中运行的XOR解决方案。然后她问我是否能想出一个空间复杂度为O（1），时间复杂度小于0（n）的解决方案

然后是关于hashmaps的很多问题：

• 什么是散列
• hashmaps中使用哪种数据结构
• C++ STL映射如何设计/内部函数的哈希映射
• 设计你自己的Hashmap

接下来是，

在链表中表示一个数字，每个数字对应链表中的一个节点。加1。我被要求编写代码。

然后这个问题被修改为：一个数字在链表中表示，这样几个数字对应链表中的一个节点。加1。示例：数字2323499表示为23->2->349->9，其输出应为

23->2->350->0（每个节点中的位数不均匀，结果在每个节点中的位数应与给定节点相同。）

然后是一个谜题：10个硬币谜题

https://www.geeksforgeeks.org/puzzle-24-10-coins-puzzle/

最后一个问题是：

在不使用额外内存的情况下反转堆栈。我被要求说出方法，然后编写代码。

(https://www.geeksforgeeks.org/reverse-stack-without-using-extra-space/)

第二轮： 技术面试（45分钟–1小时）

采访从一个总体介绍和一些关于我爱好的讨论开始。

然后让我告诉我这个方法，并为DP问题编写算法：所有1的最大大小方子矩阵

https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

在下一个问题中，所有的橙子都需要在相同的时间内进行轻微的修改。这将通过BFS解决。

https://www.geeksforgeeks.org/minimum-time-required-so-that-all-oranges-become-rotten/

除此之外，她还问了我很多问题，其中一些是：

• 编译器如何为变量分配内存地址
• 什么是记忆
• URL是如何工作的
• 在URL中编写HTTPS的意义
• 什么是DNS服务器
• 我在编译器中遇到的所有错误以及这些错误背后的原因是什么
• 你使用过的所有排序算法。你能为heapsort和quicksort编写代码吗？

然后她问我对这家公司了解多少，并给了我一个现实问题：给定航班的起止站，例如：德里到孟买、德里到勒克瑙、孟买到果阿、勒克瑙到马杜赖、马杜赖到果阿。问我喜欢什么样的数据结构，然后问我如何优化航班预订，比如说，找到一个从德里到果阿的航班，中间的停靠次数最少。

这一切都以著名的绳索谜题结束：

https://www.geeksforgeeks.org/puzzle-1-how-to-measure-45-minutes-using-two-identical-wires/

第三轮：

每小时一轮（45分钟–1小时）

这是导演做的最有趣的采访。这期间我玩得很开心。首先，面试官问我简历中提到的项目及其实际应用。

我的大多数项目都是在ML中进行的，所以他给了我一些业界在对数据进行验证时面临的现实问题。

然后我们就亚马逊推荐系统的工作进行了20分钟的讨论。然后，他让我推荐亚马逊基于ML/AI的几个新功能，这些功能可以改善他们的业务。

接下来，我们将讨论如何利用机器学习为游客提供良好的体验。

最后，他问我如何看待自己在未来几年的成长。

最后，他问我是否有什么问题要问他。

结果在几个小时后公布，我被选中了