Check if a repeated subsequence is present in a string or not
Given a string, check if a repeated subsequence is present in it or not. The repeated subsequence should have a length of 2 or more.
Tag: Hard
Swap individual bits at a given position in an integer
Given an integer, swap consecutive b bits starting from the given positions in a binary representation of an integer. The bits to be swapped should not overlap with each other.
Find minimum or maximum of two integers without using branching
Given two integers, find their minimum and maximum without using branching.
Count set bits using a lookup table
Given an integer, count set bits in it using a lookup table.
Compute the parity of a number using a lookup table
In this post, we will see how to compute the parity of a number using a lookup table. The parity refers to the total number of 1’s in the binary number.
Find maximum sum `K × K` submatrix in a given `M × N` matrix
Given an M × N matrix, calculate the maximum sum submatrix of size k × k in it in O(M × N) time.
Find the shortest path from source to destination in a matrix that satisfies given constraints
Given an N × N matrix of positive integers, find the shortest path from the first cell of the matrix to its last cell that satisfies given constraints.
Print a spiral square matrix without using any extra space
Given a positive number N, print an N × N spiral matrix containing numbers from 1 to N × N in a counterclockwise direction and without extra space.
Find the shortest safe route in a field with sensors present
Given a rectangular field with few sensors present, cross it by taking the shortest safe route without activating the sensors.
Find all occurrences of the given string in a character matrix
Given an M × N matrix of characters, find all occurrences of a given string in the matrix. We are allowed to search the string in all eight possible directions. Note that there should not be any cycles in the output path.
Inversion count of an array
Given an array, find the total number of inversions of it. If (i < j) and (A[i] > A[j]), then pair (i, j) is called an inversion of an array A. We need to count all such pairs in the array.
External Merge Sort Algorithm
The external merge sort algorithm is used to efficiently sort massive amounts of data when the data being sorted cannot be fit into the main memory (usually RAM) and resides in the slower external memory (usually a HDD).