## 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?

## Binary Tree Post-Order Traversal Iterative Solution

October 27, 2010

Given a binary tree, print the elements in post-order iteratively without using recursion.

## Print Edge Nodes (Boundary) of a Binary Tree

October 20, 2010

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

## Implement strstr() to Find a Substring in a String

October 14, 2010 in string

Write C code to implement the strstr (Search for a substring) function. Do not use any system library such as strlen.

## Searching a 2D Sorted Matrix Part III

October 13, 2010

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

## Searching a 2D Sorted Matrix Part II

October 8, 2010

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

## Searching a 2D Sorted Matrix Part I

October 6, 2010

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

## Excel Sheet Row Numbers

October 1, 2010

Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1,2,3,….}. Write code to convert an element of S2 to the corresponding element of S1.

## Print All Combinations of a Number as a Sum of Candidate Numbers

September 30, 2010

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.
Read the rest of this entry →

## Serialization/Deserialization of a Binary Tree

September 29, 2010

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.