Data Structures & Systems Design Assignment

Overview

This repository contains solutions for the Software Engineering Intern Assessment focused on Data Structures, Algorithms, and System Design concepts.

The assignment consists of two problems:

1. LRU Cache Implementation
2. Event Scheduler System

In addition to implementation, this submission includes:

• Algorithm explanation
• Time & Space Complexity Analysis
• Design Trade-offs
• Scalability Considerations
• Concurrency Discussion
• Future Enhancements

---

Problem 1: LRU Cache Implementation

Objective

Design and implement a Least Recently Used (LRU) Cache supporting:

get(key)
put(key, value)

Requirements

• Fixed cache capacity
• O(1) get operation
• O(1) put operation
• Automatic eviction of least recently used items when capacity is exceeded

---

Approach

To achieve constant-time performance, the implementation combines:

Hash Map (Dictionary)

Used for:

• Fast key lookup
• Fast insertion
• Fast deletion

Average complexity:

O(1)

Doubly Linked List

Used for:

• Tracking usage order
• Moving recently accessed items
• Removing least recently used items

Average complexity:

O(1)

---

Why This Combination?

A Hash Map alone provides fast lookup but cannot maintain access order.

A Doubly Linked List maintains order efficiently but cannot perform fast searches.

Combining both structures provides:

Operation	Complexity
get()	O(1)
put()	O(1)
remove()	O(1)
insert()	O(1)

---

LRU Cache Workflow

1. User accesses a key.
2. Node moves to the front of the list.
3. Most recently used items remain at the front.
4. Least recently used items remain near the tail.
5. When capacity is exceeded:
   • Tail node is removed.
   • Corresponding Hash Map entry is deleted.

---

Example

cache = LRUCache(2)

cache.put(1,1)
cache.put(2,2)

cache.get(1)

cache.put(3,3)

cache.get(2)

Output:

1
-1

---

Problem 2: Event Scheduler

Objective

Given a list of events:

[(start_time, end_time)]

Implement:

can_attend_all(events)
min_rooms_required(events)

---

Function 1: can_attend_all(events)

Determines whether a single person can attend all meetings without overlap.

Logic

1. Sort meetings by start time.
2. Compare each meeting with the previous one.
3. If:

current_start < previous_end

An overlap exists.

Return:

False

Otherwise:

True

---

Example

[(9,10), (10,11), (11,12)]

Output:

True

---

Function 2: min_rooms_required(events)

Determines the minimum number of meeting rooms required.

---

Approach

A Min Heap is used to track meeting end times.

Algorithm

1. Sort meetings by start time.

2. Insert first meeting's end time into heap.

3. For every new meeting:

   • If the earliest meeting has ended:

     • Reuse the room.

   • Otherwise:

     • Allocate a new room.

4. Heap size represents active meetings.

Maximum heap size equals minimum rooms required.

---

Example

[(9,10), (9.5,11), (10,12)]

Output:

2

---

Complexity Analysis

LRU Cache

Operation	Time
get()	O(1)
put()	O(1)
insert()	O(1)
delete()	O(1)

Space Complexity:

O(capacity)

---

Event Scheduler

can_attend_all()

Step	Complexity
Sorting	O(n log n)
Traversal	O(n)

Total:

O(n log n)

Space:

O(1)

---

min_rooms_required()

Step	Complexity
Sorting	O(n log n)
Heap Operations	O(n log n)

Total:

O(n log n)

Space:

O(n)

---

Design Trade-Offs

Why Hash Map + Doubly Linked List?

Hash Map

Advantages:

• Constant-time lookup
• Constant-time insertion
• Constant-time deletion

Limitation:

• No usage ordering

Doubly Linked List

Advantages:

• Efficient insertion
• Efficient deletion
• Maintains order

Limitation:

• Slow search

Combined Solution

The Hash Map locates nodes instantly.

The Doubly Linked List manages usage order.

Together they satisfy all LRU requirements efficiently.

---

Future Proofing

Assigning Meeting Rooms

Instead of storing:

end_time

Store:

(end_time, room_number)

Example:

(10, "Room A")
(11, "Room B")

Benefits:

• Actual room allocation
• Meeting schedules
• Calendar integration
• Resource utilization tracking

Example Output:

Meeting 1 -> Room A
Meeting 2 -> Room B
Meeting 3 -> Room A

---

Concurrency Considerations

Problem

Multiple threads may access the cache simultaneously.

Potential issues:

• Race conditions
• Corrupted pointers
• Data inconsistency
• Unexpected evictions

---

Solution

Protect critical sections using locks.

Example:

from threading import Lock

lock = Lock()

with lock:
    # critical section

Advanced Improvements

For production-scale systems:

• Read-Write Locks
• Fine-Grained Locking
• Concurrent Hash Maps
• Lock-Free Data Structures

---

Project Structure

DataStructures-SystemDesign-Assignment
│
├── README.md
├── lru_cache.py
├── event_scheduler.py
├── Assignment_Report.pdf
└── requirements.txt

---

Technologies Used

• Python 3
• Hash Maps
• Doubly Linked Lists
• Heaps (Priority Queue)
• Object-Oriented Programming
• Data Structures
• Algorithm Design
• System Design Principles

---

Key Concepts Demonstrated

• Time Complexity Optimization
• Space Complexity Analysis
• Cache Design
• Scheduling Algorithms
• Heap-Based Processing
• Data Structure Selection
• Concurrency Awareness
• Scalability Planning

---

Author

Akash Kumar

Software Engineering Intern Assessment Submission

June 2026