Directi面试经验|第25集（平台工程师校外）

应用方法： 我通过员工推荐向Directi提出了申请。

在线编码（每轮90分钟）

问题1 ：轻松，临时

陈述

如果给你一个数字串，你必须用这些没有前导零的数字找到可能的最小数字。

实例 如果输入为330101，则答案为100133

限制

字符串长度<=10^5

问题2：

陈述

给你两个长度相同的字符串，比如A和B。你可以用A[i]和B[i]交换1和N之间的所有i，包括1和N。不能在A或B中交换两个字符。此外，只能将A中的一个字符与B中相同索引的字符交换，而不能与其他字符交换。您可以执行此操作零次或多次。

您希望通过操作修改字符串，使字符串中的唯一字符数很小。事实上，如果n（A）是A中唯一字符的数量，n（B）是B中唯一字符的数量；您希望执行的操作使max（n（A），n（B））尽可能小。

所有操作完成后，打印max（n（A），n（B））的值。

实例

如果输入是 阿巴巴

那么输出应该是一，因为我们可以交换并生成这对字符串 （aaaaa，bbbbb）

约束条件

1 <= T <= 100
1 <= length(A) <= 16
length(B) = length(A)

问题3：

改进的背包DP问题

第二轮：算法轮（Skype，45-50分钟）

一个方形网格（NxN）将提供给您；网格上的每个位置要么是一块砖（B），要么是它的空（z）。

砖的总数正好等于在网格中建造“墙”所需的数量。参见示例以获得更清晰的理解。

也就是说，最后，所有砖块（B）都应放置在边界位置。

将砖块从 位置移动到 | i-x |+|j-y |使用燃料。

网格中的每一块砖都可以以相同的概率移动到边界上的任何位置。问题是什么 期望值 这样做需要多少燃料？每块砖最多只能移动一次。

实例 最后（移动所有砖块后），网格应该如下所示：

 B B B B
 B _ _ B
 B _ _ B
 B B B B

暗示 你会得到所有砖块的初始位置，你知道最终位置。 因为所有的砖块都是相同的，所以可以在任何边界位置放置任何砖块。

假设存在“b”边界位置=b砖块 所以你需要把旧的位置映射到新的位置。

在蛮力法中，应该是O（b！）尝试所有的招牌。 但是，如果你能更深入地了解概率是如何累积的，而不是如何安排的，你可以做得更好。

预期：O（n） 第三轮：算法轮（Skype，45-50分钟）

第四轮：技术知识轮（Skype，45分钟）

• 谈谈你的一个项目 深入。 准备好回答任何关于它的问题。你也可以谈谈你的实习项目。我谈到了我的GSoC项目。
• 准备好回答 简历上的任何内容。 我被要求谈谈简历上列出的另一个项目。
• 您将如何实施该计划 差别 git的功能？准备好跟进问题和现场的进一步优化。
• 我得到了一个示例代码，其中有一个add_balance（）和一个subtract_balance（）函数，如果有两个线程访问它，我会被要求解释这个问题。你将如何纠正它？（使用互斥锁）
  • 后续问题：互斥锁操作是如何（你认为）在操作系统中等待和信号实现的？
• 数据库索引
  • 什么是索引？它们有什么用处？
  • 如果你必须建立一个索引，你会使用什么样的数据结构？
  • 为什么是Btree而不是正常的BST（当Btree的比较数量实际上更大时）？