Python Coding Interview Guide
1. Two Sum (Amazon, Google)
Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add
up to target.
Approach: Use a hash map to store numbers and their indices. For each number, check if target - number exists in the
map.
Example: Input: nums = [2,7,11,15], target = 9 -> Output: [0,1]
Complexity: Time: O(n), Space: O(n)
def two_sum(nums, target):
num_map = {}
for i, num in enumerate(nums):
if target - num in num_map:
return [num_map[target - num], i]
num_map[num] = i
return []
2. LRU Cache (Amazon, Microsoft, Meta)
Description: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Approach: Use OrderedDict from collections to store cache keys in order of usage.
Example: cache = LRUCache(2) -> put(1,1), put(2,2), get(1) -> returns 1
Complexity: Time: O(1), Space: O(capacity)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
[Link] = OrderedDict()
[Link] = capacity
def get(self, key: int) -> int:
if key not in [Link]:
return -1
[Link].move_to_end(key)
return [Link][key]
def put(self, key: int, value: int) -> None:
if key in [Link]:
[Link].move_to_end(key)
[Link][key] = value
if len([Link]) > [Link]:
[Link](last=False)