Why Arrays and Strings Are #1
More than half of Google interview questions start with an array or string. These problems test your ability to manipulate data in-place, recognize patterns (two-pointer, sliding window, prefix sums), and optimize from brute force to efficient solutions.
Data Representation: Arrays in Python
Before diving into algorithms, let’s understand how Python represents arrays — this is exactly what Google wants you to know.
Python Lists vs. True Arrays
# Python's "list" is NOT a traditional array (like C's int[]).
# It's a dynamic array of POINTERS to objects.
#
# Memory layout of a C array: [1][2][3][4] ← contiguous integers
# Memory layout of a Python list: [ptr][ptr][ptr][ptr] ← contiguous pointers
# ↓ ↓ ↓ ↓
# obj obj obj obj ← objects scattered in heap
#
# This means:
# - Indexing is O(1) — pointer arithmetic on the pointer array
# - Each element has overhead (object header + type info)
# - Lists can hold MIXED types: [1, "hello", 3.14, True]When You’d Use a Real Array (array module)
# Python has an 'array' module for C-style typed arrays, but in interviews
# you almost NEVER use it. Just use lists. The array module exists for
# memory-efficient storage of lots of numbers, which isn't relevant here.
#
# import array
# arr = array.array('i', [1, 2, 3]) # 'i' = signed intStrings are Immutable Arrays of Characters
# In Python, strings are sequences — you can index and slice them
# just like lists. But they are IMMUTABLE — you cannot modify them.
#
# s = "hello"
# s[0] = "H" # ❌ TypeError — strings are immutable!
#
# To "modify" a string, you must create a new one:
# s = "H" + s[1:] # "Hello" — creates a completely new stringPattern 1: Two-Pointer Technique
The two-pointer technique uses two indices that move through the array, usually from opposite ends or both from the start. It often turns O(n²) brute force into O(n).
When to recognize it: The input is sorted (or can be sorted), and you’re looking for pairs/triplets that satisfy some condition.
Exercises:
-
Two Sum — the most famous interview problem
-
Container With Most Water — two pointers from both ends
Pattern 2: Sliding Window
The sliding window maintains a "window" (subarray) that slides across the array. You expand the right boundary to grow the window and contract the left boundary to shrink it.
When to recognize it: You need to find a subarray/substring with some property (max sum, contains all characters, etc.).
Exercises:
-
Sliding Window Maximum — deque-based sliding window
Pattern 3: Hash Map Lookup
Use a hash map (dict) to convert O(n) lookups into O(1) lookups, often turning O(n²) into O(n).
When to recognize it: You need to check if a complement/matching element exists.
Exercises:
-
Valid Anagram — char frequency comparison
Key Takeaways for Google
|