一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1053|回复: 15
收起左侧

[CareerCup] 【第四轮】4.6 - 4.12 Career Cup 2.1

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-7 01:36:53 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改

slaink 发表于 2015-4-7 02:11:40 | 显示全部楼层
【解题思路】
With extra buffer: Do bin sort or use hash map to de-duplicate
Without extra buffer: For each element, visit all its decedents in this linked list and remove all duplicate values.
【时间复杂度】O(N) or O(N^2)
【空间复杂度】O(C) or O(1), where C is the number of unique values in that linked list.
【gist link] https://github.com/bxshi/intervi ... ate_linked_list.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享) https://github.com/bxshi/intervi ... c/test/2_1_test.cpp
回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-7 05:15:18 | 显示全部楼层
【解题思路】
use hashtable to store the existing data, if the hastable  contans the data
    means duplicated
   
【时间复杂度】
O(N)
【空间复杂度】
O(N)

   Follow up  How would you solve this problem if a temporary buffer is not allowed?
【解题思路】   Brote force   
   use  two  iterators   one move from  the  root to the end
    second  move from first iterated   node to compare with   all the rest  and move  the dupiclated one
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/6cc6df41ce07bb8857ea
回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-7 11:36:49 | 显示全部楼层
【解题思路】
With extra buffer: 用一个hashtable存储data的值,若unique存入hash中,若又重复删去。
Without extra buffer: 对于每一个node,去除后面所有与它相同的node。
【时间复杂度】
O(N) or O(N^2)
【空间复杂度】
O(N) or O(1)
【gist link]
https://gist.github.com/chongtianzs/2f8df4b36d9c3889e64d
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-7 21:23:13 | 显示全部楼层
【解题思路】
//write a code to remove duplicates from an unsorted array
//using hashtable, time complexity is O(n), space complexity is O(n)
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/34db168892b516034894
【test case】
回复 支持 反对

使用道具 举报

coperdli 发表于 2015-4-10 09:37:07 | 显示全部楼层
本帖最后由 coperdli 于 2015-4-10 10:00 编辑

解题思路:目前只想到一种糟糕的方法,当遍历整个链表时,将剩余链表部分钟与当前元素值相同的节点统统从链表中删除。
时间复杂度:O(n^2)
空间复杂度:O(1)
code snippet & test case: https://gist.github.com/coperd/07ff535221bb887d5a79
补充: 想到另一种思路,先排序,而后遍历一遍删除相同的元素。这样子时间复杂度O(nlgn)+O(n)=O(nlgn), 空间复杂度:采用快排的话O(lgn)
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-10 11:56:07 | 显示全部楼层
【解题思路】
使用两个指针遍历链表(两层循环),当第二个指针指向的下一个节点值和第一个相同,删除第二个指针指向的下一个节点(因为实现的是双向链表所以其实多添了个指针,一共三个)
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-1-removedup-java
回复 支持 反对

使用道具 举报

芒果舞 发表于 2015-4-11 03:32:32 | 显示全部楼层
【解题思路】
1.考虑只有大写字母,用一个flag来保存字符是否出现.此时要考虑空白键,当成第27个字符。
2.考虑所有字符,用HashSet()。
3.不用Buffer,用两个指针iterate。
【时间复杂度】
1.O(n)
2.O(n)
3.O(n^2)
【空间复杂度】
1.O(1)
2.O(n)
3.O(1)
[gist link]        Java
https://gist.github.com/LinyinWu/b3a01634d2f7aa3ea8e8
[test case]
"FOLLOW UP"         --->        "FOLW UP"
"FOLLOW  P"         --->        "FOLW P
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-13 04:16:49 | 显示全部楼层
【解题思路】
  1. 用 HashSet 來檢測 duplicate,遍歷鏈表同時向 HashSet 中添加當前,一旦發現失敗了,那麽就要刪除。比較 tricky 的地方是 head 元素是不可能重複的,所以無需使用dummy node 2. 如何處理 head,讓代碼更清晰
2. 用 nested loop 來檢測 duplicate, 一旦發現重復元素就在內層循環中刪除

【时间复杂度】
1. Time - O(N)
2. Time - O(N^2)

【空间复杂度】
1. Space - O(N)
2. Space - O(1)
【gist link]
https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/RemoveDuplicates.java

【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestRemoveDuplicates.java

------------

用 intellJ 創建了 maven 的工程,這樣不需要花時間去添加 library 或者 import 之類和編程沒什麽關係的事情。此外,第二次做 CC150,感覺其實很多 solution 非常好,但是自己比較懶,沒有認真的去測試,去面試的時候面試官讓我自己寫 test case,根本就沒什麽想法。所以用 Junit 來寫test case,感覺效率高一些。

repo 的地址都在上面的鏈接裏面,我自己感覺比較方便(如果大家都這樣寫的話,那麽 review 別人的代碼也會容易一點),寫 Java 的同學不如試一下,也歡迎你一起來寫 test case
回复 支持 反对

使用道具 举报

yiyizheliu 发表于 2015-4-13 05:16:45 | 显示全部楼层
本帖最后由 yiyizheliu 于 2015-4-13 05:51 编辑

[解题思路]
1 把list转化成vector方便对每一个元素操作(c++)(暂时没有考虑follow up部分)
2 从最后一个元素开始,和前面的所有元素比较,一旦发现前面有与它相同的,删除它,否则保留
3 再把这个处理好的vector转回原来的list
[时间复杂度]
O(n^2)
[空间复杂度]
O(n)
[gist link] https://gist.github.com/yiyizheliu/32263f3957b43f013fbb
follow up: no temepare buffer available
[解题思路]
直接在list上操作,思路同上
[时间复杂度]
O(n^2)
[空间复杂度]
O(1)
[gist link] https://gist.github.com/yiyizheliu/e672737559ffe5a7bf51
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-13 11:06:44 | 显示全部楼层

【解题思路】
With extra buffer: use a hashmap to store the element and  remove the dup if it already exists in the hashmap
Without extra buffer: use two pointers, one to indicate the current element, one to iterate through the rest of the linkedlist to remove dup.
【时间复杂度】O(N) or O(N^2)
【空间复杂度】O(N) or O(1)
【gist link] https://gist.github.com/kelly-us/2aa0e810fa70696fb056
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-13 14:43:44 | 显示全部楼层
[solution 1]
use a hashset to store elements that occurred, delete the current element if it's included in the hashset.
[time]
O(n)
[space]
O(n)

[solution 2]
for each current element, test each element after it, delete the ones that is same with current element
[time]
O(n^2)
[space]
O(1)

[gist]
https://gist.github.com/A30041839/5514a3bc3e738db22054
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-15 11:30:46 | 显示全部楼层
【解题思路】
  1. 用hashtable 存数据,遇到重复的就删除。
  2. 两个指针前后扫一边
【时间复杂度】
1. O(n), 2.O(n^2)
【空间复杂度】
1. O(n) 2. O(1)
【gist link]
https://gist.github.com/songpu2015617/767122161cdf0f583ddc
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-5-26 11:24:16 | 显示全部楼层
【解题思路】   1. Use hashtable to store the data element for visited nodes, compare newly visted node
        to see if its data is already in the table. If yes, remove the duplicate, else add its data
        into the table.

   2(No temporary buffer). Use two pointers for two layers iteration.
【时间复杂度】 O(n) for 1, O(n^2) for 2
【空间复杂度】O(n) for 1, O(1) for 2
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_1.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)


回复 支持 反对

使用道具 举报

voiding 发表于 2015-5-30 06:16:24 | 显示全部楼层
【解题思路】
Go through the linked list, if it's a new value, then store it in a hashtable. If it already exists in the hashtable, then skip the node.
Using dummy head makes it easier to code.
   
【时间复杂度】
O(N)
【空间复杂度】
O(N)

Code link
https://gist.github.com/mogutou1214/e5a233231944ad32b50d
回复 支持 反对

使用道具 举报

DownToEarth 发表于 2015-6-22 05:10:21 | 显示全部楼层
coperdli 发表于 2015-4-10 09:37
解题思路:目前只想到一种糟糕的方法,当遍历整个链表时,将剩余链表部分钟与当前元素值相同的节点统统从链 ...

请问一下这个题怎么用排序做?排序完后,原始linked list的结构就变了再去remove的话能行吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 11:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表