亚马逊面试经验| 198（SDE1）-yiteyi-C++库

我最近参加了亚马逊海得拉巴的SDE-I职位面试。所有4轮比赛都由不同团队的不同人员进行。

null

总共有4轮。第一和第二是在DS、Algos和PS上第三部分是部分编码和部分设计第四轮是管理层。

以下是每次面试中提出的问题：

第一轮： 1.序列化和反序列化二叉树需要进行哪些遍历？英国夏令时呢？给定二叉树的顺序和后序，重新构造原始树。编写代码。

2.从连续出现的大量整数中，是否总是在任何特定时间找到k个最小元素？

3.有一棵二叉树。现在，您必须将每个节点的数据替换为其左右子节点的数据之和。但条件是：只有当sum>data时，才应该用sum替换节点的数据如果总和10，所以不应该替换。相反，保持节点的数据不变，并将左侧数据替换为（20-6）=14。现在root=20，left=14，right=6。现在从左边再次检查条件，直到到达叶节点。

第二轮： 1.给定一组字符串。我们需要将所有这些字符串合并成一个字符串。您将获得一个merge（str1，str2）函数，其代价是传递的字符串长度之和。

如何通过尽可能降低成本来合并字符串？

在堆中编写deleteMin、insert、percolateDown操作的代码。

解决方案：首先，按照长度的升序对字符串进行排序。现在取出前两个字符串并将它们连接起来。将结果字符串保留在已排序的字符串中，wrt其长度。

这里将使用优先级队列来实现所需的解决方案。

2.给定一个大小为m x n的矩阵。这里m和n非常大，假设为10万。在这个矩阵中有一系列的子矩阵。求每个子矩阵中所有元素的和。子矩阵的位置由其上下两部分组成：左上和右下。

例如：输入阵列：5 x 6

1, 2, 3, 4, 5, 6 7, 8, 9, 10, 11, 12 13, 14, 15, 16, 17, 18 19, 20, 21, 22, 23, 24 25, 26, 27, 28, 29, 30

子矩阵位置： (3, 4), (4, 5) 这就是 16, 17 22, 23

o/p为：78

解决方案： 由于将有多个子矩阵将给你的，它不是最好的去为每个子矩阵元素。做一些预处理，比如构建另一个和输入矩阵大小相同的矩阵，其中包含其子矩阵的和。这样我们就可以计算O（1）时间内的和。对于上述示例，求和矩阵为：

1×1 1×2 1×3 1×4 1×5 1×6 2×1 2×2 2×3 2×4 2×5 2×6 3×1 3×2 3×3 3×4 3×5 3×6 4×1 4×2 4×3 4×4 4×5 4×6 5×1 5×2 5×3 5×4 5×5 5×6

现在求子矩阵的和：（3,4）和（4,5） sum=sum[maxRow，maxCol）–sum（minRow-1，maxCol）–sum（maxRow，minCol-1）+sum（minRow-1，minCol-1）

第三轮：

1.为用户设计报纸订阅系统。本设计中考虑的所有系统是什么？

2.整数流来了。在任何特定的时间点，您都需要给出其中的第一个非重复元素。例如：2，3，1，2，1，3，5 o/p：如果我问你第二个位置（3之后），答案是：2 如果我问你第五个位置（1之后），答案是：3 如果我问你第6位（第3位之后），答案是：“没有这样的元素” 如果我问你第7位（5之后），答案是：5

解决方案：

Maintain a LinkedList, with the elements in insertion order
maintain hashMap with input integer as key and value as:
class IntValue {
   int count;
   LinkedList headNode;
}

Now when an element comes, check if the element is present in hashMap.
If(present in hashMap) {
    if(element count == 1)
         delete the element from linkedList, 
          by replacing its data with its next element's data;
} else {
    insert the element into hasmap with count as 1
    and insert the element into linked list at then end.
}

经理轮： 1.谷歌爬虫问题。给定一组N个文档。给定k个字符串：{str_1，str_2，…，str_k）现在返回包含所有k字符串的文档编号。

2.给定一棵N元树。照照这棵树。为此提供合适的树节点结构，并为其编写代码以镜像它。如：

i/p:
				1
			 /  /	|     
			2  3	4  5	6
		       /      / |
		     7        8 9
			 
			
o/p:			
				1
			 /  /	|     
			6  5	4  3	2
			       / |       
			       9  8      7

我在过去两轮中表现不好。所以我被拒绝了。但这是一次很好的经历。感谢极客们提出了很多问题。如果我们每天只问一个问题，那么为极客准备极客中的所有问题至少需要一辈子的时间。谢谢

如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

亚马逊的所有练习题 !

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章