Flatten Nested List Iterator

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. Example 1 Input: [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,1,2,1,1]`. Example 2 Input: [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,4,6]`.

by lek tin in "algorithm" access_time 4-min read

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

by lek tin in "algorithm" access_time 4-min read

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note The input string may contain letters other than the parentheses ( and ). *### Example 1 Input: "()())()" Output: ["()()()", "(())()"] *### Example 2 Input: "(a)())()" Output: ["(a)()()", "(a())()"] *### Example 3 Input: ")(" Output: [""] *### Solution # Credit: # Credit: https://leetcode.com/problems/remove-invalid-parentheses/discuss/186597/Very-easy-to-understand-Python-DFS class Solution(object): def removeInvalidParentheses(self, s): """ :type s: str :rtype: List[str] """ res = [] self.

by lek tin in "algorithm" access_time 2-min read

Task Scheduler

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.

by lek tin in "algorithm" access_time 1-min read

Encode and Decode Tinyurl

Note This is a companion problem to the System Design problem: Design TinyURL. TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

by lek tin in "algorithm" access_time 2-min read

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. Example 1 Input: [[0, 30],[5, 10],[15, 20]] Output: 2 Example 2 Input: [[7,10],[2,4]] Output: 1 Solution # Definition for an interval. # class Interval: # def __init__(self, s=0, e=0): # self.start = s # self.end = e # |____| |_______| # |_______| |____| # Number of meeting rooms: 2 class Solution(object): def minMeetingRooms(self, intervals): """ :type intervals: List[Interval] :rtype: int """ starts, ends = [], [] length = len(intervals) for i in range(length): starts.

by lek tin in "algorithm" access_time 1-min read

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.

by lek tin in "algorithm" access_time 4-min read

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1. Example 1 Input: 123 Output: "One Hundred Twenty Three" Example 2 Input: 12345 Output: "Twelve Thousand Three Hundred Forty Five" Example 3 Input: 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Example 4 Input: 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" Solution class Solution: def __init__(self): self.

by lek tin in "algorithm" access_time 2-min read

PowX N

Example 1 Input: 2.00000, 10 Output: 1024.00000 Example 2 Input: 2.10000, 3 Output: 9.26100 Example 3 Input: 2.00000, -2 Output: 0.25000 Explanation 2-2 = 1/22 = 1/4 = 0.25 Note -100.0 < x < 100.0 n is a 32-bit signed integer, within the range [−231, 231 − 1] Solution # Time: o(logN) # Space: `O(n)` class Solution: def myPow(self, x, n): """ :type x: float :type n: int :rtype: float """ if n > 0: return self.

by lek tin in "algorithm" access_time 1-min read

Validate Binary Search Tree

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. Example 1 Input: 2 / \ 1 3 Output: true Example 2 5 / \ 1 4 / \ 3 6 Output: false Explanation The input is: [5,1,4,null,null,3,6].

by lek tin in "algorithm" access_time 2-min read