Data Structures & Algorithms: Industry Edition

Unit 1: Introduction & Arrays

Basic Concepts, Complexity Analysis, Linear Arrays, Searching, Sorting — with real company examples from IRCTC, Flipkart, Google & Amazon.

🏢 Real Projects | 💻 5 Lab Programs | 📝 25 MCQs | 🎯 3 Interview Questions

Section 1

Industry Hook — The Real-World Problem First

🚂 The IRCTC Problem: 13 Million Tickets Per Day

Every morning at 10:00 AM IST, IRCTC's servers face an avalanche. Over 13 million tickets are booked daily, with peak loads hitting 25,000+ bookings per second during Tatkal window (10:00–10:15 AM). Behind every booking, the system must:

Search through 12,000+ trains and their seat availability — stored as arrays of seat objects
Insert a new booking into the reservation array in the correct position (by PNR, coach, berth)
Delete cancelled bookings and shift waitlisted passengers up — a classic array deletion
Sort the waitlist by priority (quota, booking time, senior citizen) — a sorting problem on arrays

If their search takes O(n) instead of O(log n), a single availability check on 2,000 seats takes 2,000 comparisons instead of 11. Multiply by 25,000 requests/second, and the system collapses in under a minute.

This is exactly the problem arrays, searching, and sorting solve. Let's understand how.

🇮🇳 IRCTCFlipkartGoogleAmazon

Section 2

Concept Explanation — Theory, Earned

2.1 Basic Concepts and Notations

What is a Data Structure?

Layer 1 — Intuition: Think of your wardrobe. You could throw all your clothes in a pile. But if you organize shirts on one shelf, trousers on another, and accessories in drawers, you find things in seconds instead of minutes. A data structure is exactly this — a way to organize data so operations (find, add, remove) are fast.

Layer 2 — Formal: A data structure is a specialized format for organizing, processing, retrieving, and storing data. Every data structure provides a trade-off between different operations.

What is an Algorithm?

An algorithm is a finite set of well-defined instructions to solve a specific problem. It takes input, processes it through a sequence of steps, and produces output. Key properties: Finiteness (must terminate), Definiteness (each step unambiguous), Input, Output, and Effectiveness (each step achievable).

2.2 Complexity Analysis: Time, Space & Trade-offs

Why do we measure complexity?

Layer 1 — Intuition: Imagine you're a delivery partner at Swiggy. You have 10 orders to deliver. You could deliver them randomly — or you could plan the shortest route. Both approaches "work," but one takes 40 minutes and the other takes 90 minutes. The difference is algorithmic efficiency.

Layer 2 — Visual: How long does sorting take as data grows?

Growth Visualization
Input Size:     10      100       1,000      1,000,000
─────────────────────────────────────────────────────────
O(1)            1       1         1          1
O(log n)        3       7         10         20
O(n)            10      100       1,000      1,000,000
O(n log n)      33      700       10,000     20,000,000
O(n²)           100     10,000    1,000,000  1,000,000,000,000 ← IRCTC would crash

Real consequence: IRCTC processes 1 million bookings daily. An O(n²) sort on this data would take approximately 11.5 days. An O(n log n) sort completes in under 20 seconds. This is why no production system uses bubble sort on large data.

Layer 3 — Formal Notations

Notation	Name	Meaning	Use
`O(f(n))`	Big-O	Upper bound — worst case won't exceed this	Most commonly used
`Ω(f(n))`	Big-Omega	Lower bound — best case is at least this	Best-case analysis
`Θ(f(n))`	Big-Theta	Tight bound — both upper and lower	Average-case analysis

Google processes over 8.5 billion searches per day. If their search algorithm was O(n) instead of O(log n) on their index of 100 billion pages, a single search would take 30 seconds instead of 0.0003 seconds. That's why Google invested billions in efficient data structures.

2.3 Linear Arrays: Memory Representation

Layer 1 — Intuition

An array is like a row of numbered lockers in a train station. Each locker has a fixed position (index), holds exactly one item (element), and you can go directly to locker #47 without opening lockers #1 through #46. This "go directly" ability is called random access — and it's the superpower of arrays.

Layer 2 — Memory Layout

Memory Diagram
Array: marks = [85, 92, 78, 95, 88]

Index:     0       1       2       3       4
        ┌───────┬───────┬───────┬───────┬───────┐
Value:  │  85   │  92   │  78   │  95   │  88   │
        └───────┴───────┴───────┴───────┴───────┘
Address: 1000    1004    1008    1012    1016
         base   base+4  base+8  base+12 base+16

Formula: Address(marks[i]) = Base_Address + i × sizeof(element)
         Address(marks[3]) = 1000 + 3 × 4 = 1012 ✓

This formula is why arrays give O(1) random access. The CPU computes base + i × size in a single instruction — it doesn't need to "walk through" previous elements. Linked lists, by contrast, must follow pointers one by one — O(n) access.

Layer 3 — Complexity Table

Operation	Best Case	Average	Worst Case	Space
Access by index	O(1)	O(1)	O(1)	O(1)
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)
Insert at end	O(1)	O(1)	O(1)	O(1)
Insert at position	O(1)	O(n)	O(n)	O(1)
Delete at position	O(1)	O(n)	O(n)	O(1)
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)

Real consequence: Flipkart's product catalog has 150 million products. A linear search for a product would need 150 million comparisons (≈3 seconds). Binary search on a sorted index does it in just 27 comparisons (microseconds). That's why every e-commerce search uses indexed, sorted data.

If arrays have O(1) access and O(1) insert at the end, why would anyone ever use a linked list? What's the hidden cost of arrays that makes linked lists valuable? (Hint: think about what happens when you insert in the middle of 10 million elements.)