What are Sparse arrays? Give example.
Sparse arrays are arrays (often matrices) with mostly default (e.g., zero) values.
Efficient storage: store only non-zero entries (e.g., row, column, value triplets).
Example: A 5×5 matrix with only three non-zero entries:
Copy code
(0,1)=7, (2,3)=5, (4,0)=9
would be stored as [(0,1,7), (2,3,5), (4,0,9)].
Where can we use Stack? Applications of stack.
Stack is a LIFO data structure; uses include:
1. Expression evaluation and conversion (infix ↔ postfix/prefix).
2. Function call management (call stack/recursion).
3. Undo-redo in text editors.
4. Syntax parsing, parentheses matching.
5. Depth-first traversal in trees and graphs.
6. Backtracking algorithms (e.g., maze solving).
How to represent a Binary Tree using an array?
Array representation (for complete binary tree):
o Root at index 0 (or 1).
o For node at index i:
Left child: at index 2*i + 1
Right child: at 2*i +
What is Hashing? What are its advantages?
Hashing is a technique for efficiently storing and retrieving data using a hash
function h(key) that maps keys to indexes in a table.
Advantages:
1. Fast operations: average-case time for insert/search/delete is O(1)
Wikipedia+4Vaia+4Reddit+4RedditWikipedia+2Wikipedia+2Wikipedia+2.
2. Direct access: provides quick lookups without linear scanning.
3. Efficient memory use: with good hash functions, storage is optimized.
2. Explain Priority Queue (briefly)
A Priority Queue is an abstract data type where each element has a priority, and
removals always target the highest (or lowest) priority element.
Implementations: often via binary heaps, offering O(log n) insertion and removal
Wikipedia.
Applications: used in scheduling, bandwidth management, shortest-path algorithms
like Dijkstra, etc.
Algorithm to convert infix → postfix; trace for ((A+B)^C)-((D*C)/F)
1. Algorithm (Shunting-Yard):
o Initialize empty stack and output.
o Read expression left to right:
Operand: append to output.
Operator: pop from stack to output if top has higher/equal precedence
(consider associativity), then push current.
‘(’: push to stack.
‘)’: pop and append until matching ‘(’.
o At end, pop remaining operators to output
2. Trace for ((A+B)^C)-((D*C)/F):
Input Stack Output
( (
( ((
A (( A
+ ((+ A
B ((+ AB
) (( AB+
^ ((^ AB+
C ((^ AB+C
) ( AB+C^
- - AB+C^
( -( AB+C^
( - (( AB+C^
D - (( AB+C^D
* - ((* AB+C^D
C - ((* AB+C^DC
) -( AB+C^DC*
/ - (/ AB+C^DC*
F - (/ AB+C^DC*F
) - AB+C^DC*F/
(end) (empty) A B + C ^ D C * F / -
Final postfix: AB+C^DC*F/-
. Difference: Linear vs Binary Search & C program for binary search.
Linear Search: checks elements one by one; time O(n).
Binary Search: on sorted arrays; compares to middle, halves the search; time O(log
n).
c
Copy code
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low)/2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1; // not found
}
int main() {
int arr[] = {2,4,6,8,10}, n=5, key=6;
int idx = binarySearch(arr,n,key);
printf(idx!=-1?"Found at %d\n":"Not found\n", idx);
return 0;
}
C program: insertion & deletion in a simple Queue
c
Copy code
#include <stdio.h>
#define MAX 5
int queue[MAX], front=-1, rear=-1;
void enqueue(int x) {
if (rear == MAX-1) { printf("Queue full\n"); return; }
if (front == -1) front = 0;
queue[++rear] = x;
}
int dequeue() {
if (front == -1 || front > rear) { printf("Queue empty\n"); return -
1; }
return queue[front++];
}
int main() {
enqueue(10); enqueue(20); enqueue(30);
printf("%d dequeued\n", dequeue());
printf("%d dequeued\n", dequeue());
enqueue(40);
while (front != -1 && front <= rear)
printf("%d ", dequeue());
return 0;
}
12. Heap Sort: Arrange keys [2,9,7,6,5,8] in descending order
Steps:
1. Build max-heap → [9,6,8,2,5,7] (one valid heap).
2. Repeatedly extract max and heapify:
Swap 9 & 7 → [7,6,8,2,5,9] heapify → [8,6,7,2,5,9]
Swap 8 & 5 → [5,6,7,2,8,9] heapify → [7,6,5,2,8,9]
Swap 7 & 2 → [2,6,5,7,8,9] heapify → [6,2,5,7,8,9]
... Continue until sorted.
Descending result: 9,8,7,6,5,2.
Construct Binary Tree from Inorder & Preorder traversals
Inorder: D, B, E, A, F, C
Preorder: A, B, D, E, C, F
Tree:
A
/ \
B C
/ \ \
D E F
Construction:
1. Root = A (preorder[0]).
2. Split inorder at A → left [D, B, E], right [F, C].
3. Recurse for subtrees using remaining preorder.
Implement Singly Linked List using dynamic memory
c
Copy code
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void insertEnd(struct Node **head, int val) {
struct Node *new = malloc(sizeof(struct Node));
new->data = val; new->next = NULL;
if (*head == NULL) {
*head = new; return;
}
struct Node *p = *head;
while (p->next) p = p->next;
p->next = new;
}
void display(struct Node *head) {
while (head) { printf("%d -> ", head->data); head = head->next; }
printf("NULL\n");
}
int main() {
struct Node *head = NULL;
insertEnd(&head, 10);
insertEnd(&head, 20);
insertEnd(&head, 30);
display(head);
return 0;
}
Collision resolution techniques (short note)
Separate chaining: each bucket has a linked list of entries.
Open addressing: use probing (linear, quadratic, double hashing) to find next free
slot.
Aim is avoiding clustering and collisions.
10. B-Trees (short note)
Balanced multi-way tree ideal for disk storage.
Each node can have multiple keys and children.
Keeps all leaf nodes at same depth.
Supports efficient search, insertion, deletion in O(log n).
11. D-Queues (Double-Ended Queues) (short note)
Deque allows insertion and deletion at both ends.
Can be implemented in arrays or doubly linked lists.
Useful in palindrome checking, job scheduling, and sliding window algorithms.
