# Nth number with same number of 1 bit’s set

There is a sequence of increasing numbers that have the same number of
binary 1’s in them. Given n, the number of 1 bits set in each number, write an algorithm
to find the n’th number in the series.

# Square Root – sqrt(x)

Solution – Binary Search

If you don’t remember Newton’s method, then this problem can be solved using Binary Search.
Note that the goal is not to find the exact square root r but to find the floor(r). So we terminate the loop when narrowing down the range to 1.

# Maze/Grid Puzzle – 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).

# LRU Cache

Least Recently Used (LRU) caching scheme is to discard the least recently used items first when the cache is full and a newly visted item needs to be added to the cache.
Design a LRU caching scheme that implement the following interface.

public interface LruPageCache {
/** Set the capacity of the cache. */
public setCapacity(int capacity);

# Convex Hull of a n-polygon – The “Graham Scan” Algorithm

Andrew’s monotone chain convex hull algorithm constructs the convex hull of a set of 2-dimensional points in O(n \log n) time.

It does so by first sorting the points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate), and then constructing upper and lower hulls of the points in O(n) time.

# Lexicographically Smallest String By Deleting Duplicate Characters

bcabc
You need delete 1 ‘b’ and 1 ‘c’, so you delete the first ‘b’ and first ‘c’, the new string will be abc which is smallest.
PS: If you try to use greedy algorithm to solve this problem, you must make sure that you could pass this case: ​