Close

## Minimum difference between two sorted arrays

Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array. For example consider the following two arrays. array1 = [3, 27, 45, 68, 70, 81, 99] array2 = [9, 16, 25, 35, 70, 84]…

## Finding the kth smallest element in the array

Given an array of numbers, how do we efficiently find the Kth smallest number in it? This problem is also called the selection problem. Widely used in order statistic (Find the smallest, biggest, median, top K elements etc…) For example in the array [6, 1, 9, 8, 3, 5, 4] the third smallest element is…

## Depth first traversal in a graph

Depth First Search (DFS) is graph traversal algorithm. Using this algorithm, given a source vertex (s), we can answer queries such as  What are the all the vertices connected to s? Is there any path from s to v? What is the path from s to v? For example consider the following undirected graph. 0…

## Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount? Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations {1,1,4} {1,1,1,3} {3,3}…

## Finding the edit distance between two strings

Given two strings as input, write a program to find the edit distance between them.  The edit distance is defined as the minimum number of modifications to do on one string to transform it into the other string. A modification can be inserting a character, deleting a character, or replacing an existing character. For example,…

## Valera and Plates – Code forces (Round #216) problem

In this post, we discuss a simple implementation problem from the recently concluded Code forces programming round. The problem description is given below. Valera is a lazy student. He has m clean bowls and k clean plates. Valera has made an eating plan for the next n days. As Valera is lazy, he will eat…