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

书面MCQ 有20道选择题需要在30分钟内完成，大部分技术题来自 极客问答 ，一个血缘关系问题和一个简单的概率问题。

没有负面标记。

纸张编码轮 21名学生从第一轮MCQ中入围，在这轮MCQ中，我们被要求在1小时内写出3个问题的代码（仅函数）。 问题1。您将得到一个大小为MxN的矩阵，并且该矩阵中只有可能的值是 0–表示空位置 1–代表新鲜苹果 2–代表烂苹果 一个烂苹果在1个单位的时间内将所有新鲜苹果转化为与其相邻的烂苹果。给定一个输入矩阵，你必须计算所有新鲜苹果腐烂的时间。还要确定是否所有新鲜的苹果都能在有限的时间内腐烂。（20分）

输入 2 1 0 2 1 1 0 1 2 1 1 0 0 2 1

1个时间单位后，矩阵将转换为 2 2 0 2 2 2 0 2 2 2 1 0 0 2 2

2个时间单位后，矩阵将如下所示 2 2 0 2 2 2 0 2 2 2 2 0 0 2 2

因此，输出应为2个时间单位。（相邻单元的定义仅包括左、右、下、上单元，不包括对角单元）

问题2。 给你一棵二叉树，你需要找出二叉树任意两个叶节点之间的最大路径和 （最大路径和可以通过树的根，也可以不通过树的根）。在O（n）时间内完成（20分）

问题3。 你会得到一个未排序的整数数组，你需要找出其中是否存在多数元素 （多数元素是在大小为n的数组中出现n/2次以上的元素）。在O（n）时间内完成（10分） 这一轮的结果在深夜宣布。约有7或8名学生被要求进行面对面的面试。我是第一个被呼叫的人，F2F轮从晚上11点30分开始，到早上5点结束：-p我很幸运在凌晨1点15分左右有空

面2面圆1 问题1。我无法完成围绕问题1（烂苹果）编写的论文。她（面试官）让我纠正其中的问题。我在MxN的帮助下完成了这项工作，为访问的[]矩阵提供了额外的空间。她说在原地做。我通过将矩阵值修改为3、4等来实现。

问题2。 从单链表的最后一个元素中找出第五个 .首先我给出了一个解决方案，需要两次遍历。她说只需进行1次遍历。我使用两个指针，并在它们之间保持5个节点的距离。问题3。例如，如果输入字符串为“I am abc xyz”，则会给出一个字符串。输出应该是修改后的字符串“xyz abc am I”。这是在原地和时间内完成的。

第四季度。 你会得到一个由正整数和负整数组成的未排序数组。你需要找出O（n）时间内的最大和子数组。您需要找到起始索引和结束索引以及总和。

问题5。您将获得一个BST和两个键k1和k2。你需要 找出这两个键的最低共同祖先 反复地。我建议将路径存储在向量中，并找到根中键值与k1和根t k2路径的第一个不匹配。

面对面第二轮 问题1。以对烂苹果问题进行纸编码为例，提出一些算法，允许您更改烂苹果和新鲜苹果的位置，从而使生成的矩阵将最少数量的新鲜苹果转换为烂苹果。我提出了一种方法，首先计算腐烂苹果和新鲜苹果的数量，然后从（0，0）位置开始将所有新鲜苹果排列在子矩阵中，同样地，从（N-1，M-1）位置将所有腐烂苹果排列在子矩阵中。他对这种方法感到满意

问题2。如果给你一个有3部电梯的电梯系统，你必须建议一些算法，其中一个人在某个x层等待并按下向上或向下按钮的时间应该最少，电梯内的人也不应该等待太长时间才能到达目的层。

问题3。问了一些关于什么是语言符号的一般性问题。什么是语法和产生式规则。然后他让我检查某种语言中给定的代码在语法上是否正确。我们为您提供了该语言的有效标记集，以及符号表。

第四季度。您将收到一个存储字符或单词的文本文件。建议一些压缩文件的方法，这样总有一些空间压缩是可能的。

我建议使用trie树，因为所有前缀都将共享空间。他说，这种方法取决于输入是否有共同的前缀。 建议其他方式。然后我说我们可以使用哈夫曼编码，将最小的代码分配给文件中最频繁的单词，等等。他再次表示，这种方法也取决于你的输入是否有频繁出现的单词。

然后我建议，因为所有字符都可以用8位或1字节来表示。我们可以将上一个字符和下一个字符的异或存储在当前字符位置。通过这种方式，我将能够在编码文件中始终获得n/2大小的缩减。这个想法类似于 https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

他很满意，我的第二轮F2F比赛到此结束。他让我睡一觉，因为明天早上你将与我们的技术经理进行skype面试，然后是人力资源部。

第三轮（Skype） 问题1。他让我定义NP和NP难问题，然后是自动机和正则语言的定义。然后他问我是正则表达式。

问题2。他与我共享了一个google文档，并给了我一个类似abab*（a | b）的正则表达式和一个输入字符串s。我需要编写一个代码来检查给定的输入字符串是否可以从这个正则表达式生成。返回布尔值true或false。我在5分钟内完成了编码：-p

问题3。 给您一个N元树和一个值K。如果存在sum=K的根到叶路径，则需要返回true，否则返回false。我使用递归和O（n）时间完成了它。

他告诉我你将在一段时间内进行最后一轮人力资源培训。我知道我进展顺利，因为他似乎对我的回答很满意。

最后一轮人力资源 这一轮我已经等了好几个小时了 她（人力资源部）从一些一般性的问题开始，比如告诉我你自己以及你的人生目标。你的爱好是什么。我告诉她我热爱艺术和手工艺。她问我，如果明天是她的生日，我会为她做什么？-p她非常友好，很好交谈。我好像不是在和人力资源部说话。这更像是和朋友聊天。她问我喜欢Accolite的哪些方面，为什么我想加入这家公司等等。最后，我们讨论了Accolite的薪酬标准和工作文化。

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