Coding practice

Index

• Java and OOP
• System Design
• gRPC

Table of Contents

• Search
• Sorting
  • Insertion sort
  • Bubble sort
  • Merge sort
  • Quick sort
• Data structures
  • Binary Heap (min-heap)
    • Insertion
    • Building
    • Deletion
  • Binary Search Tree
    • Insertion
    • Deletion
    • Trie
  • Graphs
    • Graph vs Tree
• Mathematical concepts
• Problems list
  • Divide and Conquer
  • Monotonic queue
  • Binary search
    • Binary search over solution space
  • Two pointers
  • Diff array technique
  • Dynamic Programming (DP)
  • Using original indexes array
  • Bit manipulation
  • Hashing
  • Sorting
  • Recursion
  • Binary Tree
  • Heap - Priority Queue
  • Sliding window
  • No or constant extra space
  • Graphs
    • Union Find
    • Topological sort
    • Breadth First Search (BFS)
    • Depth First Search (DFS)

Search

• Binary search
  • binary Helper codes
• Linear search

Sorting

Insertion sort

• Time complexity O(n²)

Bubble sort

• Time complexity O(n²)

Merge sort

• Time complexity is always O(nlog(n)), for all three cases worst, average and best cases. So, when you don’t know about the input use merge sort.
• When using arrays
  • we need additional heap space of O(n) to keep the merged array.
  • A disadvantage is that it is not an in-place sort.
• When using linked list
  • no need for the additional heap space. We only need stack space to keep recursion information. So memory required is only O(log(n)).
  • This is an in-place sort, because we only need to modify next pointers of the nodes.

Code for merge sort

Quick sort

• Time complexity
  • Best: O(n*log(n))
  • Average: O(n*log(n))
  • Worst: O(n²), when we choose the partition in such a way that the partition ends up at the beginning or at ending of the array.
• Quick sort is not stable.
• This is in-place and is faster when good partition strategies are used.

Code for quick sort

Data structures

Binary Heap (min-heap)

• This is always a complete binary tree.
• So it can be represented easily in an array.
• Children of node at i will be at 2i-2 and 2i+2. Parent of node i will be at (i-1)/2.
• In a min-heap, a parent node will always be less than or equal to their children.

Insertion

• First insert it at then end of the heap.
• See if it still follows the heap property, i.e compare it’s value with the parent and swap if needed.
• If you had to swap, then repeat the previous step till you don’t need to swap or reached the root.
• Time complexity: O(log n) = O(height)

Building

• Initialize and keep on inserting all the nodes.
• If you are inserting a total of n nodes, we might conclude that the whole operation takes O(n * log n) time. But remember that initially the size of tree is very smaller than O(log n). So, on careful calculation the building process takes O(n) time.

Deletion

• You can only delete the root of a heap.
• Replace the heap root with the last element.
• Then start the heapify process from the root in a top-down manner.
• Time complexity: O(log n) = O(height)
• If you want to delete an intermediate element (as available in PriorityQueue Java), we first need to find the element by checking through each element, which takes O(n) operations and then delete it in the same manner as we delete the root. So deletion of an arbitrary element takes O(n) complexity.

Binary Search Tree

• All the elements smaller than the root are on the left sub-tree and all higher are on the right sub-tree. This is valid for all underlying sub-tress too.
• In-order traversal will print all values in a sorted manner. This concept can be used to find the kth smallest element.

Insertion

• Similar to search.
• Go till you encounter a leaf node and attach to left/right depending on whether the new value is smaller/bigger than the leaf value.

Deletion

• If node does not have any children, you can simply mark it as null.
• If the node has only one child, replace the existing node with its child.
• If it has both the children, find the immediate successor (or predecessor) and replace the current node with that.

Trie

• Used for searching as in a dictionary.

Graphs

• Maximum flow - min cut algorithm Ford Fulkerson

Graph vs Tree

• A tree is an undirected graph which is
  • connected: Every node must be able to reach all other nodes
  • no cycle: A tree should not have a cycle
• This is can be done using DFS as mentioned in this Algo Monster Medium article.

Mathematical concepts

• Modular division and inverse
• Moyer-Moore Majority voting algorithm
• Recursive sum of digits Leetcode: Modulo of 9 or the base digit - 1

  class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0;
        if (num % 9 == 0) return 9;
        return num % 9;
    }
  }
  

Problems list

Divide and Conquer

1. A very good problem: Longest Substring with At Least K Repeating Characters

Monotonic queue

1. Shortest Unsorted Continuous Subarray
2. Sliding Window Maximum
3. Remove duplicate numbers Leetcode
4. Largest Rectangle in a histogram - solution
5. Remove k digits Leetcode

Binary search

Binary search problems folder

1. You have to find not the exact match, but the least absolute distance to the elements in the array. heaters problem

Binary search over solution space

1. Split Array Largest Sum

Two pointers

Sometimes, you may have to sort the data when using this. Also this can be extended to three pointers and more.

1. Three sum problem
2. Next Permutation
3. Longest substring without repeating characters: O(n) solution
4. Minimum window substring
5. Minimum size subarray sum This problem can be solved using cumulative sum method too. But it takes O(n^2) time.
6. Longest Repeating Character Replacement. Also watch the YT video here.
7. Longest substring with at least k repeating characters

Diff array technique

1. Corporate flight bookings - solution

Dynamic Programming (DP)

1. Maximal Square - Difficult to come up with the logic.
2. Largest magic square
3. Edit Distance
4. Maximum Profit in Job Scheduling
5. Palindrome partitioning
6. Longest Valid Parentheses
7. A little tough: Best time to buy and sell stock IV Leetcode
8. Bursting balloons
9. LIS variant: First sort the data based on one field, then find the LIS based on the second field. Russian doll envelopes
10. LIS variant: first sort and then check LIS property based on whether one is divisible by another. Largest divisble subset
11. Similar to knapsack: Partition Equal Subset Sum

Using original indexes array

1. Couples holding hands - solution

Bit manipulation

This can be used in a lot of places. Some are:

• Use XOR to find duplicates, swap numbers etc.
• Efficient way to save whether a test case is covered or not. For example if there are a max of 32 elements in array and you want to track whether element is used, just set that bit to 1 in an integer.

1. Find non-duplicate number without extra space

Hashing

1. Group anagrams - solution
2. Longest Consecutive Sequence

Sorting

1. Group anagrams - solution
2. My Calendar
3. Sometimes numbers can be converted to strings and sorted. Here a custom comparator is used to figure which type of concatenation is better (a+b or b+a) - Largest Number Leetcode
4. A variation of merge sort - Count of smaller numbers after self

Recursion

1. House Robber Three
2. Longest substring with at least k repeating characters

Binary Tree

1. House Robber Three

Heap - Priority Queue

1. Leetcode IPO
2. Asked in an interview Maximum jobs in non-consecutive towns

Sliding window

1. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

No or constant extra space

See if you can manipulate the existing array/DS itself. For example, you can change the sign of the element etc to remember wehther visited or not.

1. First Missing Positive

Graphs

1. Bipartite graph

Union Find

1. Asked in an interview: Group nodes into a network and find sum after each network merge

Topological sort

1. Course schedule two
2. Course Schedule
3. Alien dictionary The key is to understand that a dictionary problem is nothing but topological sort.

Breadth First Search (BFS)

1. Word ladder II

Depth First Search (DFS)

1. Pacific Atlantic Water Flow