[第二轮] 3/11-3/17 CareerCup 3.7

An animal shelter holds only dogs and cats, and operates ona 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 selectwhether they could prefer a dog or a cat (and will receive the oldest animal ofthat type). They cannot select which specific animal they would like. Createthe data structures to maintain this system and implement operations such asenqueue, dequeueAny, dequeueDog and dequeueCat. You may use the built-inLinkedList data structure.

发帖规范:

http://www.1point3acres.com/bbs/thread-48094-1-1.html

http://www.1point3acres.com/bbs/thread-32423-1-1.html

We will use an uni-directional linked list as the underlying data structure, find and dequeue the first node that matches the target type (dog or cat) while iteratiing the list. dequeue methods retruns null if no element could be dequeued.
enqueue : O(1)
dequeueAny : O(1)
dequeueDog : O(N)
dequeueCat : O(N)

https://gist.github.com/Zuohr/5128157

https://gist.github.com/ThunderXu/5128203
use a list<Animal> in C++

Same as ls...
https://github.com/moophis/careercup/blob/master/3.7.cpp

One Data structure consisted of two queues built by LinkedList within time_tag. one is for the cat, the other is for the dog.
enqueue : O(1)
dequeueAny : O(1)
dequeueDog : O(1)
dequeueCat : O(1)

题目不是很难。。。但是用到了oo的思想，J2SE不熟的情况去学j2ee真是纯傻逼的行为，白白浪费了一周时间。。。。。
* 包里别的文件是自己写的队列的实现。。。

https://github.com/1094401996/Ca ... /AnimalShelter.java

moophis 发表于 2013-3-10 20:33
Same as ls...
https://github.com/moophis/careercup/blob/master/3.7.cpp

I've got a problem: when there is no dog in the shelter, and I call dequeueDog(), VS2010 shows "Debug Assertion Failed". Expression: list iterator not dereferencable.

I've copied yours to test, same problem occured. How to solve?

宋小宝Dani 发表于 2013-3-19 13:24
I've got a problem: when there is no dog in the shelter, and I call dequeueDog(), VS2010 shows "De ...

I put a special enumeration invariable called "None". If there is no such kind of animal to pop, you will get a "None", which prints 2 on your console. I use g++ to compile my code and it should be fine, I do not know what is like on your VS2010 environment. Sorry.

https://github.com/quantumrose/C ... .7.AnimalQueue.java

类似EchoMemory
用了两个队列 dog cat 每个节点增加序号
复杂度都是O(1)
https://github.com/flabby/CareerCup/blob/master/3.7.cpp