Graph – Software Installation Problem
Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of...
Tagged: Intermediate
Graph – Depth First Search in Disconnected Graph
Objective: Given a Graph in which one or more vertices are disconnected, do the depth first traversal. Earlier we have seen DFS where all the vertices in graph were connected. In this article we...
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...
Print all sub sequences of a given String
Objective: Given a String write an algorithm to print all the possible sub subsequences. Example: String input = “abc”; Output: Possible sub sequences – {Empty}, {a}, {b}, {c}, {ab} ,{a,c}, {b, c}, {a, b, c}...
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:...
Graph – Depth First Traversal
Objective – Given a graph, do the depth first traversal(DFS). What is depth-first traversal– Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the...
Print all substrings of a given string
Objective: 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...
Print all subarrays of a given array
Objective: 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,...
Divide and Conquer – Rearrange array elements in special order
Objective: 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...
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 local minimum or local maximum in O(1).
Objective: Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one...
Majority Element- Boyer–Moore majority vote algorithm
Objective: Given an array of integer write an algorithm to find the majority element in it (if exist). Majority Element: If an element appears more than n/2 times in array where n is the size...
Find the local minima in a given array
Objective: Given an array of integer write an algorithm to find the local minima. Local Minima: An element is considered as local minima if it is less than both of its neighbors (if neighbors exist)....