michaelniu

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

 * 1.is it only  ascII charactors
 * 2.use an  char Array with total 256 readable  charactors 
 * check if  any of element in the array contains value
 * like boolean [] exsiting 
 * if(existing[char] == true)
 * return false;
 * else 

michaelniu

public class ReverseString_1_2 {
/*1.2 Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)
 * Nothing special  to exchange the  i to  string lenghth -i-1 by useing  stringbuilder
 * O(n) space O(1)
 * */
	public static void main(String[] args ) {
		String test= "879-4uiordedpu;";
		System.out.println(reversString(test));
	}
	

michaelniu

/*
	 * 1.3 Given two strings, write a method to decide if one is a permutation
	 * of the other. 
	 
	 create a hashtable <Integer,Integer> Key is the char of the
	 * String element, value is the count of char in the string travese first
	 * string to initial the hashtable. use the hashtable to compare the second
	 * string chars if any value become 0 return false finally return true;
	 * 
	 * O(n) with space o(n)

michaelniu

/*
 * 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
 
 * Algorithm :
 * Brute force 
 * go through the String  to  count the repeat sequence and   put   char+count to new string
 * compare the length of new string and  original string to decide which one  is returned 

michaelniu

/*
 * Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column are set to 0
algorithm
  we only need know  which row and  column to be set to  0 
  so  we need  set two boolean array to  mark the    rows and columns should be set to  0
  O(mn) and space O(n+m)
  */
	public static void main(String[] args) {
		int[][] data= new int[][]{

michaelniu

/*
 * 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?

 Algorithm
 1, the cubic has  N/2 layers and rotate layer by layer
 2.every layer star with layer  (0<=layer<=N/2) end with n-layer-1
 3.  save the top   then rotate from right to top, bottom to right ,left to bottom  and top to left
 the key is the offset is  i-first (first<=i<last-1) ;

michaelniu

/*
 * 2.1 Write code to remove duplicates from an unsorted linked list. FOLLOW
 * UP How would you solve this problem if a temporary buffer is not allowed?
 * Algorithm use hashtable to store the existing data, if the hastable  contans the data
 *   means duplicated
 *   O(N)  & O(N)
 * Follow up  How would you solve this problem if a temporary buffer is not allowed?
 * Brote force   
 *  use  two  iterators   one move from  the  root to the end
 *  second  move from first iterated   node to compare with   all the rest  and move  the dupiclated one

michaelniu

public class FindLastKthElement_2_2 {
/*
 *2.2 Implement an algorithm to find the kth to last element of a singly linked list.
 *Algorithm 
 * use two pointer   firstpointer  move k time  then  move first and second  pointer  same time  until first reach  the end
 * 
 * O(N) and O(1)
 * 
 */
	public static void main(String[] args) {

michaelniu

package cc150;
/*
 *2.3 Implement an algorithm to delete a node in the middle of a singly linked list,
given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a- >b- >d->e
 Algorithm
 set c.data = c.next.data   and  c.next= c.next .next
 O(1) and O(1)

michaelniu

package cc150;
/*
 *2.4 Write code to partition a linked list around a value x, such that all nodes less than
x come before all nodes greater than or equal to x.
Algorithm
pretty straight forward  
 iterate the  original list  
 if  the data  >=x  
      thenode.next = x.next  and  x.next= thenode
 else