Array

HashMap

Stack and Queue

Binary Tree

Depth-First Traversal Preorder Traversal (Recursive, Iterative) Left-Right Inorder Traversal (Recursive, Iterative) Left-Middle-Right Postorder Traversal (Recursive, Iterative) Left-Right-Middle Breadth-First Traversal Level Order Traversal (Iterative)

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get(key) and put(key, value).

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

Delete the Repeating Item in a Sorted Array

We need to achieve this within Space Complexity O(1).

Approach: Double Pointer Technique

To solve the problem of deleting repeating items in a sorted array, we can use a two-pointer technique. Since the array is sorted, duplicates will appear consecutively, allowing us to easily remove them by using two pointers: one for tracking the unique elements and another for iterating through the array.

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve it using recursion.

Approach: Recursion

1. Base Case: If the list is empty or has only one node, return the head as no swapping is needed.
2. Recursive Step: Recursively solve the problem for the remaining nodes (i.e., after the first pair), then swap the first two nodes.
3. Return New Head: The new head of the list after the swap will be the second node in the first pair.

Delete the Nth Node from the End of the Linked List

Given the head of a linked list, remove the Nth node from the end of the list and return its head.

Approach: Two-Pointer Technique

1. Initialize two pointers, first and second, both pointing to the head of the list.
2. Advance first pointer by N nodes. This creates a gap of N nodes between first and second.
3. Move both pointers until first reaches the end. Now, second will be pointing to the node just before the Nth node from the end.
4. Remove the target node by updating the next pointer of second.
5. Return the head of the modified list.

Letter Combinations of a Phone Number

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent. Each digit corresponds to a set of letters on a traditional telephone keypad.

Approach: DFS

We can use Depth First Search (DFS) to explore all possible letter combinations by treating each digit as a level in a decision tree, where each branch corresponds to one of the letters mapped to that digit.

Three Sum Problem

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, j != k
• nums[i] + nums[j] + nums[k] == 0

---

Longest Common Prefix

The Longest Common Prefix (LCP) problem involves finding the longest prefix that is common to all the strings in a given array of strings. The horizontal scanning approach is one of the simplest ways to solve this.

Approach: Horizontal Scanning

Palindrome Number Problem

Approach: Converting Half of The Numbers

This solution checks if an integer x is a palindrome by reversing half of the digits and comparing them.

Steps:

1. Handle Special Cases:

   • If x is negative, return false since negative numbers cannot be palindromes.
   • If x ends in 0 and is not 0 itself, return false because the first digit of a palindrome cannot be 0 (except for the number 0).

2. Reverse Half of the Number:

   • Initialize revertedNumber to 0.
   • Reverse the last half of the digits by continuously moving the last digit of x to revertedNumber until x is no longer greater than revertedNumber.

3. Check for Palindrome:

   • After the loop, x should either be equal to revertedNumber (for even-length palindromes) or revertedNumber / 10 (for odd-length palindromes, where the middle digit does not need to be compared).

4. Complexity

   • Time Complexity: O(log₁₀(n)), as the number of digits is reduced by half.
   • Space Complexity: O(1), using constant extra space.

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Approach: Expand Around Center

To find the longest palindromic substring efficiently, we can use the "Expand Around Center" technique. A palindrome mirrors around its center, so for each character in the string, we can consider it as the center and try to expand outwards in both directions to find the longest palindrome. We need to check both odd-length and even-length palindromes by treating each character and each pair of characters as potential centers.