Competitive Programming: Think Fast, Code Faster

# Rule of thumb: 10^8 operations per second
# n = 10^6: need O(n log n) or better
# n = 10^4: can afford O(n^2)
# n = 100: can afford O(n^3) or even O(n^4)

# Common complexities
# O(1) - constant
def access_array(arr, index): return arr[index]

# O(log n) - logarithmic
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1

# O(n) - linear
def linear_search(arr, target): for num in arr: if num == target: return True return False

# O(n log n) - linearithmic
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right)

# O(n^2) - quadratic
def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr

# O(2^n) - exponential (avoid!)
def fibonacci_naive(n): if n <= 1: return n return fibonacci_naive(n-1) + fibonacci_naive(n-2)

# Complexity table for different n
import time
print("Time Limit Exceeded (TLE) if time > 1-2 seconds")
print("n=10: O(n^5) = 100,000 ops ✓")
print("n=100: O(n^3) = 1,000,000 ops ✓")
print("n=1,000: O(n^2) = 1,000,000 ops ✓")
print("n=10,000: O(n log n) ≈ 130,000 ops ✓")
print("n=100,000: O(n) = 100,000 ops ✓")
print("n=1,000,000: O(log n) ≈ 20 ops ✓")

def two_sum_sorted(arr, target): """Find two numbers that sum to target in sorted array""" left = 0 right = len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target: return [left + 1, right + 1]  # 1-indexed elif current_sum < target: left += 1 else: right -= 1 return []

# Test
arr = [2, 7, 11, 15]
print(two_sum_sorted(arr, 9))  # [1, 2]

def max_area(heights): """Find max water area between two bars - O(n)""" left = 0 right = len(heights) - 1 max_area_val = 0 while left < right: width = right - left area = width * min(heights[left], heights[right]) max_area_val = max(max_area_val, area) if heights[left] < heights[right]: left += 1 else: right -= 1 return max_area_val

# Test: bars at heights [1,8,6,2,5,4,8,3,7]
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

def max_sum_k_subarray(arr, k): """Max sum of k consecutive elements - O(n)""" if k > len(arr): return 0 # Calculate first window window_sum = sum(arr[:k]) max_sum = window_sum # Slide the window for i in range(k, len(arr)): window_sum = window_sum - arr[i - k] + arr[i] max_sum = max(max_sum, window_sum) return max_sum

# Test
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(max_sum_k_subarray(arr, 4))  # 24 (10+2+3+1+8 nope... 4+2+10+2=18? no)
# Actually: 2+3+1+0+20=26? No. 4+2+10+2=18, 2+10+2+3=17, 10+2+3+1=16, 2+3+1+0=6, 3+1+0+20=24 ✓

def longest_substring_no_repeat(s): """Find longest substring with unique characters - O(n)""" char_index = {} max_length = 0 left = 0 for right in range(len(s)): if s[right] in char_index and char_index[s[right]] >= left: left = char_index[s[right]] + 1 char_index[s[right]] = right max_length = max(max_length, right - left + 1) return max_length

# Test
print(longest_substring_no_repeat("abcabcbb"))  # 3 (abc)
print(longest_substring_no_repeat("bbbbb")) # 1 (b)
print(longest_substring_no_repeat("pwwkew")) # 3 (wke)

def activity_selection(activities): """Select max non-overlapping activities - O(n log n)""" # activities = [(start, end), ...] # Sort by end time activities.sort(key=lambda x: x[1]) selected = [activities[0]] for i in range(1, len(activities)): # If start time >= last selected end time, no overlap if activities[i][0] >= selected[-1][1]: selected.append(activities[i]) return selected

# Example: school class schedule
activities = [(9, 10), (9, 11), (10, 11), (11, 12), (10, 13)]
print(activity_selection(activities))  # [(9, 10), (10, 11), (11, 12)]

def fractional_knapsack(items, capacity): """Take items with best value/weight ratio - O(n log n)""" # items = [(weight, value), ...] # Sort by value/weight ratio (descending) items.sort(key=lambda x: x[1] / x[0], reverse=True) total_value = 0 remaining_capacity = capacity for weight, value in items: if weight <= remaining_capacity: remaining_capacity -= weight total_value += value else: total_value += (remaining_capacity / weight) * value break return total_value

# Example: jewelry heist
items = [(10, 100), (20, 200), (30, 150)]  # (weight, value)
capacity = 30
print(fractional_knapsack(items, capacity))  # 400

# Problem: Given array, find element that appears > n/3 times
# Constraints: n <= 10^5, time limit: 1 second

# Approach 1: Brute force - O(n^2) ✗ Too slow
def find_majority_slow(arr): for num in arr: count = arr.count(num) if count > len(arr) // 3: return num

# Approach 2: Hash map - O(n) space, O(n) time ✓ Good
def find_majority_hash(arr): count = {} for num in arr: count[num] = count.get(num, 0) + 1 for num, cnt in count.items(): if cnt > len(arr) // 3: return num

# Approach 3: Boyer-Moore voting - O(n) time, O(1) space ✓ Optimal
def find_majority_voting(arr): candidate1, candidate2 = None, None count1, count2 = 0, 0 for num in arr: if num == candidate1: count1 += 1 elif num == candidate2: count2 += 1 elif count1 == 0: candidate1, count1 = num, 1 elif count2 == 0: candidate2, count2 = num, 1 else: count1 -= 1 count2 -= 1 return candidate1 if arr.count(candidate1) > len(arr) // 3 else candidate2

From Concept to Reality: Competitive Programming: Think Fast, Code Faster

In the professional world, the difference between a good engineer and a great one often comes down to understanding fundamentals deeply. Anyone can copy code from Stack Overflow. But when that code breaks at 2 AM and your application is down — affecting millions of users — only someone who truly understands the underlying concepts can diagnose and fix the problem.

Competitive Programming: Think Fast, Code Faster is one of those fundamentals. Whether you end up working at Google, building your own startup, or applying CS to solve problems in agriculture, healthcare, or education, these concepts will be the foundation everything else is built on. Indian engineers are known globally for their strong fundamentals — this is why companies worldwide recruit from IITs, NITs, IIIT Hyderabad, and BITS Pilani. Let us make sure you have that same strong foundation.

Object-Oriented Programming: Modelling the Real World

OOP lets you model real-world entities as code "objects." Each object has properties (data) and methods (behaviour). Here is a practical example:

class BankAccount: """A simple bank account — like what SBI or HDFC uses internally""" def __init__(self, holder_name, initial_balance=0): self.holder = holder_name self.balance = initial_balance # Private in practice self.transactions = [] # History log def deposit(self, amount): if amount <= 0: raise ValueError("Deposit must be positive") self.balance += amount self.transactions.append(f"+₹{amount}") return self.balance def withdraw(self, amount): if amount > self.balance: raise ValueError("Insufficient funds!") self.balance -= amount self.transactions.append(f"-₹{amount}") return self.balance def statement(self): print(f"
--- Account Statement: {self.holder} ---") for t in self.transactions: print(f"  {t}") print(f"  Balance: ₹{self.balance}")

# Usage
acc = BankAccount("Rahul Sharma", 5000)
acc.deposit(15000) # Salary credited
acc.withdraw(2000) # UPI payment to Swiggy
acc.withdraw(500) # Metro card recharge
acc.statement()

This is encapsulation — bundling data and behaviour together. The user of BankAccount does not need to know HOW deposit works internally; they just call it. Inheritance lets you extend this: a SavingsAccount could inherit from BankAccount and add interest calculation. Polymorphism means different account types can respond to the same .withdraw() method differently (savings accounts might check minimum balance, current accounts might allow overdraft).

Real-World System Design: Swiggy's Architecture

When you order food on Swiggy, here is what happens behind the scenes in about 2 seconds: your location is geocoded (algorithms), nearby restaurants are queried from a spatial index (data structures), menu prices are pulled from a database (SQL), delivery time is estimated using ML models trained on historical data (AI), the order is placed in a distributed message queue (Kafka), a delivery partner is assigned using a matching algorithm (optimization), and real-time tracking begins using WebSocket connections (networking). EVERY concept in your CS curriculum is being used simultaneously to deliver your biryani.

How the Web Request Cycle Works

Every time you visit a website, a precise sequence of events occurs. Here is the flow:

 You (Browser) DNS Server Web Server | | | |---[1] bharath.ai --->| | | | | |<--[2] IP: 76.76.21.9| | | | | |---[3] GET /index.html ----------------->  | | | | | | [4] Server finds file, | | runs server code, | | prepares response | | | |<---[5] HTTP 200 OK + HTML + CSS + JS --- | | | | [6] Browser parses HTML | Loads CSS (styling) | Executes JS (interactivity) | Renders final page |

Step 1-2 is DNS resolution — converting a human-readable domain name to a machine-readable IP address. Step 3 is the HTTP request. Step 4 is server-side processing (this is where frameworks like Node.js, Django, or Flask operate). Step 5 is the HTTP response. Step 6 is client-side rendering (this is where React, Angular, or Vue operate).

In a real-world scenario, this cycle also involves CDNs (Content Delivery Networks), load balancers, caching layers, and potentially microservices. Indian companies like Jio use this exact architecture to serve 400+ million subscribers.

Production Engineering: Competitive Programming: Think Fast, Code Faster at Scale

Understanding competitive programming: think fast, code faster at an academic level is necessary but not sufficient. Let us examine how these concepts manifest in production environments where failure has real consequences.

Consider India's UPI system processing 10+ billion transactions monthly. The architecture must guarantee: atomicity (a transfer either completes fully or not at all — no half-transfers), consistency (balances always add up correctly across all banks), isolation (concurrent transactions on the same account do not interfere), and durability (once confirmed, a transaction survives any failure). These are the ACID properties, and violating any one of them in a payment system would cause financial chaos for millions of people.

At scale, you also face the thundering herd problem: what happens when a million users check their exam results at the same time? (CBSE result day, anyone?) Without rate limiting, connection pooling, caching, and graceful degradation, the system crashes. Good engineering means designing for the worst case while optimising for the common case. Companies like NPCI (the organisation behind UPI) invest heavily in load testing — simulating peak traffic to identify bottlenecks before they affect real users.

Monitoring and observability become critical at scale. You need metrics (how many requests per second? what is the 99th percentile latency?), logs (what happened when something went wrong?), and traces (how did a single request flow through 15 different microservices?). Tools like Prometheus, Grafana, ELK Stack, and Jaeger are standard in Indian tech companies. When Hotstar streams IPL to 50 million concurrent users, their engineering team watches these dashboards in real-time, ready to intervene if any metric goes anomalous.

The career implications are clear: engineers who understand both the theory (from chapters like this one) AND the practice (from building real systems) command the highest salaries and most interesting roles. India's top engineering talent earns ₹50-100+ LPA at companies like Google, Microsoft, and Goldman Sachs, or builds their own startups. The foundation starts here.

Key Vocabulary

Here are important terms from this chapter that you should know:

💡 Interview-Style Problem

Here is a problem that frequently appears in technical interviews at companies like Google, Amazon, and Flipkart: "Design a URL shortener like bit.ly. How would you generate unique short codes? How would you handle millions of redirects per second? What database would you use and why? How would you track click analytics?"

Think about: hash functions for generating short codes, read-heavy workload (99% redirects, 1% creates) suggesting caching, database choice (Redis for cache, PostgreSQL for persistence), and horizontal scaling with consistent hashing. Try sketching the system architecture on paper before looking up solutions. The ability to think through system design problems is the single most valuable skill for senior engineering roles.

Where This Takes You

The knowledge you have gained about competitive programming: think fast, code faster is directly applicable to: competitive programming (Codeforces, CodeChef — India has the 2nd largest competitive programming community globally), open-source contribution (India is the 2nd largest contributor on GitHub), placement preparation (these concepts form 60% of technical interview questions), and building real products (every startup needs engineers who understand these fundamentals).

India's tech ecosystem offers incredible opportunities. Freshers at top companies earn ₹15-50 LPA; experienced engineers at FAANG companies in India earn ₹50-1 Cr+. But more importantly, the problems being solved in India — digital payments for 1.4 billion people, healthcare AI for rural areas, agricultural tech for 150 million farmers — are some of the most impactful engineering challenges in the world. The fundamentals you are building will be the tools you use to tackle them.

Crafted for Class 7–9 • Graph Algorithms & Advanced DS • Aligned with NEP 2020 & CBSE Curriculum