CS计算机代考程序代写 junit algorithm Java data structure scheme cache UC Berkeley – Computer Science

UC Berkeley – Computer Science
CS61B: Data Structures
Final, Spring 2016
This test has 13 questions worth a total of 100 points. The exam is closed book, except that you are allowed to use three pages (both front and back, for 6 total sides) as a written cheat sheet. No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. ​Write the statement out below in the blank provided and sign. You may do this before the exam begins. A​ny plagiarism, no matter how minor, will result in an F.
“I have neither given nor received any assistance in the taking of this exam.”
Video walkthrough: Nonexistent, sorry 🙁
_______________________________________________________________________________________
_______________________________________________________________________________________
Name: ________________________ SID: ________________________ Exam Room: _________________ Primary TA: _________________
Signature: _______________________________
Your 3­Letter Login: _________
Name of person to left: _____________ No ID: ______ Name of person to right: _____________ No ID: ______
Tips:
● There may be partial credit for incomplete answers. Write as much of the solution as you can, but bear in
mind that we may deduct points if your answers are much more complicated than necessary.
● There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do
not get overly captivated by interesting design issues or complex corner cases you’re not sure about.
● Not all information provided in a problem may be useful.
● Unless otherwise stated, all given code on this exam should compile. All code has been compiled and
executed before printing, but in the unlikely event that we do happen to catch any bugs during the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile.’
● The exam roughly increases in difficult as you approach the end.
Problem
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Points
0.5
8
8
6
12
7.5
4
5
0
10
6
10
13
10
Optional. Mark along the line to show your feelings Before exam: [:( ​_​___________________☺​]​. onthespectrumbetween:(​a​nd☺​.​ Afterexam: [:​( _​___________________☺​]​.

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
0. S​o It Begins III (​0.5 points). Write your name and ID on the front page. Circle the exam room. Write the names of your neighbors. If a neighbor is missing their ID, make sure to mark No ID in the appropriate blank. Write and sign the given statement. Write your login in the corner of every page.
1 . G​ i r a p h a g e ( 8 p o i n t s ) . ​ F o r y o u r c o n v e n i e n c e , w e h a v e p r o v i d e d 3 c o p i e s o f t h e g r a p h f o r p a r t s a t h r o u g h c .
a. (​2 pts)​For the graph above, give the vertices in the order they’d be visited by depth first search starting from vertex A, assuming that we always visit alphabetically earlier vertices first if there are multiple valid choices. You may not need all blanks. The alphabet is ABCDEFG.
___A___ ___​B​____ ___​D​____ ___​E​____ ___​G​____ ___​C​____ ___​F​____ _______
b. (​2 pts) F​or the graph above, give the vertices in the order they’d be visited by breadth first search starting from vertex D, assuming that we always visit alphabetically earlier vertices first if there are multiple valid choices. You may not need all blanks.
___D___ ___​A​____ ___​E​____ ___​B​____ ___​C​____ ___​G​____ ___​F​____ _______
c. (​2 pts) F​or the graph above, give the vertices in the order they’d be visited by Dijkstra’s algorithm starting from vertex A, assuming that we always visit alphabetically earlier vertices first if there are multiple valid choices. Assume that “visiting a vertex v” means “relaxing all of the edges out of v”. You may not need all blanks.
___A___ ___​C​____ ___​B​____ ___​D​____ ___​E​____ ___​G​____ ___​F​____ _______ Dijkstra’s works by expanding the node that is the least distance away from A first.
d. Suppose we are trying to find the shortest path from A to G. Give an example of a heuristic function for which A * r e t u r n s t h e w​ r o n g s h o r t e s t p a t h s t r e e ​. S p e c i f y y o u r h e u r i s t i c f u n c t i o n b y c i r c l i n g ​o n e n u m b e r ​f o r ​h ( E ) . ​ h(A)= 0
h(B)= 3
h(C)= 2
h(D)= 2
h(E)= ­4 1 2 5 ​8​ ​14 h(F)= 1
h(G)= 0
2

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
Byselectingalargevalueforh(E),A*searchwillprioritizesearchingthe bottomroutelowly,andthusreturnsthenon­optimaltopsolutionwhenitfinds G.
2. S​orting (8 points). a​) (​6 pts) B​elow, the leftmost column is an array of strings to be sorted. The column to the far right gives the strings in sorted order. Each of the remaining columns gives the contents of the array during some intermediate step of one of the algorithms listed below. Match each column with its corresponding algorithm. You will use each answer once. Write your answer in the blanks provided.
7777 1979 1979 7777 2001 1234 1234 2001 1234 2001 7777 8009 2001 1979 3015 1984 2015 4444 3015 3015 1981 2015 1981 2048 2015 2015 2015 1984 2048 2001 3015 7450 2016 2048 2001 8009 2015 4444 3015 2048 1981 2015 1979 2048 4500 2016 9150 1979 2016 7777 2016 7450 2001 1234 2016 2048 9150 3015 7777 1979 4444 1984 3015 4500 4500 7777 4500 7450 4500 4444 7450 4444 8009 2048 4500 7450 4500 4444 7777 9150 1981 7777 4444 7450 1234 7777 1234 1234 7777 7777 7777 1984 7450 1984 1984 1979 9150 7777 2016 8009 2016 8009 1981 7777 8009 1981 9150 1981 9150 1984 8009 9150 ­­­­ ­­­­ ­­­­ ­­­­ ­­­­ ­­­­ ­­­­
_1_ _​6​__ _​2​__ _​4​__ _​5​__ _​3​__ _7__
1:Unsorted,2:Insertion,3:Quick,4:Heap,5:LSD,6:MSD,7:Sorted
Column2issortedbythethousandthsplace=>MSDSort Column3isperfectlysortedexceptforthelastfournumbers,whichareuntouched=> InsertionSort Column4isinheapform,withthelast2maxelementsinitscorrectplace=>Heap Ifyouignorethethousandthsplaceofalltheelementsofcolumn5,itisinorder=>LSD Thesecondtolastcolumnimmediatelyputsthefirstelementinthecorrectplace=>strongly hintsQuickSort
Notes:
● Quicksort is non­random and uses leftmost item as a pivot. The pivoting strategy is the Hoare two­pivot
strategy, discussed in class.
● Insertion, Heapsort, LSD Radix Sort, and MSD Radix Sort as described in class.
b) (​1 pt)​One way to sort N items is to insert them randomly into a left leaning red black tree, and then traverse the LLRB. Which traversal should we use in order to print out the keys in sorted order? Circle one:
Preorder Inorder Postorder Reverse­Preorder Reverse­Postorder
3

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
c) (​1 pt)​Θ(N*log(N))​What is the worst case runtime of the sort described in part b? ​Give your answer in Big Theta notation in terms of N.​Put your answer in the given blank.
4

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
a. (​4 pts) C​onsider the following unsorted array, and the array after an unknown number of iterations of selection sort as discussed in class (where we sort by identifying the minimum item and moving it to the front by swapping). Assume no two elements are equal.
Unsorted:
After ? Iterations of Selection Sort:
For each relation, c​ircle​<, >, or ? if there is insufficient information to determine the relation between the two objects. For example, if you believe that is greater than , you’d circle the > on the first line.
b. (​2 pts) S​uppose we have a graph G. All of G’s topological sorts are listed below. I​n the space to the right, fill in the a​djacency list​for G.​There may be more than one right answer. Don’t worry about the exact formatting for your answer. As long as it is an adjacency list and it is easy to understand, we will accept your answer. ​Graph drawings will be given only partial credit ­­ please fill out the adjacency list! ​There are multiple answers. The minimal one is given. Note, topological sorts only exist for directed graphs!
1234567 1234657 1324567 1324657
3. Reverse Engineering (6 Points).
5

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
4 . F​a c t s ( 1 2 P o i n t s )
a. (7 pts) FSacginorstt.​You will be given an answer bank, each item of which ​may be used multiple times.
You may not need to use every answer.
Word Bank
A. QuickSort (non­random, in­place using Hoare partitioning, and choose the leftmost item as the pivot) B. MergeSort
C. Selection Sort
D. Insertion Sort
E. LSD Sort
F. MSD Sort
G. HeapSort
N. (None of the above)
Questions
List all letters that apply. List them in alphabetical order, or if the answer is none of them, use N. ​All answers refer to the entire sorting process, not a single step of the sorting process.​For each incorrect letter (either additional or missing), you will lose half credit for that blank.
A, B, C bounded by Ω(N log N) lower bound. N​ote: Insertion and heapsort can be linear time.
B, G is a comparison sort and has worst case runtime that is asymptotically better than Quicksort’s worst case runtime.
C
A, B, D N
in the worst case, performs Θ(N) pairwise swaps of elements. comparison based sort, and never compares the same two elements twice. runs in best case Θ(log N) time for certain inputs.
b)​T​ree Facts (5 pts).​Answer ‘True’ or ‘False’ for each of the statements below.
Free Inserting a single item into a “bushy” (balanced) BST with N items takes Θ(log N) time in all cases. ​Note:
We took either True or False for this one, since bushy could be interpreted to mean h = Θ(log(N)) False Inserting a single item into a heap with N items takes Θ(log N) time in all cases.
True The height of a BST with N items is O(N). (Note the Big O).
False Suppose X is a valid BST containing integers. If we square all values in X, the result is always a BST. True All valid left leaning red black trees are valid BSTs.
False All valid weighted quick union trees are valid BSTs.
Free The parent of the second largest item in a max heap is always the root. ​Note: We took either true or false
for this one, since it was unclear how to resolve duplicates.
False The parent of the parent of the third largest item in a max heap is always the root.
True The height of a perfectly balanced quadtree with N items is ​asymptotically​the same as the height
of a 2­3 tree with N items.
False Finding all matching tiles in getMapRaster using a quadtree takes Θ(log N) time in all cases, where N is
the number of png files.
6

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
5. (7.5 pts) Graph Algorithms.​For each statement below, circle either ​TRUE o​r F​ALSE.​I​f your answer is FALSE, draw a counterexample graph in the given box, and if applicable, provide a starting vertex.​Please use u​nique e​dge weights for any weighted graphs. If your answer is true, don’t do anything in the box/blank. ​Any counterexamples should have 5 vertices or less. ​Keep in mind these are only worth 1.5 points each!
FALSE:​The last edge added to the MST by Prim’s algorithm is always the highest weight edge in the MST. S t a r t i n g v e r t e x : _ _ _ A​_​_ _
FALSE:​The largest edge in a graph is never part of a SPT.
Starting vertex: ___E​ither_​__
FALSE:​On a graph of 4 or more nodes, DFS and BFS never visit vertices in the same order when run from the same start vertex.
S t a r t i n g v e r t e x : _ _ _ A​ o r D _​_ _
FALSE:​D​ijkstra’s algorithm always finds the shortest path in a directed acyclic graph, even if there are negative
edges:
S t a r t i n g v e r t e x : _ _ _ _ A​_​_ _ _
7

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
FALSE:​I​n any undirected graph, the shortests paths tree from any vertex always has total weight less than or equal to the weight of the MST for that graph.
S t a r t i n g v e r t e x : _ _ _ _ A​_​_ _ _
6. A​dvanced Hash Party (4 points).
( 4 p t s ) T​h e r e a r e o t h e r w a y s t o r e s i z e a h a s h t a b l e t h a n t h e w a y w e d i s c u s s e d i n l e c t u r e . F o r e a c h s c h e m e b e l o w , g i v e t h e a​m o r t i z e d ​b e s t a n d w o r s t c a s e r u n t i m e f o r a s i n g l e i n s e r t i o n o p e r a t i o n i n Θ n o t a t i o n i n t e r m s o f N , t h e number of items in the hash table. If the operation given could result in an infinite runtime, write “infinity” or ∞ inside the big Theta. Assume the hashCode function takes constant time. By the “best case”, we mean a set of items that are spread out nicely by their hashCode, and by the “worst case”, we mean a set of items that have the worst possible collisions by their hashCode. Define L to be the average number of items in each bucket. Assume resizing takes linear time. N​ote: For all answers below, L is bounded above by a constant, so we do not include them as part of our answers.
Best Case
Worst Case
Scheme
Θ( 1​)
Θ( N​​)
Quadruple # of buckets when L > 1.
Θ( 1​)
Θ( N​​)
Double # of buckets when L > 1/100.
Θ( N​​)
Θ( N​​)
Increases # of buckets by 10 when L > 1
Θ( 1​)
Θ( ∞​​)
Doubles # of buckets until no bucket has more than 5 elements in it. This may result in multiple doublings!
Enjoy​this s​pace.​
8

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
7 . ​A​ s y m p t o t i c s ( 5 p o i n t s ) . ​ F o r p a r t s a , b , a n d c , a s s u m e t h a t f r u n s i n Θ ( N ) t i m e ( i n a l l c a s e s ) , g r u n s i n Θ ( N ​2 ​) time (in all cases), and h runs in O(N​2​) time (in all cases). Assume that each function returns an array of the same length as its input. N​ote, the runtime for h is given in O notation, not Θ notation.
a) (1 pt) G​ive the runtime to complete the doStuff1 method in Θ notation if possible, or O notation otherwise. Your answer should be simple, with no unnecessary leading constants or unnecessary summations. Write your answer in this blank: _______​􏰃(N​2​)_​_________
publicstaticint[]doStuff1(int[]x){ intN=x.length; int[]effedX=f(x);
int[]newArray=newint[N]; for(inti=0;iV​get​(HashMaphm,Kkey,VdefaultValue)
/ * r e t u r n s t h e l a r g e s t v a l u e i n t h e H a s h M a p h m ​( l i n e a r t i m e ) ​ * / ● publicstaticV​maxValue​(HashMaphm)
● Also, don’t forget about ​Math.max​(intx,inty)​and ​Math.min(intx,inty)
Hint: You can use the subtraction operator ­ to find the distance between two char values without casting to int. For example: ​’b’­’a’​evaluates to 1. Similarly: ​’c’­1e​valuates to ​’b’.​ publicstaticintllans(char[]input){
HashMapcache=newHashMap(); cache.put(input[0],1);
for(inti=1;i{
privateSetchildren=newTreeSet();
1
1
0
5
3
4
1
0
privateintdig; privatebooleanexists;
}…
c o l l e c t ( N o d e z , L i s t < I n t e g e r > m a t c h e s , i n t t o p D i g i t s ) ​i s a m e t h o d w h i c h f i n d s a l l k e y s i n t h e subtrierootedat​z,​appends​topDigits​toeachkey,andaddstheresultto​matches.​Example: ​collect(z1, matches,99)​would add ​[991,99100,9910110,991123,991134]​to ​matches,​assuming that ​z1​is t h e 1 c h i l d o f t h e r o o t . T h e r e i s n o s p e c i f i c r e q u i r e d o r d e r i n g f o r t h e k e y s a d d e d b y a c a l l t o ​c o l l e c t . ​
Give the results of calling ​collect(z10,matches,1),​assuming ​z10​is the ​0 child of the 1 child​of the root​.​Use exactly the two blanks provided below. Either order is fine. Hint: Unlike our example above with topDigits=99,​your answer should exactly match two keys in the trie from part a​! This problem should be easy and is setting you up for part c.
____1​00_​___ ___1​0110_​__
//thisdigit //trueifthisitemexists
{dig=x;} publicintcompareTo(Nodex) {returnthis.dig­x.dig;}
publicNode(intx)
15

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
c. (5 points) F​ill in the private ​collect​method so that it behaves as in part b. Note that if ​topDigits​is 0 you should not prepend a zero (in fact, it’s impossible), i.e. ​collect(z10,matches,0)​would add [​0,110].​ A s s u m e t h a t ​c o l l e c t ​i s n e v e r c a l l e d o n t h e r o o t , s o y o u d o n ’ t n e e d t o w o r r y a b o u t a n y w e i r d e d g e c a s e s . ​N o t e that this method is a method of ​TrieIntegerSet,​not N​ode.​
/*Collectsalistofallkeysinthesubtrierootedatx,assumingthat *theyareallprefixedbytopDigits.Assumenevercalledonroot.*/
privatevoidcollect(Nodex,Listmatches,inttopDigits){ i f ( ​x = = n u l l ​) { ​r e t u r n ​; }
i f ( ​x . e x i s t s = = t r u e ​) { ​m a t c h e s . a d d ( t o p D i g i t s * 1 0 + x . d i g ) ​; } for(​Nodechild:x.children​){
​collect(child,matches,topDigits*10+x.dig​);
__________________________________________________________________; }
} ​//Youmaynotneedalllines.Thisisatimeconsumingproblem.
d. (5 points) F​ill in the private method below such that ​publicfindRepeaters​returns a list of all numbers in a ​T r i e I n t e g e r S e t ​t h a t h a v e a n y c o n s e c u t i v e r e p e a t e d d i g i t s . F o r e x a m p l e , f o r t h e T r i e f r o m p a r t a , t h i s m e t h o d would return ​[100,10110,1123,1134,355].​It would not return ​2101​since the 1s are not consecutive. You may use ​collect​from part c even if you didn’t finish it or your answer is incorrect. You do not need to use t h e m o d u l u s o p e r a t o r % f o r t h i s p r o b l e m . O r d e r d o e s n ’ t m a t t e r . T h i s m e t h o d a l s o b e l o n g s t o ​T r i e I n t e g e r S e t ​.
publicListfindRepeaters(){ Listmatches=newArrayList(); ​findRepeaters(root,matches,0);
returnmatches;
}
/**Findsallkeysinthesubtrierootedinxthathaveatleastone *pairofrepeateddigits,assumingtheyareallprefixedbytopDigits.*/
p r i v a t e v o i d ​f i n d R e p e a t e r s ​( N o d e x , L i s t < I n t e g e r > m a t c h e s , i n t t o p D i g i t s ) { i f ( x = = n u l l ) { ​r e t u r n ​; }
for(Nodechild:x.children){
​if(x.dig==child.dig){ collect(child,matches,topDigits*10+x.dig);
}else{ findRepeaters(child,matches,topDigits*10+x.dig);
}
____________________________________________________________________
____________________________________________________________________ }
//Youmaynotneedalllines.Thisisatimeconsumingproblem.
}
16

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
13. A​(Fond?) Farewell to 61B (10 points).​In your life after 61B, you’ll often need to use one data structure to i m p l e m e n t a n o t h e r . I n t h i s p r o b l e m , y o u ’ l l b u i l d a F I F O ( f i r s t ­ i n f i r s t ­ o u t ) q u e u e o f t y p e ​ ​M a g i c S t r i n g Q u e u e which has two operations that are just like a regular queue, namely ​enqueue​and ​dequeue.​For example, if we m a d e t h e f o l l o w i n g c a l l s i n t o a n i n i t i a l l y e m p t y ​M a g i c S t r i n g Q u e u e ​c a l l e d ​m q : ​
● mq.enqueue(“giraffe”),mq.enqueue(“zebra”),mq.enqueue(“alf”) ● System.out.println(mq.dequeue())
T h e n t h e p r i n t s t a t e m e n t w o u l d p r i n t ​“ g i r a f f e ” ​s i n c e i t w a s a t t h e f r o n t o f t h e q u e u e . I n s t e a d o f u s i n g a n a r r a y or linked list to build the queue, you must use a ​MagicBag,​which has the following operations:
publicvoidadd(Kkey):addsanitemoftypeKtotheMagicBag,orreplaces itifthereisalreadyanitemthat.equalskey
publicKremove(Kkey):removestheitemthat.equalskey(ifitexists) andreturnsthatiteminthebag,ornullotherwise
D e s c r i b e h o w y o u ’ d b u i l d a ​M a g i c S t r i n g Q u e u e ​u s i n g o n l y a ​M a g i c B a g ​a n d ​a c o n s t a n t a m o u n t o f a d d i t i o n a l memory.​Solutions that use more memory will be given zero points.}
N o t e s : Y o u m a y a s s u m e t h a t e n q u e u e ( ) i s c a l l e d a t m o s t 1 m i l l i o n t i m e s . Y o u r ​M a g i c S t r i n g Q u e u e ​m​ a y o n l y u s e a c o n s t a n t a m o u n t o f m e m o r y , e x c e p t f o r a s i n g l e ​M a g i c B a g ​w h i c h m a y u s e l i n e a r m e m o r y . ​I t i s O K t o create a single helper class (see part b of this problem). Strings are immutable in Java.
a) List the instance variables of your M​agicStringQueue.​
classMagicStringQueue{ MagicBagbag;
intaddNumber,removeNumber; }
b) Very briefly describe your helper class (if needed). List its instance variables as well as any methods. Briefly describe how any such methods work. Include any default methods that you @Override.
classHelper{ Stringvalue;
intposition;
publicHelper(Stringvalue,intposition); publicbooleanequals(Objectobj); //Dependentonposition publicinthashCode(); //Consistentwith.equals
}
c ) D e s c r i b e h o w y o u r ​M a g i c S t r i n g Q u e u e ’ ​s e n q u e u e a n d d e q u e u e o p e r a t i o n s w o r k i n t e r m s o f i t s i n s t a n c e variables (including any calls to ​MagicBag’​s methods). You may use pseudocode if you’d like. Do not write Java code. Don’t worry about handling dequeueing from an empty queue.
17

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
Use two integer instance variables in MagicStringQueue to keep track of (1) the “queue position” of the first item i n t h e q u e u e ( r​e m o v e N u m b e r )​, a n d ( 2 ) t h e q u e u e p o s i t i o n t h a t s h o u l d b e u s e d f o r t h e n e x t i t e m t h a t ’ s e n q u e u e d (a​ddNumber)​. The queue position of the first item enqueued will be 0, the position of the next item will be 1, and so on. When an item is enqueued, it will be assigned a position equal to ​addNumber​, and a​ddNumber​will be incremented by 1.
The MagicBag will store a helper class with two instance variables: a String representing the item in the queue, and an integer representing the queue position. To make it possible to implement the dequeue operation, the helper class should override the .equals() method to only compare the position. To dequeue something from the queue, the dequeue method can create a dummy instance of the helper class with position equal to ​removeNumber and then call the remove() method of MagicBag using that dummy object. Before returning, the dequeue method should increment r​emoveNumber.​
Orinpseudocode:
enqueue(string){ Helperh=newHelper(string,toAdd); bag.add(h);
incrementaddNumber;
}
dequeue(){ Helperh=newHelper(“”,toRemove); IncrementremoveNumber; returnbag.remove(h).value;
}
Solution B (no credit): C​reate a Node helper class with reference to other nodes. Store a Node instance variable in MagicStringQueue. Use the nodes to store the items that need to be enqueued/dequeued, effectively reusing the idea from LinkedListDeque from project 1a. This approach was not allowed even if you put all the nodes in a MagicBag. In this solution, the MagicBag is useless, and you’ve just built a linked list, which is forbidden by the problem statement.
Solution C (no credit):​Create an array with 1,000,000 items and keep two pointer indices to the front and the back. This approach is not acceptable because you are just using an array, and are basically redoing ArrayDeque from project 1a. In this solution, the MagicBag is useless, and you’ve built and array list, which is forbidden by the problem statement.
Also of note: Some of you made notes to the effect of “1,000,000 is constant”. Technically yes, but by that logic ArrayLists use constant time and memory since no array can be larger than 2,000,000,000 items, and taking it
18

UC BERKELEY, CS61B FINAL, SPRING 2016 Login:​_______
even a bit further, ALL data structures we’ve discussed in the course use constant time and memory since the memory of real computers is finite.
Solution D: M​agic bag has two String instance variables: ​first ​and l​ast​. Class H​elper​has two String instance variables, i​tem a​nd p​revious,​and overrides the .equals method to only compare ​item​. To enqueue, create a new Helper with i​tem​set to the new String and p​revious ​set to ​last,​and then set ​last e​qual to the new String (also set
f i r s t ​e q u a l t o t h e n e w S t r i n g , i f t h e M S Q i s e m p t y ) . T o d e q u e u e , s e t a v a r i a b l e ​t e m p e​q u a l t o ​f i r s t ​, s e t ​f i r s t ​e q u a l t o MagicBag.remove(new Helper(item = first, previous = “”)).previous, and return t​emp.​This solution was unexpected and a very clever way of essentially creating a linked list, but without actually using a linked list or nodes. Unlike solution B, the MagicBag is essential to the functioning of this implementation, rather than an afterthought to satisfy the problem statement. Unfortunately, It did not receive full credit because it does not handle duplicate Strings in the queue correctly (e.g., if “giraffe” is put in the queue multiple times at different locations).
19