This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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[][]{ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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) ; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) { |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
OlderNewer