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.

1.7 matrixSetZero

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column is set to 0

My first thought to simply iterate through the matrix, and when it hit a zero, then set the entire row/col to zero. The problem, I quickly realized, is that this would cause the algorithm to make the entire matrix set to zero, because it will keep hitting zeroes.

Therefore, you need to track the zeros separate from the actual matrix. So we need a second matrix. But do we really need a second matrix? After all, all we need to know is that if there is at least one zero in that row, not the exact positions of the zeros in the row. So, I'm going to go for 2 arrays rather than 1 whole matrix.

1.6 rotateMatrix

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place?

So the only way I can think of doing it "in place" is if you save one spot. Let me explain. If you have "ABCD" and you want to shift everything forward ONE...you save the "D', shift it to "_ABC", then insert the D. Except this is one a one dimensional array, it's a two dimensional one.

We do this in layers. Say have we have a 4x4 matrix, first we start at "layer 1", where its just the outside border. Then we do layer "2", where its the inside 4 blocks. Then we're done. So we only do N/2.

Have not doublechecked this code yet.

1.5 replaceSpace

Write a method to replace all spaces in a string with ‘%20’

Tough thing about this method will be how to replace a single char with 3 chars. We don't want to have to increase the array size everytime we hit a space because that wouldn't be very memory efficient. We want to increase the array size once and be done with it. Therefore, we want to find out how many spaces are there to begin with.

PsuedoCode


Now that we have the number of spaces, we need to increase the size of the array by 2*spaces. Next, we want to keep track of where we are in the old and new array. That way we can correctly put things from the old position to the new, adjusted position.

Lastly,we want to start from the back and move backwards. Because the back is filled with "null" chars, we won't lose any information.

1.3 removeDuplicates

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer  NOTE: One or two additional variables are fine. An extra copy of the array is no

It took me a while to understand the solution to this problem, not sure why.

If we ran the word "badboy" through this code, we would expect "badoy0" to return, where 0 is the end of unique characters. "ababab" would turn into "ab0bab." This is because we cannot create another array, so we must stick with the original string size.

First, we need to change the string input into a character array.
Next, we introduce a variable "tail" which keeps track of how far we have moved in the array. Tail position will start at the beginning of the array and move forward everytime we confirm that the current letter is not a duplicate. It DOES NOT move forward if we discover that the letter is a duplicate, that way we can overwrite the duplicate in the next iteration.

Code:

void removeDuplicates(char[] str)
   int tail = 1;
   for (int i=1; i< str.length ; i++) //we start at 1 because we know the first character has to be unique
           int j;//we need j outside of the for loop, so we must declare outside
           for (j=0; j<tail; j++ )
                   if (str[i] == str[j])
                          break;
            if ( j == tail ) //this means we never break-ed
                   str[tail] = str[i]
                   tail++ //tails is only incremented if there wasn't a duplicate
   str[tail] = 0; //add 0 to end of correct letters

this runtime is actually pretty bad, O(n^2). Not sure if there is a better way to do it if you aren't allow to create another string.

You could add error checking that if the string length is less than 3, just instantly stop.

PIE LinkedList Methds

public Class Node{
   public Node next;
   public int data;

public Node(int d){
this.data = d;
this.next = null;
}

public Class LinkedLists{
   public Node head;

   public LinkedLists(){ //constructor
     this.next = null;
    this.data = null;
}
  public Node AddToFront(int obj){
   Node newNode = new Node(obj);
   newNode.next = head;
   return newNode; //return new head
}

public Node Find(int data){
   Node next = head;
   while (next!=null && next.data !=data){
      next = next.next;
  }
  return next;
}

}

PIE Linked Lists

C++


public class Node {
   Node* next;
   object data;
}

public class LinkedList {
   Node* head;
}

Java

public class Node {
   public Node next;
   public object data;
}
public class LinkedList{
   public Node head;
}

Ruby (not sure about this)
Node = Struct.new(:next, :data)
list = Cell.new("head",nil)

1.2 Reverse a String

Given a string "abcd", write a function that would make it "dcba"

My idea was to basically swap the first and last element, then swap 2nd and 2nd to last element, etc...

psuedocode:

string Reverse(string input_string)
  int front = 0;
  int back = input_string.Length -1
  string reverse_string = new string(input_string.Length - 1)

while front < back
    reverse_string[front] = input_string[back]
    reverse_string[back] = input_string[front]
    front++
    back--
return reverse_string

1.1 Check if Unique String

Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures?

You could use a nested for loop, but that would you leave you at O(n^2) running time, which is never desired.

The best algorithm still hasto be O(n) because you must check every character at least once.

My approach is to have a separate boolean array that checks if the letter has been seen before. Use of the ASCII table is perfect here, because we can turn a CHAR into an INT. That INT can be the place in the array where we store our boolean value. For example, the string "aba" in ASCII is "65 66 65," where A=65. Well, if we take an Array[65] = true, when we hit the second "a" and check for Array[65], we can see that Array[65] has already been set true, which means this string has repeated "a."

Psuedocode:

CheckUnique ( string input)
Boolean IsInString[256] // 256 because there are 256 available ASCII characters
Change input to CharArray

FOR I from 0 to input_length
       ascii_number = Get_Ascii_number_of(input[i])
       IF IsInString[ascii_number] == true //this letter has already been set true before!!
             return False
       ELSE //never seen this letter before
             IsInString[ascii_number] = true //so set as true
 END FOR
//if you get here,we never hit the same letter twice
return True

improvements:
Space used can be smaller with you know that you are working with only alphabetical letters, and you can use toUpper or toLower to conserve even more space.