Adobe访谈|第6集（MTS-1校园）-yiteyi-C++库

我要感谢整个Geeksforgeks团队，他们的贡献对我准备面试和进入Adobe有很大帮助。

null

轮数： 1个apti+1个书面+4个PI

能力倾向轮： 1小时

分析能力15题，数据解释和定量能力30题

书面传阅： 2小时

关于算法和操作系统的10个问题，关于C/C++代码段输出的10个问题

圆周率-

第一轮：45分钟

1. 使用2个堆栈实现队列（推送和弹出的平均时间复杂度O（1）

2.关于请求寻呼的讨论。然后，面试官让我使用面向对象的方法详细介绍请求分页的实现，从页面表到交换磁盘I/O，再到页面替换策略。

第二轮：45分钟

1.这一轮从一个谜题开始：有两个桶——一个装100升水，另一个装50升牛奶。从第一个桶中取出一匙水，加入第二个桶中，搅拌混合物，然后从第二个桶中取出一匙水，加入第一个桶中。比较第一桶中牛奶的最终体积和第二桶中水的最终体积。

2.缺陷球拼图：在7个球中找到缺陷球，使用最少数量的测量。

3.系统发送多个查询以查找两个给定数字之间的所有素数。在不到O（p）的时间内为每个查询提供服务（p是素数的总数）

解决方案：首先对埃拉托斯坦进行筛分，并维护素数列表。对于传入的查询，使用二进制搜索查找给定数字之间的第一个和最后一个素数。

4、河内问题塔的改造：考虑3塔A（源）、B（辅助）、C（目的地）和N盘。原始问题的所有常规约束均成立，但增加了一个新约束：不能将光盘从a直接移动到C或从C移动到a，必须在两者之间使用B。

解决方案：对于N盘和塔A、B、C分别作为源、辅和目的地，考虑以下功能：

Move(n discs, A,B,C)
{

    If(n==1) print(nth disc, A->B->C);

    Else
    {

        Move(n-1 discs, A,B,C);

        print(nth disc, A->B);

        Move(n-1 discs, C,B,A);

        print(nth disc, B->C);

        Move(n-1 discs, A,B,C);

    }
}

这将需要O（3^n）的时间，而不是O（2^n）的时间，因为在河内问题的正常塔。

面试官似乎对这个解决方案印象深刻。

第三轮：45分钟

1.机器人可以向前移动1步或2步。没有找到达到第n步的可能方法（容易的DP问题）。

2.关于调度概念、如何为SJF调度预测cpu突发长度、指数平均等的问题。

3.面试官让我在用户空间中实现自己的计时器服务。不允许使用系统计时器倒计时，只允许读取当前系统时间。

解决方案：创建一个高优先级的助手进程P，它将对时间流有一些概念（因为我们不能使用硬件计时器），因此将充当任何需要计时器服务的进程的沙钟。

P将进行以下操作：

t1=getSystemTime（）

进行虚拟操作（应该花费更少的时间）

t2=getSystemTime（）

（t2-t1）将是P的时间单位。每当任何进程需要倒计时t时，它将与P通信，并请求P在时间t之后发送信号。P将t除以其时间单位，执行其操作t/（t2-t1）次，然后通知请求进程时间段已过。