chouclee’s gists

chouclee / UniqueString.java

Created June 16, 2014 03:48

[CC150][1.1] Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? (not applicable for Unicode)

	import java.util.Scanner;
	public class UniqueString {

	public static boolean unique(String s) {
	if (s == null) return false;
	boolean[] flag = new boolean[256];
	for (int i = 0; i < s.length(); i++) {
	if (flag[s.charAt(i)])
	return false;
	else

chouclee / UniqueStringHashSet .java

Last active August 29, 2015 14:02

[CC150][1.1] Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? (applicable for Unicode, but use HashSet)

	import java.util.Scanner;
	import java.util.HashSet;

	public class UniqueStringHashSet {

	public static boolean unique(String s) {
	HashSet<Character> set = new HashSet<Character>();
	for (int i = 0; i < s.length(); i++) {
	if (!set.add(s.charAt(i)))
	return false;

chouclee / reverseString.cpp

Created June 17, 2014 03:30

[CC150][1.2] Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.

	#include <iostream>
	using namespace std;

	void reverseString(char *str) {
	char *start = str;
	for (;*str;str++); //loop to '\0' terminal of the string
	if (*start) str--; //in case string is blank
	while (start < str) {
	start ^= str; //swap two elements using XOR
	str ^= start;

chouclee / permutation.java

Last active August 29, 2015 14:02

[CC150][1.3] Given two strings, write a method to decide if one is a permutation of the other. (Consider case sensitivity and whitespace as significant)

	import java.util.HashMap;

	public class permutation {

	public static boolean isPermut(String a, String b) {
	if (a == null \|\| b == null) throw new NullPointerException();
	if (a.length() != b.length()) return false;
	HashMap<Character, Integer> aMap = new HashMap<Character, Integer>();
	HashMap<Character, Integer> bMap = new HashMap<Character, Integer>();
	traverse(a, aMap);

chouclee / replace.java

Created June 17, 2014 11:32

[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 pla…

 public class replace {
 	public static String replaceBlank (String s) {
 		if(s == null) return null;
 		int count = 0;
 		for (int i = 0; i < s.length(); i++)
 			if (s.charAt(i) == ' ') count++;
 		char[] newStr = new char[s.length() + count << 1];
 		for (int i = 0 , j = 0; i < s.length() ; i++) {
 			if (s.charAt(i) == ' ') {

chouclee / compressStr.java

Created June 17, 2014 12:42

[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.


	public class compressStr {
	public static String compress(String s) {
	StringBuilder sb = new StringBuilder();
	int idx = 0;
	int l = s.length();
	boolean first = true;
	int count = 0;
	while (idx < l) {
	if (first) {

chouclee / Image.java

Created June 17, 2014 16:34

[CC150][1.5] 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 class Image {
	private int N;
	private int[][] img;
	public Image(int[][] image) {
	if (image == null) throw new NullPointerException();
	this.img = image;
	if (image.length != image[0].length) throw new IllegalArgumentException();
	this.N = image[0].length;
	}

chouclee / Solution.java

Created June 18, 2014 03:41

[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.

	//* Time O(MN)
	// Use two extra boolean arrays to record which rows and cols should be set to 0.
	//* Space O(M+N)

	public class Solution{
	private int[][] matrix;
	private int M;
	private int N;

	public Solution(int[][] m) {

chouclee / isRotation.java

Last active August 29, 2015 14:02

[CC150][1.8] 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”)


	public class isRotation {

	public static boolean isRotate(String s1, String s2) {
	if (s1.length() != s2.length()) return false;
	return isSubstring(s2, s1.concat(s1));
	}


	public static boolean isSubstring(String s1, String s2) {

chouclee / rmDuplicate.java

Created June 18, 2014 08:47

[CC150][2.1] Write code to remove duplicates from an unsorted linked list.

	import java.util.LinkedList;
	import java.util.HashSet;

	public class rmDuplicate {

	//* why return a new LinkedList rather than modifiying the original one?
	//* remove(object) in LinkedList(Java) could be O(N) in worst case (i.e. closer to tail of the LinkedList)
	//* for LinkedList [1,1,...,1,1,1] (length N), remove dupicate elements would cost (1+2+...+N-1) ~ O(N^2)
	//* write your own LinkedList where you can manipulate the reference could solve the problem
	public static<Item> LinkedList<Item> rm (LinkedList<Item> list) {

Zhoucheng Li chouclee