雅高乐面试体验|第四套（校园）

第一轮（书面） 大约140名学生参加了离线测试。

有20个MCQ需要在30分钟内完成，问题来自操作系统、数据库管理系统和数据结构。 在那一轮编码之后（纸质编码），给出了3个问题，我们必须尝试任何2（1小时）

1. 编写自己的sqrt（）函数。 如果函数是一个完美的平方，那么它应该返回平方根，否则返回楼层（sqrt（x）） 2. 给定一个包含正整数和负整数的数组。你必须找到丢失的最小正数。 你的代码应该在O（n）时间和O（1）空间中运行。 3. 给定一个字符串数组，找出这些字符串是否可以链接成一个圆。 如果x的最后一个字符与y的第一个字符相同，则可以将字符串x放在另一个字符串y之前。

第一轮面试后，有19人入围面试名单。

第二轮（技术）（1:30小时） 1.跟我说说你自己。与此同时，他（面试官）查看了我的简历，询问了我的项目。 我做了3个项目，所以他开始讨论CUDA和并行编程，以及如何在图像上实现边缘检测，以及获得了多少增益因子。 其次，我做了一个关于在线投票系统的项目，所以他要求我绘制E-R图、模式以及它们之间的关系和它们的功能。大约（25-30）分钟的讨论。

2. 给定一个BST，你必须找到其中第k个最小的元素 在O（n）时间和O（1）空间中。

3.假设您有一个服务器，其中有多个请求在时间t1、t2…现在假设用户在任何特定时间t点击服务器，那么服务器应该返回最后一个请求。你必须为同样的目的设计数据结构。 我建议我们可以使用将返回最后一个请求的堆栈，然后他让我对最后10个请求执行此操作，然后我建议使用存储请求号和时间戳的结构数组。现在，我们可以在任何时候向后移动10个元素，但他说，假设用户频繁点击，那么每次我都必须一次又一次地来回移动，所以时间复杂度会非常高。我同意并建议了另一种类似于LRU实现的解决方案，以便能够更快地处理频繁出现的请求。然后他修改了一个问题，用户需要最后1分钟的请求，他给出了一个提示，有必要存储所有请求吗？我们不能只存储每1分钟的请求，然后突然它点击我，我建议使用deque 60秒，现在假设请求在第61秒到达，那么我们可以只在后面添加一个，从前面删除一个，保持60秒的窗口。他很满意，但他不想删除，所以我告诉他使用循环deque，这样我们就可以替换以前的元素。他现在对这种方法完全满意。（约35分钟讨论）

4. 给出一个包含30天股票价格的数组。一个人有1股股票，他可以多次买卖，你必须找到可以赚取的最大利润。 我提出了一种方法，创建两个辅助数组MIN from left和MAX from right，如果MAX[I]和MIN[I]之间的差异大于maxDiff，则同时遍历这两个数组，然后更新maxDiff并存储当前索引，如果index+1不等于当前迭代索引，则添加到sum，最后返回sum。他在我的代码上尝试了一些测试用例，发现在某些情况下给出了错误的答案，然后他问我对动态编程的掌握如何，我告诉我只知道标准的，没有其他经验，然后他说这个问题是关于DP的，但他很高兴看到我的方法。（大约20-25分钟）

第三轮（技术）（1:30小时） 1.她（面试官）问我是否在笔试中尝试了第三个问题，我说我只尝试了第一个和第二个，然后她给了我试卷，并告诉我实施第三个问题。 我建议使用两个结构数组（第一个字符和最后一个字符），其中包含布尔值来标记字符串中是否存在字符及其索引。现在比较两个数组，看看这两个数组是否具有相同的布尔值以及所有第一个和最后一个字符的不同索引。如果是这样，那么字符串可以形成一条链，否则就不能。她怀疑我的解决方案，所以她发现了一个测试用例，我的代码给出了错误的答案，所以她告诉我寻找另一个解决方案，我想出了另一种方法，告诉她我们可以从第一个和最后一个字符生成一个有向图，然后在DFS中遍历它，现在假设再次访问访问的节点，并且访问的节点总数与访问的节点总数相同，那么我们可以说字符串将形成一个链，现在她对这种方法感到满意，并要求我编写代码，现在由于我的图很弱，我感到震惊，所以她说只编写伪代码。

2. 给定一个BST，你必须找到其中第k个最大的元素 在O（n）时间和O（1）空间中。 我建议声明一个静态变量count，它将在按顺序访问节点时增加count，如果count变为k，我将打印该节点的数据并返回。然后她问我静态是如何工作的，以及全局和静态之间的区别。

三。 比如说诺基亚手机的移动键盘和一本包含所有有意义单词的字典， 假设现在用户键入一些数字（输入），那么程序必须建议字典中所有有意义的单词。在实现这一点之前，她要求我使用数据结构来高效地存储字典，然后如何使用此数据结构来编写代码。 首先，我建议将字典存储在二维数组中，并按字典顺序对其进行排序，现在假设用户键入一个数字，并在数组中搜索以该字符开头的字符串。她说要降低复杂性，因为字典可能包含1000个单词，然后我建议使用trie数据结构来存储和搜索字符串，她现在很满意，并要求我解释这个概念。 4 给定图的前序和后序，如何构造图。 当我听到这个问题时，我被困了2分钟，但后来我说，就图表而言，我不知道它，但一个独特的树不能用前序和后序来构建，所以作为图表，为了有序是必要的，她很高兴，并同意了答案。

第四轮（技术）（2:30小时） 1.假设给出了一个链表，并且有一个循环，你必须在O（n）时间内找到孤立节点。孤立节点是循环外部的节点。

2.设计BRTS交通信号系统，确保两辆车不发生碰撞。请注意，BRTS巴士将沿着BRTS交通灯B1、B2、B3、B4的四个方向行驶，常规交通将只沿着常规交通灯R1、R2、R3、R4行驶。在输入中，只给出了所有转角情况下的最大循环时间（过程重复后的时间）检查（交通灯只有两种状态（红色和绿色））。在最大循环时间内，你必须告诉任何一种可能的交通灯组合。（约1小时讨论）。

3. 假设给出了一个链表，但我们不知道节点的数量，那么您必须从最后一个节点找到第k个节点，而不计算节点。 4.给定一个由n个整数组成的数组，例如一些元素在0到n-1的范围内，而一些超出范围的元素可能是负数。您必须重新排列数组，以便范围内的所有元素都显示在它们的索引上，其余元素以排序方式显示不存在的索引。这应该在O（n）时间和O（1）空间中完成。 假设n=6，456-3输出=3,6,2,3,4,5

5.你怎么能 使用队列实现堆栈。 6.如何借助队列对元素进行排序。 我提出了一个O（n）时间解决方案和O（n）额外空间。他要求在O（1）空间做，所以我建议德克，他似乎很满意。

直到这一轮，只有4人被选中（我是其中之一）

第五轮（酒吧提升者）（30分钟）

1. 查找从索引0开始的字符串中最长回文的长度。 2. 查找字符串B中是否存在字符串a。 3.查找字符串中最长前缀的长度

在这之后，两人最终被选中，不幸的是，我不在其中，因为他们可能认为我压力不大。最后，我建议你的方法和概念必须强大，因为它们总是给出一些不同的问题。

如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。