Category: python interview questions

Finding duplicates in a list can be approached in several ways, depending on the requirements and constraints (e.g., time complexity, memory usage). Here are various methods:

1. Using a Dictionary (Efficient Approach)

This approach uses a dictionary (or a collections.Counter) to count occurrences of each element.

def find_duplicates(lst):
    element_counts = {}
    duplicates = []

    for item in lst:
        if item in element_counts:
            element_counts[item] += 1
        else:
            element_counts[item] = 1

    for item, count in element_counts.items():
        if count > 1:
            duplicates.append(item)

    return duplicates

# Example usage
lst = [1, 2, 3, 2, 4, 5, 1, 6, 1]
print(find_duplicates(lst))  # Output: [1, 2]

Time Complexity: O(n)O(n)
Space Complexity: O(n)O(n) (for the dictionary)

2. Using collections.Counter

A cleaner way to count occurrences is to use collections.Counter.

from collections import Counter

def find_duplicates(lst):
    counts = Counter(lst)
    return [item for item, count in counts.items() if count > 1]

# Example usage
lst = [1, 2, 3, 2, 4, 5, 1, 6, 1]
print(find_duplicates(lst))  # Output: [1, 2]

Time Complexity: O(n)O(n)
Space Complexity: O(n)O(n)

3. Using a Set (Efficient Memory-wise)

This approach uses a set to track seen elements and another set to store duplicates.

def find_duplicates(lst):
    seen = set()
    duplicates = set()

    for item in lst:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)

    return list(duplicates)

# Example usage
lst = [1, 2, 3, 2, 4, 5, 1, 6, 1]
print(find_duplicates(lst))  # Output: [1, 2]

Time Complexity: O(n)O(n)
Space Complexity: O(n)O(n) (for the sets)

4. Using Sorting (In-Place)

This approach first sorts the list, then checks adjacent elements for duplicates.

def find_duplicates(lst):
    lst.sort()  # Sort the list (in-place)
    duplicates = []

    for i in range(1, len(lst)):
        if lst[i] == lst[i - 1] and lst[i] not in duplicates:
            duplicates.append(lst[i])

    return duplicates

# Example usage
lst = [1, 2, 3, 2, 4, 5, 1, 6, 1]
print(find_duplicates(lst))  # Output: [1, 2]

Time Complexity: O(nlog⁡n)O(n \log n) (due to sorting)
Space Complexity: O(1)O(1) (in-place sorting)

5. Brute Force (Inefficient)

This naive approach compares each element to every other element in the list.

def find_duplicates(lst):
    duplicates = []

    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j] and lst[i] not in duplicates:
                duplicates.append(lst[i])

    return duplicates

# Example usage
lst = [1, 2, 3, 2, 4, 5, 1, 6, 1]
print(find_duplicates(lst))  # Output: [1, 2]

Time Complexity: O(n2)O(n^2)
Space Complexity: O(n)O(n) (for the duplicates list)

Summary of Approaches

For most practical purposes, dictionary-based or set-based approaches are preferred due to their efficiency.

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Here are several methods to generate the Fibonacci sequence:

1. Iterative Approach (Efficient)

def fibonacci_iterative(n):
    sequence = []
    a, b = 0, 1
    for _ in range(n):
        sequence.append(a)
        a, b = b, a + b
    return sequence

# Example usage
print(fibonacci_iterative(10))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

2. Recursive Approach (Less Efficient for Large n)

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Generate a sequence
n = 10
sequence = [fibonacci_recursive(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Note: This approach has exponential time complexity (O(2n)O(2^n)) due to repeated calculations.

3. Memoization (Efficient Recursive Approach)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memoized(n):
    if n <= 1:
        return n
    return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)

# Generate a sequence
n = 10
sequence = [fibonacci_memoized(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

4. Generator Approach

def fibonacci_generator(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

# Example usage
print(list(fibonacci_generator(10)))  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

5. Matrix Exponentiation (Advanced)

This method uses matrix exponentiation for a logarithmic time complexity solution.

import numpy as np

def fibonacci_matrix(n):
    F = np.matrix([[1, 1], [1, 0]])
    result = (F ** (n - 1))[0, 0]
    return result

# Generate a sequence
n = 10
sequence = [fibonacci_matrix(i) for i in range(1, n + 1)]
print(sequence)  # Output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

6. Using a Formula (Binet’s Formula)

The Fibonacci number can also be computed using the golden ratio (ϕ\phi): F(n)=ϕn−(1−ϕ)n5F(n) = \frac{\phi^n – (1 – \phi)^n}{\sqrt{5}}

import math

def fibonacci_formula(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi**n - (-1/phi)**n) / math.sqrt(5))

# Generate a sequence
n = 10
sequence = [fibonacci_formula(i) for i in range(n)]
print(sequence)  # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Best Practice

• Use the iterative approach or generator for most practical applications.
• Use memoization for recursive implementations if you need recursion and want to avoid repeated calculations.
• Use matrix exponentiation or Binet’s formula for very large Fibonacci numbers.