Detailed DSA Interview Cheat Sheet - TCS Ninja Level
1. Arrays
Definition:
An array is a collection of elements, all of the same type, stored in contiguous memory locations.
Each element can be accessed directly using its index.
Advantages:
- Fast access using index (O(1)).
- Easy to implement.
Disadvantages:
- Fixed size.
- Insertion and deletion are costly (O(n)).
Java Example:
int[] arr = new int[5];
arr[0] = 10;
System.out.println(arr[0]); // Output: 10
Interview Q:
Q: How do you find the max element?
A: Loop through and keep track of the largest value.
2. Linked List
Definition:
A Linked List is a linear data structure where elements (nodes) point to the next node. Each node has two parts: data
and a pointer to the next node.
Types:
- Singly Linked List
- Doubly Linked List
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
- Circular Linked List
Advantages:
- Dynamic size.
- Efficient insertion/deletion.
Java Example (Singly Linked List Node):
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
Interview Q:
Q: How do you reverse a linked list?
A: Using three pointers: prev, current, next.
3. Stack
Definition:
A stack is a LIFO (Last In First Out) structure where elements are added (pushed) and removed (popped) from the top.
Java Example:
Stack<Integer> stack = new Stack<>();
stack.push(10);
System.out.println(stack.pop()); // Output: 10
Applications:
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
- Function calls
- Expression evaluation
- Undo operations
Interview Q:
Q: What is stack overflow?
A: When stack memory limit is exceeded due to deep recursion.
4. Queue
Definition:
Queue is a FIFO (First In First Out) structure where elements are added from the rear and removed from the front.
Java Example:
Queue<Integer> queue = new LinkedList<>();
queue.add(10);
System.out.println(queue.remove()); // Output: 10
Types:
- Circular Queue
- Priority Queue
- Deque
Interview Q:
Q: Real-life example?
A: People standing in line to buy tickets.
5. HashMap
Definition:
HashMap stores data in key-value pairs. It uses a hash function to compute an index into an array of buckets.
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
Java Example:
HashMap<String, Integer> map = new HashMap<>();
map.put("Janani", 25);
System.out.println(map.get("Janani")); // Output: 25
Advantages:
- Fast access (O(1) average).
- Key-based access.
Interview Q:
Q: What happens if two keys hash to same bucket?
A: Collision occurs, handled via chaining or open addressing.
6. Tree & BST
Definition:
A tree is a hierarchical structure. A Binary Search Tree (BST) is a binary tree where left child < root < right child.
Traversals:
- Inorder (Left, Root, Right)
- Preorder (Root, Left, Right)
- Postorder (Left, Right, Root)
Java Node Example:
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
Interview Q:
Q: Why is BST better than arrays for search?
A: Average case O(log n) for search, insert, delete.
7. Graph
Definition:
Graph is a set of vertices (nodes) and edges. Can be directed or undirected.
Representation:
- Adjacency Matrix
- Adjacency List
Traversal:
- BFS (uses queue)
- DFS (uses stack or recursion)
Java Example (Adjacency List):
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
Interview Q:
Q: Applications?
A: Social networks, maps, recommendation systems.
8. Sorting Algorithms
Definition:
Sorting means arranging elements in an order (ascending/descending).
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
Common Sorts:
- Bubble Sort: Compare and swap (O(n²))
- Selection Sort: Select min in every pass (O(n²))
- Merge Sort: Divide and conquer (O(n log n))
- Quick Sort: Partition-based (O(n log n))
Java Example (Bubble Sort):
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
Interview Q:
Q: Which sorting is best for large arrays?
A: Merge Sort.
9. Searching Algorithms
Definition:
Searching is finding the presence/location of a value in a data structure.
Types:
- Linear Search (O(n))
- Binary Search (O(log n)) - requires sorted array
Java Example (Binary Search):
int low = 0, high = n-1;
while (low <= high) {
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
Interview Q:
Q: When to use binary search?
A: When the array is sorted.
10. Recursion & DP
Recursion:
A function that calls itself. Requires base case and recursive case.
Java Example (Factorial):
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1);
Dynamic Programming:
An optimization over recursion using memoization or tabulation.
Java Example (Fibonacci with DP):
int fib(int n, int[] dp) {
if (n <= 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = fib(n-1, dp) + fib(n-2, dp);
}
Detailed DSA Interview Cheat Sheet - TCS Ninja Level
Interview Q:
Q: What is memoization?
A: Caching results to avoid recomputation.
