j*********5
发帖数: 362 | 1 其实后来我想了一下，没想象那么简单。Leetcode上实际上没有。
给两个数组，A是Sorted，B也是Sorted，要求Merge这两个，非常简单吧？立刻想到
Leetcode的merge two sorted array和merge sorted linked list之类的。
其实不然。
有要求，要求就是merge成两个数组，一个存unique value，一个存duplicated。这基
本上是对方要求的原话，没有更多信息了。
我的错误在于没理解题意，我觉得有好几种理解方法：
假设:
A是[1, 3, 4, 4, 5, 6, 6]
B是[1, 2, 4, 5, 6, 7]
我理解成输出：
Unique Array[2, 3, 7]
Duplicate Array[1, 1, 4, 4, 4, 5, 5, 6, 6, 6]
因为原话说“把unique的value都存到一个数组，duplicate的存到另一个”，此外，
number是有意义的（每个人的身高），所以我理解为Duplicate的数字是不能随便合并
的，原题也没有任何暗示说可以合并数字。
另一种理解方式（也是interviewer的expected）是
Unique Array[1, 2, 3, 4, 5, 6, 7] （所有出现过的value "uniquely"）
Duplicate Array[1, 4, 5, 6] （所有出现过的duplicate value "once only"）
但是平心而论，我个人觉得这种理解其实不是很正常的思维方式，因为数据都是身高，
per person，either你保留所有的每个人的身高，or你可以统计有多少unique身高，或
是有多少duplicate身高，但是duplicated身高也要出现在Unique Array里面，尤其令
人费解。
其实还有其他理解方式，我就不提了。
所以我的最关键的错误就在于这里：理解错了题意。
当然，我最大的错误就是急于分析，而没有举例，问他expected是什么。如果我快速写
个例子，问他输出是什么，也许就可以避免这个问题了。
但是，他一直催促写代码，感觉也不是很愿意回答我的问题或是听我的分析，所以我就
慌了，只能赶紧写代码，最后就悲剧了。
其实说实话，我觉得写个trie还更不容易出事儿，就是因为再难，大家也理解你想干嘛
，trie能有什么误解？说实话，我宁愿碰什么Word Search II也不愿意碰这种题，如果
interview不愿意交流，就惨了。
其次，可能我的思维有定式，受什么“remove all duplicates from Linked List”这
种Leetcode题影响太深，自己自作聪明，以为duplicates肯定要一起都去第二个数组。
当然，我以前onsite也碰过一个类似的情景，就是一个人拿blog举例，其实是想让我实
现LRU。 LRU俺倒是会，问题是谁能想到Blog是LRU？我思维定式中就觉得blog的任何文
章都是根据发表时间排序的，他的意思是这篇blog文章被看过了就该被放到latest，新
文章也是latest。我就惊呆了。
如果说是browsing history之类的，早就懂了。
唉。看来还是要机灵点。 | j*****8
发帖数: 3635 | 2 一开始你没要求和他一起跑一个例子来确保你们 on the same page？如果没有，那是
你的问题。
如果有，他不配合，那是他的问题
而且你这个帖子里的第二种理解方式也有问题阿，漏掉了3
从你的帖子，我感觉他要求的就是
unique array 存所有出现过的value (一次或多次）
duplicate的存所有出现过多于一次的value
【在 j*********5 的大作中提到】
: 其实后来我想了一下，没想象那么简单。Leetcode上实际上没有。
: 给两个数组，A是Sorted，B也是Sorted，要求Merge这两个，非常简单吧？立刻想到
: Leetcode的merge two sorted array和merge sorted linked list之类的。
: 其实不然。
: 有要求，要求就是merge成两个数组，一个存unique value，一个存duplicated。这基
: 本上是对方要求的原话，没有更多信息了。
: 我的错误在于没理解题意，我觉得有好几种理解方法：
: 假设:
: A是[1, 3, 4, 4, 5, 6, 6]
: B是[1, 2, 4, 5, 6, 7]
| j*********5
发帖数: 362 | 3 我的确没强烈要求。他给的例子只有一个duplicate， 但没有expected output。
但我提出想看看duplicate怎么处理、设想一下思路，他催促我赶紧写代码，说一会儿
再细说duplicate的情况。
所以我的责任更大。
3那个问题改过来了，笔误。
他之前的文字说法是事先打好的，跟实际说法差别很大，很误导。这个是我比较郁闷的
地方。
原文大概是：“put all unique values in first array，and put all the
duplicated values in the second array”。
【在 j*****8 的大作中提到】
: 一开始你没要求和他一起跑一个例子来确保你们 on the same page？如果没有，那是
: 你的问题。
: 如果有，他不配合，那是他的问题
: 而且你这个帖子里的第二种理解方式也有问题阿，漏掉了3
: 从你的帖子，我感觉他要求的就是
: unique array 存所有出现过的value (一次或多次）
: duplicate的存所有出现过多于一次的value
| j*****8
发帖数: 3635 | 4 这种coding一开始一定要一起跑几个例子，确保你理解的是他想要的
一般面试官都不会拒绝这个的
【在 j*********5 的大作中提到】
: 我的确没强烈要求。他给的例子只有一个duplicate， 但没有expected output。
: 但我提出想看看duplicate怎么处理、设想一下思路，他催促我赶紧写代码，说一会儿
: 再细说duplicate的情况。
: 所以我的责任更大。
: 3那个问题改过来了，笔误。
: 他之前的文字说法是事先打好的，跟实际说法差别很大，很误导。这个是我比较郁闷的
: 地方。
: 原文大概是：“put all unique values in first array，and put all the
: duplicated values in the second array”。
| j*********5
发帖数: 362 | 5 嗯，明白。
还是交流的问题。
但是这时即使对方态度不好，也要问么？
感觉这人一开始就态度很差，就是“你赶紧写code”这种想法。
【在 j*****8 的大作中提到】
: 这种coding一开始一定要一起跑几个例子，确保你理解的是他想要的
: 一般面试官都不会拒绝这个的
| j*********5
发帖数: 362 | 6 补充一点：
这题不让用任何数据结构。
比如，如果求unique的话，用set直接解决；
我设想是用hash table （array实现，因为身高是在一个很小范围内的值），扫一遍两
个数组都出来了。 | j*********5
发帖数: 362 | 7 其实如果明白题意，做法就非常简单了：
双指针i j，都从0开始，比较大小；
如果A[i] >= B[j]，准备加B[j]但要看B[j]是不是已经在Unique Array里面了，如果不
是，加进去；如果已经在Unique Array里，要看Duplicate Array里面有没有这个值，
如果没有，加，如果有，什么都不做；
A[i] < B[j] 同理；
最后要处理i和j，either会没到最后一个element，code 同上。
我这里有个巨大的错误，面试时。我试图处理当A[i] == B[j]时同时移动指针，这个非
常蠢，主要是一次移动一个会很简单不容易出错，一次移动两个就非常复杂，比如A[1,
1, ....], B[1,1, ....]，到第二个1时，会比较难判断，一大堆if else，人就晕了。 | p*******n
发帖数: 2697 | 8 我觉得没啥，就是他一开始就看你不爽不想要你。或者他这人就这性格，进去了也是要
走人，何必纠结
【在 j*********5 的大作中提到】
: 其实后来我想了一下，没想象那么简单。Leetcode上实际上没有。
: 给两个数组，A是Sorted，B也是Sorted，要求Merge这两个，非常简单吧？立刻想到
: Leetcode的merge two sorted array和merge sorted linked list之类的。
: 其实不然。
: 有要求，要求就是merge成两个数组，一个存unique value，一个存duplicated。这基
: 本上是对方要求的原话，没有更多信息了。
: 我的错误在于没理解题意，我觉得有好几种理解方法：
: 假设:
: A是[1, 3, 4, 4, 5, 6, 6]
: B是[1, 2, 4, 5, 6, 7]
| j*********5
发帖数: 362 | 9 是。
但是我还是试图提高自己的面试心态和交流技巧嘛，得会打顺风局和逆风局，才是好
DOTA玩家。
感觉分析了一下还是有用，这题不像想象那么简单，其次，交流太重要了，妈的
expectation都没搞清楚我就写code，找死！
【在 p*******n 的大作中提到】
: 我觉得没啥，就是他一开始就看你不爽不想要你。或者他这人就这性格，进去了也是要
: 走人，何必纠结
| i******s
发帖数: 301 | 10 简单来说就是，面试经验缺乏，想当然。面试官态度差很有可能: 1) 工作压力大，耐
心不够。2) 觉得问题没那么难，但是面试者交流理解题意没达到他预期，不耐烦了。3
) 看你不爽(多种原因。。。)
"但是平心而论，我个人觉得这种理解其实不是很正常的思维方式，因为数据都是身高，
per person，either你保留所有的每个人的身高，or你可以统计有多少unique身高，或
是有多少duplicate身高，但是duplicated身高也要出现在Unique Array里面，尤其令
人费解。"
这个说句实话，我觉得面试官期待的倒是更符合逻辑(我本人的)。在这种情况下，建议
跑几个例子。还有一点，面试的时候一开始要观察面试官属于那种类型的。你碰到的这
个，我建议，1) 跑几个例子，确定理解题意。2) 不要话太多，分析太多，仔细花几分
钟想清楚然后跟面试官说算法，他肯定了以后迅速写出。3) 中间不要啰嗦，不拖泥带
水。
最后一点，现在很多公司其实觉得也不缺人，所以比较diao。反正就是一个面试，该干
嘛干嘛。 | | | j*****8
发帖数: 3635 | 11 其实都不用check是不是已经加到unique / duplicate里
每次只加小的那个值 + pointA， pointB前移时跳过相同的值就可以搞定了
if a[i] == b[j]
put a[i] to unique & duplicate
i++;
while(i < a.length && a[i] == a[i-1]) i++;
j++;
while(j < b.length && b[j] == b[j-1]) j++;
else if a[i] > b[j]
put b[j] to unique
j++;
while(j < b.length && b[j] == b[j-1]) j++;
if exist duplicate put b[j] to duplicate
else
put a[i] to unique
i++;
while(i < a.length && a[i] == a[i-1]) i++;
if exist duplicate put a[i] to duplicate
最后check是否某个数组有剩下的，加进去就行（去重）
1,
【在 j*********5 的大作中提到】
: 其实如果明白题意，做法就非常简单了：
: 双指针i j，都从0开始，比较大小；
: 如果A[i] >= B[j]，准备加B[j]但要看B[j]是不是已经在Unique Array里面了，如果不
: 是，加进去；如果已经在Unique Array里，要看Duplicate Array里面有没有这个值，
: 如果没有，加，如果有，什么都不做；
: A[i] < B[j] 同理；
: 最后要处理i和j，either会没到最后一个element，code 同上。
: 我这里有个巨大的错误，面试时。我试图处理当A[i] == B[j]时同时移动指针，这个非
: 常蠢，主要是一次移动一个会很简单不容易出错，一次移动两个就非常复杂，比如A[1,
: 1, ....], B[1,1, ....]，到第二个1时，会比较难判断，一大堆if else，人就晕了。
| L*****e
发帖数: 8347 | 12 你想得太多了，不是说是sorted array么？你只需要和加到unique array里最后一个比
就知
道是不是unique了，哪里需要set或者hash table？
两个index从0开始loop两个sorted array，谁指的小，current value就是小的那个，
谁指的小，谁的index往前移。
然后看current value是不是大于unique array里最后一个，大的话，就加进去;
如果等于unique array里最后一个，再比是不是等于duplicate array里最后一个，大
的话就加到duplicate array里，等于的话就ignore。
【在 j*********5 的大作中提到】
: 补充一点：
: 这题不让用任何数据结构。
: 比如，如果求unique的话，用set直接解决；
: 我设想是用hash table （array实现，因为身高是在一个很小范围内的值），扫一遍两
: 个数组都出来了。
| L*****e
发帖数: 8347 | 13 A[I]==B[j]时，两个指针一起移一点问题没有，不增加任何if else判断。。。
1,
【在 j*********5 的大作中提到】
: 其实如果明白题意，做法就非常简单了：
: 双指针i j，都从0开始，比较大小；
: 如果A[i] >= B[j]，准备加B[j]但要看B[j]是不是已经在Unique Array里面了，如果不
: 是，加进去；如果已经在Unique Array里，要看Duplicate Array里面有没有这个值，
: 如果没有，加，如果有，什么都不做；
: A[i] < B[j] 同理；
: 最后要处理i和j，either会没到最后一个element，code 同上。
: 我这里有个巨大的错误，面试时。我试图处理当A[i] == B[j]时同时移动指针，这个非
: 常蠢，主要是一次移动一个会很简单不容易出错，一次移动两个就非常复杂，比如A[1,
: 1, ....], B[1,1, ....]，到第二个1时，会比较难判断，一大堆if else，人就晕了。
| j*********5
发帖数: 362 | 14 是啊。
我后来一想，的确如此。
很简单。
还是这种题不熟。
【在 L*****e 的大作中提到】
: 你想得太多了，不是说是sorted array么？你只需要和加到unique array里最后一个比
: 就知
: 道是不是unique了，哪里需要set或者hash table？
: 两个index从0开始loop两个sorted array，谁指的小，current value就是小的那个，
: 谁指的小，谁的index往前移。
: 然后看current value是不是大于unique array里最后一个，大的话，就加进去;
: 如果等于unique array里最后一个，再比是不是等于duplicate array里最后一个，大
: 的话就加到duplicate array里，等于的话就ignore。
| j*********5
发帖数: 362 | 15 是。
我的意思是，其实A[i] == B[j]可以归到另外两个情况（大于、小于）之一，换句话说
，根本没必要判断等于这种情况。
【在 L*****e 的大作中提到】
: A[I]==B[j]时，两个指针一起移一点问题没有，不增加任何if else判断。。。
:
: 1,
| d****r
发帖数: 300 | 16 你思路是对的，这样逻辑更简洁。每个loop，只要拿到较小的那个，和上回的那个比一
下，放到相应队列就行了。
【在 j*********5 的大作中提到】
: 是。
: 我的意思是，其实A[i] == B[j]可以归到另外两个情况（大于、小于）之一，换句话说
: ，根本没必要判断等于这种情况。
|
|
