# Nuts in an Oasis

Jan 20, 2011 at 3:27 am in Uncategorized by 1337c0d3r

A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the town is ‘D’ kilometers away from the pile.

The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that can be transported to the town.

The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can carry at most ‘C’  [read more →]

# Studious Student Problem Analysis

Jan 10, 2011 at 5:24 pm in Uncategorized by 1337c0d3r

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.

# Peg Game Problem Analysis

at 5:23 pm in Uncategorized by 1337c0d3r

At the arcade, you can play a simple game where a ball is dropped into the top of the game, from a position of your choosing. There are a number of pegs that the ball will bounce off of as it drops through the game. Whenever the ball hits a peg, it will bounce to the left with probability 0.5 and to the right with probability 0.5. The one exception to this is when it hits a peg on the  [read more →]

# Double Square Problem Analysis

at 5:16 pm in Uncategorized by 1337c0d3r

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32 + 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares.

# Facebook Hacker Cup Online Qualification Round Begins Now!

Jan 8, 2011 at 1:31 am in Uncategorized by 1337c0d3r

Facebook decided to launch Hacker Cup, a programming contest to attract the world’s best talents to their HQ. The qualification round started on Friday 4pm (US’s PST timezone) and continues for 72 hours, so go ahead and join now.

Facebook’s Hacker Cup, equivalent to Google’s Code Jam. The cheapest way to attract the best talents from all over the world.

Just finished Facebook Hacker Cup Online Qualification Round and thought that I might share  [read more →]

# CTRL+A, CTRL+C, CTRL+V

Jan 4, 2011 at 4:40 am in Uncategorized by 1337c0d3r

Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.

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

Nov 29, 2010 at 9:17 pm in binary tree, linked list by 1337c0d3r

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)

Nov 27, 2010 at 2:17 pm in binary tree, linked list by 1337c0d3r

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)

Nov 25, 2010 at 3:06 pm in binary tree, divide and conquer by 1337c0d3r

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

Nov 22, 2010 at 2:17 pm in binary tree by 1337c0d3r

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)

Nov 18, 2010 at 2:06 am in binary tree by 1337c0d3r

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

Nov 16, 2010 at 8:04 pm in Uncategorized by 1337c0d3r

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

Nov 14, 2010 at 4:09 pm in Uncategorized by 1337c0d3r

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

# Best Time to Buy and Sell Stock

Nov 10, 2010 at 2:02 am in Uncategorized by 1337c0d3r

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

Nov 7, 2010 at 6:53 pm in Uncategorized by 1337c0d3r

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

Nov 6, 2010 at 3:02 am in string by 1337c0d3r

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

Nov 4, 2010 at 3:06 am in backtracking, dynamic programming by 1337c0d3r

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

Oct 27, 2010 at 6:48 pm in binary tree by 1337c0d3r

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

# Print Edge Nodes (Boundary) of a Binary Tree

Oct 20, 2010 at 3:20 am in binary tree by 1337c0d3r

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

Oct 14, 2010 at 4:13 am in string by 1337c0d3r

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