Monthly Archives: August 2016

1.6 String Compression – CCI

  • traverse through string
  • keep track of each unique char in sequence and counts
  • join into compressed version
  • if length is shorter than original return that one
# [1:6]. 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)

# Time complexity: O(n)
# Space complexity: O(c) for distinct chars

import unittest

def compress(s):
    if not s:
        return None
    elif len(s) < 3:
        return s

    counter = [1]
    compressed = [s[0]]

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            counter[-1] += 1

    encrypted = encrypt(counter, compressed)

    if len(encrypted) < len(s):
        return encrypted
    return s

def encrypt(counter, keys):
    result = []
    for i in range(0, len(keys)):
        result = result + [keys[i] + str(counter[i])]
    return ''.join(result)

class Test(unittest.TestCase):
    def test_compress(self):
        self.assertEqual(compress('aaabbb'), 'a3b3')
        self.assertEqual(compress('aaaaccccbaa'), 'a4c4b1a2')
        self.assertEqual(compress('ababa'), 'ababa')
if __name__ == "__main__":

1.5 One Away – CCI

  • if strings are the same, return True
  • if length of strings are different by more than one, return False
  • if lengths are equal, check that only one character is off
  • if lengths are not equal, check that only one character is off
    • use pointers on arrays
    • increment pointer for larger array when char off
    • check if off by more than 1
# [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.
# Time complexity: O(n). Where n is the shorter string
# Space complexity: O(1). only creating pointers and a counter 
import unittest
def one_away(s1, s2):
    if s1 == s2:
        return True
    elif len(s1) == len(s2):
        return equal_size(s1, s2)
    elif abs(len(s1) - len(s2)) > 1:
        return False
    elif len(s1) > len(s2):
        larger = s1
        smaller = s2
        larger = s2
        smaller = s1
    return unequal_size(larger, smaller)
def equal_size(s1, s2):
    chars_off = 0
    for i, char in enumerate(s1):
        if char != s2[i]:
            chars_off += 1
        if chars_off > 1:
            return False
    return True
def unequal_size(larger, smaller):
    chars_off = 0
    small_index = 0
    large_index = 0
    while small_index < len(smaller): 
        if larger[large_index] != smaller[small_index]: 
            chars_off += 1 
            large_index += 1 
            large_index += 1 
            small_index += 1 
        if chars_off > 1:
            return False
    return True
class Test(unittest.TestCase):
    def test_one_away(self):
if __name__ == "__main__":

1.4 Palindrome Permutation – CCI

  • A palindrome will have duplicate characters on opposite sides except potentially the middle
  • get the count of characters
  • loop through the char count and return False if multiple characters have an odd count
  • could also keep track of odd counts while counting, but would have to check for each char
  • can also use a bit vector and map each char to pos 0-25
    • toggle on and off for each char
    • at the end, if permutation, will have only one True
    • if you get the value & value – 1, will be zero if there was only one True
# 1.4. Palindrom Permutation: Given a string, write a function to check 
# if it is a permutation of a palindrome. A palindrome is a word or
# phrase that is the same forwards and backwards. A permutation is a 
# rearrangement of letters. The palindrome does not need to be limited
# to just dictionary words.

# Input: Tact Coa
# Output: True

# Hash Table Solution
# Time complexity: O(n) count characters and then loop through smaller
# subset
# Space complexity: O(c) where c is each char / Also can be thought
# of as O(1) because set of characters is limited

# Bit Vector Solution
# Time complexity: O(n) need to look through each character
# Space complexity: O(1) information all stored in one integer

import unittest

def palindrome_permutation(s):
    char_count = get_char_count(s)
    odd_count = 0
    for char in char_count:
        if odd_count > 1:
            return False
        if char_count[char] % 2 == 1:
            odd_count += 1
    return True
def get_char_count(s):
    char_count = {}
    for char in s:
        if char not in char_count:
             char_count[char] = 1
            char_count[char] += 1
    return char_count
def palindrome_permutation2(s):
    bv = [0]*26
    for char in s:
       bv[array_index(char)] = 1^bv[array_index(char)]

    bit_str = [str(b) for b in bv]
    if int(''.join(bit_str),2) & int(''.join(bit_str),2) - 1:
        return False
        return True
def array_index(s):
    return ord(s.lower()) - 97
class Test(unittest.TestCase):
    def test_palindrome_permutation(self):
        # hash table solution

        # bit array solution
if __name__ == "__main__":

1.3 URLify – CCI

Solution 1

  • Loop through and replace ” ” with “%20”
  • Return joined list as a string

Solution 2

  • Split string into a list on ” ” characters
  • Join list into a string with ‘%20’
# 1.3. 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. 

# Input: "Mr John Smith", 13
# Output: "Mr%20John%20Smith"

# Time complexity: O(n) goes through each char in string
# Space complexity: O(n + 2k) creating new list and for each
#                   space will add two additional chars
#                   e.g. ' ' will become '%20'

import unittest

def urlify(s, l):
    return ''.join(['%20' if char == " " else char for char in s])

def urlify2(s, l):
    return '%20'.join(s.split(' '))

class Test(unittest.TestCase):
    def test_url(self):
        self.assertEqual(urlify("Mr John Smith", 13), "Mr%20John%20Smith")
        self.assertEqual(urlify("he lloo", 6), "he%20lloo")
        self.assertEqual(urlify("he lloo ", 6), "he%20lloo%20")

        self.assertEqual(urlify2("Mr John Smith", 13), "Mr%20John%20Smith")
        self.assertEqual(urlify2("he lloo", 6), "he%20lloo")
        self.assertEqual(urlify2("he lloo ", 6), "he%20lloo%20")
        self.assertEqual(urlify2(" he lloo ", 6), "%20he%20lloo%20")

if __name__ == "__main__":

1.2 Check Permutation – CCI

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

  • check that lengths are not the same
  • get the character counts for each string
  • loop through the char counts for one of the strings
  • if a character in one string is not in the other, cannot be a permutation
  • also, if a character count is not the same, then cannot be a permutation
# Time complexity: O(n + m), must go through all characters for both strings
# Space complexity: O(c), hash table will be size of available chars

import unittest

def check_permutation(s1, s2):

    # if lengths are different, cannot be a permutation
    # assuming we are counting ' ' as a separate char
    if len(s1) != len(s2):
        return False

    s1_count = char_count(s1)
    s2_count = char_count(s2)

    for char in s1_count:
        # if a char in s1 is not in s2, cannot be a permutation
        if not char in s2_count:
            return False
        #if the count of a char is different, cannot be a permutation
        elif s1_count[char] != s2_count[char]:
            return False

    # if all the chars were in char1 and char2 and the counts were the same
    # must be a permutation
    return True

def char_count(s):
    char_counter = {}
    for char in s:
        # if char not in hash table, add it
        if not s in char_counter:
            char_counter[char] = 1
        # if char in hash table, increment it by one
            char_counter[char] += 1

    return char_counter

class Test(unittest.TestCase):
    def test_permutation(self):
        self.assertTrue(check_permutation('banana', 'ananab'))

        self.assertFalse(check_permutation('banana', 'cat'))
        self.assertFalse(check_permutation('bat', 'cat'))

if __name__ == "__main__":

1.1 Is Unique – CCI

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

Part 1

  • Create a hash table that keeps track of count for each character
  • Loop through each character and add to hash table if not already in there
  • If character is in the hash table, there must be a duplicate
# Time complexity: O(n) because needs to check each character
# Space complexity: O(c) where c is each character

import unittest

def is_unique(s):
    # create a hashmap to keep track of char count
    char_count = {}

    for char in s:
        # if character is not in hashmap add it
        if not char in char_count:
            char_count[char] = 1
            # if char is in hashmap, means there is a duplicate character
            return False

    return True

class Test(unittest.TestCase):
    def test_unique(self):

if __name__ == "__main__":

Part 2: No Additional Data Structures

  • Loop through each character
  • for each character loop through all characters
  • make sure you are not comparing the same character
  • otherwise, if the characters are equal, not all characters are unique
# Time complexity: O(n**2) because loops through all characters for each character
# Space complexity: O(1)

import unittest

def is_unique(s):
    for i, char1 in enumerate(s):
        for j, char2 in enumerate(s):
            if i != j and char1 == char2:
                return False

    return True

class Test(unittest.TestCase):
    def test_unique(self):

if __name__ == "__main__":



I’m currently working through the recursion chapter of Cracking the Coding Interview. Recursion is essentially using the same function repeatedly to solve smaller subsets of the initial data.

The Fibonacci numbers are a good example of this (i.e. 1, 1, 2, 3, 5, 8, 13…). Each number is the sum of the previous two numbers.

def fib(n):
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

If we are trying to find the 4th fibonacci term, we would have to first find the 2nd and 3rd term and so on and so forth. Recursion only works if there is a base case that eventually returns something. In this example, when n is eventually 0 or 1, the value 1 will be returned.