Tab 1

1. Time & Space Complexity

Q1: What is time complexity, and why is it important?

A: Time complexity represents how the runtime of an algorithm increases with input size. It is
important because it helps analyze the efficiency of an algorithm and compare different
solutions.

Q2: Explain Big O, Omega (Ω), and Theta (Θ) notations.

A:

●​ Big O (O): Worst-case complexity (upper bound).

●​ Omega (Ω): Best-case complexity (lower bound).
●​ Theta (Θ): Average-case complexity (tight bound).

Q3: Compare O(n log n) and O(n²). When does one perform better than the
other?

A: O(n log n) (e.g., MergeSort) is better than O(n²) (e.g., BubbleSort) for large inputs. O(n²) is
only preferable for small datasets due to lower constant factors.

Q4: How do you calculate the time complexity of a recursive function?

A: Use recurrence relations and solve them using the Master Theorem or recursion tree
method.

2. Arrays and Strings

Q5: What are the advantages of arrays over linked lists?

A:

●​ Faster access (O(1) for arrays, O(n) for linked lists).

●​ Better cache locality, leading to faster performance.
●​ Easier to use with dynamic programming.
Q6: How is a 2D array stored in memory?

A:

●​ Row-major order (used in C, C++): Stored row by row.

●​ Column-major order (used in Fortran, MATLAB): Stored column by column.

Q7: How do you find duplicates in an array efficiently?

A:

●​ Using a HashSet (O(n) time, O(n) space).

●​ Using XOR if there’s only one duplicate (O(n) time, O(1) space).
●​ Sorting the array first (O(n log n) time, O(1) space).

3. Linked Lists
Q8: Compare singly linked lists and doubly linked lists.

A:

●​ Singly linked list: Uses less memory, unidirectional traversal.

●​ Doubly linked list: Requires more memory but allows bidirectional traversal.

Q9: How can you detect and remove a cycle in a linked list?

A: Use Floyd’s Cycle Detection Algorithm (Tortoise & Hare method) to detect the cycle,
then remove it by adjusting pointers.

4. Stacks & Queues

Q10: What is a stack, and where is it used?

A: A stack is a LIFO (Last In, First Out) data structure used in function calls, expression
evaluation, and backtracking (e.g., DFS).

Q11: How does a circular queue differ from a regular queue?

A: A circular queue reuses empty space by wrapping around when the end is reached,
whereas a normal queue does not.
5. Trees & Graphs
Q12: What is a binary search tree (BST)?

A: A BST is a binary tree where the left child is smaller than the parent, and the right child is
greater.

Q13: What is the difference between BFS and DFS?

A:

●​ BFS (Breadth-First Search) uses a queue and explores level by level.

●​ DFS (Depth-First Search) uses a stack (or recursion) and explores deeper first.

Q14: Explain Dijkstra’s algorithm. How does it work?

A:​
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a graph
using a priority queue (min heap).

6. Sorting & Searching

Q15: Why is Merge Sort preferred over QuickSort for linked lists?

A: Merge Sort is preferred because it does not require random access and works well with
linked list pointer manipulations.

Q16: Explain the difference between stable and unstable sorting

algorithms.

A:

●​ Stable Sort: Maintains the relative order of duplicate elements (e.g., Merge Sort).
●​ Unstable Sort: Does not guarantee order (e.g., QuickSort).

7. Hashing
Q17: What is a hash function?

A: A function that converts an input (key) into a fixed-size numerical value (hash code).

Q18: How do hash collisions occur, and how can they be resolved?

A:​
Collisions occur when two keys generate the same hash. They can be resolved using:

●​ Separate Chaining: Use linked lists at each index.

●​ Open Addressing: Find an alternative empty slot.

8. Dynamic Programming & Greedy Algorithms

Q19: What is dynamic programming (DP)?

A: DP is an optimization technique used to avoid recomputation by storing results of

subproblems (memoization or tabulation).

Q20: Why is the 0/1 Knapsack problem solved using DP instead of greedy?

A: The greedy approach fails because it doesn’t always give the optimal solution. DP
considers all combinations.

9. Bit Manipulation
Q21: How do you check if a number is a power of 2 using bitwise
operations?

A:

boolean isPowerOfTwo(int n) {
return (n > 0) && (n & (n - 1)) == 0;
}

If n & (n-1) == 0, then n is a power of 2.

Q22: How does XOR help in finding a missing number in an array?

A:​
If an array contains numbers from 1 to n with one missing, XOR all elements and all numbers
from 1 to n. The missing number remains.

10. Miscellaneous Topics

Q23: What is a trie? Where is it used?

A: A trie is a tree-based data structure used for efficient string searching (e.g., auto-complete,
spell checking).

Q24: Explain the concept of backtracking with an example.

A: Backtracking is a brute-force approach used for solving constraint satisfaction problems

like Sudoku, N-Queens, and permutations.
Tab 2
I am working as a Java full stack developer in CDAC Mumbai, a central government
organisation. I am working on a sms service project called mobile seva which provides sms
facilities to government departments to send sms to citizens and i have worked on 2 more
projects 1 is the billing portal used by CDAC accounts department to update and manage
prepaid and postpaid payments of government departments using our sms services I upgraded
this legacy project using struts to java spring boot for backend and angular for frontend.

I am a quick learner. If I am given a task I'll make sure I complete it with full efficiency. There
might be a situation where i might not be aware of some topics or things given to me as a task
but i ll still make sure i research and learn about it to complete it in time,
Tab 3
 1.​ which is better merge sort/quick sort ?

If you need stable sorting or are working with linked lists → Use Merge Sort.

If you need fast in-place sorting and have limited memory → Use Quick Sort.

For large datasets, Quick Sort is usually better due to its lower constant factors.

If worst-case time complexity is a concern, use Merge Sort.

2.​ Worst case complexity of quick sort?

When the pivot selection is poor, leading to unbalanced partitions.

If the smallest or largest element is always chosen as the pivot

3.​ What is the estimated value of 2^24 (give a mental roadmap of how you arrived at its
value, hint: 2^24 = 2^4*(2^10)^2 = 16*(10^3)^2 = 16 million)

To estimate 2242^{24}224, let's break it down step by step:

Recognizing the Powers of 2:​

224=24×(210)22^{24} = 2^4 \times (2^{10})^2224=24×(210)2​
This is useful because we know:

a.​ 24=162^4 = 1624=16

b.​ 210≈103=10002^{10} \approx 10^3 = 1000210≈103=1000

Squaring 2102^{10}210:​
(210)2=(1000)2=106=1,000,000(2^{10})^2 = (1000)^2 = 10^6 =
1,000,000(210)2=(1000)2=106=1,000,000

Multiplying by 242^424:​
224=16×1,000,0002^{24} = 16 \times 1,000,000224=16×1,000,000

Final Answer:​
16,000,000 (16 million)16,000,000 \text{ (16 million)}16,000,000 (16 million)
4.​ Worst case complexity of look up time in self balancing BST? What about in normal
BST?

1️⃣ Normal (Unbalanced) BST

●​ Worst-case time complexity: O(n)

●​ Why?
○​ If the BST becomes skewed (like a linked list), each lookup may require traversing
all n nodes.

Example: Inserting elements in sorted order creates a degenerate tree:​

markdown​
1

○​ Searching for 5 requires O(n) comparisons.

2️⃣ Self-Balancing BST (e.g., AVL, Red-Black Tree)

Worst-case time complexity: O(log⁡n)

Why?

a.​ These trees maintain a height of O(log⁡n) by balancing themselves after

insertions/deletions.
 b.​ Example: In an AVL Tree, the height is always bounded by O(log⁡n), ensuring that
lookups never degrade to linear time.
5.​ Worst case for insertion in hash table? What about average case?

1️⃣ Worst-Case Complexity: O(n)

●​ When does it happen?

○​ If all keys hash to the same bucket (worst-case collision), forming a linked list or
tree at that bucket.
○​ In open addressing, if the table is almost full, probing for an empty slot can take
O(n).
○​ In rehashing, when the table is resized, reinserting all elements takes O(n).

2️⃣ Average-Case Complexity: O(1)O(1)O(1)

Why?

With a good hash function and low load factor (e.g., α<0.7\alpha < 0.7α<0.7), collisions
are rare.

a.​ Most insertions happen in constant time by simply placing the key in an empty
bucket.
6.​ Examples of self balancing BST

7.​ How does merge sort work (Divide and conquer)

 Divide:

●​ If the array has more than one element, divide it into two halves.
●​ Recursively apply merge sort on each half.

Conquer (Sort & Merge):

Sort both halves recursively.

Merge the two sorted halves into a single sorted array.

✅ Best, Average, and Worst Case: O(nlog⁡n)O(n \log n)O(nlogn)

✅ Space Complexity: O(n)O(n)O(n) (Extra space needed for merging)
✅ Stable Sort: Yes (Preserves order of equal elements)
8.​ How is priority queue implemented (Min/Max heap)

Priority queue is implemented using min/max heap which uses a binary tree data structures.

9.​ For an unweighted graph, which algorithm should be used to find shortest path:
breadth first search or Dijkstras?

For an unweighted graph, you should use Breadth-First Search (BFS) to find the shortest path.
🚀
Why BFS?

✅ Correctness: In an unweighted graph, the shortest path is the one with the fewest edges. BFS
explores all nodes level by level, ensuring that when it reaches a node, it has found the shortest
path to it.

✅ Time Complexity:
●​ BFS: O(V+E)O(V + E)O(V+E) (where VVV = vertices, EEE = edges)
 ●​ Dijkstra’s: O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV) (because of the priority queue)
●​ BFS is faster for an unweighted graph since it doesn’t require priority queues or extra
overhead.

Why Not Dijkstra’s?

❌ Unnecessary Complexity:
●​ Dijkstra’s Algorithm is designed for weighted graphs. It uses a priority queue to always
expand the minimum cost node, but in an unweighted graph, all edge costs are equal (1),
making this unnecessary.
●​ BFS naturally finds the shortest path without extra computational overhead.

JAVA

1.​ What is reference?

In Java, a reference is a variable that stores the memory address of an object rather than the
actual object itself.

Key Points:

✅ A reference points to an object stored in the heap memory.​

✅ Java does not support pointers (like C/C++), but references act similarly.​
✅ Assigning a reference variable does not copy the object, it only copies the memory address.
2. Name 2 implementations of hashtable in Java

Key Differences: HashMap vs. Hashtable

Feature HashMap Hashtable

 Thread-Sa ❌ Not synchronized ✅ Synchronized
fety (thread-safe)

Null ✅ Allows null keys & ❌ No null keys/values

Keys/Valu values
es

Performa 🚀 Faster (No sync 🐢 Slower (Sync

nce overhead) overhead)

Usage Single-threaded apps Multi-threaded apps

🔹 For multi-threaded apps, use ConcurrentHashMap instead of Hashtable (better

performance).

3. Does Java support multiple inheritance?

Multiple inheritance is NOT allowed with classes 🚫

✔ Multiple inheritance is supported using interfaces ✅
✔ Java avoids the Diamond Problem by enforcing method override