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,

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.

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,

Paint House I
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green,

Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2],

Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

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

Analysis

We can sort the intervals using the start time. Then we check whether there is conflict. For instance. for this two pairs, [0, 30],[5, 10] As 5 is smaller than 30, the person cannot attend both.

When we do the check, we should record the latest end time before the current interval. For current interval,

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,

LinkedIn(39)

1 Two Sum 23.0% Easy
21 Merge Two Sorted Lists 35.4% Easy
23 Merge k Sorted Lists 23.3% Hard
33 Search in Rotated Sorted Array 30.2% Hard
34 Search for a Range 29.1% Medium
46 Permutations 35.7% Medium
47 Permutations II 28.0% Medium
50 Pow(x, n) 27.9% Medium
53 Maximum Subarray 36.6% Medium
56 Merge Intervals 25.3% Hard
57 Insert Interval 23.8% Hard
65 Valid Number 12.1% Hard
68 Text Justification 16.1% Hard
76 Minimum Window Substring 21.2% Hard
101 Symmetric Tree 33.9% Easy
102 Binary Tree Level Order Traversal 32.7% Easy
103 Binary Tree Zigzag Level Order Traversal 28.6% Medium
104 Maximum Depth of Binary Tree 47.8% Easy
127 Word Ladder 19.6% Medium
149 Max Points on a Line 14.2% Hard
150 Evaluate Reverse Polish Notation 23.5% Medium
152 Maximum Product Subarray 22.1% Medium
156 Binary Tree Upside Down 38.3% Medium
170 Two Sum III -

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

1. Try two pointers.