Problems to solve

Array problems

Q. Move Negative elements to front

Move Negative elements to front is a simple problem that tests your knowledge of how to move elements across an array. Partition Scheme and has direct application in algorithms like QuickSort.

import java.util.Arrays;

public class MoveToFront {
    /*
    Example:
        Input:
        2 -9 10 12 5 -2 10 -4
        Note:
        The order of negative elements are same.
        All negative elements have been moved to the front.
    */

    public static void main(String[] args) {
        int[] input = {2, -9, 10, 12, 5, -2, 10, -4};
        System.out.println(Arrays.toString(input));

        // we have to move all negatives to front so all positives must go to end
        //if order does not matter
        for (int i = 0,j=input.length-1; i < j ; ) {
            if (input[i]<0){
                i++;
            } else{
                System.out.println( "swapping "+ input[i]+" with "+input[j]);
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
                j--;
                System.out.println(Arrays.toString(input) );
            }
        }

        System.out.print(Arrays.toString(input) );
        System.out.println();
        System.out.println();
        System.out.println();

        /*
        [2, -9, 10, 12, 5, -2, 10, -4]
        swapping 2 with -4
        [-4, -9, 10, 12, 5, -2, 10, 2]
        swapping 10 with 10
        [-4, -9, 10, 12, 5, -2, 10, 2]
        swapping 10 with -2
        [-4, -9, -2, 12, 5, 10, 10, 2]
        swapping 12 with 5
        [-4, -9, -2, 5, 12, 10, 10, 2]
        FINALLY
        [-4, -9, -2, 5, 12, 10, 10, 2]
        */

        // FOR PRESERVING RELATIVE ORDER OF NEGITIVES
        input = new int[]{2, -9, 10, 12, 5, -2, 10, -4};
        int j = 0;
        for (int i = 0; i < input.length; i++) {
            if (input[i] < 0) {
                System.out.println( "swapping "+ input[i]+" with "+input[j]);
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
                j++;
                System.out.println(Arrays.toString(input) );
            }
        }
        System.out.print(Arrays.toString(input) );
    }

    /*
    swapping -9 with 2
    [-9, 2, 10, 12, 5, -2, 10, -4]
    swapping -2 with 2
    [-9, -2, 10, 12, 5, 2, 10, -4]
    swapping -4 with 10
    [-9, -2, -4, 12, 5, 2, 10, 10]
    [-9, -2, -4, 12, 5, 2, 10, 10]
    * */
}

Q. 2 Sum Problem

2 Sum problem is a standard problem where you need to find two elements that add up to a given number.

    Input: arr[] = {0, -1, 2, -3, 1}, x= -2
    Output: [-3,1]
    Explanation: If we calculate the sum of the output,1 + (-3) = -2
    Input: arr[] = {1, -2, 1, 0, 5}, x = 0
    Output: No

Approaches

Brute Force

    void two_sum(int[] list, int sum)
    {
        int length = list.length;
        int count = 0;
        for(int i = 0; i<length; i++)
            for(int j = i+1; j<length; j++)
                if(list[i] + list[j] == sum)
                    System.out.println(list[i] +" "+ list[j]);
    }

Hash Map based approach

    public class TwoSum {
        public static int[] findTwoSum(int[] arr, int x) {
            HashMap<Integer, Integer> seen = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
            int complement = x - arr[i];
            if (seen.containsKey(complement)) {
                return new int[]{complement, arr[i]};
            }
            seen.put(arr[i], i);
            }
            return null;
        }

        public static void main(String[] args) {
            int[] arr = {0, -1, 2, -3, 1};
            int x = -2;

            int[] result = findTwoSum(arr, x);

            if (result != null) {
            System.out.println("Two elements that add up to " + x + " are: " + result[0] + " and " + result[1]);
            } else {
            System.out.println("No two elements found that add up to " + x);
            }
        }
    }

Q. 2 Sum Closest

Find 2 elements with sum closest to target

    public class TwoSumClosest {
        public static int[] findClosestSum(int[] arr, int target) {
            int closestSum = Integer.MAX_VALUE;
            int[] closestPair = null;
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    int currentSum = arr[i] + arr[j];
                    int diff = Math.abs(currentSum - target);
                    if (diff < closestSum) {
                        closestSum = diff;
                        closestPair = new int[]{arr[i], arr[j]};
                    }
                }
            }
            return closestPair;
        }

        public static void main(String[] args) {
            int[] arr = {0, -1, 2, -3, 1};
            int target = -2;
            int[] result = findClosestSum(arr, target);
            if (result != null) {
                System.out.println("Two elements with closest sum to " + target + " are: " + result[0] + " and " + result[1]);
            }
        }
    }

Q. A 3 Sum Problem

Given an array, we need to find if there is a triplet in the array whose sum is equal to a given value. If such a triplet is present, we need to print it and return true. Else, return false.

    Input: array = {12, 3, 4, 1, 6, 9}, sum = 24; 
    Output: 12, 3, 9 
    Explanation: There is a triplet (12, 3 and 9) present 
    in the array whose sum is 24. 

    Input: array = {1, 2, 3, 4, 5}, sum = 9 
    Output: 5, 3, 1 
    Explanation: There is a triplet (5, 3 and 1) present 
    in the array whose sum is 9.

Brute Force Approach

    public class ThreeSumBruteForce {
        public static void main(String[] args) {
            int arr[] = { 1, 4, 2, 6, 10, 8}; 
            int sum = 9; 
            int arr_size = arr.length;
            triplet(arr, arr_size, sum); 
        }

        static Boolean triplet(int arr[], int arr_size, int sum) { 
            //i for first element
            for (int i = 0; i < arr_size - 2; i++) { 
                //j for second element
                for (int j = i + 1; j < arr_size - 1; j++) {  
                    //k for third element
                    for (int k = j + 1; k < arr_size; k++) { 
                        if (arr[i] + arr[j] + arr[k] == sum) { 
                            System.out.println("Triplet is " +arr[i]+" "+arr[j]+ "  "+arr[k]);
                            return true; 
                        } 
                    } 
                } 
            } 
            //false if no such triplet is found 
            return false; 
        } 
    }

1. A 3 Sum Closest Problem

   You have attempted the 2 Sum Closest problem variant but can you use similar ideas to solve 3 Sum Closest problem as well.

2. 4 Sum Problem

   4 Sum problem brings in new ideas and puts your knowledge from previous problems to test. If you are able to solve it, try the 4 Sum Closest problem on your own.

Linked List problems

1. Linked List with no NULLs

   This is an important topic that you must cover. In interviews at top companies like Google, you must implement Linked List without using NULL as this is the standard coding practice in Industry.

2. XOR Linked List

   XOR Linked List is the memory efficient version of Doubly Linked List. The concept of using XOR in such cases in very important for Interviews.

3. Linked List vs Array

   Understand the differences between Array and Linked List. Often, asked in initial rounds.

4. Binary Search on LL

   Binary Search is frequently used to solve Interview problem. Is Binary Search on Linked List equally efficient?.

5. Middle element in LL

   This problem of “Finding middle element of a Linked List” involves the technique of Slow and Fast pointer which is widely used.

6. Sort LL on absolute values

   Sort Linked List whose values have already been sorted on absolute values is a HOT interview problem.

7. Loop in Linked List

   There are 3 methods to detect a loop in Linked List.

8. Reverse a Linked List

   Reversing a Linked List may seem to be a simple problem but it uses 3 pointers. The challenge is to reverse a Linked List using 2 pointers. This involves the idea of XOR.

9. Cycle detection

   This is a HOT interview question. There are over 3 methods to detect Cycle in a Linked List and a follow-up question will to be remove a cycle.

Stack problems

1. 2 Stacks in one Array

   This problem of implementing 2 Stacks in 1 array is a simple problem. The main challenge is with the next problem.

2. N Stacks in one Array

   This problem is much more challenging problem. Understand the solution carefully as this is a HOT interview question now. Similar problem is N Queues in one Array.

3. Monotonic Stack

   Monotonic Stack is a core technique which exploits the properties of Stack to solve several challenging problems. Go through some example problems to hone your skills.

4. Merge Intervals

   The problem of Merge Intervals is a HOT interview problem. It is, often formulate as Time interval or duration of an event.

Queue problems

1. Delete middle element of Queue

   Delete middle element of Queue is a simple problem that tests how you can use core operations to build other operations. If needed, you should quickly revise the basics of Queue and types of Queue.

2. Monotonic Queue

   Monotonic Queue is a core technique using Queue to solve challenging problems like Daily Temperate problem.

3. Queue using Stack

   Implementing Queue using Stack data structure is another important Interview problem to test your concepts. The corresponding problem is to Implement Stack using Queue.

4. Next Larger / Smaller element in Array

   Next Larger / Smaller element in Array is a difficult interview problem that use the idea of Monotonic Queue.

5. Maximal Rectangle problem

   Maximal Rectangle problem is another difficult interview problem that use the idea of Monotonic Queue.

Binary Tree

1. Diameter and Height

   Finding the Diameter and Height of a Binary Tree is a simple yet core problem that everyone should be fluent in. Every few students know that the average height of a random Binary Tree is O(N^0.5) (see how?).

2. No NULL implementation

   Implementing Binary Tree with no NULLs is an approach that sets you apart from other candidates. Avoiding NULLs is Industry standard.

3. Largest Independent Set

   Finding the Largest Independent Set in Binary Tree is a problem that requires the application of Dynamic Programming. This is an important interview problem.

4. Copy Binary Tree

   Copying a Binary Tree with random pointers is a challenging problem. The trick is to handle the random pointers efficiently as the destination node may not have been processed. A related concept is Threaded Binary Tree.

5. Traversal of Binary Tree

   Zig Zag traversal and Level Order traversal of a Binary Tree is a problem that tests your Binary Tree handling skills. Different types of view of a Binary Tree is equally important problem.

6. Self-balancing Trees

   Self-balancing Trees are important concepts. Interviewers usually ask to list a few self-balancing binary trees. Some advanced levels may ask to explain the idea behind Red Black Tree.

7. Spreadsheet

   A HOT interview question is to design a spreadsheet / Excel sheet. This ivolve the idea of using Binary Tree.

Trie problems

1. Maximum XOR of two numbers

   This problem of finding the Maximum XOR of two numbers involve the use of Trie data structure which is not obvious from the problem statement.

2. Longest Common Suffix

   This is a HOT interview problem. Finding the Longest Common Suffix cannot be done efficiently using Trie. Similarly, you can solve the Longest Common Prefix problem.

3. All Valid Word Breaks of a Sentence

   Word Break Problem is a standard problem that involve the use of DP and Greedy algorithms. This variant: All Valid Word Breaks of a Sentence use Trie to solve it optimally.

4. Autocomplete feature

   Autocomplete feature is the most common feature of True data structure and Interviews revolve around this specific application.

Hash Map / Set

1. Collision Resolution

   There are different Collision Resolution techniques in a Hash Set and is frequently asked in Interviews.

2. LFU (Least Frequently Used) Cache

   Designing LFU (Least Frequently Used) Cache is a HOT interview question that involve the use of Hash Map. Another related problem is to design Least Recently Used (LRU) Cache.

3. Quadratic Probing

   The concept of Quadratic Probing and Linear Probing are frequently asked in Interviews.

4. Hash Functions

   Knowing multiple examples of Hash Functions is important for Interview as it is the fundamental component of Hash Set. You may need to hash an array or set.

5. All O`one Data Structure

   This problem is about designing a custom Data Structure. These type of problems are HOT in interview. Try: All O`one Data Structure.

Sorting Algorithms

1. Search in Sorted 2D matrix

   The problem to Search an element in Sorted 2D matrix is a HOT interview problem.

2. Quick Sort

   Quick Sort is the most important topic in Sorting. Revise Time Complexity of Quick Sort, Median of Medians algorithm. Practice these MCQs for Interviews.

3. Hybrid Sorting Algorithm

   The concept of Hybrid Sorting presents to the Interviewer that you understand how real-world algorithms are designed. There is no single algorithm that works best for all cases.

4. Radix Sort

   Knowing a few Non-comparison based sorting algorithms is important and Radix Sort is a strong example. Analyze Time Complexity for Non-Comparison based Sorting algorithm.

5. Sort on Linked List

   Sorting on array and linked list are two different things. One may work well on array but not on Linked List and vice versa. Insertion sort on Linked List is a must.

Mathematical Algorithms

1. Analyze Algorithms

   Having an overview of Mathematics for Analyzing Algorithms is a fundamental skill that you should have.

2. Permutation

   Permutation is a HOT interview questions. Problems like K-th permutation, Lexicographical Next Permutation, Heap’s algorithm for generating permutations and Counting derangements are must practice problems.

3. N-th root of a number

   There are 3 mainstream algorithms to find the N-th root of a number which everyone should have an idea of. You can also use Binary Search to find Square Root and Cube Root of a number.

4. Regula Falsi Method

   Regula Falsi Method and Newton Raphson Method are used to find root of a Polynomial.

5. Find GCD

   Binary GCD algorithm or Stein’s algorithm is the most basic algorithm to find GCD of numbers efficiently. Euclidean Algorithm is an efficient alternative.

6. Integer Factorization

   There are multiple Integer Factorization Algorithms and Pollard’s rho algorithm for factorization is a must.

7. Generate 0 and 1

   This is a HOT interview problem. Generate 0 and 1 with 25% and 75% probability using standard random functions.

8. Swap two numbers

   This is a HOT MCQ interview problem. There are over 6 different techniques to swap two numbers.

String Algorithms

1. Sub-strings of a string

   This is more like a brute force approach but candidates fail to implement or design an algorithm to generate all sub-strings of a string. This will help you solve most standard problems.

2. Number of palindromic substrings

   There are over 4 algorithms to find the Number of palindromic substrings in a string which involves use of Dynamic Programming and Modifed Manacher’s algorithm.

3. Pattern Search

   This is often asked in last Interview rounds at FAANG. KMP algorithm is the standard technique while Aho Corasick Algorithm helps you generalize the problem (asked frequently). Rabin-Karp Pattern Searching Algorithm is another efficient algorithm.

4. String Matching

   The concept of String Hashing and Rolling Hash is important in String Matching as it takes O(N) time to match a string but only O(1) time to match an integer. Shift OR algorithm for String Matching and String Matching using Bitset is a MUST for Interviews.

5. Sorted order of characters

   The problem Alien Dictionary problem: Sorted order of characters is a HOT interview problem involving the concept of Topological Sort.

Dynamic Programming

1. Basic problems on DP

   Standard DP problems that are common in Interviews are: Longest Geometric Progression, Calculate Binomial Coefficient and Coin Change Problem.

2. Shortest Path with k edges

   This is a HOT interview problem where DP is applied on Graph problem. Finding the Shortest Path with k edges and Number of paths with k edges with Dynamic Programming is a must practice.

3. Assembly Line Scheduling

   Scheduling problems are HOT interview problems. Assembly Line Scheduling using DP is a must. Similarly, Weighted Job scheduling problem is a variant that is popular in Interviews.

4. Knapsack Problem

   Knapsack Problem is one of the most common Interview problems. 0-1 Knapsack Problem is a variant that uses Dynamic Programming.

5. Box Stacking Problem

   Box Stacking Problem is a common problem for FAANG interviews. A variant of this is asked in every 3 out of 4 interviews.

6. Travelling Salesman Problem

   Travelling Salesman Problem and its variants are frequently asked in Interviews. It involves DP and bitmasking concepts. This is NP-Complete problem.

Greedy Algorithms

1. Activity Selection Problem

   Activity Selection Problem is one of the important problems where Greedy Algorithm is the direct solution. A variant of this: Scheduling tasks to Minimize Lateness is a critical Interview problem.

2. Egyptian Fraction Problem

   Egyptian Fraction Problem is an important Interview problem that lies at the intersection of Mathematical and Greedy Algorithms.

3. Fractional Knapsack Problem

   Fractional Knapsack Problem is a variant of Knapsack Problems that can be solved using Greedy Algorithms.

4. Largest Cube Formed

   The problem of Largest Cube Formed by deleting digits is interesting because of Time Complexity Analysis which many may get wrong in Interviews. It is O(N1/3 logN logN).

5. Maximal Clique

   Greedy Algorithms are also applied on Graph based problems. Finding Single Maximal Clique is a challenging Interview problem that is asked.

6. Fitting Shelves Problem

   This problem of Fitting Shelves is HOT interview problem requiring Greedy Algorithm.

Backtracking problems

1. Backtracking Algorithm for Sudoku

   Solving Sudoku using Backtracking is a standard technique though the implementation strategy is challenging in an Interview setting.

2. 8 Queens Problem

   Solving 8 Queens Problem using Backtracking is yet another important Interview problem. In similar chess setting, MCQs on number of possibilities of a given condition are asked frequently.

3. Subset Sum Problem

   Subset Sum Problem is a very common problem and many try to solve it using DP. Very few practice a variant where Backtracking is applied on Subset Sum Problem.

4. Knight’s Tour Problem

   In case of problems dealing with Chess, Backtracking is a potential technique. Solving Knight’s Tour Problem is important for Interviews and involve Backtracking and Warnsdorff’s algorithm.

5. Word Break Problem

   Word Break Problem is an important Interview problem that involve concepts like Backtracking and Dynamic Programming.

Divide and Conquer

1. Closest Pair of Points

   Closest Pair of Points is the most important Interview Problem based on Geometry and uses the concept of Divide and Conquer to solve it.

2. Karatsuba Algorithm

   Very few realize that there are algorithms that optimized fundamental operations like Multiplication. Karatsuba Algorithm uses the concept of Divide and Conquer to multiply two number efficiently.

3. Floor in sorted array

   Finding floor in sorted array is an easy problem that is asked in Interviews. Having a good hold on Binary Search is a must.

4. Elements with difference K

   Finding 2 elements with difference K in a sorted array is a fundamental problem that many get wrong.

5. Peak Element in an Array

   The problem of finding Peak Element in an Array tests your understanding of Divide and Conquer technique.

Decrease and Conquer

1. Fake Coin Problem

   Fake Coin Problem is the most frequently asked Interview Problem that involve the concept of Decrease and Conquer. Very few use this technique.

2. Basics of Decrease & Conquer

   Revise the basics of Decrease and Conquer along with overview of fundamental problems.

Graph Algorithms

1. Islands Problem

   Number of Islands in MxN matrix (of 0 and 1) and Making A Large Island by changing one 0 to 1 are HOT interview problems. This involve the concept of BFS and DFS.

2. Transitive Closure Of A Graph

   Transitive Closure Of A Graph using Graph Powering is a core concept that helps to solve several challenging interview problems.

3. Dijkstra’s algorithm

   Dijkstra’s algorithm will help you solve shortest path problems. Time Complexity of Dijkstra’s algorithm is a HOT interview problem.

4. Topological Sort

   Topological Sort is used to order nodes in a Graph linearly. There are multiple ways to implement Topological Sort like using BFS, using DFS and Kahn’s Algorithm. Understand the applications to understand the potential.

5. Bridges in Graph

   The problem of finding all bridges in a Graph is a hot Interview topic.

6. Hamiltonian Path & Cycle (+ Eulerian)

   The concept of Hamiltonian Cycle and Hamiltonian Path is critical for Interviews. Remember this is a NP-Hard problem but it is important to identify when an interview problem requires Hamiltonian Path (a path that goes through all nodes in the graph once).
   The alternative concept is Eulerian path which is a path that covers all edges in the graph. It can be found efficiently (not NP-Hard) using algorithms like Fleury’s Algorithm.

7. Count all paths

   Finding all paths is a way to count the paths but there exists other optimal ways where we can find the the total count without finding the actual paths.

8. Minimum Spanning Tree

   The concept of Minimum Spanning Tree is important. Kruskal Minimum Spanning Tree Algorithm and Prim Minimum Spanning Tree Algorithm are two core algorithms to find MST. Several graph based problems can be solved easily using MST like the Water Distribution problem in a village.

Computational Geometry

1. Number of integral points

   This problem of finding the Number of integral points between two points is a basic Interview problem. This involves Pick’s theorem. A variant is Number of Integral points inside a triangle.

2. Oriented area of a triangle

   Oriented area of a triangle is an important Interview problem for Computational Geometry.

3. Furthest Pair of Points

   Closest Pair of Points is a standard problem yet Furthest Pair of Points is becoming a common questions in Interviews. It involves Rotating Calipers method.

Game Theory

1. Game of Kayle

   Game Theory problems are rare in Interviews but there are 2 concepts that are tested. Sprague-Grundy Theorem and Game of Kayle is one core concept.

Time Complexity Analysis

1. Dynamic Array

   Time Complexity Analysis of Dynamic Array is a HOT interview questions. Candidates are asked how it works better than standard Array.

2. Multiplication

   This is a tricky interview question. Many candidate think multiplication is a simple operation but it is not. Understanding the Time Complexity Analysis of Multiplication is important.

3. Interpolation Search

   Binary Search is a common theme among interviews and Time Complexity of Interpolation Search is a HOT follow-up question in such cases.

Advanced problems

1. Range Minimum query

   The problem of Range Minimum query is common in advanced Interview rounds in FAANG. This can be solved using Segment Tree and Square Root Decomposition.

2. Distinct Elements

   The problem of finding Number of Distinct elements in a range is a HOT interview problem. A follow-up interview question is to support single element updates.

3. Count inversions in array

   This is another HOT interview problem in advanced rounds: Count inversions in an array. This is solved using the idea of Fenwick Tree.

4. Longest Increasing Subsequence

   The problem of Longest Increasing Subsequence is a standard problem that is solved using Binary Search and Dynamic Programming. The challenge is to use Fenwick Tree to solve LIS problem.

   find Longest Common Increasing Subsequence and

   Longest Increasing Consecutive Subsequence.