Interface
there are a lot of benefits when we use interface to programming not class.
Client has many implementation for this interface from which choose the best suitable one. As we know List is a famous interface in java collections. so we have linked list which have good performance when insert at front. and we have array list implementation which random get is O (1).
when programmer do implementation, they can not know details of client need.
stack implementation
below picture is described how to use linkedlist to implement stack. stack also could be implemented by array.
below is array implementation
and we need to care two edge case. one is overflow, one is underflow.
overflow means array is full, we need to resize it. underflow means client pop on an empty array, we need to throw exception or return null.
so the next question is that how to resize?
how to shrink array?
if we halve size of array when array is one-half full.
it is terrible consider push - pop - push -pop when array is full
each operation takes time proportional to N
so now the stack have two implementation. when should we choose array, when should we choose linkedlist
if u want to make every operation time is little in the worst case. i mean even if one operation is cost too many time is disaster, u should choose linked list.
array implentation have good memory usage and good performance on amortized time. but sometimes when need to expand/resize, that operation will cost more time than regular ones.
Queue
queue is almost same as stack, except it is fifo, stack is lifo.
Generic
java generic have two benefits.
one is avoid casting in client, another is discover type mismatch in compile time instead of run time.
Autoboxing
Iterators
Bag
Quiz analysis
Q1
the stack is lifo, queue is fifo. when we want to out, we need to reverse elements in stack. so that's the usage of second stack.
Q2
the naive though for this problem, we keep two stack, one is original, another is keep the current max.
we can do better, because there are a lot of data redundancy in second stack.
we can only record the one which make the max changed idx.
then if we pop to that idx, we need to pop from max stack.
for example,
stack : 1,1,2,2,3
max val: 1,2,3
max idx, 0,2,4
Q3
Java generics. Explain why Java prohibits generic array creation.
first, java array are covariant, but java generic are not
Each object in Java has a "class" which can be retrieved at runtime, using the .getClass() method. When you use .getClass() on an array object, you get the "array class" representing that type of array. Arrays of different component types correspond to different array classes. So .getClass() called on an int array will return a different thing than .getClass() called on a String array. From any array object, we can query its (array) class at runtime, and then from that, get the component type of the array. That is what I meant that the array remembers its component type at runtime.
How does an object know its class? That's because it was provided explicitly when the object was created. The same applies for array objects. When you create an array, you must specify the type of array, including an explicit component type. However, Generic types in code are a compile-time illusion. When you have a type variable like T, code that uses that type cannot know what type T is; and in fact, the point is that the code must work with any type in the place of T. That is why the class or method is said to be "generic". That is what I meant when I said T represents a type that is unknown at runtime, and thus you cannot create an array of T since you cannot provide the component type needed to create the array.
Note that this contrasts with Generic containers. For example, new ArrayList<T>() is perfectly legal. You might ask, why is it possible to create a List of T, but not possible to create an array of T? Generic types in Java work very differently from array types. A new ArrayList<Integer>() object and new ArrayList<String>() object have the same "class" at runtime. That is, the type parameter is an illusion and it is not possible to tell at runtime whether a list is a list of String or list of Integer. Therefore, such containers do not know their component type at runtime; and correspondingly it is not necessary to know the component type at runtime to create such a container object.
Q4
Implement a deque with two stacks so that each deque operations takes a constant amortized number of stack operations
the thought is similar with the two stack implementing queue. we keep two stack, one the open for left, another is open for right. so offer first, go left stack, offer last, go right stack.
the hardest part is poll first or poll right when the left stack or right stack empty
we need to do a rebalance action like the Q1, we keep another auxiliary stack, to move half elements of not empty stack into it then move another half to the empty stack. then we move the auxiliary stack back.
Project Deques and Randomized Queues
https://coursera.cs.princeton.edu/algs4/assignments/queues/specification.php
this week project we can practice generic, interface. a lot of point in course mentioned u have a chance to practice.
for deque, i use linked list to implement and also i use dummy node to reduce the complexity of the code. the important thing is u not only need to implement correctness algorithm for this data structure but also handle edge case. i mean sometimes the client use your data structure in wrong way. u should mention them.
for randomized queue, i use array to implement, so we have to implement resize function to handle when the queue is full.
Bonus
the bonus on the permutation is that could we use only O(k) space to finish it.
let think from k = 1. how to use O 1 space to get random one value.
we keep a output value. first it should be the first element. then next element will have 1/2 chance to replace this output value. the third element will have 1/3 chance to replace output value
at now, the first element will have 1 * 1/2 * 2/3 = 1/3 in the output value
the second element will have 1/2 * 2/3 = 1/3
the third element will have 1/3
they are the same
so how to expand this algorithm to K elements.
assume k is 2, total element is 3, so we want each element have 2/3 chance in the result.
at first we put 2 element in randomized queue.
the next element will have 2/3 chance to replace one of element in queue
now the problem solve
so we can get the formula
first we put k element in randomized queue. then the next element we have k/i to replace it in the randomized queue. i is the index of i th element start from 1
take N =5, k= 3 as example
first put 1st, 2nd, 3rd into random queue
the 4th have 3/4 chance to replace one of them
the 5th have 3/5 chance to replace one of them
the 1st have 1 * (2/3 * 3 /4 + 1/4) * (2/3 * 3/5 + 2/5) = 3/5 in the queue
u can calculate by yourself for other elements.
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
