# Category: Top Companies

## Snake and Ladder Problem

Objective – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the dice you throw results in always...

## 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...

## Minimum Copy Paste Operations

Objective: You have given a character ‘A’ which is already printed. You are allowed to perform only 2 operations – Copy All – This operation will copy all the printed characters. Paste – This...

## 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,...

## Graph – Print all paths between source and destination

Objective: Given a graph, source vertex and destination vertex. Write an algorithm to print all possible paths between source and destination. This problem also known as “Print all paths between two nodes” Example: Approach:...

## 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,...

## Print all substrings of a given string

Objec­tive:  Given a string write an algorithm to print all the possible sub strings. Example: String input = “abcd”; Output: Possible sub strings – a          a b      a b c   a b c d b...

## 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} ,...

## 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...

## Divide and Conquer – Rearrange array elements in special order

Objec­tive:  Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and last n elements are set up in alternative manner. Say n = 3 and...

## Dynamic programming – Printer Problem

Objective:  Given a printer which can perform only 2 operations- Printer can print consecutive identical characters in one go. It can replace consecutive characters by consecutive identical characters at any position. You are given a...