Islands in a two dimensional array
Each element in the array is connected to eight other elements (toward top, down, left and right). For example, the zero below is connected to all the ones 1 1 1 1 0 1 1 1 1 Given a two-dimensional array of 0’s and 1’s. Find the number of islands where an island is a […]
Hamming distance
Write code to calculate hamming distance between two strings. Hamming distance between two strings of equal length is equal to the total number of positions at which corresponding characters in the two strings are different. String-1 String-2 Hamming distance ———— ———— —————- TONED ROSES 3 KAMAL RAWAT 3 203 233 1 RITAM BHARA 5 OK […]
Array of products except the current elements
Given an array of integers, create another array whose i‘th element contain the product of all the elements in original array except the i’th element in original array.
Number of possible triangles from given array of numbers
Given an array of numbers, write an algorithm to count how many triangles are possible with three numbers from array as their side. If input array is: {7, 3, 6, 4} Then the output should be 3 because there are 3 possible triangles, viz.: {3, 4, 6}, {3, 6, 7} and {4, 6, 7}.
Transpose of non-symmetric matrix
Given a M*N order matrix, which is stored in an array in a row-major order. eg. if the matrix is of order 2*4 with below elements a b c d e f g h Then it is stored in a one dimensional array as below: a b c d e f g h Write a program […]
Find non repeating number
Given an array of numbers where each number is repeating thrice. In that array one element is not repeating at all. Find that number. Input Array: {5, 9, 2, 5, 2, 5, 2} Output: 9
Find number occurring odd number of times in an array
Given an array of positive integers in which each number is repeated even number of times, except one which is repeated odd number of times. Write an O(n) time algorithm to find the Number repeating odd number of times. For Example, If the input array is: {1, 2, 9, 2, 8, 1, 9, 2, 8, […]
Kadane's Algorithm to find maximum subarray sum
Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example: Array Maximum Sub-Array sum ———————– ———————– —- {5, 7, 12, 0, -8, 6} {5, 7, 12} 24 {6, -2, -3, 4, -1, 10 } {6, -2, -3, […]
check if all nodes of a tree has only one child
Given the PreOrder traversal of a binary search tree (in the form of a tree), check if all the nodes (except the last) of the tree has exactly one child. For Example: If the Preorder traversal of the tree is given as below: {50, 25, 45, 30, 27, 29} The the output should be: TRUE […]
Comparison of sorting algoritms
Which sorting algorithm makes minimum number of memory write ?
