被pocket gems一道题绕了半天，杯具啊！

题目是很简单的clone graph
可是面试官说graph node是没有value field的
搞得我当场就慌了，心想没有value fiel我怎么建node啊！！
于是跟面试官扯了半天！！什么把node pass进constructor啥的。
后来灵机一动！！尼玛，没value field建个空的摆那，把neighborhood存进去不就行了！！！
最后虽然做出来了，但面试官也看我犯了很久的蠢……
估计要挂啊


补充内容 (2015-11-4 04:05):
补充一下吧，我这是二轮电面第二题。第一题是sort colored object（3 colors）follow up 1 : test cases 该怎么设置？ follow up 2： k个color怎么sort，object color 不可改，object 不能construct。

补充内容 (2015-11-4 04:06):
上周五面的，现在还没消息，求bless拿到onsite～～～～～～～～～～～～～～～～～

补充内容 (2015-11-4 06:34):
太灵了。。真的收到onsite邀请了，撒花！！！！！！！！！！！！！！！！！！！

dxpppi 发表于 2015-11-4 04:02
map指针是什么意思？map的key是original graph node，value是cloned graph node
sort color 3个颜色o(n) ...

key是original node的地址，value是cloned graph node的地址
用unordered_map<GraphNode*,GraphNode*> map;
来定义

O(n)空间是我想到了一个小的变形……那个题里面给的是一堆object，然后每个object都有一种method “get_catagory()”。要求按照catagory排序，且要保持相对顺序

plich 发表于 2015-11-4 03:59
clone graph你用的是map么……可以直接map指针吧……

sort colors难道是要你写bucket sort？O(n) 时间 O ...

map指针是什么意思？map的key是original graph node，value是cloned graph node
sort color 3个颜色o(n) time o(1) space
k个颜色 o(n) time o(k) space  count sort呗。。。因为不许用constructor就先遍历一遍找出现过的object

dxpppi 发表于 2015-11-4 04:04
补充一下吧，我这是二轮电面第二题。第一题是sort colored object（3 colors）follow up 1 : test cases 该 ...

那就使用基于比较的排序算法啦....quick sort的partition... 对于 3 color 只要一遍，O(n) time, O(1) space
k color,一样，worse O(kn)的时间，  在k远小于n的时候 可以认为是On ， 空间worse case是O(k)...

吃一堑长一智嘛...可能面试官就是想刁难你一下...

楼主是电面还是onsite 啊

楼主是二面电面吗？

AlexandraVon 发表于 2015-11-3 10:15
楼主是二面电面吗？

是的～～～～～～～～～～～～～～～

269644943 发表于 2015-11-2 15:49
楼主是电面还是onsite 啊

二面撒～～～～

dxpppi 发表于 2015-11-3 10:21
是的～～～～～～～～～～～～～～～

收到onsite了吗？

AlexandraVon 发表于 2015-11-3 10:24
收到onsite了吗？

没……等待中

dxpppi 发表于 2015-11-3 10:25
没……等待中

祝楼主拿到onsite啊！我也刚接到了二面通知，楼主是就面了这一道题吗？

AlexandraVon 发表于 2015-11-3 13:44
祝楼主拿到onsite啊！我也刚接到了二面通知，楼主是就面了这一道题吗？

还有一道sort color
要求sort的是objects with data field color(3 种)
follow up是有N个color怎么sort
给的object没有constructor
不可以change object's color