DEPARTMENT OF INFORMATION TECHNOLOGY
25 BATCH IT-3
Data Structures Using C ++
Assignment 1
Course Outcomes:
1. Understand the concepts of OOPs.
2. Analyse the time complexity of operations on data structures.
3. Apply sorting techniques, pattern-matching algorithms, and hashing.
4. Demonstrate operations on linear and nonlinear data structures.
5. Develop solutions to the problems using linear and nonlinear data structures.
Problem 1: Bank Account Class with Inheritance
CO: CO1
Bloom Level: BL3 (Apply)
Problem Statement:
Design a base class Account with private data members int accountNumber and double
balance. Implement public member functions: constructor Account(int acc, double bal),
virtual void deposit(double amount), virtual void withdraw(double amount), and double
getBalance() const. Derive SavingsAccount (adds double interestRate; deposit(amount)
adds interest: amount * interestRate) and CurrentAccount (adds double overdraftLimit;
withdraw(amount) allows balance to go negative but not below -overdraftLimit) from
Account. Write a function void printAccountInfo(Account *acc) that prints account
number and balance.
Constraints:
1000 ≤ accountNumber ≤ 9999
balance ≥ 0
Sample Input:
Account *acc1 = new SavingsAccount(1001, 5000, 0.05);
Account *acc2 = new CurrentAccount(1002, 3000, 1000);
acc1->deposit(1000);
acc2->withdraw(4000);
printAccountInfo(acc1);
printAccountInfo(acc2);
Expected Output:
Account 1001, Balance: 6300
Account 1002, Balance: -1000
Problem 2: Shape Hierarchy with Polymorphism
CO: CO1
Bloom Level: BL3 (Apply)
Problem Statement:
Define an abstract base class Shape with pure virtual functions: virtual double area() const
= 0 and virtual void display() const = 0. Derive Rectangle, Circle, and Triangle from
Shape. Each derived class stores appropriate dimensions and implements area() and
display(). Write a function void processShapes(std::vector<Shape*> &shapes) that calls
display() for each shape and computes and prints the total area of all shapes.
Constraints:
All dimensions > 0
Sample Input:
std::vector<Shape*> shapes;
shapes.push_back(new Rectangle(4, 5));
shapes.push_back(new Circle(3));
shapes.push_back(new Triangle(3, 4, 5));
processShapes(shapes);
Expected Output:
Rectangle: 4 x 5, area = 20
Circle: radius = 3, area = 28.27
Triangle: sides 3,4,5, area = 6
Total area = 54.27
Problem 3: Employee-Manager Hierarchy with Polymorphism
CO: CO1
Bloom Level: BL3 (Apply)
Problem Statement:
Design a base class Employee with private data members int id, std::string name, double
salary. Implement public member functions: constructor Employee(int i, const std::string
&n, double s), virtual void raiseSalary(double percent), and double getSalary() const.
Derive Manager from Employee with additional data member int teamSize.
Manager::raiseSalary(percent) gives an extra 5% bonus on top of the base raise. Write a
function void printEmployees(const std::vector<Employee*> &emps) that prints each
employee's name and salary.
Constraints:
id > 0
salary ≥ 0
Sample Input:
std::vector<Employee*> emps;
emps.push_back(new Employee(101, "Alice", 50000));
emps.push_back(new Manager(102, "Bob", 70000, 5));
emps[0]->raiseSalary(10);
emps[1]->raiseSalary(10);
printEmployees(emps);
Expected Output:
Alice 55000
Bob 80500
Problem 4: Point Class with Const Member Functions
CO: CO1
Bloom Level: BL3 (Apply)
Problem Statement:
Design a class Point that represents a 2D point with private data members double x,
double y. Implement public member functions: constructor Point(double a, double b),
void move(double dx, double dy) (changes x, y), double distance(const Point &other)
const (distance to another point), and void print() const (prints (x, y)). Write a function
void testPoint() that creates two Point objects, moves one of them, computes and prints
the distance between them.
Constraints:
No constraints on coordinates
Sample Input:
testPoint();
Expected Output:
(0, 0)
(3, 4)
Distance = 5
Problem 5: Multiple Inheritance - StudentEmployee
CO: CO1
Bloom Level: BL3 (Apply)
Problem Statement:
Design: Person with std::string name and int age. Student with int rollNo and double gpa.
Employee with int empId and double salary. Derive StudentEmployee from both Student
and Employee using virtual inheritance for Person to avoid ambiguity. StudentEmployee
has an additional data member std::string department. Implement void displayInfo() that
prints all details.
Constraints:
All numeric fields > 0
Sample Input:
StudentEmployee se("Alice", 20, 101, 3.8, 201, 50000, "CSE");
[Link]();
Expected Output:
Name: Alice, Age: 20
Roll: 101, GPA: 3.8
EmpId: 201, Salary: 50000, Dept: CSE
Problem 6: Sort an Array
CO: CO2, CO3
Bloom Level: BL3 (Apply), BL4 (Analyze)
Sort an Array → #912
Problem Statement:
Given an integer array nums, return it in non-decreasing order. Implement using:
selectionSort (O(n²)), mergeSort (O(n log n)), and quickSort (O(n log n) average). Count
comparisons and swaps for each. Analyse time complexity and compare performance.
Constraints:
1 ≤ [Link] ≤ 5 × 10⁴
-5 × 10⁴ ≤ nums[i] ≤ 5 × 10⁴
Sample Input:
std::vector<int> nums = {5, 2, 3, 1};
Expected Output:
[1, 2, 3, 5]
Problem 7: Kth Largest Element in an Array
CO: CO2
Bloom Level: BL4 (Analyze)
Kth Largest Element in an Array → #215
Problem Statement:
Given an integer array nums and an integer k, return the kth largest element in the array.
Implement using quickSelect (randomized pivot). Count comparisons and analyse worst-
case vs average-case time complexity.
Constraints:
1 ≤ k ≤ [Link] ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Sample Input:
std::vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
Expected Output:
5
Problem 8: Sort List (Merge Sort on Linked List)
CO: CO2
Bloom Level: BL3 (Apply), BL4 (Analyze)
Sort List (Merge Sort on Linked List) → #148
Problem Statement:
Given the head of a linked list, sort it in ascending order using mergeSort. Count
comparisons and analyse time complexity (O(n log n)).
Constraints:
The number of nodes in the list is in the range [0, 5 × 10⁴]
-10⁵ ≤ [Link] ≤ 10⁵
Sample Input:
// head: 4 -> 2 -> 1 -> 3
Expected Output:
1 -> 2 -> 3 -> 4
Problem 9: Maximum Gap (Bucket Sort)
CO: CO3
Bloom Level: BL3 (Apply), BL4 (Analyze)
Maximum Gap (Bucket Sort) → #164
Problem Statement:
Given an integer array nums, return the maximum difference between successive elements
in its sorted form. Implement using bucket sort (linear-time sorting). Analyse time
complexity (O(n) average).
Constraints:
1 ≤ [Link] ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
Sample Input:
std::vector<int> nums = {3, 6, 9, 1};
Expected Output:
3
Problem 10: Radix Sort
CO: CO3
Bloom Level: BL3 (Apply), BL4 (Analyze)
Radix Sort → closest: #2343 for digital/radix
Problem Statement:
Implement radixSort for non-negative integers using counting sort as subroutine. Analyse
time complexity (O(dn)).
Constraints:
1 ≤ n ≤ 1000
0 ≤ arr[i] ≤ 10000
Sample Input:
std::vector<int> arr = {170, 45, 75, 90, 2, 802, 24, 66};
Expected Output:
2 24 45 66 75 90 170 802
Problem 1: Check Even or Odd
CO: CO1 BL: BL1
LeetCode ID: #1342 – Number of Steps to Reduce a Number to Zero
Problem statement
Given a non-negative integer num, repeatedly apply:
if num is even, divide it by 2
if num is odd, subtract 1
Return the number of steps to reduce num to zero.
Input: 14
Output: 6
Problem 2: Find Maximum of Three Numbers
CO: CO1 BL: BL2
LeetCode ID: #1281 – Subtract the Product and Sum of Digits of an Integer
Problem statement
Given an integer n, calculate the product of its digits and the sum of its digits, then
return product – sum. Use loops and conditionals to process each digit.
Input: 234
Output: 15
(Explanation: product = 2×3×4 = 24, sum = 2+3+4 = 9, result = 24 – 9 = 15)
Problem 3: Simple Grading-style Logic
CO: CO1 BL: BL2
LeetCode ID: #1108 – Defanging an IP Address
Problem statement
Given a valid IPv4 address string, replace every "." with "[.]" using conditional logic
while iterating through the string.
Input: [Link]
Output: 1[.]1[.]1[.]1
Problem 4: Leap-Year-type Condition
CO: CO1 BL: BL2
LeetCode ID: #292 – Nim Game
Problem statement
You are playing a game with n stones. On each turn, you can remove 1 to 3 stones. You
win if you can make the last move. Using a simple conditional rule, determine if you can
win given n, assuming both players play optimally.
Input
Input: 4
Output: false
Problem 5: Sum of First N Natural Numbers (loop)
CO: CO2 BL: BL2
LeetCode ID: #1480 – Running Sum of 1d Array
Problem statement
Given an array nums, compute the running sum of the array using a loop:
runningSum[i] = nums[0] + nums[1] + ... + nums[i].
Input: [1, 2, 3, 4]
Output: [1, 3, 6, 10]
Problem 6: Multiplication Table-type Loop
CO: CO2 BL: BL2
LeetCode ID: #412 – Fizz Buzz
Problem statement
Given an integer n, print numbers from 1 to n with the following rules using loops and
conditionals:
For multiples of 3, print "Fizz".
For multiples of 5, print "Buzz".
For multiples of both 3 and 5, print "FizzBuzz".
Otherwise, print the number itself.
Example (n = 5):
1
2
Fizz
4
Buzz
Problem 7: Count Positive, Negative, and Zero
CO: CO2 BL: BL3
LeetCode ID: #2553 – Separate the Digits in an Array
Problem statement
You are given an array of positive integers. Using loops and conditionals, split each
number into its digits and form a resulting array of all digits in order.
Input: [13, 25, 83, 77]
Output: [1, 3, 2, 5, 8, 3, 7, 7]
Problem 8: Reverse Digits of an Integer (while loop)
CO: CO2 BL: BL2
LeetCode ID: #7 – Reverse Integer
Problem statement
Given a signed 32-bit integer x, reverse its digits using a loop. If the reversed integer
overflows 32-bit signed range, return 0.
Input: 123
Output: 321
Problem 9: Sum of Even Numbers in a Range
CO: CO2 BL: BL3
LeetCode ID: #2652 – Sum Multiples
Problem statement
Given an integer n, find the sum of all integers in the range [1, n] that are divisible by 3,
5, or 7 using loops and conditional checks.
Input: 7
Output: 21
(3 + 5 + 6 + 7 = 21)
Problem 10: Simple Menu-Driven Calculator Logic
CO: CO2 BL: BL3
LeetCode ID: #2315 – Count Asterisks
Problem statement
Given a string s containing * and |, count how many * characters are not between pairs
of | characters. Use loops and conditional logic to simulate a simple state machine.
Input: "l|*e*et|c**o|*de|"
Output: 2