Loading…
Welcome to this lesson on fundamental Python algorithms. These are some of the most common, classic coding questions you might encounter in an interview. They aren't "trick" questions; they are designed to test your core problem-solving skills, your understanding of data structures, and your ability to write clean, efficient code. We'll cover each one with clear explanations, analogies, and runnable examples. Let's dive in!
This is a common question with several great answers. The interviewer is looking to see if you can move from a simple solution to a more efficient one.
Analogy: Imagine you are a bouncer at a party. You need to find out who has a "duplicate" name.
Example: Method 1 (Using a Set)
def find_duplicates_set(nums):
seen = set()
duplicates = set()
for num in nums:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return list(duplicates)
# --- Usage ---
my_list = [1, 2, 3, 4, 2, 5, 6, 1, 8, 3]
print(f"List: {my_list}")
print(f"Duplicates (set): {find_duplicates_set(my_list)}")
Expected Output:
List: [1, 2, 3, 4, 2, 5, 6, 1, 8, 3]
Duplicates (set): [1, 2, 3]
Example: Method 2 (Using `collections.Counter`)
from collections import Counter
def find_duplicates_counter(nums):
# Counter builds a hash map of {item: count}
counts = Counter(nums)
# Use a list comprehension to find items with count > 1
return [item for item, count in counts.items() if count > 1]
# --- Usage ---
my_list = [1, 2, 3, 4, 2, 5, 6, 1, 8, 3]
print(f"List: {my_list}")
print(f"Duplicates (Counter): {find_duplicates_counter(my_list)}")
Expected Output:
List: [1, 2, 3, 4, 2, 5, 6, 1, 8, 3]
Duplicates (Counter): [1, 2, 3]
This is a famous algorithm problem. The standard solution is Floyd's Tortoise and Hare (fast and slow pointer) algorithm.
Analogy: Imagine two runners on a track.
If the track is a straight line (no cycle), the fast runner will just reach the end. But if the track is a loop, the fast runner will eventually "lap" the slow runner, and they will land on the same spot. We just have to check if they ever meet.
# First, define the ListNode
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode | None) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while fast and fast.next:
if slow == fast:
return True # Cycle detected!
slow = slow.next
fast = fast.next.next
return False # Reached the end, no cycle
# --- Usage ---
# 1. Create a list WITH a cycle
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 # <-- This creates the cycle (4 points back to 2)
print(f"List 1 (1->2->3->4->2...): Has cycle? {has_cycle(node1)}")
# 2. Create a list WITHOUT a cycle
node5 = ListNode(5)
node6 = ListNode(6)
node5.next = node6
print(f"List 2 (5->6): Has cycle? {has_cycle(node5)}")
Expected Output:
List 1 (1->2->3->4->2...): Has cycle? True
List 2 (5->6): Has cycle? False
Binary search is a very efficient algorithm for finding an item in a sorted list . This is a critical pre-condition; it will not work on an unsorted list.
Analogy: You're looking for the word "Python" in a 1,000-page dictionary.
You repeat this, cutting the problem in half every time, which is extremely fast. This is an O(log n) algorithm.
def binary_search(sorted_list, target):
"""
Finds the index of a target in a sorted list.
Returns -1 if the target is not found.
"""
left = 0
right = len(sorted_list) - 1
while left <= right:
# Calculate mid-point, avoiding overflow
mid = (left + right) // 2
if sorted_list[mid] == target:
return mid # Found it!
elif sorted_list[mid] < target:
# Target is in the right half
left = mid + 1
else:
# Target is in the left half
right = mid - 1
return -1 # Target not in the list
# --- Usage ---
my_sorted_list = [2, 5, 7, 13, 19, 25, 30, 42]
target1 = 19
target2 = 100
print(f"List: {my_sorted_list}")
print(f"Find {target1}: Index {binary_search(my_sorted_list, target1)}")
print(f"Find {target2}: Index {binary_search(my_sorted_list, target2)}")
Expected Output:
List: [2, 5, 7, 13, 19, 25, 30, 42]
Find 19: Index 4
Find 100: Index -1
The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting from 0 and 1. (0, 1, 1, 2, 3, 5, 8, 13, ...)
While you can solve this with recursion, it's very inefficient (O(2^n)). The iterativesolution is much better (O(n)).
A generator is the most "Pythonic" way to handle this, as it generates the numbers one by one without storing the whole sequence in memory.
def fib_generator(n_terms):
"""
A generator that yields Fibonacci numbers up to n_terms.
"""
# Start with the first two numbers
a, b = 0, 1
count = 0
while count < n_terms:
yield a
# This is the magic:
# The new 'a' becomes 'b'
# The new 'b' becomes 'a + b'
a, b = b, a + b
count += 1
# --- Usage ---
print("First 10 Fibonacci numbers:")
# We can use the generator in a for loop
fib_seq = []
for num in fib_generator(10):
fib_seq.append(num)
print(fib_seq)
# Or convert it directly to a list
print(f"First 5: {list(fib_generator(5))}")
Expected Output:
First 10 Fibonacci numbers:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
First 5: [0, 1, 1, 2, 3]
A prime number is a number greater than 1 that has no divisors other than 1 and itself.
The key optimization is that you only need to check for divisors up to the square root of the number.
Analogy: If you are looking for factors of 100, once you find 2 (and its pair, 50), you don't need to check 50. If you find 4 (and 25), you don't need to check 25. The "halfway" point for factors is the square root (which is 10). If you haven't found a factor by the time you reach 10, you won't find one after.
import math
def is_prime(n):
"""Checks if a number is prime."""
# 1. Handle edge cases
if n < 2:
return False
if n == 2:
return True
# 2. Handle even numbers (optimization)
if n % 2 == 0:
return False
# 3. Check odd divisors up to the square root
# We only check odd numbers (3, 5, 7...)
limit = int(math.sqrt(n)) + 1
for i in range(3, limit, 2):
if n % i == 0:
return False
return True
# --- Usage ---
test_numbers = [1, 2, 3, 4, 17, 25, 97]
print("--- Prime Number Check ---")
for num in test_numbers:
print(f"Is {num} prime? {is_prime(num)}")
Expected Output:
--- Prime Number Check ---
Is 1 prime? False
Is 2 prime? True
Is 3 prime? True
Is 4 prime? False
Is 17 prime? True
Is 25 prime? False
Is 97 prime? True
Tip: These questions are all about clarity and efficiency. Always state your assumptions (like "this list must be sorted" for binary search) and talk through the time complexity (like O(n) or O(log n)) if you can. Good luck!
3 questions · no sign-up, nothing stored
Progress is stored in this browser only - no sign-up, nothing sent anywhere.
Step through the algorithms behind these answers one operation at a time, forwards or backwards, with the code highlighted as it runs.
Tortoise and hare, plus the algebra behind why restarting at the head finds the loop entry.
Including the overflow bug that sat in the JDK for nine years.
The Fibonacci question, with the call tree drawn and a memoisation toggle.
The set-based duplicate check, and what it costs when keys collide.