cc150_2.3,2.4

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

public static boolean deleteNode(LinkedListNode n){
 if(!n || !n->next) return false;
 n.data = n.next.data;
 n.next = n.next.next;
 return true;
}

2.4 Write code to partition a linked list around a value x, such that all nodes less than x
come before alt nodes greater than or equal to x.

public LinkedListNode partition(LinkedListNode node, int x){
  LinkedListNode index = node, cur = node;
  while(cur){
     if(cur.data < x){
            int temp = cur.data;
            cur.data = index.data;
            index.data = temp;
            index = index.next;
     }
    cur = cur.next;          
    }
 return node;
}

singleton pattern

deal with multithreading:
1, synchronization: if it's used rarely in the application
public class Singleton{
  private Singleton(){}
  private static Singleton  uniqueInstance;
  public static synchronized Singleton getInstance(){
    if(uniqueInstance == null){
        uniqueInstance = new Singleton();
    }
    return uniqueInstance;
  }
 // other methods
}

2， make an eagerly created instance

public class Singleton{
  private Singleton(){}
  private static Singleton  uniqueInstance = new Singleton();
  public static  Singleton getInstance(){
    return uniqueInstance;
  }
 // other methods
}

3, double check lock

public class Singleton{
  private Singleton(){}
  private static volatile Singleton  uniqueInstance;
  public static Singleton getInstance(){
    if(uniqueInstance == null){
      synchronized(Singleton.class){
        if(uniqueInstance == null) 
          uniqueInstance = new Singleton();
       } 
    }
    return uniqueInstance;
  }
 // other methods
}

cc150_2.2

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

LinkedListNode  nthToLast(LinkedListNode head, int k) {
  if(k <= 0) return null;
  LinkedListNode prev = head;
  LinkedListNode cur = head;
  while(cur && k > 1){    
     cur = cur.next;
     k--;
  }
  if(!cur) return null;
  while(cur.next){
     cur = cur.next;
     prev = prev.next;
  }

 return prev;
}

cc150_2.1

Write code to remove duplicates from an unsorted linked list.

//method: hashtable
public static void deleteDups(LinkedListl\lode n) {
   Hashtable table = new Hashtable();
   LinkedListNode prev = null;
   while(n){
       if(table.containsKey(n.data)){
          prev.next = n.next;
      }
      else table.put(n.data, true);
      n = n.next;
   }

}

tips: Hashtable vs HashMap
There are several differences between HashMap and Hashtable in Java:

1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
3. One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable

cc150_1.8

Assume you have a method isSubstring which checks if one word is a substring
of another. Given two strings, si and s2, write code to check Ifs2 is a rotation of si
using only onecalltoisSubstring (e.g., "waterbottLe" is a rotation of "erbottLewat").

public boolean isRotation(String si, String s2){
  if(s1.length() != s2.length() || s1.length() == 0) return false;
  return isSubstring(s1+s1, s2) ;
}

cc150_1.7

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

public void setZeros(int[][] matrix) {
  boolean[] column = new boolean[matrix[0].length];
  for(int i = 0; i < matrix.length; i++){
     for(int j = 0; j < matrix[0].length; j++){
          if(column[j]) continue;
          if(matrix[i][j] == 0) {
           //set i-th row and j-th col zero
             for(int k = 0; k < matrix[0].length; k++){
                   matrix[i][k] = 0;
             }
             for(int k = 0; k < matrix.length; k++){
                   matrix[k][j] = 0;
             }
             //mark column and move to next row
             column[j] = true;
             break;
          }
    }
  }
}

cc150_1.6

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?

public void rotate(int[][] matrix, int n){
  for(int i = 0; i < n/2; i++){
   for(int j = i; j < n-1-i; j++){
      int tmp = matrix[i][j];
      matrix[i][j] = matrix[j][n-i-1];
      matrix[j][n-i-1] = matrix[n-i-1][n-j-1];
      matrix[n-i-1][n-j-1] = matrix[n-j-1][i];
      matrix[n-j-1][i] = matrix[i][j];
    }
  }
}

cc150_1.5

Implement a method to perform basic string compression using the counts of
repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

//use StringBuffer to avoid useless copying
public String compressBad(String str){
   int  count = 1, n = str.length();   if(n == 0) return null;
   StringBuffer res =new StringBuffer(); 
   for(int i = 1; i < n; i++){
      if(str.charAt(i) == str.charAt(i-1)){
          count++;
      }
     else {
          res.append(str.charAt(i-1));
          res.append(count);
          count = 1;
   }
 res.append(str.charAt(n-1));
 res.append(count);
 String cp = res.toString();
 if(cp.length() < n) return cp;
 else return str.
}

//if don't use StringBuffer, first figure out the new size, then do backtracking to get desired string from a new char array.

cc150_1.4

Write a method to replace all spaces in a string with '%20'. You may assume that the
string has sufficient space at the end of the string to hold the additional characters,
and that you are given the "true" length of the string. (Note: if implementing in Java,
please use a character array so that you can perform this operation in place.)

public void replaceSpaces(char[] str, int length) {
  int spacecount = 0, newlength, index;
  for(int i = 0; i < length; i++){
     if(str[i] == ' ') spacecount++;
  }
  index = length + (spacecount<<1);
  str[index--] = '\0';
  for(int i = length - 1; i >= 0; i--){
       if(str[i] != ' ') str[index--] = str[i];
       else{
          str[index--] = '0';
          str[index--] = '2';
          str[index--] = '%';
      }
  }
}

cc150_1.3

Given two strings, write a method to decide if one is a permutation of the other.

//method 1: sort and compare
String sort(String s){
  char[] content = s.toCharArray();
  java.util.Arrays.sort(content);
  return new String(content);
}

public boolean permutation(String s, String t){
  if(s.length() != t.length()) return false;
  return sort(s).equals(sort(t));
}

//method 2: hash and compare
public boolean permutation(String s, String t) {
  if (s.length() != t.lengthQ)  return false;
  int[] count = new int[256];
  for(int i = 0; i < s.length(); i++){
     int ch = s.charAt(i);
     count[ch]++;
  }
 for(int i = 0; i < s.length(); i++){
     count[ch]--;
    if(count[ch] < 0) return false;
  }

  return true;

}

cc150_1.1

1.1 Implement an algorithm to determine if a string has all unique characters. What if
you cannot use additional data structures?
//if it's ASCII characters: 256 candidates
public boolean isUnique(String str){
  if(str.length() > 256) return false;
  boolean[] v = new boolean[256];
  for(int i = 0; i < str.length(); i++){
      int ch = str.charAt[i];
      if(v[ch]) return false;
      v[ch] = true;
  }
  return true;
}

//use bit to save space: assume that it's a~z characters: 26 candidates, so one int = 32 bits is enough.
public boolean isUnique(String str){
  int checker = 0;
  for(int i = 0; i < str.length(); i++){
    int ch = str.charAt[i] - 'a';
    if( (checker & (1<<ch)) ) return false;
    checker |= (1<<ch);
  }
  return true;
}