D.E.Shaw实习面试经历（2018-2019年校园）

第一轮：

这是一轮编码。在线平台（Hackerrank）上有两个编码问题。测试持续时间为50分钟。

第一个问题

如果给你一个带有开始和结束标记的HTML标记字符串，我们必须找到最大的标记总数，我们将相同的标记组合在一起，并对它们进行计数。在这里，标签被定义为一个开始和一个结束标签，其中开始和结束标签的顺序无关。开始标记定义为写入角括号内的文本（ ），结束标记定义为写入角括号内的文本，后跟（…>）

样本输入 ：

样品 输出 : 3

说明：

总共3个头部标签和2个身体标签，所以答案是3，即最多2，3。

这里需要考虑的一点是，标签要么是先开后关（不一定连续），要么是先关后开。

第二个问题

在前n个自然数的第i个置换中找到第k个索引处的数。输入按n，i，k的顺序给出。

示例输入： 3 2 2

样本输出： 3.

共有22名学生被选中参加下一轮面试。

第二轮：

这是一轮技术性的讨论，持续了大约1小时45分钟，他们问你为什么在线编码讨论中的第二个问题不起作用。我告诉他们我的代码中有一个小缺陷。

第二轮的进一步问题是：

1. 你会得到一个n*m的网格，其中一些单元格是空的，有些着火了，有些有墙。有一个人站在一个特定的牢房上，在最右边的牢房底部有一个出口。火在网格中每秒向四个方向传播一次，如果传播方向上的单元是墙，否则它会在该单元处停止。这个人每秒可以在四个方向的空旷空间中旅行。你必须找到那个人是否能安全逃离电网。
2. 使双链接列表的内存效率更高。基本上，您必须将每个节点的指针数量从2个减少到1个，并且仍然能够在两个方向上进行遍历。
3. 解释多态性（运行时和编译时）、重载（函数和运算符）。接着讨论了虚拟函数、VPTR和VTABLE。
4. 指针和引用之间的差异。为什么在所有传统的数据结构（如链表和树）中都使用指针，而不是引用？
5. 给定不平衡的括号字符串。必须删除最小括号数才能使其平衡，并在删除最小括号数后打印所有平衡括号。

第三轮：

这也是技术回合。持续约1.5小时。

本轮提问包括：

1. N/4多数元素问题。他们给了我一个真实的情况，解决方案归结起来就是找到给定数组中出现超过N/4次的所有元素。
2. 散列，冲突，冲突解决技术，在单独链接的情况下快速散列。
3. 网页浏览器设计问题。您将设计web浏览器，并希望实现返回和转发选项卡的功能。你将如何实现这一点？
4. 尽量减少现金流问题。
5. C++的一些理论概念，如悬空指针、空指针、内存错误（不要混淆数组外的异常），在分割错误中抛出什么核心？过程和程序之间有什么区别，程序是如何变成过程的？。
6. 数据库管理系统的基本概念，如键、规范化等。
7. 一些简单的SQL查询问题，包括连接表、差异、不同查询的交叉等概念。

第四轮 :

当时是人力资源部，她问了我这样的问题：

1. 跟我说说你自己。
2. 第一年结束时你的平均绩点是多少？
3. 你多久看一次报纸？
4. 你对D.E.肖了解多少？
5. 你对自己在GK的1-5分上的评分是多少？
6. 她给了我一个谜题。它的正式定义是“给你8个外观相同的球。其中一个球比其余7个球重（所有其他球的重量完全相同）。你有一个简单的机械天平，你只能使用2次。找到更重的球”。
7. 你擅长数字吗？她给了我一个简单的问题，就是找到133^9的最后一位数字。
8. 如果有机会在海得拉巴实习，你是否愿意转到海得拉巴的办公室？

结果：选中