San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1391|回复: 16
收起左侧

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

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

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

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

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
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
头像被屏蔽
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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 12:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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