Arrays & Strings

Check Permutation

Given two strings, write a method to decide if one is a permutation of the other.

# O(n*log n)
def check_permutation(s, t):
    return sorted(s) == sorted(t)

Is Unique

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

# O(n)
def unique_chars(string):
    seen = set()
    for c in string:
        if c in seen:
            return False
        seen.add(c)
    return True

# Without data structures, O(n*log n)
def unique_chars2(string):
    s = sorted(string)
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            return False
    return True

# Without data structures, O(n^2)
def unique_chars3(string):
    for i in range(len(string)):
        for j in range(len(string)):
            if i != j and string[i] == string[j]:
                return False
    return True

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 fewer away.

Iterate separately through the strings. When a mismatch is found, count one edit and:

• if the strings are different lengths, assume an insertion/removal and increment the iterator for the longer string only
• if the strings are the same length, assume a replacement and increment both iterators

If more than one mismatch is found, return False

# O(n)
def one_away(s, t):
    if s == t:
        return True
    if abs(len(s) - len(t)) > 1:
        return False

    s_index = 0
    t_index = 0
    edits = 0
    while s_index < len(s) and t_index < len(t):
        if s[s_index] != t[t_index]:
            edits += 1
            if edits > 1:
                return False

            if len(s) > len(t):
                s_index += 1
                continue
            elif len(t) > len(s):
                t_index += 1
                continue

        s_index += 1
        t_index += 1

    return True

Palindrome Permutation

Given a string, write a function to check if it is a permutation of a palindrome. The palindrome does not need to be limited to just dictionary words.

EXAMPLE

Input: Tact Coa

Output: True

Only one char in a palindrome permutation can have an odd count (the pivot char(s) in the middle of the palindrome)

# O(n)
def is_palindrome_permutation(string):
    counts = {}
    for c in string.lower():
        if c not in counts:
            counts[c] = 1
        else:
            counts[c] += 1

    num_odd = 0
    for c in set(string.lower()):
        if c == " ":
            continue
        if counts[c] % 2 != 0:
            num_odd += 1
            if num_odd > 1:
                return False
    return True

Rotate Matrix

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?

First attempt (not in place):

template <size_t size>
void rotate_clockwise(int (&matrix)[size][size]) {
    int temp[size][size];
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            temp[j][size - 1 - i] = matrix[i][j];
        }
    }

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            matrix[i][j] = temp[i][j];
        }
    }
}

TODO: rotate in place one layer at a time

String Compression

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a-z).

# O(n)
def compress_string(string):
    count = 0
    last = string[0]
    compressed = string[0]
    for c in string:
        if c != last:
            last = c
            compressed += str(count) + c
            count = 1
        else:
            count += 1
    compressed += str(count)

    if len(compressed) >= len(string):
        return string
    else:
        return compressed

String Rotation

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").

def isSubstring(s, t):
    """
    Return whether s is a substring of t.
    """
    return s in t

def isRotation(s, t):
    """
    Return whether s is a rotation of t.
    """
    if len(s) != len(t):
        return False

    return isSubstring(t, s+s)

URLify

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string.

def URLify(string):
    return "%20".join(string.split())

Zero Matrix

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

template <size_t rows, size_t cols>
void zero_matrix(int(&matrix)[rows][cols]) {
    bool row_zeroed[rows];
    bool col_zeroed[cols];

    for (int r = 0; r < rows; r++) {
        row_zeroed[r] = false;
    }
    for (int c = 0; c < cols; c++) {
        col_zeroed[c] = false;
    }

    // Find all rows, cols to be zeroed
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {

            if (matrix[r][c] == 0) {
                row_zeroed[r] = true;
                col_zeroed[c] = true;
            }
        }
    }

    // Zero rows
    for (int r = 0; r < rows; r++) {
        if (row_zeroed[r]) {
            for (int c = 0; c < cols; c++) {
                matrix[r][c] = 0;
            }
        }
    }

    // Zero cols
    for (int c = 0; c < cols; c++) {
        if (col_zeroed[c]) {
            for (int r = 0; r < rows; r++) {
                matrix[r][c] = 0;
            }
        }
    }
}