Python Data Structures and Coding Interview Questions and Answers

15 hands-on questions: time complexity, collections, sorting, slicing, common coding tasks, and Python idioms.

1. 1. What is the time complexity of common list, dict, and set operations?

   List: index access O(1), append O(1) amortized, insert or delete in the middle O(n), membership test O(n), sort O(n log n). Dict and set: lookup, insert, and delete are O(1) on average and O(n) in the worst case. Membership testing in a set or dict is far faster than in a list for large data.

2. 2. How do you reverse a string or list in Python?

   Use slicing with a negative step for strings and lists, or reversed() for an iterator, or list.reverse() to reverse a list in place.

   text = 'python'
   print(text[::-1])                  # nohtyp
   nums = [1, 2, 3]
   print(list(reversed(nums)))        # [3, 2, 1]
   nums.reverse()                     # in place

3. 3. How do you check whether a string is a palindrome?

   Normalize it and compare it with its reverse.

   def is_palindrome(text):
       cleaned = [c.lower() for c in text if c.isalnum()]
       return cleaned == cleaned[::-1]
   
   print(is_palindrome('A man, a plan, a canal: Panama'))   # True

4. 4. How do you count the frequency of items?

   Use collections.Counter, which is a dictionary subclass built for counting, with most_common for top items.

   from collections import Counter
   words = 'the cat and the hat'.split()
   counts = Counter(words)
   print(counts.most_common(1))   # [('the', 2)]

5. 5. How do you find duplicates in a list efficiently?

   Track seen items in a set for O(n) time.

   def duplicates(items):
       seen, dupes = set(), set()
       for item in items:
           if item in seen:
               dupes.add(item)
           seen.add(item)
       return dupes

6. 6. How would you solve the two-sum problem?

   Store each number's index in a dictionary and, for every number, look up its complement. This runs in O(n) time and O(n) space, compared with O(n squared) for checking every pair.

   def two_sum(nums, target):
       seen = {}
       for i, n in enumerate(nums):
           if target - n in seen:
               return [seen[target - n], i]
           seen[n] = i
       return []

7. 7. How does sorting work in Python? What is the difference between sort and sorted?

   sorted(iterable) returns a new sorted list, while list.sort() sorts in place and returns None. Both use Timsort, which is stable and O(n log n). Use the key argument for custom ordering and reverse=True for descending.

   people = [('Ada', 36), ('Bob', 25), ('Cy', 36)]
   print(sorted(people, key=lambda p: (-p[1], p[0])))

8. 8. How does slicing work?

   sequence[start:stop:step] takes items from start up to but not including stop. Negative indexes count from the end, missing parts default to the start, end, and step 1, and slices create a new object. Out-of-range slices do not raise errors.

   nums = [0, 1, 2, 3, 4, 5]
   print(nums[1:4])    # [1, 2, 3]
   print(nums[::2])    # [0, 2, 4]
   print(nums[-2:])    # [4, 5]

9. 9. What is the difference between enumerate, zip, and map?

   enumerate pairs each item with its index. zip walks several iterables in parallel and stops at the shortest. map applies a function to every item lazily. In modern Python, comprehensions are often preferred over map and filter for readability.

   for i, name in enumerate(['a', 'b']):
       print(i, name)
   for name, score in zip(['a', 'b'], [90, 80]):
       print(name, score)

10. 10. How do you merge two dictionaries?

    In Python 3.9 and newer use the union operator: merged = a | b, where the right-hand values win on conflicts. In older code use {**a, **b}. To update in place use a.update(b) or a |= b.

11. 11. Which standard library data structures help in coding problems?

    collections.deque for fast appends and pops at both ends (queues, sliding windows), collections.defaultdict and Counter for grouping and counting, heapq for priority queues and top-k problems, bisect for binary search in sorted lists, and itertools for combinations, permutations, and grouping.

12. 12. How do you implement a stack and a queue?

    A list works as a stack with append and pop. For a queue use collections.deque, because list.pop(0) is O(n) while deque.popleft() is O(1).

    from collections import deque
    stack = []
    stack.append(1); stack.pop()
    queue = deque()
    queue.append(1); queue.popleft()

13. 13. How do you read a large file without loading it into memory?

    Iterate over the file object line by line, which reads lazily, or process it in chunks.

    with open('big.log', encoding='utf-8') as f:
        errors = sum(1 for line in f if 'ERROR' in line)

14. 14. How do you find the second largest number in a list?

    For a one-pass approach, track the two largest values. For simplicity, convert to a set to drop duplicates and take the largest two with heapq or sorting.

    import heapq
    def second_largest(nums):
        unique = set(nums)
        if len(unique) < 2:
            return None
        return heapq.nlargest(2, unique)[1]

15. 15. What Pythonic idioms do interviewers like to see?

    Use enumerate instead of range(len(x)), zip to iterate in parallel, comprehensions for simple transformations, with for resources, dictionary methods such as get and setdefault, unpacking for swaps (a, b = b, a), truthiness checks like if items:, and the standard library before writing your own helper.