一亩三分地论坛

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

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

[CareerCup] 【第三轮】7.7-7.13 CareerCup 3.7

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-6 20:49:33 | 显示全部楼层 |阅读模式

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

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

x
3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.You may use the built-in LinkedList data structure.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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



grassgigi 发表于 2014-7-6 23:25:14 | 显示全部楼层
Maintain two separate queues for dogs and cats.
tracking timestamp of when each pet was sent to the shelter(for dequeueAny operatioin)

【解题思路】
Maintain two separate queues for dogs and cats.

【时间复杂度】
O(1)

【空间复杂度】
O(N) - N is number of pets in shelter

【gist link】
https://gist.github.com/chrislukkk/dd3de2826162c1d403b2
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-7 00:48:06 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-7-7 01:05:18 | 显示全部楼层
【解题思路】
这题挺简单的,重点在design,而且还得知道java自带的LinkedList能干啥
Use two stacks, one for cats and one for dogs to keep track of the animals. Give each animal a timestamp to keep record of the order of when they are added to the shelter. Desigin data structures for Cat and Dog, and Animal.

【时间复杂度】
O(1)

【空间复杂度】
O(N) - N is number of animals in shelter

【gist link】
https://gist.github.com/XiaoxiaoLi/8809731a2943f5daa4e5
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-7 22:59:27 | 显示全部楼层

【解题思路】Use 2 queues to store cats and dogs, in dequeue, compare the oldest cat and dog
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/bitcpf/b74012a227ae4d1444a0
回复 支持 反对

使用道具 举报

pud 发表于 2014-7-8 03:21:00 | 显示全部楼层
【解题思路】two queues for cats and dogs, compare arrive time to dequeue
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/yokiy/de756effa80ea6f5d112
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-8 13:52:02 | 显示全部楼层
【解题思路】two queue; cats &dogs ,they are extended from animal.  Use some timestamps to mark when each animal was enqueued. Peek the head of cats or dogs then return the oldest.
【时间复杂度】o(1)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/02d64d36b92f031f3c87
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-8 22:34:04 | 显示全部楼层

【解题思路】
                  新来的动物都有一个time stamp(递增) , 我用了三个list : any, dog, cat.  具体就是push_back 和 pop_front
【时间复杂度】
O(1)

【空间复杂度】
O(N)

【gist link】https://gist.github.com/xun-gong/e8ee632b8455e6dd0ef0
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-9 01:17:56 | 显示全部楼层
【解题思路】
用两个LinkedList
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q3_7
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-9 12:52:55 | 显示全部楼层
本帖最后由 jason51122 于 2014-7-9 12:54 编辑

【解题思路】Use 2 linkedlist as 2 queues for dog and cat.
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/2936de75e6f1dd06d1b7
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-9 12:55:19 | 显示全部楼层
donnice 发表于 2014-7-9 01:17
【解题思路】
用两个LinkedList
【时间复杂度】

Please do not use characters to represent dog and cat. It's better to create 2 classes. Thanks.
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-9 19:15:56 | 显示全部楼层
jason51122 发表于 2014-7-9 12:55
Please do not use characters to represent dog and cat. It's better to create 2 classes. Thanks.

昨天没时间了…没必要写两个 class啊,两个list就够了,分别给猫狗起名,dequeue时输入名字,contains(String name)而已,小技术
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 09:30:35 | 显示全部楼层
【解题思路】
Use two linked list, one for cats, one for dogs
add timestamps to cats and dogs

【时间复杂度】
O(1)


【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/8a155f4feea9cf27df4d

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-12 08:36:40 | 显示全部楼层
【解题思路】
Use two linked lists for cats and dogs respectively;  use an extra attribute for animal " order " to record the time they enter the shelter.
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/jyhjuzi/de9393fb070b4061d34e
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-13 01:05:26 | 显示全部楼层
【解题思路】
Maintain two separate queues for dogs and cats.

【时间复杂度】
O(1)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/JoyceeLee/d530c6ba41dd9c16abcc
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-13 07:02:58 | 显示全部楼层
【解题思路】
Create two Queue Cats and Dogs, the class Cat and Dog inherits from Animal, use id to indicate the arrival time
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/896f3f2b5b67a0ee3340
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-14 04:17:33 | 显示全部楼层
【解题思路】
开始没看见“use the built-in LinkedList data structure” 就自己写了个queue, 直接用java.util.LinkedList<E> 也是大同小异
这题主要考design,用继承和多态区分dog和cat就可以了,至于queue,可以用generic也可以用多太写
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/Noahsark/9974157a98091e89773e
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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