# Category: Amazon Questions

## Topological Sort

Topological Sort: A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed...

## Count and print all Subarrays with product less than K in O(n)

Objec­tive:  Given an array of positive integers and integer ‘K’. Write an algorithm to count all the possible sub arrays where product of all the elements in the sub array is less than k. Example:...

## Sliding Window Algorithm (Track the maximum of each subarray of size k)

Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k. Example: int [] nums = { 1, 2, 3, 2, 4, 1, 5,...

## Print all sub sequences of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub subsequences. Example: int [] a = {1, 2, 3}; Output: Possible sub sequences – {Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2,...

## Sum of all sub arrays in O(n) Time

Objec­tive:  Given an array write an algorithm to find the sum of all the possible sub-arrays. Example: int [] a = {1, 2, 3}; Output: Possible subarrays – {1}, {2}, {3}, {1, 2} , {2,...

## Print all subarrays of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub arrays. Example: int [] a = {1, 2, 3}; Output: Possible subarrays – {1}, {2}, {3}, {1, 2} , {2, 3}, {1,...

## Text Justification Problem (OR Word Wrap Problem)

Objec­tive:  Given a list of words and length L. Format the words so that each line will have only L characters and fully justified (left and right justified). Restrictions- You need to fit as many...

## Dynamic Programming – Egg Dropping Problem

Objec­tive:  There are n number of eggs and building which has k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if egg is dropped,...

## Nuts & Bolts Problem (Lock & Key problem)

Objec­tive:  Given ‘n’ Nuts and ‘n’ Bolts of different sizes. There is one-to-one mapping between nuts and bolts. Write an algorithm to find all matches between nuts and bolts Note: This problem can also be...

## Remove Duplicates from a string

Objective:  Given a string, write an algorithm to remove the duplicate characters in that string. Example: Input: tutorialhorizon Output: tuorialhzn Approaches: There are multiple approaches to solve this problem- Use Sorting – (Will change the...

## Find median of two sorted arrays of same size

Objective:  Given two sorted arrays of size n. Write an algorithm to find the median of combined array (merger of both the given arrays, size = 2n). What is Median? The median is the value separating the...

## Find two non-repeating numbers in an array in O(n) time and O(1) space

Objective:  Given an array of integers which has all the repeating numbers (twice) but two numbers which are non-repeating. Write an algorithm to find out those two numbers. Example int [] arrA = {4,5,4,5,3,2,9,3,9,8}; Output:...

## Find the increasing OR decreasing point in an array

Objec­tive:  Given an array of integer which is first increasing then decreasing. Find the element in array from which point it starts decreasing. OR Given an array of integer which is first increasing then decreasing....

## Algorithm to calculate power(k,n).

Objective:  Given two numbers ‘k’ and ‘n’. Write an algorithm to calculate kn. Example: k = 4, n = 5 kn = 45 = 1024 k = 2, n = 3 kn = 23 =...

## Number of 1’s in bit representation of a number

Objec­tive:  Write an algorithm to count the number of 1’s in the bit representation in given number. Exam­ple: Number: 6 Output: 2 ( 1 1 0) Number: 11 Output: 3 ( 1 0 1 1)...