# Data Structures and Algorithms: Complete Guide for Interviews

# The Complete Data Structures & Algorithms Guide for Technical Interviews

## Introduction

Data Structures and Algorithms (DSA) form the foundation of computer science and are critical for technical interviews. This comprehensive guide covers essential concepts, implementation strategies, and practical tips to help you excel.

## 1. Arrays

### Overview
Arrays are contiguous memory blocks storing elements of the same type, accessible via indices.

### Time Complexity
- Access: O(1)
- Search: O(n)
- Insertion: O(n) - requires shifting
- Deletion: O(n) - requires shifting

### Space Complexity
O(n) where n is the number of elements

### When to Use
- Fast random access needed
- Size is known beforehand
- Memory locality is important
- Simple data storage requirements

### Code Example (Python)
```python
# Array operations
arr = [1, 2, 3, 4, 5]

# Access
print(arr[2])  # O(1) - Output: 3

# Search
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Insert at position
arr.insert(2, 10)  # O(n)

# Delete
arr.pop(2)  # O(n)
```

## 2. Linked Lists

### Overview
Linked lists consist of nodes where each node contains data and a reference to the next node.

### Time Complexity
- Access: O(n)
- Search: O(n)
- Insertion (at head): O(1)
- Deletion (at head): O(1)

### Space Complexity
O(n) plus extra space for pointers

### When to Use
- Frequent insertions/deletions
- Unknown size
- No random access needed
- Implementing stacks/queues

### Code Example
```python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def search(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False
```

## 3. Stacks

### Overview
LIFO (Last In, First Out) structure supporting push and pop operations.

### Time Complexity
- Push: O(1)
- Pop: O(1)
- Peek: O(1)

### When to Use
- Function call management
- Undo mechanisms
- Expression evaluation
- Backtracking algorithms

### Code Example
```python
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
    
    def peek(self):
        return self.items[-1] if self.items else None
    
    def is_empty(self):
        return len(self.items) == 0

# Practical example: Balanced parentheses
def is_balanced(expression):
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:
            stack.push(char)
        elif char in pairs.values():
            if stack.is_empty() or pairs[stack.pop()] != char:
                return False
    return stack.is_empty()
```

## 4. Queues

### Overview
FIFO (First In, First Out) structure with enqueue and dequeue operations.

### Time Complexity
- Enqueue: O(1)
- Dequeue: O(1)
- Front: O(1)

### When to Use
- BFS traversal
- Task scheduling
- Buffer management
- Request handling

### Code Example
```python
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        return self.items.popleft() if self.items else None
    
    def is_empty(self):
        return len(self.items) == 0
```

## 5. Trees

### Binary Trees
Each node has at most two children.

### Binary Search Trees (BST)
Left subtree < node < right subtree

### Time Complexity (BST)
- Search: O(log n) average, O(n) worst
- Insertion: O(log n) average, O(n) worst
- Deletion: O(log n) average, O(n) worst

### When to Use
- Hierarchical data
- Fast search, insert, delete
- Sorted data maintenance

### Code Example
```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)
    
    def _insert_recursive(self, node, val):
        if val < node.val:
            if node.left:
                self._insert_recursive(node.left, val)
            else:
                node.left = TreeNode(val)
        else:
            if node.right:
                self._insert_recursive(node.right, val)
            else:
                node.right = TreeNode(val)
    
    def inorder_traversal(self, node, result=[]):
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.val)
            self.inorder_traversal(node.right, result)
        return result
```

## 6. Graphs

### Overview
Collections of vertices connected by edges.

### Representations
- Adjacency Matrix: O(V²) space
- Adjacency List: O(V + E) space

### When to Use
- Network modeling
- Social networks
- Path finding
- Dependency resolution

### Code Example
```python
class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)
    
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        result = []
        
        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            
            for neighbor in self.graph.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return result
    
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        result = [start]
        
        for neighbor in self.graph.get(start, []):
            if neighbor not in visited:
                result.extend(self.dfs(neighbor, visited))
        return result
```

## 7. Sorting Algorithms

### Quick Sort
- Time: O(n log n) average, O(n²) worst
- Space: O(log n)
- Use: General purpose, in-place sorting

```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
```

### Merge Sort
- Time: O(n log n) always
- Space: O(n)
- Use: Stable sorting, linked lists

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result
```

## 8. Searching Algorithms

### Binary Search
```python
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
```

## Interview Tips

1. **Clarify Requirements**: Ask about input size, constraints, edge cases
2. **Think Aloud**: Explain your thought process
3. **Start Simple**: Brute force first, then optimize
4. **Test Your Code**: Walk through examples
5. **Analyze Complexity**: Always state time and space complexity
6. **Practice Common Patterns**: Two pointers, sliding window, DFS/BFS
7. **Know Trade-offs**: Understand when to use each data structure
8. **Handle Edge Cases**: Empty inputs, single elements, duplicates

## Conclusion

Mastering DSA requires consistent practice. Focus on understanding concepts deeply rather than memorizing code. Use platforms like LeetCode, HackerRank, and practice implementing these structures from scratch regularly.