A number X is said to be ‘seed’ of number Y if multiplying X by its digit equates to Y. For example, 123 is a seed of 738 coz 123*1*2*3 = 738. Now given a number find all its ‘seed’. Solution:
Count Pairs of Numbers with a Given Difference K
Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. Return count of such pairs. Example k=4 and a[]={7,623,19,10,11,9,3,15} Output should be : 6 Pairs can be: 7,11 7,3 6,10 19,23 15,19 15,11 Solution: Time Complexity: O(NLogN) Space Complexity: O(1)
Number of Trailing Zeros in Factorial of a Number
Write a program to output the number of consecutive trailing zeros in the factorial of a number? Solution: 1. The number of trailing zeros in a number is equivalent to the power of 10 in the factor of that number. 2. The number power of 10 in the factors is the same as the minimum … Read More →
Passing Car East or West Codility
A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of … Read More →
Largest subarray with equal number of 0s and 1s
Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Examples: Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1} Output: 1 to 8 (Starting and Ending indexes of output sub array) Implementation: In this method,use two nested loops. The outer loop … Read More →
Counting Sort
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items. Algorithm: 1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the … Read More →
Sort Elements By Frequency
Problem: You are given an array. You have to sort the array elements in decreasing order of their frequency. eg. [2,3,4,2,8,1,1,2] Output: [2 2 2 1 1 3 4 8] Solution: Method 1 (Use Sorting) 1) Use quick sort algorithm to sort the elements O(nlogn) 2) Scan the sorted array and construct a 2D array … Read More →
Group all Words in Set of Anagrams of Each Other in Dictionary
Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets. For example – Input: “bat”, “tar”, “xyz” , “tab”, “tar” Output:[["bat", tab"], ["tar", rat"],”xyz” ] Thi sproblem was asked in amazon interview. Steps: 1)Use some sort of a hash … Read More →
Find Anagrams in array of Strings
Problem: You are given an array of strings and you have to print all the anagrams within the array. What is anagram – For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Solution: Let’s use this … Read More →
Find the Minimum Element in the Rotated Sorted array
Problem : Find the minimum element in the rotated sorted array. For example we have array as – 1,3,6,9,12,15. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 12,15,1,3,6,9 Solution – The answer to this lies on the fact that if we can find the point on … Read More →
Deleting all Leaves from a Binary Tree
Problem: Given a binary tree, how do you remove leaves of it? Solution: By using post-order traversal we can solve this problem (other traversals would also work). Time Complexity: O(n). Where is numbe of nodes in tree. Write or Comment if you find anything incorrect or better approach.
Find a Pair Whose Sum is Closest to Zero in Array
Problem: This problem is also called minimum absolute sum pair. You are given an array of integers, containing both +ve and -ve numbers. You need to find the two elements such that their sum is closest to zero. eg. Array [15, 5, -20, 30, -45] O/P should be 15, -20 Solution: Searching for two numbers … Read More →
What’s going on ?