Chapter 1 – Arrays & Strings – Solution 1.3

Question:

1.3 Write a method to decide if two strings are permutation. i.e. “hello” is a permuataion of “oellh”.

If one string is a permutation of the other, they should has the same length and every character appear the same times in these two strings.

So the solution is to check the length and appear time of each character of these two strings.

We can use the same idea in question in 1.1 to solve this question. For example, use an array to store the appear time of all the characters in ASCII table.

Here is my solution, the time complexity was O(n) and space complexity is O(1).

bool
permutation(string a, string b)
{
  // if the length is different, can not be permutation
  if(a.size() != b.size()) return false;

  // use idea of Bucket-sort to count every ASCII character
  int bucket[256] = {};

  // count the apprear time of every character in a
  for(size_t i=0; i<a.size(); i++)
    bucket[a[i]]++;

  // the appear time of character in b shold be the same with a
  for(size_t i=0; i<b.size(); i++)
    if(bucket[b[i]]-- == 0) return false;

  return true;
}

Chapter 1 – Arrays & Strings – Solution 1.2

1.2 Write code to reverse a C-Style String (char* str). (C-String means that “abcd” is represented as five characters, including the null terminator.)

We can use two pointer, one is pointed to the first character, the other is pointed to the last character before the null pointer. Then we can swap the two character, and move the two pointer one step to each other and repeat.

Here is my solution, the time complexity  of this algorithm is O(n), and the space complexity is O(1).

void
reverse(char* str)
{
  size_t i = 0, j = 0;

  while(str[i]!=0) ++i; // go to the end of string "\0"
  --i; // move to the charcter before "\0"

  while(i>j) // swap the head and end characters one by one
  { // xor swap
    str[i] ^= str[j]; // a = a xor b
    str[j] ^= str[i]; // b = b xor (a xor b) = a
    str[i--] ^= str[j++]; // a = (a xor b) xor a = b
  }

  return;
}

Chapter 1 – Arrays & Strings – Solution 1.1

Cracking the code interviews – Solution

Chapter 1 Arrays & Strings

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

If the characters comes from the ASCII table, there can only be 256 types of them. We can use a boolean array of size 256 to mark each type of characters. This is the same idea of Bucket-sort algorithm.
About Bucket-Sort: http://en.wikipedia.org/wiki/Bucket_sort

When a new character is already marked as true (already appeared), then we will know that this string contains duplicate characters. The time complexity of isUnique() is O(n) and space complexity is O(1).

Here is my solution in c++:

bool
isUnique(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  bool bucket[256] = {}; // remember every ASCII character

  for(size_t i=0; i<str.size(); ++i)
  {
    // mark the appeared character to true
    // if already set true, report the duplicated character
    if(bucket[str[i]])
      return false;

    bucket[str[i]] = true;
  }

  return true;
}

Another solution is to use a 256-bit-map to mark the characters in ASCII table.
The time / space complexity of isUniqueV2() is also O(n) / O(1).

bool
isUniqueV2(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  uint64_t bucket[4] = {};

  for(size_t i=0; i<str.size(); ++i)
  {
    int index = str[i] / 64; // which bucket should be check
    int bit = str[i] % 64; // which bit in the bucket should be check

    // mark the appeared character to true
    // if already set true, report the duplicated character
    if( (bucket[index] & (1 << bit)) != 0)
      return false;

    bucket[index] |= (1 << bit);
  }

  return true;
}