Directi面试|第6组（校园实习）

最近，Directi访问了我们的校园进行实习生选拔。在codechef上主持了1轮在线编码，2轮Algo面试和1轮技术面试。>

在线编码回合： 有两个问题。问题1得2分，而问题2得1分。

• 问题1。 有一个压缩字符串，例如“ab2c3”，该字符串包含小写字符和数字。我们可以按如下方式解压给定的字符串：每当我们在字符串中得到一个数字“n”，该数字之前的字符串部分将重复“n”次。在上面的例子中，我们得到了一个2，所以字符串将变成“ababc3”，现在我们得到了一个3，所以最后一个字符串将是“ababc”。 给定一个压缩字符串和一个数字k，必须输出k ^th 未压缩字符串中的字符。1<=字符串长度<=1500 1<=n<=1000 1<=k<2 ³¹ 例子：

  input: ab2c3 10 
  output: c

• 问题2。 有一个字符串，其字符只能是“a”、“b”或“u”（字符串中只能有一个“u”）。在每个步骤中，我们都可以按如下方式修改字符串： 1.“u”可以与其相邻字符交换，例如，“a_ba”可以更改为“_aba”或“ab_a”。 2.如果两个字符不同，则与‘‘’相邻的两个字符（都在‘‘’的同一侧）可以与‘‘’一起反转，例如，“aa_-ba”可以改为“aaab_”，但不能改为“_-aaba”，因为两个字符都是“a”。

  如果给您两个字符串，初始状态和最终状态（长度相同），您必须输出将初始状态的字符串更改为最终状态的字符串所需的最小步骤数。

  例子：

  input: a_b ab_ 
  output: 1 
  input: abaa_a b_aaaa 
  output: 4 
  

  提示： 使用广度优先搜索

  比赛结束后，他们将12名学生列入下一轮比赛的候选名单。

第二轮（电话采访）：

• 问题1。 假设给你一个长度为n的字符串和一组对（i，j，0<=i th 还有j ^th 字符串中的字符任意次数。您必须输出字典中最小的字符串，该字符串可以通过对输入字符串进行任意数量的交换而产生。 例子：

  input: zcxfbe  0, 1    0, 2    3, 5
  output: cxzebf

  提示： 尝试将问题建模为图形问题。

• 问题2。 假设桌子上有两堆盘子。一个有“m”红色盘子，另一个有“n”黑色盘子。在他/她的机会中，玩家可以选择任意数量的红牌或任意数量的黑牌，或同等数量的红牌和黑牌。如果一个玩家不能在他/她的机会内采取行动，他/她就会输。你在和你的朋友玩这个游戏。考虑到游戏开始时两名玩家都发挥了最佳状态，如果你输了，输出“L”，如果你赢了，输出“W”。 例子：

  input: m = 1, n = 2
  output: L
  input: m = 2, n = 2
  output: W

  在这一轮面试之后，他们挑选了4人参加下一轮面试。

第三轮（面对面）：

• 问题1。 假设有n棵树（字面上的树，而不是计算机科学的树，假设它们没有任何分支，更像是一根直杆），每棵树都有一定的高度。我们想要x长度的木头。我们有一个樵夫，我们将用它来砍掉离地面相同高度的所有树木，如果“h”大于任何一棵树的高度，就意味着这棵树没有被砍掉。考虑到所有树木的高度和所需木材的长度“x”，从你要砍伐所有树木的地方输出距离地面的高度“h”。
• 问题2。 你有一个无向加权图，给定输入“x”和“y”，这是图的任意两个顶点，你必须输出从x到y的任何最短路径中的所有边。 请注意，从x到y可以有多条最短路径。我们必须输出这些最短路径中的所有边。

  下一轮他们只选了一名学生。

第四轮（技术轮，电话）： 在这一轮中，他问了我一些小问题，包括：

1. 关于我的任何自我项目。
2. BST和哈希的优缺点。与哈希等中的冲突相关的问题。
3. 一个关于数据库的问题，他让我提出一个问题。
4. 在任何给定的时间内，计算时钟的时针和分针之间的角度。
5. 假设我们有一个巨大的CSV文件，其中包含IP地址范围和相应的国家代码，给定任何IP地址，我们将如何找到它所属的国家。
6. BST和Trys之间的区别。
7. 他从网络课程和操作系统课程中提出了一些问题。
8. 你有一个巨大的链表，你将如何检测链表中的任何循环。

   他又问了几个我不记得的小问题，然后面试结束了。 我在通过所有这些回合后被选中。

提示：

1. 他们主要关注字符串和图形，做好准备。
2. 在纸上或谷歌文档上练习你的代码，你将不会得到任何用于编码的编辑器。
3. 在所有主题上保持概念清晰，他们可以询问您任何数据结构或算法的任何细节。

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