- DSA
- LLD
- HLD
Q1: Design and implement an Excel Spreadsheet
Design a minimal in-memory spreadsheet library that supports integer values and simple =A+B formulas with two integers. The system must allow setting cells to raw values (including formulas), resetting them with an empty string, and viewing both raw and computed values. A print method should display the full grid clearly.
Example:
Input: set(0, 0, “=2+8”) set(0, 1, “5”) set(1, 0, “”) // reset print()
Output: [Raw: =2+8 | Computed: 10] [Raw: 5 | Computed: 5] [Raw: | Computed: 0]
Explanation: Cell (0,0) stores=2+8 as raw value and computes 10. Cell (0,1) stores 5 directly. Cell (1,0) is reset to default (empty raw, 0 computed). The print method shows both raw and computed views.
Q2: Problem Statement: Design a Song Play Analytics System
Build a class SongAnalytics to track song plays and generate analytics. It should assign auto-incrementing IDs when adding songs, record play events by user, and print a summary sorted by unique listener count (descending), then by song name (ascending). Each user is counted only once per song.
Example:
Input: add_song(“Shape of You”) add_song(“Blinding Lights”) play_song(1, 101) play_song(1, 102) play_song(2, 101) play_song(2, 103) play_song(2, 101) // duplicate user print_analytics()
Output: Blinding Lights (2 unique listeners) Shape of You (2 unique listeners)
Explanation: Both songs have 2 unique listeners. Since counts are equal, they are sorted lexicographically: “Blinding Lights” comes before “Shape of You”.
Q3: Add driver and per hour rate.
Design a system to calculate total payment for delivery drivers based on hourly rates and delivery timestamps (epoch seconds). Support adding drivers, logging deliveries, and computing total pay. Assume each delivery contributes to active time.
Example:
Input: add_driver(1, 20.0) // driver 1, $20/hour add_delivery(1, 1672531200) // Jan 1, 2023 00:00:00 add_delivery(1, 1672534800) // Jan 1, 2023 01:00:00 get_total_payment()
Output: 20.0
Explanation: Driver worked 3600 seconds (1 hour) at $20/hour → $20.0 total.
Q4: Design a Driver Payment Management System
Extend Q3 with payment cycles. Support clearing payments at a given time and querying unpaid amounts. Drivers earn based on time between deliveries.
Example:
Input: add_driver(1, 25.0) add_delivery(1, 1672531200) add_delivery(1, 1672538400) // +2 hours add_delivery(1, 1672545600) // +2 hours clear_payments(1672542000) // clear at +3 hours mark get_unpaid_amount()
Output: 25.0
Explanation: Total time: 4 hours → $100. Cleared at 3 hours → $75 paid. Unpaid: $25 for last hour.
Q5: Competing Reactions in an Isothermal Reactor
Maximize net benefit of a reactor producing B from A, while minimizing unwanted C. Reactions A→B and A→C have different activation energies. Optimize temperature T (K) and residence time t_res (s) to maximize (benefits from B) – (costs of A, operation, disposal of C, reuse of A).
Example:
Input: Constants provided; optimize T ∈ [1200] K, t_res ∈ [0.1, 10] s.
Output: Optimal T: 850 K, t_res: 2.1 s Final: A=0.45 M, B=2.30 M, C=0.25 M Net benefit: $342.50 per M of A
Explanation: Higher T favors C (higher Ea), so optimal T balances B yield vs C formation. Net benefit includes: +$460 (B), -$50 (A), -$420 (operation), -$0.25 (C disposal), +$2.25 (A reuse) → $342.50.
Q6: Currency Conversion Rate Calculation Using Exchange Mappings
Given currency conversion rates as triplets [from, to, rate], compute the rate from a source to target currency. Use graph traversal (BFS/DFS) to find a path and multiply rates.
Example:
Input: rates = [[‘USD’, ‘JPY’, 110], [‘USD’, ‘AUD’, 1.45], [‘JPY’, ‘GBP’, 0.0070]] from_to = [‘GBP’, ‘AUD’]
Output: 1.89
Explanation: Path: GBP ← JPY ← USD → AUD. Rates: 1 GBP = 1/0.0070 ≈ 142.86 JPY, 142.86 JPY = 142.86/110 ≈ 1.30 USD, 1.30 USD = 1.30 × 1.45 ≈ 1.89 AUD.
Q7: Design a Data Store to execute
Build a key-value store with CRUD operations and nested transaction support. begin() starts a transaction. commit() saves all changes; rollback() undoes them. Extend to commit(t) and rollback(t) for partial apply/undo of the first/last t state-changing operations.
Example:
Input: create(“key1”, “val1”) begin() update(“key1”, “val2”) delete(“key1”) create(“key2”, “val3”) rollback(1)
Output: read(“key1”) → “val2” read(“key2”) → “val3”
Explanation: Three transaction ops: update, delete, create. rollback(1) undoes only the last (create), so key2 is removed. key1 remains updated to “val2”.
Q8: Design an Event Tracking and Analytics System
Design a scalable system like Amplitude to ingest, store, process, and query user events (e.g., “page_viewed”). Must support high-throughput writes, real-time aggregations (DAU, funnels), flexible queries, and horizontal scaling with fault tolerance.
Example:
Input: track_event(user_id=101, event=”purchase”, amount=99.99, timestamp=now) query(dau, from=“2023-01-01”, to=“2023-01-02”)
Output: DAU: 1420
Explanation: Events are ingested via API → Kafka → processed by Flink/Spark → stored in ClickHouse/DynamoDB. DAU query scans user-day keys in OLAP store and returns count of unique users.
Q9: Expense Policy Rules Engine
Design a rules engine to validate employee expenses. Apply expense-level rules (e.g., max $75 for restaurants) and trip-level rules (e.g., total trip ≤ $2000). Return violations clearly.
Example:
Input: expenses = [ {“expense_id”: “e1”, “trip_id”: “t1”, “amount_usd”: 80, “expense_type”: “restaurant”}, {“expense_id”: “e2”, “trip_id”: “t1”, “amount_usd”: 1500, “expense_type”: “airfare”} ] rules = [“no_restaurant_over_75”, “no_airfare”, “trip_total_under_2000”] evaluate(expenses, rules)
Output: [“e1: restaurant expense $80 exceeds $75 limit”, “e2: airfare expenses are not allowed”, “t1: total trip expenses $1580 exceed $2000 limit”]
Explanation: Three violations: one per-expense (restaurant), one per-expense (airfare), one per-trip (total). Engine evaluates each rule across relevant scope and returns descriptive errors.
