## Alpha

Binary Tree Right Side View
*Flatten Nested List Iterator
*The Skyline Problem
Nested List Weight Sum II
Reverse Nodes in k-Group

UTF-8 Validation
*Basic Calculator
Longest Valid Parentheses
Validate Binary Search Tree

## Beta

### EQ-1

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
`Input: [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]`

##### Solution 1: Recursive, combine right and left:

5 lines, 56 ms
Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.

##### Solution 1: Recursive, combine right and left:

5 lines, 56 ms
Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.

##### Solution 3: Iterative, level-by-level:

7 lines, 48 ms
Traverse the tree level by level and add the last value of each level to the view. This is O(n).

https://leetcode.com/problems/binary-tree-right-side-view/discuss/56064/5-9-Lines-Python-48%2B-ms

### EQ-2 *

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.

### EQ-3 *

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] ]` .

### EQ-4

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

### EQ-5

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: `1->2->3->4->5`
For `k = 2`, should return: `2->1->4->3->5`
For `k = 3`, should return: `3->2->1->4->5`

### EQ-6

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

• For 1-byte character, the first bit is a 0, followed by its unicode code.
• For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

### EQ-7 *

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.

### EQ-8

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

### EQ-9

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

### EQ-10

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Feb 10, 2020
La Jolla, CA

## Omega

https://leetcode.com/