by 1337c0d3r
November 29, 2010 in binary tree, linked list
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.
by 1337c0d3r
November 27, 2010 in binary tree, linked list
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
by 1337c0d3r
November 25, 2010 in binary tree, divide and conquer
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
by 1337c0d3r
November 22, 2010 in binary tree
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.
by 1337c0d3r
November 18, 2010 in binary tree
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.
by 1337c0d3r
November 16, 2010 in Uncategorized
Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
by 1337c0d3r
November 14, 2010 in Uncategorized
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 →
by 1337c0d3r
November 10, 2010 in Uncategorized
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.
by 1337c0d3r
November 7, 2010 in Uncategorized
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.
by 1337c0d3r
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’.
by 1337c0d3r
November 4, 2010 in backtracking, dynamic programming
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?
by 1337c0d3r
October 27, 2010 in binary tree
Given a binary tree, print the elements in post-order iteratively without using recursion.
by 1337c0d3r
October 20, 2010 in binary tree
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.
by 1337c0d3r
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.
by 1337c0d3r
October 13, 2010 in divide and conquer
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]
by 1337c0d3r
October 8, 2010 in divide and conquer
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]
by 1337c0d3r
October 6, 2010 in divide and conquer
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]
by 1337c0d3r
October 1, 2010 in Uncategorized
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.
by 1337c0d3r
September 30, 2010 in backtracking
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 →
by 1337c0d3r
September 29, 2010 in binary tree
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’.