Question
You are given an integer array:
A = [18, 5, 42, 18, 9, 27, 18, 33, 12]
Write a program using linear search only (do not sort the array or use any built-in
search functions) to perform the following tasks:
1. Search for the key 18.
2. Count how many times the key appears in the array.
3. Store and display all the indices where the key is found.
4. Display the index of the first occurrence and the last occurrence of the key.
5. If the key is not found, print "Element not found".
Constraints:
● You must traverse the array only once.
● Time Complexity: O(n)
● Extra space should be limited to storing the indices of matching elements.
Example Output:
Key: 18
Occurrences: 3
Indices: 0, 3, 6
First Occurrence: 0
Last Occurrence: 6
This problem tests not only basic linear search but also efficient traversal, counting,
tracking positions, and handling multiple occurrences in a single pass.
Question: Insertion of an Item into a Linear List
You are given a linear list stored in an array with a maximum capacity of 15 elements.
Current list:
L = [12, 25, 18, 40, 55, 70, 90]
The current size of the list is 7.
Write an algorithm to perform the following tasks:
1. Insert a new item X at a specified position P (0-based indexing).
2. Before insertion, check whether the list is already full. If the list is full, display
"Overflow: Insertion not possible."
3. Verify that the specified position is valid (0 ≤ P ≤ current size). If the position is
invalid, display "Invalid Position."
4. If the item X already exists in the list, insert the new item immediately after its
last occurrence, ignoring the specified position.
5. Shift the necessary elements to create space for the new item.
6. Display the updated list after insertion.
Example 1
Input:
X = 35
P=3
Output:
Updated List:
[12, 25, 18, 35, 40, 55, 70, 90]
Example 2
Input:
X = 25
P=6
Output:
Updated List:
[12, 25, 25, 18, 40, 55, 70, 90]
Note: Since 25 already exists, the new 25 is inserted immediately after its last
occurrence instead of position 6.
Question: Deletion of an Item from a Linear List
You are given a linear list stored in an array with a maximum capacity of 15 elements.
Current list:
L = [12, 25, 18, 40, 25, 55, 70, 90]
The current size of the list is 8.
Write an algorithm to perform the following tasks:
1. Delete the item X from the list.
2. If the item appears multiple times, delete only its first occurrence.
3. If the item is not found, display "Element not found."
4. After deletion, shift the remaining elements to fill the empty position.
5. Update the size of the list.
6. Display the updated list after deletion.
Example 1
Input:
X = 25
Output:
Updated List:
[12, 18, 40, 25, 55, 70, 90]
Example 2
Input:
X = 100
Output:
Element not found.
Bonus Task (Optional):
Modify your algorithm so that if the item occurs multiple times, all occurrences of the
item are deleted in a single traversal of the list while maintaining the order of the
remaining elements.
Question: Enhanced Bubble Sort
You are given the following unsorted array of integers:
A = [45, 12, 78, 23, 56, 12, 89, 34, 67]
Write an algorithm using Bubble Sort to perform the following tasks:
1. Sort the array in ascending order using the Bubble Sort algorithm.
2. Display the array after each complete pass of the algorithm.
3. Count and display:
o The total number of comparisons performed.
o The total number of swaps performed.
4. Implement an optimization to terminate the algorithm early if no swaps occur
during a pass.
5. After sorting is complete, display:
o The sorted array.
o The total number of passes executed.
o Whether the algorithm terminated early or completed all passes.
Example Output (Partial):
Pass 1: [12, 45, 23, 56, 12, 78, 34, 67, 89]
Pass 2: [12, 23, 45, 12, 56, 34, 67, 78, 89]
...
Sorted Array:
[12, 12, 23, 34, 45, 56, 67, 78, 89]
Comparisons = 36
Swaps = 14
Passes Executed = 7
Early Termination = Yes
Constraints:
● Do not use any built-in sorting functions.
● Use only the Bubble Sort algorithm.
● The algorithm should have a worst-case time complexity of O(n²).
Question: Time and Space Complexity Analysis
Consider the following C program:
#include <stdio.h>
int main() {
int n, i, j, sum = 0;
scanf("%d", &n);
int arr[n];
for (i = 0; i < n; i++) {
arr[i] = i + 1;
}
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
sum += arr[j];
printf("%d\n", sum);
return 0;
Answer the following questions:
1. Determine the time complexity of the program using Big-O notation.
2. Determine the space complexity of the program using Big-O notation.
3. Show the step-by-step analysis of the nested loops to justify your answer.
4. Identify which part of the program contributes the most to the overall time
complexity.
5. If the nested loop is replaced with a single loop that computes the same result
more efficiently, what would be the new time complexity?
Note: Ignore the time required for input/output operations (scanf() and printf()) when
analyzing the complexity.
Question: Advanced Array Traversal
You are given an integer array:
A = [15, 8, 22, 7, 15, 30, 18, 8, 45, 12, 30]
Write an algorithm to traverse the array only once and perform the following tasks:
1. Calculate the sum of all elements in the array.
2. Find the largest and smallest elements along with their indices.
3. Count the number of even and odd elements.
4. Count the frequency of a given key value K.
5. Find the second largest unique element in the array.
6. Store the indices of all duplicate elements.
7. Reverse the array without using another array.
8. Display the final updated array.
Constraints:
● The array must be traversed only once for tasks 1–6.
● Do not use built-in functions.
● Do not sort the array.
● Handle the case when a second largest element does not exist.
Example Input:
K = 15
Expected Output:
Sum = 190
Largest Element = 45
Index = 8
Smallest Element = 7
Index = 3
Even Count = 7
Odd Count = 4
Frequency of 15 = 2
Second Largest Unique Element = 30
Duplicate Element Indices:
0, 4, 7, 10
Reversed Array:
[30, 12, 45, 8, 18, 30, 15, 7, 22, 8, 15]
Question: Stack Implementation and Operations
You are given a stack of maximum size 10 implemented using an array.
Write an algorithm/program to perform the following operations:
1. Initialize an empty stack.
2. Perform the following sequence of operations:
PUSH(15)
PUSH(25)
PUSH(35)
POP()
PUSH(45)
PUSH(55)
POP()
PUSH(65)
PUSH(75)
3. Display the stack after all operations.
4. Display the top element of the stack.
5. Count the total number of elements currently present in the stack.
6. Check whether the stack is:
o Empty
o Full
Additional Requirements:
● Implement the functions:
o push()
o pop()
o peek()
o display()
● Handle the following conditions:
o If insertion is attempted when the stack is full, display "Stack Overflow".
o If deletion is attempted when the stack is empty, display "Stack
Underflow".
Expected Output:
Stack:
15 25 45 65 75
Top Element = 75
Number of Elements = 5
Stack Status: Not Empty
Constraints:
● Use array implementation only.
● Do not use built-in stack libraries.
● Maintain the LIFO (Last In First Out) property.