Preparing for a coding interview can be a daunting task. While you might be well-versed in common data structures and algorithms, interviewers often throw curveballs to test your problem-solving skills and ability to think on your feet. In this article, we’ll explore ten unexpected coding interview questions that you might encounter and provide detailed solutions to help you tackle them with confidence.
1. The Skyline Problem
This problem is a classic example of a question that seems simple at first glance but requires careful consideration to solve efficiently.
Question:
Given a list of buildings where each building is represented by a triplet (left, right, height), where left and right are x-coordinates, and height is the building’s height, return a list of the key points in the skyline formed by these buildings.
Solution:
This problem can be solved using a sweep line algorithm and a priority queue. Here’s a Python implementation:
import heapq
def get_skyline(buildings):
events = []
for l, r, h in buildings:
events.append((l, -h, r)) # start of building
events.append((r, 0, 0)) # end of building
events.sort()
res = []
heap = [(0, float('inf'))]
max_height = 0
for x, neg_h, r in events:
if neg_h != 0:
heapq.heappush(heap, (neg_h, r))
else:
while heap[0][1] <= x:
heapq.heappop(heap)
if -heap[0][0] != max_height:
max_height = -heap[0][0]
res.append([x, max_height])
return res
This solution has a time complexity of O(n log n) where n is the number of buildings.
2. LRU Cache Implementation
Implementing a Least Recently Used (LRU) cache is a common interview question that tests your understanding of data structures and your ability to optimize for both time and space complexity.
Question:
Implement an LRU cache with get and put operations in O(1) time complexity.
Solution:
We can use a combination of a hash map and a doubly linked list to achieve O(1) time complexity for both operations:
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self._add(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
lru = self.head.next
self._remove(lru)
del self.cache[lru.key]
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
This implementation ensures that both get and put operations have O(1) time complexity.
3. Design a Tiny URL System
System design questions are becoming increasingly common in coding interviews. This question tests your ability to design a scalable system and consider various trade-offs.
Question:
Design a system that generates short URLs from long URLs and vice versa.
Solution:
Here’s a high-level design for a TinyURL system:
- Use a hash function to generate a unique short code for each long URL.
- Store the mapping between short codes and long URLs in a database.
- Implement an API with endpoints for shortening URLs and redirecting short URLs.
Here’s a simple Python implementation of the core functionality:
import hashlib
class TinyURL:
def __init__(self):
self.url_to_code = {}
self.code_to_url = {}
def shorten(self, long_url):
if long_url in self.url_to_code:
return self.url_to_code[long_url]
code = self._generate_code(long_url)
while code in self.code_to_url:
code = self._generate_code(code)
self.url_to_code[long_url] = code
self.code_to_url[code] = long_url
return code
def expand(self, short_code):
return self.code_to_url.get(short_code, '')
def _generate_code(self, url):
return hashlib.md5(url.encode()).hexdigest()[:6]
This is a simplified version and doesn’t address all aspects of a production system, such as handling collisions more robustly or dealing with database scalability.
4. Implement a Rate Limiter
Rate limiting is a crucial concept in system design, especially for APIs. This question tests your understanding of distributed systems and concurrency.
Question:
Implement a rate limiter that allows n requests per second per user.
Solution:
We can use the token bucket algorithm to implement a rate limiter. Here’s a simple Python implementation:
import time
class RateLimiter:
def __init__(self, capacity, refill_rate):
self.capacity = capacity
self.refill_rate = refill_rate
self.tokens = capacity
self.last_refill_time = time.time()
def allow_request(self):
now = time.time()
time_passed = now - self.last_refill_time
self.tokens = min(self.capacity, self.tokens + time_passed * self.refill_rate)
self.last_refill_time = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
# Usage
limiter = RateLimiter(capacity=10, refill_rate=1) # 10 requests per second
for _ in range(15):
print(limiter.allow_request())
time.sleep(0.1)
This implementation allows for a burst of requests up to the capacity, then throttles to the specified rate.
5. Implement a Thread-Safe Singleton
This question tests your understanding of design patterns, concurrency, and language-specific features.
Question:
Implement a thread-safe singleton pattern in your preferred language.
Solution:
Here’s a thread-safe singleton implementation in Python using a decorator:
import threading
def singleton(cls):
instances = {}
lock = threading.Lock()
def get_instance(*args, **kwargs):
if cls not in instances:
with lock:
if cls not in instances:
instances[cls] = cls(*args, **kwargs)
return instances[cls]
return get_instance
@singleton
class MyClass:
def __init__(self):
self.value = None
def set_value(self, value):
self.value = value
# Usage
instance1 = MyClass()
instance2 = MyClass()
print(instance1 is instance2) # True
This implementation ensures that only one instance of the class is created, even in a multi-threaded environment.
6. Implement a Circular Buffer
Circular buffers are useful in scenarios with fixed-size buffers, such as in embedded systems or when implementing certain algorithms.
Question:
Implement a circular buffer with fixed size that overwrites the oldest data when full.
Solution:
Here’s a Python implementation of a circular buffer:
class CircularBuffer:
def __init__(self, size):
self.buffer = [None] * size
self.size = size
self.head = 0
self.tail = 0
self.count = 0
def push(self, item):
if self.count == self.size:
self.head = (self.head + 1) % self.size
else:
self.count += 1
self.buffer[self.tail] = item
self.tail = (self.tail + 1) % self.size
def pop(self):
if self.count == 0:
return None
item = self.buffer[self.head]
self.head = (self.head + 1) % self.size
self.count -= 1
return item
def __len__(self):
return self.count
def __str__(self):
return str(self.buffer)
# Usage
cb = CircularBuffer(5)
for i in range(7):
cb.push(i)
print(cb) # [5, 6, 2, 3, 4]
print(cb.pop()) # 2
print(cb) # [5, 6, None, 3, 4]
This implementation efficiently manages the buffer, overwriting the oldest data when the buffer is full.
7. Implement a Basic Garbage Collector
While most modern languages have built-in garbage collection, understanding how it works is crucial for systems programming and can be asked in interviews for more low-level positions.
Question:
Implement a basic mark-and-sweep garbage collector for a simple object system.
Solution:
Here’s a simplified implementation of a mark-and-sweep garbage collector in Python:
class Object:
def __init__(self):
self.marked = False
self.children = []
class GarbageCollector:
def __init__(self):
self.objects = []
def allocate(self):
obj = Object()
self.objects.append(obj)
return obj
def add_root(self, obj):
self.objects.append(obj)
def mark(self, obj):
if obj.marked:
return
obj.marked = True
for child in obj.children:
self.mark(child)
def sweep(self):
self.objects = [obj for obj in self.objects if obj.marked]
for obj in self.objects:
obj.marked = False
def collect(self):
for obj in self.objects:
if hasattr(obj, 'root') and obj.root:
self.mark(obj)
self.sweep()
# Usage
gc = GarbageCollector()
root = gc.allocate()
root.root = True
child1 = gc.allocate()
child2 = gc.allocate()
root.children = [child1, child2]
print(len(gc.objects)) # 3
gc.collect()
print(len(gc.objects)) # 3
child1.children = [gc.allocate()]
print(len(gc.objects)) # 4
gc.collect()
print(len(gc.objects)) # 4
root.children = [child1]
gc.collect()
print(len(gc.objects)) # 3
This implementation demonstrates the basic principles of mark-and-sweep garbage collection, though real-world garbage collectors are much more complex and optimized.
8. Implement a Basic Regular Expression Matcher
Understanding how regular expressions work under the hood can be valuable, especially for roles involving text processing or compiler design.
Question:
Implement a basic regular expression matcher that supports ‘.’ (matches any single character) and ‘*’ (matches zero or more of the preceding element).
Solution:
Here’s a recursive implementation of a basic regex matcher in Python:
def match(text, pattern):
if not pattern:
return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return (match(text, pattern[2:]) or
(first_match and match(text[1:], pattern)))
else:
return first_match and match(text[1:], pattern[1:])
# Usage
print(match("aa", "a")) # False
print(match("aa", "a*")) # True
print(match("ab", ".*")) # True
print(match("aab", "c*a*b")) # True
This implementation handles the basic cases of ‘.’ and ‘*’, but doesn’t support more complex regex features like grouping or alternation.
9. Implement a Basic JSON Parser
Parsing is a fundamental concept in computer science, and implementing a basic parser tests your ability to work with grammars and recursive structures.
Question:
Implement a basic JSON parser that can handle strings, numbers, booleans, null, arrays, and objects.
Solution:
Here’s a simplified JSON parser implementation in Python:
import re
def parse_json(s):
def parse_value():
nonlocal i
if s[i] == '{':
return parse_object()
elif s[i] == '[':
return parse_array()
elif s[i] == '"':
return parse_string()
elif s[i].isdigit() or s[i] == '-':
return parse_number()
elif s[i:i+4] == 'true':
i += 4
return True
elif s[i:i+5] == 'false':
i += 5
return False
elif s[i:i+4] == 'null':
i += 4
return None
def parse_object():
nonlocal i
obj = {}
i += 1 # Skip '{'
while s[i] != '}':
key = parse_string()
i += 1 # Skip ':'
value = parse_value()
obj[key] = value
if s[i] == ',':
i += 1
i += 1 # Skip '}'
return obj
def parse_array():
nonlocal i
arr = []
i += 1 # Skip '['
while s[i] != ']':
value = parse_value()
arr.append(value)
if s[i] == ',':
i += 1
i += 1 # Skip ']'
return arr
def parse_string():
nonlocal i
i += 1 # Skip opening quote
start = i
while s[i] != '"':
if s[i] == '\\':
i += 1
i += 1
result = s[start:i]
i += 1 # Skip closing quote
return result
def parse_number():
nonlocal i
start = i
while i < len(s) and (s[i].isdigit() or s[i] in '.-+eE'):
i += 1
return float(s[start:i])
i = 0
return parse_value()
# Usage
json_str = '{"name": "John", "age": 30, "city": "New York", "hobbies": ["reading", "swimming"]}'
parsed = parse_json(json_str)
print(parsed)
This parser handles basic JSON structures but doesn’t include full error handling or support for all JSON escape sequences.
10. Implement a Basic Neural Network
With the increasing importance of machine learning, understanding the basics of neural networks can be valuable in many software engineering roles.
Question:
Implement a basic feedforward neural network with one hidden layer and train it on a simple dataset.
Solution:
Here’s a simple implementation of a neural network with one hidden layer in Python, using numpy for efficient matrix operations:
import numpy as np
class NeuralNetwork:
def __init__(self, input_size, hidden_size, output_size):
self.W1 = np.random.randn(input_size, hidden_size)
self.b1 = np.zeros((1, hidden_size))
self.W2 = np.random.randn(hidden_size, output_size)
self.b2 = np.zeros((1, output_size))
def sigmoid(self, x):
return 1 / (1 + np.exp(-x))
def sigmoid_derivative(self, x):
return x * (1 - x)
def forward(self, X):
self.z1 = np.dot(X, self.W1) + self.b1
self.a1 = self.sigmoid(self.z1)
self.z2 = np.dot(self.a1, self.W2) + self.b2
self.a2 = self.sigmoid(self.z2)
return self.a2
def backward(self, X, y, output):
self.dZ2 = output - y
self.dW2 = np.dot(self.a1.T, self.dZ2)
self.db2 = np.sum(self.dZ2, axis=0, keepdims=True)
self.dZ1 = np.dot(self.dZ2, self.W2.T) * self.sigmoid_derivative(self.a1)
self.dW1 = np.dot(X.T, self.dZ1)
self.db1 = np.sum(self.dZ1, axis=0)
def train(self, X, y, epochs, learning_rate):
for _ in range(epochs):
output = self.forward(X)
self.backward(X, y, output)
self.W1 -= learning_rate * self.dW1
self.b1 -= learning_rate * self.db1
self.W2 -= learning_rate * self.dW2
self.b2 -= learning_rate * self.db2
# Usage
X = np.array([[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]])
y = np.array([[0], [1], [1], [0]])
nn = NeuralNetwork(3, 4, 1)
nn.train(X, y, epochs=10000, learning_rate=0.1)
# Test
print(nn.forward(np.array([[1, 1, 0]])))
This implementation demonstrates the basic concepts of feedforward neural networks and backpropagation, though it’s simplified and not optimized for large-scale problems.
Conclusion
These ten unexpected coding interview questions cover a wide range of topics, from system design to low-level programming concepts. While you may not encounter these exact questions in your interviews, understanding the principles behind them will help you tackle similar challenges.
Remember, the key to succeeding in coding interviews is not just knowing the solutions to specific problems, but understanding the underlying concepts and being able to apply them to new situations. Practice regularly, focus on problem-solving skills, and don’t be afraid to think outside the box during your interviews.
Good luck with your coding interviews!