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: ​
cbacdcbc. answer is acdb not adcb.

Count Triangle Segments/Triplets

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).