xun-gong

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

#include <iostream>
#include <string>
#include <cstring> // for memset()

using namespace std;

xun-gong

/* Chapter 1
 * 1.2 Implement function void reverse(char* str) in C or C++ which reverses a null-terminated string.
 */

#include <iostream>
#include <string>

using namespace std;

// Approach 1:

xun-gong

/* Chapter 1
 * 1.3 Given two strings, write a method to decide if one is a permutation of the other.
 */

#include <iostream>
#include <string>

using namespace std;

bool permutation(char* str1, char* str2)

xun-gong

/* Chapter 1
 * 1.4 Write a method to replace all the space in a string to %20
 * you may assume the given space is sufficient.
 * Example: "Mr John Troy(_extra_space_)"
 *        =>"Mr%20John%20Troy."
 */


#include <iostream>
#include <string>

xun-gong

/* Chapter 1
 * 1.5 Write a method to perform basic string compression using the counts of repeated characters
 * Example: "aabcccccaaa"
 *        =>"a2b1c5a3"
 * If "compressed" string would not become smaller than the original string ("abc" => "a1b1c1"), your method should
 * return the original string. Assume the string has only upper and lower case letters (a~z)
 */

#include <iostream>
#include <string>

xun-gong

/* Chapter 1
 * 1.6 Given an image represented by an N*N 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?
 */

/* Rotate 90 degree counter-clockwise */

#include <iostream>

using namespace std;

xun-gong

/* Chapter 1
 * 1.7 Write a algotithm such that if an element in an M*N matrix is 0, its entire
 * row and column are set to 0.
 */

#include <iostream>

using namespace std;

#define M 4

xun-gong

/* Chapter 1
 * 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
 * (e.g. "waterbottle" is a rotation of "erbottlewat")
 */

#include <iostream>
#include <string>

xun-gong

/**
 * Chapter 2
 *
 * 2.1 Write code to remove duplicates from an unsorted linked list. 
 * How would you solve this problem if a temporary buffer is not allowed?
*/
#include <iostream>
#include <unordered_set>  // removeDuplicates() need to remember

using namespace std;

xun-gong

/**
 * Chapter 2
 *
 * 2.2 Implement an algorithm to find the kth to last element of a singly linked list.
 */
#include <iostream>

using namespace std;

// Define a Node class