Close

Edit distance 1

Given two strings, how do we check if their edit distance is 1? Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string. For example let us consider two strings “java”, “lava” they both differ by just one character.…

Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below. Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right Similarly move right, and fill each element which is one greater than it’s…

Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]…A[j]), For example, let the array be [15, 6, 1, 12, 7, 4, 10] Sum(A[1:3]) = 15+6+1 = 22 Sum(A[4:6]) = 12+7+4 = 23 … The simplest solution is to iterate through the elements from i to j and return the…

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one. How do you find the different number? For example consider the array [1, 2, 3, 5, 9], 2 is the different number. Similarly in the array [10, 6, 7, 24, 36], 7 is the different number. This…

XOR of all sub arrays

Given an array of elements, how do we find the XOR of each sub-array and XOR of those results? For example let us consider the array [1, 2, 3], all possible sub-arrays are XOR[1] = 1XOR[1, 2] = 1 ^ 2 = 3XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0XOR[2] = 2XOR[2,…