查看: 2821| 回复: 16
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。




上一篇:如果这样的类生成,该怎么办?
下一篇:【第三轮】7.7-7.13 CareerCup 4.1
全局:
【解题思路】
这题挺简单的,重点在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
回复

使用道具 举报

推荐
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
回复

使用道具 举报

🔗
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
回复

使用道具 举报

🔗
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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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