## Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

November 29, 2010

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

## Convert Sorted List to Balanced Binary Search Tree (BST)

November 27, 2010

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

## Convert Sorted Array to Balanced Binary Search Tree (BST)

November 25, 2010

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

## Largest Binary Search Tree (BST) in a Binary Tree

November 22, 2010

Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

## Largest Subtree Which is a Binary Search Tree (BST)

November 18, 2010

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

## Stack that Support Push, Pop, and GetMin in Constant Time

November 16, 2010

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

## Finding the Minimum Window in S which Contains All Elements from T

November 14, 2010

Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n). Read the rest of this entry →

## Best Time to Buy and Sell Stock

November 10, 2010

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

## Rejection Sampling

November 7, 2010

Given a function which generates a random integer in the range 1 to 7, write a function which generates a random integer in the range 1 to 10 uniformly.

## A String Replacement Problem

November 6, 2010 in string

Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

## Unique Paths

November 4, 2010

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?