LeetCode[218]: The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Hackerrank: Count Luck

Problem:

Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they’ve managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.

Consider the forest as an grid. Each cell is either empty (represented by .) or blocked by a tree (represented by ). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWNthrough empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character , and the cell with the portkey is marked with a . The upper-left corner is indexed as .

In example above, Ron and Hermione are located at index and the portkey is at . Each cell is indexed according to Matrix Conventions

Hermione decides it’s time to find the portkey and leave. Each time they are able to move in more than one direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly times. Can you determine if Ron’s guesses are correct?

Note: It is guaranteed that there is only one path from the starting location to the portkey.

Input Format

The first line contains an integer, , the number of test cases.

Each test case is described as follows:
The first line contains space-separated integers, and , respectively, denoting the forest matrix.
The subsequent lines each contain a string of length describing a row of the forest matrix.
The last line contains an integer, , denoting Ron’s guess as to how many times Hermione will wave her wand.

Constraints

• There will be exactly one and one in the forest.
• Exactly one path exists between and .

Output Format

On a new line for each test case, print if Ron impresses Hermione by guessing correctly; otherwise, print .

Sample Input

Sample Output

Explanation

For each test case , denotes the number of times Hermione waves her wand.

Case 0: Hermione waves her wand at , giving us . Because , we print on a new line.
Case 1: Hermione waves her wand at , , and , giving us . Because , we print on a new line.
Case 2: Hermione waves her wand at , , and , giving us . Because and , and we print on a new line.

Code:

Hackerrank: Bricks Game

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Input Format

First line will contain an integer T i.e. number of test cases. There will be two lines corresponding to each test case: first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

Constraints

1 ≤ T ≤ 5
1 ≤ N ≤ 105
0 ≤ each number on brick ≤ 109

Output Format

For each test case, print a single line containing your maximum score.

Sample Input

Sample Output

Explanation

In first test case, you will pick 999,1,1. If you play in any other way, you will not get a score of 1001.
In second case, best option will be to pick up the first brick (with 0 score) at first. Then your friend will choose the next three blocks, and you will get the last brick.

Code:

LeetCode[412]: Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:
n = 15,

Return:
[
“1”,
“2”,
“Fizz”,
“4”,
“Buzz”,
“Fizz”,
“7”,
“8”,
“Fizz”,
“Buzz”,
“11”,
“Fizz”,
“13”,
“14”,
“FizzBuzz”
]

Count Inversions in an array

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

LeetCode[401]: Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:
Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

LeetCode[421]: Maximum XOR of Two Numbers in an Array

Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].

Could you do this in O(n) runtime?

Input: [3, 10, 5, 25, 2, 8] Output: 28

“第一位为0的subset中，第二位为0的subset”都不为空，或者“” “”则result第二位为1

LeetCode[352]: Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:
[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

LeetCode[416]: Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Find subarray with given sum

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

Follow up 1: What if the array contains negative numbers?

Follow up 2: If there is no subarray found, return the subarray whose sum is the closest to the target sum.

Follow up 3: What if the subarray do not need to be continuous?