My software development journey
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]…
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 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…
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}…
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,…
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…