3.0 Stack and Queue Implementation

Stack
First In is Last Out.

Queue
First in is First Out

2.4 findBeginning

Given a circular linked list, implement an algorithm which returns node at the begin-
ning of the loop.

I'm still wrapping my head around this algorithm. Definitely not something I would've thought of on the spot, especially the second part.

Here's the algorithm steps.

1. Find out if it actually does have a loop by sending two runners through, one at normal pace, one at double the pace. If they hit, there is a loop.

2. Realize that the place it meets in is significant. Let's say it the list is this: 1->2->3->4->5->6->7->8->9->3. If we send "A" through the loop twice as fast as "B", they will actually always meet two after the "3", the beginning of the circle. Why is that?

Well. If there is an x amount of space to the first circular node, then by the time "B" the circular node actually enters the cycle, A will be x amount ahead of B. (If B goes 3, A will go 6. Therefore A is 3 ahead.)

Now, when will they meet? Well, if two runners at the track start at the same position, "A" runner going twice as fast as "B", "A" runner would lap "B" runner after two laps. However, what if "A" started with a "x" distance headstart? They would actually meet at 2 laps - x distance.

So here's what we do for the algorithm. We send A and B until they meet, A going twice as fast. We leave A at the meeting position, send B to the beginning. They are now both x distance away from the beginning of the cycle. So,now we move them forward at the same pace, until they meet. That is where the beginning is.

2.3 removeNode

Implement an algorithm to delete a node in the middle of a single linked list, given
only access to that node

Interesting algorithm. Say you have a->b->c->d and you want to delete B. Since it is a singly linked list, you only have access to b, c d, NOT A. So, instead of doing the normal delete, where you have a->c, and you're done, you overwrite b's data with c's data. Then you "delete" c, have b -> d. Even though you deleted the C node, you deleted B's data and kept C's node. So in fact, you did delete the correct Node.

2.2 removeNthToLast

Implement an algorithm to find the nth to last element of a singly linked list.

This was fairly easy once you figure out that you need two LLNODEs. You send the first node ahead n nodes from the head. Then you move the first node (starting n ahead) and the second node (starting at the head), move them forward one node at a time. When the first node hits the end, that means the second node is at the Nth to Last.

2.1.2 removeDuplicates (without buffers)

Again, we need to keep track of the previous node, so we can delete the current node. Because we cannot have a buffer, we loop through every previous (with "runner") to check for duplicates. This algorithm is O(n^2)

2.1 removeDuplicates (with buffer)

Write code to remove duplicates from an unsorted linked list

This longer than I care to admit to figure out/understand.

Basically, there are two parts this. We need to see if something is a duplicate, so I will use a hashtable to keep track of the different objects that I come across. Next, in order to remove a linkedlist node, we need to keep track of where the previous node is, that way we can do a

previous.next = currentNode.next. This will remove the currentNode from the Linked List.

1.8 isRotation

Assume you have a method isSubstring which checks if one word is a substring of
another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).

Man, these are the questions that really make you think outside of the box. My cs mind made me want to jump straight to for loops, and going through every rotation of the word with an O(n^2) algorithm, maybe more because isSubstring is probably O(n) or O(n^2).

However, the solution to this problem is just to double the word, "waterbottlewaterbottle," then use isSubstring, because that will cover all rotations. Quite a simple problem once you realize the solution.

Lastly, we need to do a length check. "a" could be a substring of "apples," but it's not a rotation.