亚马逊面试题分享|S20 _数据结构

最近接受了亚马逊海得拉巴SDE1的采访。
书面
1)
给定一个BST, 以及一个节点的左右指针, 它具有向前和向后的指针, 使用这些额外的指针将树转换为双链表。
2)A = {5, 3, 8, 9, 16}
经过一轮迭代后, A = {3-5, 8-3, 9-8, 16-9} = {-2, 5, 1, 7}
第二次迭代后, A = {5-(-2), 1-5, 7-1}和= 7 +(-4)+ 6 = 9
给定一个数组, n次迭代后返回总和
3)编写一个将字符串AAACCCBBD压缩为A3C3B2D的函数
等功能从压缩生成。
第一f2f)
1)
检查给定的BT是BST
2)每天给出股票的成本, 以数组的形式给出, 找到当日通过买卖可以赚取的最大利润
3)在矩阵A [m] [n]中, 对每一行进行排序, 对每一列进行排序, 编写一个函数来检查此矩阵中是否存在数字。
4)给定一个字符串, 找到最长的仅包含唯一字符的子序列。
第二个-f2f)
1)
将BT转换为SUM BT
(每个节点的值=左右节点的总和)
2)"我每天收到数千封电子邮件",
在每封电子邮件中找到所有字谜, 并在每封电子邮件中打印所有字谜的计数。
【亚马逊面试题分享|S20】我的解决方案是使用Trie和哈希函数来增加Trie中每个节点的计数器。
哈希函数将以某种排序的方式返回给定的单词, 他要求我编写繁琐但给出粗略草稿的代码。
初始设置成本会很高, 但是通过将所有计数器都设为零, 可以将相同的trie用于任何电子邮件。
第三f2f)
1)他谈到我的项目差不多45分钟, 并询问我们如何实施它。我也在我当前的公司中从事Web服务的工作, 因此他们对在那里的问题更感兴趣, 并想知道我在那里的实施情况。
2)国际象棋int board [8] [8]的设计问题, 矩阵中的每个值代表一个字符。 1-9数字代表所有白人, 11-19数字代表所有黑人。
给定(x, y)的棋子, 则打印所有可能的移动。假设白色为索引0, 黑色为索引7。
第四f2f)
1)在二维空间(一个平面)中有三叉树。打印从平面右侧可见的所有元素(如果沿y轴平面看到)
例如)在下面的答案将是(1)(5)(8)
————————(1)————————————
--————-(2)–(3)–(4)–(5)——————————
--——-(6)–(7)–(8)————————————
2)以Z字形顺序打印这些元素, 首先是第1级, 然后是第n级, 第2级和第n-1级, 依此类推。
用简单的话来说, 在三叉树的每个级别中都打印最右边的结束元素。
我的方法是采用两个队列, 在Q1入队根, 在Q2出队入队其子级, 同时将元素从一个队列移到另一个队列中, 将最后一个元素存储在双向链表中。
在打印时, 请使用此双链表, 从头开始, 然后从尾部移除, 直到其变空。
第五f2f)
1)在帕斯卡三角形的第i行中找到第j个元素
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1…和儿子pascal(4, 2)应该返回6。

pascal(int i , int j){ if(i< 0||j< 0) return 0; if(i==0 & & j==0) return 1; if(i==0 & & j!=0) return 0; return pascal(i-1, j-1)+pascal(i-1, j); }

复杂性不好, 一旦计算出子问题, 我就不对解决方案进行分组
2)使用键作为字符串实现自己的哈希函数, 并且值的类型为Object
最初, 我告诉BST删除订单log(n)插入内容, 然后他告诉我思考和回答, 然后我告诉自平衡BST, 他要求我实施,
3)使用运算符优先级评估数学表达式2 * 3 +(5-6 / 2), 类似这样。
每个f2f面试时间为50至60分钟。在每个f2f回合中, 他们都会询问更改原因以及你当前的项目。你应该对当前的项目做出完美的回答, 不要对任何事情都感到困惑, 他们也会在当前的项目中提出很好的问题。
这些问题可能会占用15-20分钟以上的时间, 在其余时间中, 你必须在DS中回答最少两个问题, 并对它们进行编码。
如果回答, 你将再得到一个有益的问题which
首先, 他将解释问题并给你一些时间。
你需要先解释该解决方案, 如果他喜欢它, 那么他会要求你编写生产代码并拿纸。
每次面试都不像亚马逊的水平, 他们既不会与你也不会与其他面试官分享反馈。
面试过程完成后, 所有接受面试的人都将坐下来并进行判断(这就是人力资源部告诉我的??)
所有面试官都很友好, 最后我接到人力资源部的电话, 说我被选中了。
亚马逊的所有练习题
!