d*k
发帖数: 207 | 1 MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
老美给了个strong reject。另一个是一个烙印的一道题：
输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
5 10 1 6 2 4 11 7 3
输出是
1-6
7
10-11
我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
提示，但我没明白他的意思。欢迎大家讨论。
经验教训：累了千万说话，硬撑悲剧后没人可怜你，最后一面的时候哪怕给我一杯水或
者让我出去溜达十分钟呼吸下新鲜空气，结果可能就不一样了。在那个不通风的小屋子
里连着好几个小时真心受不了。其实题目算不上难，我前两面都很好，只好是两个hire
。后面累的和sb一样，结果悲剧了。
祝大家好运。 |
j******2
发帖数: 362 | |
t*********h
发帖数: 941 | 3 元素不大的话 开个数组一面扫描就出来了 不过完全没用到double linked
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
d**********x
发帖数: 4083 | 4 貌似由于这个问题的特殊性，不用union-find也是可以的，每个set直接就一段链表结
构放在那里就可以。。。
如果不惜空间的话，用union-find和hash
首先，用hashtable存每个元素
然后每次新来一个元素n，如果它已经存在于table中，忽略
如果它不存在，则插入table，并且加一个指针元素，指向新建立的一个节点，准备插
入到某个set中
查找n - 1，如果存在于table中，则做union
查找n + 1，如果存在于table中，则视前面一个查找结果而定：
如果n - 1存在，则将n + 1所在的set和n -1 所在的set union
否则将n加入n + 1所在的set
否则单纯保留这个引用，暂时成为一个单独的set
处理完所有元素之后，这是近似O(n)时间（因为hashtable和union-find都是近似O(1))
每个set中包含连续的一组整数，扫描一遍，O(n)出结果
至于为什么是链表，我现在也不知道了。
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
m******s
发帖数: 165 | 5 为啥不是1-7 10-11。。。
其实休息这个事儿也要分情况的。。。貌似G家休息的时间是算在你面试时间里的，我
面的时候不知道这点轮轮休息，结果5轮只coding了4道题（除了discussion以外一轮一
道）。不过运气比较好面的都是非主流难题（最后留下的时间都是连一道水题都来不及
的）所以最后没有悲剧。。。
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
p*****2
发帖数: 21240 | |
f*****e
发帖数: 2992 | 7 没有看你来报g offer啊。
【在 m******s 的大作中提到】
: 为啥不是1-7 10-11。。。
: 其实休息这个事儿也要分情况的。。。貌似G家休息的时间是算在你面试时间里的，我
: 面的时候不知道这点轮轮休息，结果5轮只coding了4道题（除了discussion以外一轮一
: 道）。不过运气比较好面的都是非主流难题（最后留下的时间都是连一道水题都来不及
: 的）所以最后没有悲剧。。。
:
: 入是
|
w****a
发帖数: 710 | 8 弱弱的问一句，面的都是非主流难题为什么就不容易悲剧？
【在 m******s 的大作中提到】
: 为啥不是1-7 10-11。。。
: 其实休息这个事儿也要分情况的。。。貌似G家休息的时间是算在你面试时间里的，我
: 面的时候不知道这点轮轮休息，结果5轮只coding了4道题（除了discussion以外一轮一
: 道）。不过运气比较好面的都是非主流难题（最后留下的时间都是连一道水题都来不及
: 的）所以最后没有悲剧。。。
:
: 入是
|
l****i
发帖数: 2772 | 9 我前几天G的第一个电面，最后还有几分钟，老印就出了这题。5分钟没想出一遍扫出来
的算法，老印直接和我说，时间到了，就thank you把电话挂了。期间，面我的老印还
一直和边上一个女老印讲话，我都能听到。真想投诉丫的！但是G家和我联系的HR，也
全部是老印。无语了。
挂了电话，我想了想，大概思路是这样。
比如输入 1 3 2.....
做一个interval(start,end)的结构
读到1：（1，1）
读到3：（1，1）（3，3）
读到2： （1，2）（2，3）--》（1，3）
这样就有点像合并interval的那题了。
唉，老印太狠，G的hr和我说会用google doc，结果老印无视，说只需要电话交谈。每
次给我说一个题目，就耗费1-2分钟时间。
一共电面45分钟，首先扯了15分钟的毕业论文。然后问了一堆找数字和排序的问题。每
题都是关乎Big O的。
1. sorted的数组，找一个数
2. unsorted数组，找一个数。follow up，如果知道这个unsorted数组里，只有一个数
的位置是unsorted的，怎么找出来，怎么把这个数组变为sorted。
3. 知道哪些排序算法？每个排序算法的复杂度是多少？把冒泡和merge的算法，具体解
释一遍。
4. 2个sorted数组，找第K个maximum的数。开始给了一个O（K）的答案，不满意。想了
半天，每个数组取最后K个元素。这样就有点像找median的那题。应该是O(logK).
5. 就是最后那道找interval的题目。5分钟没找到O（n）。只想到naive的排序，是O（
nlogn）.
回头想想，总体也不是特别难。但是老印电话里一直催，又不用google doc，越紧张想
问题越慢。G家一面就挂了，move on。 |
d*********g
发帖数: 154 | 10 这样做不是O(n)吧？对每个数，找到它需要插入的interval的时候最坏也需要O(n)，所
以复杂度是O(n^2)吧？
【在 l****i 的大作中提到】
: 我前几天G的第一个电面，最后还有几分钟，老印就出了这题。5分钟没想出一遍扫出来
: 的算法，老印直接和我说，时间到了，就thank you把电话挂了。期间，面我的老印还
: 一直和边上一个女老印讲话，我都能听到。真想投诉丫的！但是G家和我联系的HR，也
: 全部是老印。无语了。
: 挂了电话，我想了想，大概思路是这样。
: 比如输入 1 3 2.....
: 做一个interval(start,end)的结构
: 读到1：（1，1）
: 读到3：（1，1）（3，3）
: 读到2： （1，2）（2，3）--》（1，3）
|
|
|
l****i
发帖数: 2772 | 11 不在乎空间的话，加一些辅助，我觉得应该可以做到O(n).就像楼上那位兄弟说的，可
以用hashtable记录出现的数。我觉得可以用2个hashtable，一个记录start的数和位置
，一个记录end的数和位置。如果一个新读入的数字，替换了一个interval的end，同时
替换了一个interval的start，就合并这2个interval。
大家觉得呢？
【在 d*********g 的大作中提到】
: 这样做不是O(n)吧？对每个数，找到它需要插入的interval的时候最坏也需要O(n)，所
: 以复杂度是O(n^2)吧？
|
j*****y
发帖数: 1071 | 12 因为是双向链表，可以用 insertion sort, 不用 extra space.
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
f*****e
发帖数: 2992 | 13 先扫一遍，确定范围。然后分配一个这个范围大小的数组A。
每个数组元素，结构为：
{bool, Node *} bool记载这个点occupied or not。
然后创建一个Node链表B，每个Node存放起点和终点。
struct Node {
int start;
int end;
Node* next;
}
A的每一个occupied的元素指向B的一个元素。
当插入v到A的时候，如果A[v]已经occupied了就什么事也不做，如果A[v]没有occupied
并且A[v-1]或A[v+1]有一个已经occupied，就并入那个occupied的interval:A[v]=A[v-
1]或A[v]=A[v+1], 并且更新相应的B的start & end信息。如果A[v-1]和A[v+1]两个都
occupied，就合并两个B interval。如果两边都没有occupied，就加入一个新元素到B
。好想见到过或做过。
【在 l****i 的大作中提到】
: 不在乎空间的话，加一些辅助，我觉得应该可以做到O(n).就像楼上那位兄弟说的，可
: 以用hashtable记录出现的数。我觉得可以用2个hashtable，一个记录start的数和位置
: ，一个记录end的数和位置。如果一个新读入的数字，替换了一个interval的end，同时
: 替换了一个interval的start，就合并这2个interval。
: 大家觉得呢？
|
j*****y
发帖数: 1071 | 14 如果分配了一个范围大小的数组，那直接用 direct access table就行了吧，
【在 f*****e 的大作中提到】
: 先扫一遍，确定范围。然后分配一个这个范围大小的数组A。
: 每个数组元素，结构为：
: {bool, Node *} bool记载这个点occupied or not。
: 然后创建一个Node链表B，每个Node存放起点和终点。
: struct Node {
: int start;
: int end;
: Node* next;
: }
: A的每一个occupied的元素指向B的一个元素。
|
t*********n
发帖数: 89 | 15 先找出数组范围，然后用bitmap记录出现的数字，最后扫一遍bitmap得出区间。
这个类似与hash table. 问题是双向链表到底有什么用呢？ |
p*****2
发帖数: 21240 | 16
范围很大，链表很小怎么办？
【在 t*********n 的大作中提到】
: 先找出数组范围，然后用bitmap记录出现的数字，最后扫一遍bitmap得出区间。
: 这个类似与hash table. 问题是双向链表到底有什么用呢？
|
c********t
发帖数: 5706 | 17 我觉得也是，如果没有空间限制，这道题没有太大意义。只有有O(1)空间限制，
doublelinked list才有意义，需要in place 排序，但我还没想好怎么做，好像quick
sort不容易实现，只能selection sort或者bubble sort了。
【在 j*****y 的大作中提到】
: 如果分配了一个范围大小的数组，那直接用 direct access table就行了吧，
|
j*****y
发帖数: 1071 | 18 quick sort 不错，可以做到 in place
quick
【在 c********t 的大作中提到】
: 我觉得也是，如果没有空间限制，这道题没有太大意义。只有有O(1)空间限制，
: doublelinked list才有意义，需要in place 排序，但我还没想好怎么做，好像quick
: sort不容易实现，只能selection sort或者bubble sort了。
|
p*****2
发帖数: 21240 | 19
quick sort可以，但是是不是也不一定需要double linkedlist?
【在 j*****y 的大作中提到】
: quick sort 不错，可以做到 in place
:
: quick
|
c********t
发帖数: 5706 | 20 难点是如何partition？我想想看。
【在 j*****y 的大作中提到】
: quick sort 不错，可以做到 in place
:
: quick
|
|
|
c********t
发帖数: 5706 | 21 我感觉doulbe linked 可以对partition两头夹，swap啊
【在 p*****2 的大作中提到】
:
: quick sort可以，但是是不是也不一定需要double linkedlist?
|
j*****y
发帖数: 1071 | 22 这是题目的条件阿，题目给的是 double linked list
如果是 single linked list 就没办法 quick sort 了
【在 p*****2 的大作中提到】
:
: quick sort可以，但是是不是也不一定需要double linkedlist?
|
p*****2
发帖数: 21240 | 23
single 的就不可以了吗？
【在 j*****y 的大作中提到】
: 这是题目的条件阿，题目给的是 double linked list
: 如果是 single linked list 就没办法 quick sort 了
|
j*****y
发帖数: 1071 | 24 想了一下， single 的也可以， 不用交换node,只需要 swap 两个 value就可以了
【在 p*****2 的大作中提到】
:
: single 的就不可以了吗？
|
d**********x
发帖数: 4083 | 25 ...
in-place必然是merge-sort啊兄弟
quick-sort在这里不容易randomize，就算你用三选一pivot也包不齐。。
quick
【在 c********t 的大作中提到】
: 我觉得也是，如果没有空间限制，这道题没有太大意义。只有有O(1)空间限制，
: doublelinked list才有意义，需要in place 排序，但我还没想好怎么做，好像quick
: sort不容易实现，只能selection sort或者bubble sort了。
|
d**********x
发帖数: 4083 | 26 其实也不是不可以
如果链表只有两个元素，分别是INT_MAX和INT_MIN的话，你只要分配一个500M的数组就
行了
然后扫一遍这个500M的数组直接出结果
【在 t*********n 的大作中提到】
: 先找出数组范围，然后用bitmap记录出现的数字，最后扫一遍bitmap得出区间。
: 这个类似与hash table. 问题是双向链表到底有什么用呢？
|
c********t
发帖数: 5706 | 27 好像也有道理，我糊涂了。至少我感觉single linkedlist肯定做不到O(nlgn)sort吧。
你们都写写psudo codes吧。
【在 d**********x 的大作中提到】
: ...
: in-place必然是merge-sort啊兄弟
: quick-sort在这里不容易randomize，就算你用三选一pivot也包不齐。。
:
: quick
|
d**********x
发帖数: 4083 | 28 MERGE-SORT(L)
IF (MID == NULL) RETURN;
MID = FIND-AND-SPLIT-AT-MID(L)
IF (MID == NULL || MID == L) RETURN;
MERGE-SORT(L) //L-->MID - 1
MERGE-SORT(MID) // MID --> TAIL
MERGE(L, MID)
merge sort不要求是双向。当然如果O(logn)的栈也算的话...
【在 c********t 的大作中提到】
: 好像也有道理，我糊涂了。至少我感觉single linkedlist肯定做不到O(nlgn)sort吧。
: 你们都写写psudo codes吧。
|
c********t
发帖数: 5706 | 29 可行，栈的问题应该可以忽略。虽然MID = FIND-AND-SPLIT-AT-MID(L)感觉有些不爽，
但确实也没增加复杂度。
【在 d**********x 的大作中提到】
: MERGE-SORT(L)
: IF (MID == NULL) RETURN;
: MID = FIND-AND-SPLIT-AT-MID(L)
: IF (MID == NULL || MID == L) RETURN;
: MERGE-SORT(L) //L-->MID - 1
: MERGE-SORT(MID) // MID --> TAIL
: MERGE(L, MID)
: merge sort不要求是双向。当然如果O(logn)的栈也算的话...
|
t*********h
发帖数: 941 | 30 百司不得其解 求如果元素范围很大情况下的线形接法
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
|
|
s****0
发帖数: 117 | 31 devilphoenix的是正解，兄弟。
1 额外空间
hashtable：key=元素，value=一个object标明开始结束
扫描链表，union-find
2 不用额外空间
a double link list -> BST optionally merge sets.
b inorder traversal BST
赞题目。
【在 d**********x 的大作中提到】
: 貌似由于这个问题的特殊性，不用union-find也是可以的，每个set直接就一段链表结
: 构放在那里就可以。。。
: 如果不惜空间的话，用union-find和hash
: 首先，用hashtable存每个元素
: 然后每次新来一个元素n，如果它已经存在于table中，忽略
: 如果它不存在，则插入table，并且加一个指针元素，指向新建立的一个节点，准备插
: 入到某个set中
: 查找n - 1，如果存在于table中，则做union
: 查找n + 1，如果存在于table中，则视前面一个查找结果而定：
: 如果n - 1存在，则将n + 1所在的set和n -1 所在的set union
|
w****x
发帖数: 2483 | 32 一个是hash_table两边扫了，O(n)但是需要额外空间，
一个是链表的quick sort, 不需要空间但是nlogn |
w********p
发帖数: 948 | 33 请教下，有谁给解释下这道题在问什么吗？
没有看懂题目。
整数所构成的区间， 指的是啥？
入是
【在 d*k 的大作中提到】
: MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
: ，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
: 老美给了个strong reject。另一个是一个烙印的一道题：
: 输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
: 5 10 1 6 2 4 11 7 3
: 输出是
: 1-6
: 7
: 10-11
: 我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
|
c********t
发帖数: 5706 | 34 大侠说说对于链表的quick sort，doubly 有什么意义？
【在 w****x 的大作中提到】
: 一个是hash_table两边扫了，O(n)但是需要额外空间，
: 一个是链表的quick sort, 不需要空间但是nlogn
|
w****x
发帖数: 2483 | 35
两个set O(n)时间， O(n)空间
void union_print(set& st1, set& st2, int i)
{
if (st2.find(i) != st2.end())
return;
int nRgt = i;
while (st1.find(nRgt) != st1.end())
st2.insert(nRgt++);
nRgt--;
int nLft = i;
while (st1.find(nLft) != st1.end())
st2.insert(nLft--);
nLft++;
cout<
}
void printScope(list& lst)
{
set st1, st2;
for (list::iterator it = lst.begin(); it != lst.end(); it++)
st1.insert(*it);
for (list::iterator it = lst.begin(); it != lst.end(); it++)
union_print(st1, st2, *it);
}
【在 d**********x 的大作中提到】
: 貌似由于这个问题的特殊性，不用union-find也是可以的，每个set直接就一段链表结
: 构放在那里就可以。。。
: 如果不惜空间的话，用union-find和hash
: 首先，用hashtable存每个元素
: 然后每次新来一个元素n，如果它已经存在于table中，忽略
: 如果它不存在，则插入table，并且加一个指针元素，指向新建立的一个节点，准备插
: 入到某个set中
: 查找n - 1，如果存在于table中，则做union
: 查找n + 1，如果存在于table中，则视前面一个查找结果而定：
: 如果n - 1存在，则将n + 1所在的set和n -1 所在的set union
|
w****x
发帖数: 2483 | 36
没意思
单链表的quick sort就可以了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev->pNext;
pIterBeg = pIterBeg->pNext;
nCount++;
}
pIterEnd = pIterEnd->pNext;
}
swap(pNode->nVal, pPrev->nVal);
sort(pNode, nCount);
sort(pIterBeg, nLen - 1 - nCount);
}
NODE* sortLinkedList(NODE* pHead)
{
if (NULL == pHead)
return NULL;
int nLen = 0;
NODE* pIter = pHead;
while (pIter != NULL)
{
pIter = pIter->pNext;
nLen++;
}
sort(pHead, nLen);
return pHead;
}
【在 c********t 的大作中提到】
: 大侠说说对于链表的quick sort，doubly 有什么意义？
|
o***d
发帖数: 313 | 37 st2.find(i)似乎导致至少 log(n!)吧
还是得用纯粹的hash,然后指向每个set?每个set只存interval?这样似乎近似log(n)?
另外,感觉如果对space要求不高,双向链表一定是个废条件,我加个n的空间就可以把单项
连标变成双向了阿.
所以我怀疑这题不会有什么很牛的解决办法把?用很少的space和log(n)?????
【在 w****x 的大作中提到】
:
: 没意思
: 单链表的quick sort就可以了
: struct NODE
: {
: int nVal;
: NODE* pNext;
: NODE(int n) : nVal(n), pNext(NULL) {}
: };
: void sort(NODE* pNode, int nLen)
|
w****x
发帖数: 2483 | 38
单项
那把set换成hash_set
【在 o***d 的大作中提到】
: st2.find(i)似乎导致至少 log(n!)吧
: 还是得用纯粹的hash,然后指向每个set?每个set只存interval?这样似乎近似log(n)?
: 另外,感觉如果对space要求不高,双向链表一定是个废条件,我加个n的空间就可以把单项
: 连标变成双向了阿.
: 所以我怀疑这题不会有什么很牛的解决办法把?用很少的space和log(n)?????
|
m****s
发帖数: 1197 | |
