【第三轮】7.7-7.13 CareerCup 3.7

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

【解题思路】
这题挺简单的，重点在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

【解题思路】
开始没看见“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

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

【解题思路】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

【解题思路】two queues for cats and dogs, compare arrive time to dequeue
【时间复杂度】O(1)
【空间复杂度】O(N)
【gist link】https://gist.github.com/yokiy/de756effa80ea6f5d112

【解题思路】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

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

【空间复杂度】
O(N)

【gist link】https://gist.github.com/xun-gong/e8ee632b8455e6dd0ef0

【解题思路】
用两个LinkedList
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q3_7

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