亚马逊面试题和面试经验分享|S70（校园实习）

在线编码问题：

1. 给定浮点数7.64, 可使用任何内置函数/库将其转换为字符串而无需使用.

   for eg:
   input
   float no.: 7.64
   output
   string: 7.64

2. 给定二叉树的中序和前序遍历, 输出它的后序遍历.

   for eg:
   input:
   Inorder: 7, 8, 4, 1, 6, 2, 5
   Preorder: 1, 4, 7, 8, 2, 6, 4
   output:
   Postorder: 8, 7, 4, 6, 5, 2, 1

第一轮编程：

给定一个字符串, 找到最长的子字符串的长度, 该子字符串的任何字符均不重复?

for eg:
i/p string:
abcabcbb
length of longest substring with no repeating charcters: 3 (abc)

给定一个带有右指针的链接列表, 并且列表的每个元素都有一个向下链接, 其中包含另一个带有向下指针的链接列表, 如下所示：

5 -> 7 -> 9 -> 18
 |    |    |    |
10    6    14   20
 |    |    |    |
11    8    19   22
 |    |         |
12    13        24
 |    
15

每个右下方列表都进行了排序。

编写一个函数flatten(), 将该链接列表展平为单个链接列表, 所有元素的排序顺序为：

5-> 6-> 7-> 8-> 9-> 10-> 11-> 12-> 13-> 14-> 15-> 18-> 19-> 20-> 22-> 24

PI回合1：

面试首先是对实习项目和我的简历中提到的其他项目的讨论和质疑。

在讨论了项目之后, 面试官问了一个关于字符串的问题, 这个问题是：

1. 给出了一个长度为n和整数m的字符串, 给出了一个算法。将弦逆时针旋转m。要求我提供输入m的所有检查条件。
   然后, 面试官要求我为同一代码编写严格的准则, 即代码中不应有任何错误；)。
2. 之后, 他问我关于堆, 最小和最大堆, 堆中的插入和删除。他要求我证明在堆中插入n个元素的时间复杂性。
   他至少询问了堆数据结构以及使用堆实现的其他数据结构的用法。

PI回合2：

1. 黑白抽象和接口类有什么区别？
2. 编写一个程序来创建单线程并打印” Hello World”, 并说明createThread函数的所有参数？
3. 什么是死锁？死锁发生的必要条件是什么？
4. 什么是高速缓冲存储器及其实现方式？
5. 解释LRU, FIFO和其他页面替换算法？
6. 编写代码以实现LRU缓存, 然后实现完整的缓存？