Data Structures Career Options for Students in Delhi

# two_sum.py — the classic first-round problem
# Appears in almost every product-company online assessment.

def two_sum(nums: list, target: int) -> list:
    """
    Return the indices of the two numbers that add up to target.
    Time:  O(n)
    Space: O(n)
    """
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

# Test
print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]
print(two_sum([3, 3], 6))           # [0, 1]

# Why interviewers love this problem:
# - The brute-force O(n^2) solution is obvious. The O(n) hash-map
#   solution is not. It reveals whether you can trade time for space.
# - It is language-agnostic — Java, Python, C++, Go all work.
# - It tests the most common pattern in first-round interviews.
#
# Why Delhi NCR companies use it:
# - It filters candidates who can only write brute-force solutions.
# - It tests basic time/space complexity understanding.
# - It is the standard opener for both services firms and product
#   companies.
#
# The mistake most students make:
# - They memorise the solution instead of the pattern.
# - Interviewers vary the problem (3-sum, pairs with difference,
#   subarray sums) and the pattern is what transfers.

# level_order.py — the second most common pattern after hashing
# Appears in almost every second technical round.

from collections import deque

class TreeNode:
    def __init__(self, val: int, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root) -> list:
    """
    Return node values level by level (BFS).
    Time:  O(n)
    Space: O(w)  where w = max width of the tree
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

# Build a small tree and test
#         1
#        / \
#       2   3
#      / \
#     4   5
tree = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3))
print(level_order(tree))   # [[1], [2, 3], [4, 5]]

# Why interviewers test this:
# - BFS is the foundation of shortest-path problems, graph traversal,
#   social-network distances, and level-by-level processing.
# - It tests queue usage, which most students skip in favour of DFS.
# - The follow-up is often "now do it with DFS" — revealing whether
#   you understand both approaches.
#
# The pattern behind the problem:
# - BFS = queue = level by level.
# - DFS = stack or recursion = go deep first.
# - Once you see this pattern, you can adapt it to graphs, trees,
#   and grid problems.
#
# What Delhi NCR interviewers actually check:
# - Can you choose BFS over DFS and explain why?
# - Do you handle an empty tree?
# - Can you write clean code that a reviewer would accept?

# coin_change.py — the classic DP problem in third rounds
# Appears when interviewers want to see problem decomposition.

def coin_change(coins: list, amount: int) -> int:
    """
    Return the fewest coins needed to make up amount.
    Return -1 if the amount cannot be reached.
    Time:  O(amount * len(coins))
    Space: O(amount)
    """
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float("inf") else -1

# Test
print(coin_change([1, 2, 5], 11))   # 3  (5 + 5 + 1)
print(coin_change([2], 3))          # -1
print(coin_change([1], 0))          # 0

# Why interviewers test DP:
# - It distinguishes memorisers from problem solvers.
# - The naive recursion is exponential; the DP solution is polynomial.
# - It tests whether you can break a big problem into overlapping
#   subproblems — the core skill of engineering.
#
# The pattern behind the problem:
# - "Fewest / maximum / number of ways" + overlapping choices
#   → dynamic programming.
# - "All combinations / permutations" → backtracking.
# - "Shortest path" → BFS or Dijkstra.
#
# What Delhi NCR companies actually use this for:
# - Payment routing and pricing (fintech)
# - Inventory allocation and delivery batching (e-commerce)
# - Resource scheduling and optimisation (logistics)
#
# Learn the patterns, not the problems. There are hundreds of DP
# problems but only a handful of DP patterns.