Algorithms | Learn for Master - Part 7
• Leetcode – Excel Sheet Column Number (Java)

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

Related to this question Excel Sheet Column Title

This is a normal number system conversion problem.  Think about how we convert a binary number to a decimal number?

1101001 = 1* 2 ^6 + 1 * 2^5 ..

We can easily have the following implementation:

• An efficient Prime number generation algorithm (Java)

Given a number n, print all primes smaller than or equal to n.

For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is not too large.

Leetcode. Count Primes: https://leetcode.com/problems/count-primes/

Here is the basic idea of this algorithm:

1. Build a table or an array with n numbers from 1 to n.
• Leetcode – Largest Rectangle in Histogram Java

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Analysis

A simple solution is to expand for each bar to its both left and right side until the bar is lower.

• Leetcode – Maximal Rectangle solution 1 (Java)

Maximum Rectangle area for a 0 1 matrix.

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Source: https://leetcode.com/problems/maximal-rectangle/

This is a hard one from Facebook.

The key to solve this problem is to first build a matrix ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure.

We have:

We can fill up the matrix ones[][] using dynamic programming. The formula is :

How to use the ones[][] matrix to calculate the maximum area?

• Leetcode – Word Ladder solution In Java

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

One shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.

Analysis

From each word, we can change its letter one by one, thus a bread first search tree is constructed. The problem becomes to find the shortest path from the start word to the end word.

• Leetcode – LRU cache solution in Java

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis

The popular method to implement an LRU cache is to use a bounded Queue.

The key to for implementing an LRU is to put any recently used data at the head of the queue.

• Leetcode – Paint House II solution (Java)

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different.

You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x k cost matrix.

For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2,

• Leetcode – Meeting Rooms II (Java)

Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

This is a follow up question for the Meeting Rooms one.

Analysis

This problem can be solved using the greedy method. We sort the intervals using the start time, then we try to merge the next one that has the smallest start time ts from the remaining intervals with the previous interval that has smallest end time te.

• LeetCode – Excel Sheet Column Title solution in Java

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:

1 -> A
2 -> B
3 -> C

26 -> Z
27 -> AA
28 -> AB

To convert a number from a system with base m to Decimal number system, we can use the following formula:

xyz = x * m^2 + y * m^1 + z * m^0.

For instance, the binary number 1010 = 1 * 2^3 + 1 * 2^1 = 10.

Now to convert a number N in decimal system to a system with base m,