Sort a doubly-linked list using merge sort
Given a doubly linked list, sort it using the merge sort algorithm. Merge sort is an efficient sorting algorithm that uses the divide-and-conquer technique to sort a sequence of items.
Tag: Medium
Activity Selection Problem using Dynamic Programming
Given a set of activities and the starting & finishing time of each activity, find the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.
Find the sorted triplet in an array
Given an integer array A, efficiently find a sorted triplet such that A[i] < A[j] < A[k] and 0 <= i < j < k < n, where n is the array size.
Convert a ternary tree to a doubly-linked list
Write an efficient algorithm to convert a ternary tree into a doubly-linked list. A ternary tree is a tree data structure in which each node has three child nodes distinguished as left, mid, and right.
Find total ways to reach n’th stair with at-most `m` steps
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person is only allowed to take at most m steps at a time.
Find the number of ways to fill an `N × 4` matrix with `1 × 4` tiles
Given an n × 4 matrix where n is a positive number, find the number of ways to fill the matrix with 1 × 4 tiles.
Pairwise swap adjacent nodes of a linked list
Given a linked list, pairwise swap its adjacent nodes. The swapping of data is not allowed, only links should be changed.
Count subtrees in a BST whose nodes lie within a given range
Given a BST, count subtrees in it whose nodes lie within a given range.
Convert an infix expression into a postfix expression
Given an infix expression, convert it to the postfix expression. Assume that the infix expression is a string of tokens without any spaces.
Maximum Overlapping Intervals Problem
Consider an event where a log register is maintained containing the guest’s arrival and departure times. Given an array of arrival and departure times from entries in the log register, find the point when there were maximum guests present in the event.
Find total ways to reach the n’th stair from the bottom
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person can only climb either 1 or 2 or 3 stairs at a time.
Construct a Cartesian tree from an inorder traversal
Write an efficient algorithm to construct a Cartesian tree from inorder traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has a smaller value than the node itself.