Traveloka SDE3面试体验详细分享（校园）

第一轮在线技术目标：本轮有50个有关C ++及其输出的问题。它是在Hackerrank上进行的。分配的时间限制为75分钟。

第一轮结束后, 约有50名学生获得了第二轮资格。

第2轮在线编码–有2个问题需要解决。

问题1：ñ给定的节点。如果两个节点相互连接, GCD(node1, node2)大于给定的阈值(T)。问题在于查找给定的两个节点之间是否存在用于Q查询的任何路径。创建邻接矩阵后应用修改的BFS通过了大多数测试用例。

问题2。修改后的硬币找零问题.

曾经有ñ必须转换成的硬币中号硬币。如果你在X硬币, 那么你可以去(X + Y)通过增加ÿ硬币在哪里ÿ是一个主要方面ofX。加Y构成一个单 步骤。问题是找到转换所需的最少步骤数。问题可以通过以下方法解决动态编程。

8在编码回合之后选择了学生进行访谈。

第一轮访谈：采访也在Skype上在线进行。采访从定期介绍开始。然后我被问到我的首选语言以及我在其中所做的项目。然后提出了一些编码问题。

问题1：在二叉树中找到最大路径总和。该路径可以在树中的任何节点处开始和结束。我与他讨论了我的方法, 他对此保持沉默。他告诉我为此编写一个伪代码。后来他发现了一些错误, 并告诉我重新检查。一段时间后, 我给了他O(n)的方法。他对此感到满意。

问题2：在二叉树中找到LCA。我被困在BST中而不是二叉树中找到LCA。因此, 首先我给了他一个在BST中查找LCA的O(高度)解决方案。但是他期待二叉树的O(n)解决方案。因此, 我给他提供了另一种解决方案, 以使用O(n)中的路径遍历来查找LCA。

问题3：对存储库有N次提交。对于特定的提交x, 已知存储库中没有错误, 并且在提交Y之后, 存储库中存在一些错误。问题是要找到导致错误的提交。

我针对复杂度为O(log(n))的问题编写了二进制搜索算法。试运行后, 他确信该解决方案可以解决该问题。

该轮持续了1小时 。下一轮进一步选择了4名学生。

第二轮访谈本轮也是从介绍开始的。面试官问我上一轮的问题以及我的解决方法。 

问题一：我获得了一个队列数据结构, 该数据结构支持enqueue()和dequeue()之类的标准操作。我必须仅使用Queue实例和实例上允许的队列操作来实现Stack数据结构。

解决方案：lsbin使用queue实现stack

问题2：实现LRU缓存。我正在使用哈希映射和链表O(n)实现它。他期望O(1)进行页面替换。然后, 在我的方法中使用了使用双向链接列表的Queue。

解：lsbin LRU缓存实现

然后他问了我另一个解决问题的问题。提出了一些内存管理概念, 与项目相关的问题和DBMS概念。他想知道在我的项目中选择其他技术的原因。

之后, 他问我是否有任何问题。我问他一些问题。他用解释回答了我的每个问题。

这回合持续了大约1小时15分钟。面试官有兴趣了解我解决DS问题的方法, 而不是代码。

整个过程持续了两天。我被选为SLI + FTE。最后提供了4名学生。