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 […]

# Author Archives: 1337c0d3r

# Studious Student Problem Analysis

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 […]

# Peg Game Problem Analysis

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 […]

# Double Square Problem Analysis

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!

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 […]

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

Imagine you have a special keyboard with the following keys: A Ctrl+A Ctrl+C 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 […]

# Convert Binary Search Tree (BST) to Sorted Doubly-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.

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

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)

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

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)

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

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

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

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

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

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

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 […]

# Binary Tree Post-Order Traversal Iterative Solution

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

# Print Edge Nodes (Boundary) of a 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.

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

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