My software development journey
Given an array of N distinct values, how to find the number of pairs with a difference of K? For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}. One obvious solution could be to examine each possible pair…
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…
Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K. For example let us consider the following array as input [4, 5, 3, 2, 6, 1, 2, 3, 8, 4] Let as take the sliding window of size 3.…
Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it’s elements is minimum among all K-size sub arrays. For example Let us consider the following array of size 10. {1, 2, 1, 3, 1, 1, 1, 4, 2, 3} The…
Given an array containing all elements twice except two numbers. Write a program to find those two numbers. For example let us consider the following array {2, 3, 2, 1, 4, 1, 4, 5} The answer is {3,5} because they appear only once and all remaining elements appear twice. This question is somewhat similar to earlier…