Python Full-Stack Interview Questions 81–85 (Classic Algorithms I)

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!

81. Write a Python program to find duplicates in a list.

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]

82. Write a Python program to detect a cycle in a linked list.

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

83. Write a Python program to implement binary search.

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

84. Write a Python program to generate Fibonacci numbers.

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]

85. Write a Python program to check for prime numbers.

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!