The Stock Span Problem

Suppose, for a stock, we have a series of n daily price quotes, the span of the stock's price on a given day is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

Let, Price (i) = price of the stock on day "i".

Then, Span (i) = max {k : k >= 0 and Price (j) <= Price (i) for j = i - k, .., i}

Thus, if Price (i-1) > Price (i), then Span (i) = 0.

Reference: http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#The_Stock_Span_Problem

Time Complexity: O(n)
Space Complexity: O(n) for stack.

Reversing the stack contents

Algorithm:

1. Pop all the elements of stack till it becomes empty.
2. After each recursive call, push the popped element at the bottom of stack.

Time Complexity: O(n^2)
Space Complexity: O(n): For recursion stack.

Counting the number of set bits in an integer

Reference: http://graphics.stanford.edu/~seander/bithacks.html




Time Complexity: O(log n)

The Great Tree List Recursion Problem

Reference: http://cslibrary.stanford.edu/109/TreeListRecursion.html

Tree structure allows extensive use of recursion for performing various operations. This property of trees is exploited for converting a given BST into a circular doubly linked list.

Algorithm:

1. Convert left subtree of the tree into a circular doubly linked list.
2. Convert right subtree of the tree into a circular doubly linked list.
3. Append root to the list of left subtree.
4. Append the list of right subtree to the root.

Checking if a Linked List is a Palindrome

Algorithm:

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the second half again and attaching it back to the first half.

Time complexity: O(n)
Space complexity: O(1)

66. Cross-country (CRSCNTRY)

Problem statement: http://www.spoj.com/problems/CRSCNTRY/

Algorithm: Dynamic Programming - Longest Common Subsequence problem.

Approach: Basically, this an LCS problem. We need to calculate the lengths of longest common subsequence of the route of Agnes and each of the routes of Tom and print the maximum among these lengths. Easy!

Time Complexity: O(d * a * t), d = no. of datasets, a = length of route of Agnes, t = length of route of Tom