Todo

Problem Given an integer array, count the number of inversions. What is an inversion? This was taught in Algorithms: Design and Analysis Part I on coursera - how to count inversions. Inversion count is the distance of order of elements in an array from the the sorted order i.e. it indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. ...

Count Primes Problem Given an integer n, return the number of prime numbers that are strictly less than n. Examples Example 1: Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. ...

Depth First Search DFS Traversal for Graph The idea Depth-First Search (DFS) is a graph traversal algorithm that explores as deeply as possible along each branch before backtracking to explore other options. This is similar to how we play a maze game. DFS can be implemented iteratively using a stack data structure, similar to Breadth-First Search (BFS) which utilizes a queue. Alternatively, a recursive approach is very natural for DFS due to its depth-oriented exploration. We will explore both implementations in detail later. ...

Problem Given that integers are read from a data stream. Find median of elements read so for in efficient way. OR Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) ...

Find First Unique Character From a Stream of Characters Problem Given a string A denoting a stream of lowercase alphabets. You have to make new string B. B is formed such that we have to find first non-repeating character each time a character is inserted to the stream and append it at the end to B. If no non-repeating character is found then append ’#’ at the end of B. ...

Problem The Fibonacci Numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, Sequence is defined as, $$ F_{0} = 0 $$ and $$ F_{1} = 1 $$ and $$ F_{n} = F_{n-1} + F_{n-2} $$ Given n, calculate F(n). Examples Example 1: Input : n = 2 Output : 1 ...

Problem The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagaram: A chess knight can move as indicated in the chess diagram below: ...

Problem Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Examples Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. ...

Problem Given a binary tree root and a linked list with head as the first node. Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False. In this context downward path means a path that starts at some node and goes downwards. Examples Example 1: ...

Problem You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi. You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d. Return the maximum number of events you can attend. Examples Example 1: ...