Arrays And Strings

2022-02-13

Cracking the Coding Interview

雜湊表 (Hash Tables)

雜湊表是對應鍵(key)與值(value)，以供高效率查詢的資料結構。

以下描述簡單但最常見的實作。

我們使用一個鏈接清單(linked list)陣列與一個雜湊編碼函式(hash code function)。
當要插入鍵與值時，我們會執行：

首先計算鍵的雜湊編碼，通常為int或long。

注意兩個不同的鍵可能有相同的雜湊編碼。

對應該雜湊編碼到陣列的一個索引(index)。
它可以是hash(key)% array_length。

兩個不同的雜湊編碼可能對應到同一個索引。

此索引有個鍵與值的鏈接清單。將鍵與值存在這個索引中。
我們必須使用鏈接清單是因為有衝突(collision):
兩個不同的鍵具有相同的雜湊編碼，或不同的雜湊編碼對應到相同索引。

若衝突量很高，最差的執行時間是$O(n)$，N為鍵的數量。
但好的實作可以將衝突降至最少，此時的查詢時間為$O(1)$。

hash-tables

另外我們也可以用平衡二元搜尋樹(balanced binary search tree)實作雜湊表。
它具有$O(logN)$查詢時間。好處是使用較少空間，因為不需要分配(allocate)大陣列。
還能夠依序迭代(iterate)所有鍵，在某些情況很實用。

Binary Search Tree(BST):

Key(L)<Key(Current)<Key(R)
Both subtrees of each node are also BSTs

Balanced Binary Search Tree:

A binary search tree in which the left and right subtrees of every node differ in height by no more than 1

ArrayList 與可變大小陣列

有些語言的陣列可以自動調整大小 (通常稱為清單)。
Java等其他語言的陣列大小是固定的。

你需要可動態調整大小的類陣列結構時，通常可使用ArrayList。
ArrayList是自行調整大小的陣列但存取還是$O(1)$。
典型的實作會在陣列滿時，加倍大小。

每次加倍需要$O(n)$時間，但很少發生，插入時間平攤後還是$O(1)$。

ArrayList<String> merge(String[] words, String[] more) {
  ArrayList<String> sentence = new ArrayList<String>();
  for (String w : words) sentence.add(w);
  for (String w : more) sentence.add(w);
  return sentence;
}

為什麼分攤後的插入時間是$O(1)$?

參考先前的平攤時間。

StringBuilder

假設要如下連接字串清單，這段程式的執行時間是什麼？

假設字串的長度(x)都相等且有n個字串。

String joinWords(String[] words) {
  String sentence = '';
  for (String w : words) {
    sentence = sentence + w;
  }
  return sentence;
}

每個連接都產生新的字串拷貝，將兩個字串複製並連接在一起。
第一個迭代需要複製x個字元、第二個迭代需要複製2x個字元、…

因此總時間為$O(x+2x+…+nx) = O(xn^2)$

(因為$1+2+…+n = n(n+1)/2$)

StringBuilder可以避免這個問題。
StringBuilder建構可調整大小的陣列，只在有需要時再複製成字串。

String joinWords(String[] words) {
  StringBuilder sentence = new StringBuilder();
  for (String w : words) {
    sentence.append(w);
  }
  return sentence.toString();
}

面試題目

1.1 Is Unique

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

先詢問字串是ASCII或Unicode。

補充:

ASCII (American Standard Code for Information Interchange，美國標準資訊交換碼)
用一個位元組(bite)，即8個位元(bit)，來表示一個字元。
位元組的最高位統一規定為0，剩餘7位用來存儲數據。共128種編碼。
擴展的ASCII編碼，則是把位元組的最高位原本統一設置為0的，也用來存儲字符數據。
但各國在擴展的部分定義不同。共256種編碼。
Unicode，又被稱為統一碼、萬國碼，使用兩個位元組，即16位元來表示字元。
UTF-8 (8-bit Unicode Transformation Format)，是Unicode的一種編碼方式。
可以用一至四個位元組對Unicode字元集中的所有有效編碼點進行編碼。為解決向下相容ASCII碼而設計。

假設為ASCII的128個字元。

public static function isUnique($string): bool
{
    if (strlen($string) > 128) {
        return false;
    }

    $charSet = [];
    for ($i = 0; $i < strlen($string); $i++) {
        $value = substr($string, $i, 1);

        if (isset($charSet[$value])) {
            return false;
        }
        $charSet[$value] = true;
    }

    return true;
}

此程式的時間複雜度為$O(n)$，n為字串長度。
空間複雜度為$O(1)$。
也可以說時間複雜度為$O(1)$，因為不會迭代超過128個字元。

若不想假設字元集的大小，可以說時間複雜度為$O(min(c,n))$。
其中c為字元集的大小。

提示：使用位元向量。

使用位元向量可降低使用空間。

假設字串只使用a到z的小寫字母。

public static function isUnique($string): bool
{
    $checker = 0;

    for ($i = 0; $i < strlen($string); $i++) {
        $value = substr($string, $i, 1);

        $asciiDiff = ord($value) - ord('a');

        /**
         * $a & $b: 取位元的交集。
         * $a << $b: 將位元向左移動b次(即乘以2的b次方)。
         */
        if (($checker & (1 << $asciiDiff)) > 0) {
            return false;
        }

        /**
         * $a |= $b: $a = $a | $b。
         */
        $checker |= (1 << $asciiDiff);
    }

    return true;
}

若不能使用其他資料結構呢？

相互比較字串的每個字元，需要$O(n^2)$的時間與$O(1)$空間。
若可以修改字元，我們可以用$O(nlog(n))$時間將字串排序，
然後線性檢查相鄰字元是否相同。
注意：許多排序演算法需要額外空間。

1.5 One Away

There are three types of edits that can be performed on strings: Insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

[Example]
pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bake -> false

public static function isOneOrZeroAway(string $string1, string $string2): bool
{
  $length1 = strlen($string1);
  $length2 = strlen($string2);

  if ($length1 == $length2) {
      return self::isReplaceCharacter($string1, $string2);
  } elseif (abs($length1 - $length2) == 1) {
      return ($length1 > $length2)
          ? self::isOneCharacterDifferent($string1, $string2)
          : self::isOneCharacterDifferent($string2, $string1);
  }

  return false;
}

public static function isReplaceCharacter(string $string1, string $string2): bool
{
  $result = true;

  $isReplaceOneTime = false;

  for ($i = 0; $i < strlen($string1); $i++) {
      if ($string1[$i] == $string2[$i]) {
          continue;
      }

      if ($isReplaceOneTime) {
          $result = false;
          break;
      }

      $isReplaceOneTime = true;
  }

  return $result;
}

/**
 * Think of
 * (i) bed & ed
 * (ii) bed & bd
 * (iii) bed & be
 *
 * @param string $longString
 * @param string $shortString
 * @return bool
 */
public static function isOneCharacterDifferent(string $longString, string $shortString): bool
{
  $result = true;

  $isOneCharacterDifferent = false;

  for ($i = 0; $i < strlen($longString) - 1; $i++) {
      if ($isOneCharacterDifferent && ($longString[$i] != $shortString[$i - 1])) {
          $result = false;
          break;
      }

      if ($longString[$i] == $shortString[$i]) {
          continue;
      }

      $isOneCharacterDifferent = true;
  }

  return $result;
}

1.9 String Rotation

Assume you have a method isSubstring which checks if oneword is a substring of another. Given two strings, sl and s2, write code to check if s2 is a rotation of sl using only one call to isSubstring.

(e.g. “waterbottle” is a rotation of”erbottlewat”)

First Answer:

public static function isRotation($string1, $string2): bool
{
  $length1 = strlen($string1);
  $length2 = strlen($string2);
  if ($length1 != $length2) {
      return false;
  }

  $stringRotations = [];
  for ($offset = 1; $offset < $length1; $offset++) {
      $partA = substr($string1, $offset);
      $partB = substr($string1, 0, $offset);

      $stringRotations[] = $partA . $partB;
  }

  return in_array($string2, $stringRotations);
}

Best Answer:

public static function isRotation($string1, $string2): bool
{
  $length1 = strlen($string1);
  $length2 = strlen($string2);
  if ($length1 != $length2) {
      return false;
  }

  return strpos($string1 . $string1, $string2);
}

ʕ •ᴥ•ʔ：程式碼可參考：CtCI-6th-php。

Algorithm