Find duplicates in an given array in O(n) time and O(1) extra space.
Objective: Given an array of integers, find out duplicates in it. Example: int [] a = {4, 6, 2, 1, 2, 5}; Output: Array has duplicates : 2 int a [] = {1, 6,...
Tagged: Intermediate
Find longest Snake sequence in a given matrix
Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequence in the matrix, you need to return the one...
Dynamic Programming – Count all paths in 2D Matrix with Obstructions in it
Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down....
Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix
Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down....
Print All Diagonals of a given matrix
Objective: Given two dimensional matrix, write an algorithm to print all the diagonals of matrix. Example: Approach: We will solve this problem in two parts. first half of diagonals and second half of diagonals....
Dynamic Programming – Maximum Subarray Problem
Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. Example: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,...
Kadane’s Algorithm – Maximum Subarray Problem
Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. Example: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,...
Introduction to Threaded Binary Tree
What is Threaded Binary Tree?? A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers...
Swap Nodes in pairs in a Linked List by changing links
Objective: Given a linked list write an algorithm to swap nodes in pairs by changing links . Earlier we have seen “Swap Every Kth node in a Linked List“, where we have seen how...
Convert BST to Greater Sum Tree
Objective: Given a binary search tree (BST), convert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the...
Reverse Alternative ‘k’ nodes in a Linked List.
Objective: Given a linked list and a number ‘k’, write an algorithm to reverse alternate ‘k’ nodes in the linked list. This problem was asked in the Microsoft and Amazon interviews. Example: Approach: Recursion...
Reverse a Linked List in groups of given size ‘K’
Objective: Given a linked list and integer ‘k’, write an algorithm to reverse the linked list in groups of size ‘k’. Example: Approach: Earlier we have seen how to reverse a linked list, solution...
Generate Maximum revenue by selling K tickets from N windows
Objective: Given ‘N’ windows where each window contains certain number of tickets at each window. Price of a ticket is equal to number of tickets remaining at that window. Write an algorithm to sell...
Convert binary tree to its Sum tree
Objective: Given a binary tree, write an algorithm to convert it into its Sum tree. What is Sum tree: Sum tree of a binary tree, is a tree where each node in the converted...
Dynamic Programming – Maximum Product Cutting Problem.
Objective: Given a rope of length n meters, write an algorithm to cut the rope in such a way that product of different lengths of rope is maximum. At least one cut has to...