[2/9]G家Intern面经

一面：一个印度妹子，口音不是很重，但就是听不懂在讲什么，还是题目都在google doc上写下来了。1. 2sum（含duplicates），返回所有可能的pair，慢慢优化，复杂度从n^2, 到nlogn,到最后的n
2. Add and Search Wor

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

。

没想到遇到了这么简单的题，运气还挺好的，准备的过程看了很多地里的面经，谢谢各位！
找不到实习，暑假就在实验室搬砖了= =

wju1556 发表于 2016-2-22 21:45
话说2sum with duplicate怎么会On呢。。
如果一个array全是dup的话输出结果也得N^2吧？
求解答~

        static vector<std::pair<int, int>> twoSum(std::vector<int> &nums, int target){
                std::unordered_set<int> hashset;
        std::vector<std::pair<int, int>> vec;
                for(size_t i = 0; i < nums.size(); ++i)
                {
                        int num = target - nums[i];
                        if(hashset.find(num)!=hashset.end())
                        {
                vec.push_back(std::make_pair(num, nums[i]));
                hashset.erase(num);
                        }
                        else hashset.insert(nums[i]);
                }
                return vec;
        }

刚刚收到拒信，回想起来有几点做得不好，做了5道题，3道题都有bug，有的是面试官当场指出的，有的是我后来回想起来的。还有第一个面试我的是印度妹子，所以经常没听懂，但是一开始她问我听不听得清，我跟她说我听得很清楚，后来一想如果遇到口音重的面试官，应该直接和她说信号不好，听不清楚，这样后面的pardon也可以谅解。

wuzhenyu_sjtu 发表于 2016-2-18 05:06
刚刚收到拒信，回想起来有几点做得不好，做了5道题，3道题都有bug，有的是面试官当场指出的，有的是我后来 ...

额， pat pat，我更惨，总共只做了3道，都是超简单的，也没bug free，题目简单的我都不好意思贴。。我的rej应该快到了。

求最长子序列吗？要输出序列还是只要长度？

houqingniao 发表于 2016-2-11 00:22
求最长子序列吗？要输出序列还是只要长度？

只要长度

一面第一题Follow up是3sum，我直接遍历数组，然后每次调用2sum做的，复杂度是O(n^2)，她问我能不能降到n，我说不行

wuzhenyu_sjtu 发表于 2016-2-11 06:19
只要长度

n叉树 这个咋弄啊

houqingniao 发表于 2016-2-11 10:18
n叉树 这个咋弄啊

和二叉一样处理，DFS搜的时候多搜分支即可

2 sum 怎么o(n)?

知道了 用个hash table

楼主进pool了没？

leewave 发表于 2016-2-16 02:39
楼主进pool了没？

还在等结果，很慌现在