Validate Binary Search Tree: Check if a Binary Tree is BST or not

Given the root of a binary tree, write a program to check whether it is a valid binary search tree (BST) or not. A BST is valid if all nodes in the left subtree have values less than the node’s value, all nodes in the right subtree have values greater than the node’s value, and both left and right subtrees are also binary search trees.

Valid Anagram: Check if Two Strings are Anagram or not

Given two strings str1 and str2 of size m and n, write a program to check whether the two strings are an anagram of each other or not. A string str1 is an anagram of str2 if the characters of str1 can be rearranged to form str2.

Merge Sort Algorithm

Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.

Minimum in a Rotated and Sorted Array

A sorted and rotated array of size n is given, write a program to find the minimum element in the array. Rotation by k times means that the first k sorted elements of the array will move to the last k positions, and the last n - k sorted elements move to the first n - k positions (in an anti-clockwise fashion).

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two-pointers approach provides an efficient solution in O(n) time and O(1) space.

Counting Sort Algorithm

The counting sort algorithm assumes that each n input element is an integer in the range 0 to k. So by using array indexing as a tool for determining relative order, counting sort can sort n numbers in O(k + n) time when k = O(n). In other words, counting sort is one of the popular linear time sorting algorithms that works in O(n) time complexity if input elements are an integer in the range 0 to k.

Maximum difference in an array

Given an array A[] of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.

Print Matrix in Spiral Order

Given a 2-dimensional matrix, print the elements in spiral order. We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. This is a good matrix problem to learn problem-solving using iteration and recursion.

First Missing Positive

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best searching problems for learning step-by-step optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate correct output.

Container With Most Water Problem

Given an array of n non-negative integers height[n], where each represents a point at coordinate (i, height[i]). n vertical lines are drawn such that the two endpoints of line i is at (i, height[i]) and (i, 0). Write a program to find two lines, which together with the x-axis form a container, such that the container contains the most water.

Binary Search Algorithm

The binary search is one of the fastest searching algorithms, which search a value in the sorted array in an O(logn) time complexity. Here we search a value using divide and conquer by repeatedly dividing the search interval in half. Problem statement: Given a sorted array X[] of n elements, search a given element key in X[]. If the key exists, then return its index in the sorted array. Otherwise, return -1.

Least Frequently Used (LFU) Cache Implementation

The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency.

Valid Mountain Array

Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.

kth smallest element in an array

Given an array and a positive integer k, write a program to find the kth smallest element in the array. This is an excellent problem to learn problem-solving using the heap data structure. The quick-select approach (divide and conquer) is also worth exploring that helps optimize time complexity to O(n) time average.

Implement Least Recently Used (LRU) Cache

The Least Recently Used (LRU) is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time.

Leaders in an array

Given an integer array X[] of size n, write a program to find all the leaders in the array X[]. An element is a leader if it is strictly greater than all the elements to its right side. So the largest and last element of an array is a leader by default. This is an excellent problem to learn problem-solving using a single loop and variables.

Kth Largest Element in a BST

Given the root of a BST and an integer k, write a program to find the kth largest value among all the nodes' values in the tree. This is an excellent problem to learn problem-solving using inorder traversal and data structure augmentation (storing extra information inside BST nodes for solving a problem).

Minimum Absolute Difference in a BST

Given the root of a Binary Search Tree (BST), write a program to find the absolute minimum difference between the values of any two nodes in the tree. Here node values in the tree can be positive, negative, or zero. This is an excellent problem to learn problem-solving using in-order traversal in a BST.

Find Max Consecutive 1's in an Array

A binary array X[] is given where elements are either 0 or 1. Write a program to find the maximum consecutive ones. The subarray with max continuous 1's can be present anywhere, starting from some index i and ending at some index j. This is an excellent problem to learn problem-solving using the sliding window and a single loop.

Find Product of Array Except Self

Given an array X[] of n integers, write a program to find an array product[] such that product[i] is equal to the product of all the elements of X[] except X[i]. We need to solve this problem without using division operations. This is an excellent problem to learn problem-solving using prefix array and a single loop.

Sort Characters by Frequency

Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.

Intersection of Two Unsorted Arrays

Given two integer arrays, X[] and Y[] of size m and n. Write a program to find the intersection of these two arrays. The intersection of two arrays is a list of distinct elements present in both arrays. The elements in the intersection can be in any order. Suppose m > n and elements in both arrays are distinct.

Length of the Largest Subarray with Zero Sum

Given an array X[] of n integers, find the length of the longest subarray with a sum equal to 0. In general, for all j > i, find max (j - i + 1) among all subarray with zero-sum. Note: the subarray length starting from index i and ending at index j will be j - i + 1. This is an excellent question to learn problem-solving using a hash table.

Maximum depth or height of a binary tree

Given a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to the leaf, i.e., the max number of nodes from the root to the most distant leaf. This is an excellent problem to learn problem-solving using DFS and BFS traversal.

Max Continuous Series of 1s

You are given an array of 1s and 0s and you are given an integer k which signifies the number of flips allowed. Write a program to find the position of zeros which when flipped will produce maximum continuous series of 1s.This is one of the good problems to understand the idea of the sliding window technique. Using this approach, We can solve several interview problems efficiently in O(n) and O(1) space.

Find maximum j – i such that A[j] > A[i]

Given an unsorted array X[] of distinct elements, write a program to find the maximum j - i such that j > i and X[j] > X[i].

Intersection of two sorted linked lists

Given two sorted linked lists, write a program to find the intersections of the linked lists, and return the head of the new Linked List.

Find middle element in linked list

Given a singly linked list, write a program to find the middle node of the linked list. If the node count is even then we need to return the second middle node.

Implement Stack using Queues

Write a program to implement a stack using the queues. The implemented stack should support standard operations like push(x), pop(), and top(). This is an excellent problem to learn problem-solving and visualize the use case of stack and queue operations.

Minimum Depth of a Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. The path has to end on a leaf node.

Check if two arrays are equal or not

Given two integer arrays X[] and Y[], write a program to check if the arrays are equal or not. Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must also be the same for both arrays.

Longest Common Subsequence

The longest common subsequence algorithm is a problem to find the length of the longest subsequence common to all subsequences of two strings. The lcs algorithm differs from the algorithm of the longest common substring problem. Explore and Enjoy!

Find the next greater element for every element in an array

Given an array, find the next greater element for every element in the array. The next greater element for an element is the first greater element on the right side of the array. This is one of the best problems to learn problem-solving using stack.

Minimum number of Jumps to reach End

An array of non-negative integers is given and the aim is to reach the last index in the minimum number of jumps. You are initially positioned at the first index of the array and each element in the array represents your maximum jump length at that position.

Roman to Integer

Given a Roman numeral, write a program to find its corresponding decimal value. Roman numerals are represented by seven different symbols: I , V, X, L, C, D and M.

Remove Nth Node from List End

Write a program to remove the Nth node from the end of the linked list i.e. when the node is traversed from the end we have to delete the Nth node from there.

Find all possible combinations of K numbers from 1 to n

Given two numbers n and K and you have to find all possible combinations of K numbers from 1 to n. This is a good interview problem to understand the concept of problem-solving using backtracking and combinatorics.

Detect Loop in a Linked List

Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.

Reverse a linked list

Write a program to reverse a linked list. A head pointer of a linked list is given and our task to reverse the entire list so that when the resulted list is traversed it looks like we are traversing the original list from tail to head.

Minimum Coin Change Problem

If we want to make a change for a given value K of cents, and we have an infinite supply of each of coin[ ] = [C1, C2, …, Cm] valued coins, write a program to find the minimum number of coins required to make the change?

Median of two sorted arrays of the equal size

There are two sorted arrays A and B of size n each, write a program to find the median of the array obtained after merging both the arrays(i.e., an array of length 2n which is even). The median of a sorted array of size n is defined as the middle element when n is odd and the average of the middle two elements when n is even.

Climbing Stairs Problem

There is a staircase of n steps and you can climb either 1 or 2 steps at a time. You need to count and return the total number of unique ways to climb the staircase. The order of steps taken matters.

Longest Substring Without Repeating Characters

Write a program to find the length of the longest substring without repeating characters. Substring is the continuous sub-part of the string. The aim is to determine the maximum such subpart which has all the unique characters.

Longest Consecutive Sequence

Given an array X[] of n integers, write a program to find the length of the longest consecutive elements sequence. In other words, we need to find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers. The consecutive numbers can be in any order.

Find most frequent element in an array

Given an array X[] of size n, write a program to find the most frequent element in the array, i.e. the element which occurs the most number of times. It is assumed that at least one element is repeated.

Find row with maximum number of 1s

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. This is an excellent matrix problem that can be solved in linear time complexity. The best part is — we are using the sorted order property and nested loops to improve the solution over the binary search approach.

Find whether an array is a subset of another array

We are given two integer arrays X[] and Y[], write a program to check whether array Y[] is a subset of array X[] or not. An array Y is a subset of another array X if each Y element is present in X. How do you check if one array is a subset of another? Explore and Enjoy!

Find the maximum in an array which is first increasing and then decreasing

You are given an array of integers that is initially increasing and then decreasing, find the maximum value in the array.

Find first and last positions of an element in a sorted array

Given an array of integers sorted in ascending order, find the first and last position of a given value. This is a good interview problem to learn problem-solving using binary search.

Iterative Binary Tree Traversal using Stack: Preorder, Inorder and Postorder

In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.

Level Order Traversal (BFS Traversal) of a Binary Tree

Level order traversal accesses nodes in level by level order. This is also called breadth-first search traversal or BFS traversal. Here we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.

Find Majority Element in an Array

You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.

Search in a row-wise sorted 2D matrix

You are given a row-wise sorted 2D matrix and a given integer k, write a program to find whether the integer ‘k’ is present in the matrix or not. The matrix has the following properties: Integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Maximum Subarray Sum (Kadane’s Algorithm)

Given an array X[] with n elements, we need to write a program to find the largest contiguous subarray sum. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.

Check for pair in an array with a given sum

Given an array of n integers and a target number, write a program to check whether a pair sum exits in the array or not. In other words, we need to check whether pair of elements in the array sum exactly to the target value.

Rotate a matrix by 90 degrees

Given an n x n 2D matrix representing an image, rotate the image by 90 degrees in an anticlockwise direction.

n Repeated element in 2n size array

In an array of size 2n, there are n+1 unique elements, and exactly one of these elements is repeated n times. Return the element repeated n times.

Quick Sort Algorithm

Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!

Remove duplicates from sorted array

Write a program to remove the duplicates from the sorted array. For this we are given a sorted array, the task is to remove the duplicate elements such that there is a single occurrence of each element in the array.

Sort an array of 0s, 1s, and 2s —Dutch National Flag Problem

Given an array X[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order. This is a famous coding interview problem asked in facebook, microsoft and amazon.

Sort an array in a waveform

Given an array of integers, sort the array into a wave-like arrangement. In other words, An array A[0..n-1] is sorted in wave form if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ….This problem has been asked during google coding interview.

Find the minimum and maximum value in an array

Given an array X[] of size n, we need to find the maximum and minimum element present in the array. This coding problem has been asked during facebook and microsoft interview.

Move all Zeroes to the End of an Array

Given an array X[] of n elements filled with several integers, some of them being zeroes, write a program to move all the zeroes to the end. This is an excellent coding problem to learn space and time complexity optimization.

Equilibrium Index of an Array

Write a program to find the equilibrium index of an array. An array's equilibrium index is an index such that the sum of elements at lower indexes equals the sum of elements at higher indexes. This is an excellent coding question to learn time and space complexity optimization using several approaches.

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.