高盛面试经验|第31组（实习）

• 有36匹马。我们必须找出最快的三匹马。在一场比赛中，最多可以跑6匹马。在不使用秒表的情况下，最少需要多少场比赛才能获得结果？

  我们可以先骑6-6匹马进行6场比赛，在每场比赛中获得最快的马。 A1、A2、A3、A4、A5、A6 B1、B2、B3、B4、B5、B6 C1，C2，C3，C4，C5，C6 D1、D2、D3、D4、D5、D6 E1，E2，E3，E4，E5，E6 F1，F2，F3，F4，F5，F6 这里是A1>A2>A3>A4>A5>A6，其他人也是这样。 现在让我们在每场比赛中选最快的马，然后在他们之间进行一场比赛。让结果为A1>B1>C1>D1>E1>F1。我们有最快的马（A1）。 现在我们需要找到第二和第三快的马。第二个位置的可用马是B1和A2，第三个位置的可用马是A3、B2和C1。其他的马不可能都排在前三名。让我们在这些马之间进行一场比赛，排名前二的分别是第二和第三快的马。 所以总共需要8场比赛。

• 哪一个 数据结构 最适合 求连续数字流的中位数 （在线算法）

  堆 其思想是使用max heap和min heap分别存储左半部分低于当前中值和右半部分高于当前中值的元素。堆中的元素数量相差最大，每输入一个元素。当两个堆包含相同数量的元素时，我们选择平均值作为中位数，否则从包含更多元素的堆中选择中位数。 有关更多详细信息，请参阅 在这里 .

• 一个聚会上有N个人，他们可能知道也可能不知道对方的名字。 群中有一位名人，名人不认识任何人，所有人都认识这位名人。我们只能问“A知道B吗？”这样的问题。 ( 名人问题 ) 寻找名人的最佳解决方案最糟糕的时间复杂度是什么？

  O（n） 假设我们问“A知道B吗？”。如果A认识B，A就不能成为名人。如果A不认识B，B就不能成为名人。所以在每个问题之后，我们可以拒绝一个人。因此，我们最多需要问n个问题，才能正确判断名人。 有关更多详细信息，请参阅 在这里 .

• 给定两个字符串A和B，返回一个字符串，其中A和B中的字符交替填充，顺序与原始字符串中以A中的字符开头的顺序相同，例如A=“Hello”，B=“Bye”，则输出应为“HBeylelo”。（|A |，|B |<25000）

  创建一个新的空字符串。运行一个循环min（|a |，|B |）时间，然后将a的第i个字符和B的第i个字符附加到答案字符串。最后，将字符串A或B的剩余部分附加到应答字符串。

• 给定一个数N，找出将N写成两个或多个连续正整数之和的方法的数量，如果N为7，则只有一种方法，即3+4。（0

  假设我们从1开始求和，即1+2+3+…。。 总和小于或等于N的最大数：楼层（X） 哪里 X*（X+1）/2=N 所以N作为一个正的连续整数之和，最多由X个数组成。 在这里，我们可以检查2和X之间的每个可能性k（假设），为了检查，我们可以使用A.P.的概念，因为求和序列是一个A.P，其和为N。 我们知道A.P.n:k中的术语数量 应付款总额，S:N 共同点，d:1 我们可以很容易地用公式计算出第一项a：

          S=n/2*(2a + (n-1)d)

  如果a是一个整数，那么N可以表示为k个连续整数的和，否则，这是不可能的。当a是整数时，计算出现的次数，这就是我们的答案。 时间复杂性： 循环运行X时间是O（sqrt（N）），在每次迭代中，我们取O（1）时间。所以总体时间复杂度是 O（sqrt（N）） .

附言：笔试还包括与以下方面有关的问题： 毫升 和 定量 .

如果你喜欢Geeksforgek并想投稿，你也可以使用contribute写一篇文章。极客。组织或邮寄你的文章到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。