有赞2019校招前端笔试（第三批）

给定一个有序整数数组以及一个整数  ，请问在该数组中查找比   大的最小元素的最优算法时间复杂度是多少？

有 8 个完全相同的硬币，其中只有一个硬币比其他 7 个重，给你一个没有刻度的天平，请问最少需要称多少次才能找到重的那个硬币？

数组的   元素是指比它右边所有元素都大的元素，请问查找数组中所有   元素的最优算法时间复杂度是多少？

给定以下哪些遍历结果可以重建出 BST？

请问下面这个函数的时间复杂度是多少（假设 ）？

function fn(n)
{
   if (n === 1)
     return 1
   else
     return fn(n-1) + fn(n-1)
}

关于下面这段 JavaScript 代码说法正确的是

var i = 0
(function fn() {
  console.log(i++)
  setTimeout(fn, 1000)
})()

假设实现了一个归并排序（merge sort），这个实现在最坏情况下需要 30 秒的时间来处理一个长度为 64 的输入。请问该实现在 6 分钟内可以处理的最大输入长度最接近多少？

在有 100 个元素的数组中找出其中最大的以及最小的元素所需的最少比较次数是多少次？

关于 HTTP 的说法正确的是

请使用一个固定长度的数组实现 3 个独立的栈，这三个栈都可以独立使用。要求除了这个数组之外只使用 O(1) 的空间，并且数组的空间利用率在各种情况下都应该尽可能的高。请详细说明如何实现  和   这两个函数。参数   用来表示要操作哪个栈，三个栈编号0，1，2。

function push&ltT> (arr: T[], stackId: number, elem: T): boolean
入栈，成功返回 true，失败返回 false

function pop&ltT> (arr: T[], stackId: number): T | null
出栈，成功返回栈顶元素，栈空则返回 null

在一座荒岛上有三种变色龙，分别是 12 只棕色，15 只灰色以及 16 只黑色。当两只不同颜色的变色龙相遇时他们会同时变色为另外一种颜色，例如当 1 只棕色和 1 只灰色的变色龙相遇时他们会同时变成黑色的。请问这个荒岛上这些变色龙可能全部变成同一种颜色吗？请详细说明你的分析过程。