亚马逊面试题分享|S54（实习）

大家好。这是我在亚马逊实习的采访经验。
职位：2个月实习生
回合数：1在线+ 2 PI(2 F2F)
第一回合：(90分钟)
20个MCQ和2个编码问题
基于C输出, 概率, 基础数学, OOPS, 算法分析和操作系统, 共有20个MCQ。
问题1：
给定一个链表, 编写一个函数来反转每k个节点
(其中k是该函数的输入)。
例子：
输入：1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> NULL且k = 3
输出：3-> 2-> 1-> 6-> 5-> 4-> 8-> 7-> NULL。
输入：1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> NULL且k = 5
输出：5-> 4-> 3-> 2-> 1-> 8-> 7-> 6-> NULL。
问题2：
给定一个包含以任意数量的空格分隔的单词的字符串。编写一个返回由每个单词的第一个字母组成的字符串的函数。
(请注意：给定字符串的开头, 给定字符串的末尾或字符串中的单词之间可以有任意数量的空格。)
例子：
输入："这是一个测试案例"
输出：tiatc
(给出了两个问题的功能原型和主要内容。尽管许多解决方案通过了最初的测试用例, 但由于不满足边界情况而被拒绝。)
第二回合：(面对面)(1小时20分钟)
问题1：
给定两个链接列表表示的两个数字, 编写一个返回和列表的函数。
总和列表是两个输入数字相加的链表表示。
例子

Input: First List: 5-> 6-> 3//represents number 563 Second List: 8-> 4-> 2 // represents number 842 Output Resultant list: 1-> 4-> 0-> 5//represents number 1405

我颠倒了链表, 并简单地将相应的节点与进位一起添加。然后, 他让我解决了这个问题, 而又不撤掉这份清单。然后, 我迭代地解决了该问题, 而无需反转列表。
然后, 面试官要求我针对相同的问题编写一个递归代码。
之后, 他要求我修改代码, 以便每个位置的进位值通过值传递, 而不是使用指针(我在代码中使用过指针)。
问题2：迭代和递归代码反向链接列表(要注意一些特殊情况：当列表没有节点或包含单个节点时)
问题3：
编写函数以检查一棵二叉树是否为另一棵二叉树的子树
(检查所有极端情况)。
我以O(n ^ 2)时间复杂度解决了它。他没有要求我优化我的代码。
问题4：你将使用哪种数据结构来记录股市记录？
我请他澄清问题陈述。
然后他问我：假设你必须在不同时期内维持不同公司的股票价值, 并在给定的时间内返回特定公司的最低股票价值。
我回答了段树(可能正确的答案是队列数据结构)。
但是, 面试官对分类树进行了提问。
他要求我为
a)创建一个细分树
b)在段树中执行范围最小查询
c)更新段树
他要求我分析构建分段树和在分段树中执行范围最小查询的时间复杂度。
然后他问我：如果要在过去6个月中保持公司的股票价值, 那么你每天必须通过删除股票价值并插入新的股票价值来更新细分树。你会怎么做？
在这里我陷入困境, 无法在比O(n)的时间更好的情况下执行更新(但是使用队列可以在O(1)的时间执行)。
他终于问我是否有任何问题。
第三回合：(面对面)(20分钟)
在这一轮中, 我只问了一个技术问题。
a)他让我说说自己和我的技术成就。
b)如何在文件中存储二叉树然后回读。(不一定是BST)
首先, 我回答说我将存储树的层级遍历。
然后, 他问我如何在各个级别上维护节点(我无法回答)。因此, 我改变了方法, 并告诉我：我将按顺序存储和顺序遍历该树, 以便从中轻松检索原始树。
但是后来他告诉我优化我的方法(因为这种方法需要两倍的原始空间才能将数据存储在节点中)。我无法进一步优化我的方法(但是更好的方法是使用括号。

A /\ BC /\ DE

如果这是二叉树, 则可以将其存储为(A(B(D), (E)), (C))在文件中。)
c)然后进行了10分钟的讨论, 讨论我的项目, 遇到的问题以及如何解决它们。
d)最后他问我是否有任何问题。
我问了有关亚马逊的实习项目及其中DBMS和NETWORKING的使用情况。
他开始详细介绍亚马逊的整个工作流程以及他的工作经验……..我很难理解其中的大多数。他还告诉我对JAVA有很好的了解, 因为在项目的某些阶段将需要它。
【亚马逊面试题分享|S54（实习）】终于我被选中了。