Cracking the Coding Interview - Gayle Laakmann McDowell#

This book is recommended reading material when preparing for technical interviews. However, all of its examples are in Java. In these notes, I’m going to maintain solutions for all the exercises, and examples, in Python. I’ll stick to Python 3.8 and above, where applicable.

I recommend getting a physical copy of this book to read along with my notes.

While the initial sections of the book dwell on the pre-interview process, I do not find them too relevant to me. I am going to focus purely on the problem-solving skills.

Exercises#

1.1 Unique Characters in String#

 1"""1.1 Implement an algorithm to determine if a string has all unique
 2characters. What if you cannot use additional data structures?"""
 3
 4
 5def is_unique(input_string):
 6    """determines if a string has all unique characters"""
 7    from collections import Counter
 8
 9    counter = Counter(input_string)
10    for char, values in counter.items():
11        if values > 1:
12            return False
13    return True
14
15
16def test_is_unique():
17    assert is_unique("asdfg") == True
18    assert is_unique("asssdffasdf") == False
19
20
21def is_unique_without_counter(input_string):
22    """Check if a string has all unique characters *without* using additional
23    data structures"""
24    input_string = sorted(input_string)
25    last_char = None
26    for char in input_string:
27        if char == last_char:
28            return False
29        last_char = char
30    return True
31
32
33def test_is_unique_without_counter():
34    assert is_unique_without_counter("asdfg") == True
35    assert is_unique_without_counter("asssdffasdf") == False