Author: SJ

Dynamic Programming – Highway Billboard Problem

Objective:  Suppose you’re managing construction of billboards on the Rocky & Bullwinkle Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by...

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

Convert Binary Tree into Threaded Binary Tree

Objective: Given a binary tree write an algorithm to convert it into threaded binary tree. Note: Tree node has extra Boolean field to be used. In earlier article “Introduction to Threaded Binary Tree” we...

Double Threaded Binary Tree Complete Implementation

In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see...

Single Threaded Binary Tree Complete Implementation

In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see...

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

Implement Stack Using Linked List

Objective: Write an algorithm to implement Stack using Linked List. If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the...

Doubly Linked List Complete Implementation

In this article we will see what is doubly linked list, how it is different from other linked list and how to implement it. Earlier we have seen what is Singly Linked List and...

Circular Linked List Complete Implementation

Earlier we have seen what is Singly Linked List and How to implement it. In a way you say that it’s an extension of singly linked list. I would suggest that if you do...

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

Shortest Range in K-sorted Lists

Objective: You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. This is very nice and tricky solution, This problem was asked...

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