Flipkart访谈|第三组-yiteyi-C++库

最近我参加了Flipkart的采访。我想分享我的经验。

null

第一轮：电话（45分钟）

给定一个按升序排序的n个不同整数的数组。查找索引i s.t ar[i]=i。如果不存在此类索引，则返回-1。请注意，数组中的整数可以是负数。文章链接： https://www.geeksforgeeks.org/find-a-fixed-point-in-a-given-array/ 练习环节： https://practice.geeksforgeeks.org/problems/value-equal-to-index-value1330/1
设计一个包含整数值的堆栈，使得getMinimum（）函数应该返回堆栈中的最小元素。后续操作：实现popMin（）函数，该函数将从原始堆栈中弹出最小元素。O（1）需要实施。（提示：使用LinkedList实现堆栈，并在最小堆栈中存储最小元素节点的地址）文章链接： https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/ 练习环节： https://practice.geeksforgeeks.org/problems/special-stack/1
打印组织层级。纳文管理萨蒂什萨蒂什管理阿努什里萨蒂什管理桑德普古林德管理纳文
古林德->纳文 Naveen->Satish 萨蒂什->阿努什里，桑德普 Anushree-> Sandeep->

轮：30-2分钟

给定一个先严格递增，然后严格递减的数组。在此数组中查找一个元素。讨论各种方法及其复杂性。文章链接：https://www.geeksforgeeks.org/find-element-bitonic-array/ 练习环节：https://practice.geeksforgeeks.org/problems/maximum-value-in-a-bitonic-array3001/1

第三轮：内部编码（1小时45分钟） 用任何语言编写运行代码来实现著名的井字游戏 . 首先，讨论了实施该计划所需的各种方法和基本职能。然后我被要求编写代码。我有1小时15分钟的时间来编写代码。我必须按照以下步骤设计这个游戏：

第四轮：数据结构和问题解决（1小时）

给定一个经过排序和旋转的数组。在此数组中查找一个元素。（著名问题）
这是一个有趣的问题。给定一组间隔，比如5-10、15-20、25-40、30-45、50-100。找出这些间隔中的第i个最小数。假设没有重复的数字。
```
e.g:  1st smallest number = 5
      6th smallest number = 10
      7th smallest number = 15 and so on. 
```
我告诉他，我们将首先根据起始数字对间隔进行排序。然后合并重叠区间，得到一组非重叠区间，如5-10、15-20、25-45、50-100。现在我们可以在找到合适的区间后找到第i个最小数。

跟进：然后他修改了这个问题，以适应重复的数字。
```
Suppose we have intervals like 5-10, 8-12. 
Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12} 
        So, 1st smallest number: 5
            4th smallest number: 8
            5th smallest number: 8 (here is the 
change since now we have duplicate elements also) and so on. 
```
给我一本五万字的字典。给一个没有空格的短语加上空格，使其成为一个合适的句子。
```
e.g: input:  thequickbrownfoxjumpoverlazydog
    output: the quick brown fox jump over lazy dog
```

后续问题：