Expressive Words

Sometimes people repeat letters to represent extra feeling, such as “hello” -> “heeellooo”, “hi” -> “hiiii”. In these strings like “heeellooo”, we have groups of adjacent letters that are all the same: “h”, “eee”, “ll”, “ooo”. For some given string S, a query word is stretchy if it can be made to be equal to S by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is 3 or more.

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

Validate Stack Sequence

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack. Example 1 Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true Explanation: We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 Example 2 Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output: false Explanation: 1 cannot be popped before 2.

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

Delete Nodes and Return Forest

Given the root of a binary tree, each node in the tree has a distinct value. After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees). Return the roots of the trees in the remaining forest. You may return the result in any order. Example 1 Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]] Constraints 1 The number of nodes in the given tree is at most 1000.

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

Insert Delete Getrandom O1

Design a data structure that supports all following operations in average O(1) time. insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned. Example // Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set.

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

Insert Delete Getrandom O1 Duplicates Allowed

Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed. insert(val): Inserts an item val to the collection. remove(val): Removes an item val from the collection if present. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains. Example // Init an empty collection.

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

Moving Average From Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Example MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3 Solution from collections import deque class MovingAverage: def __init__(self, size: int): """ Initialize your data structure here.

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

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0. Example Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?

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

Logger Rate Limiter

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds. Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false. It is possible that several messages arrive roughly at the same time. Example Logger logger = new Logger(); // logging string "foo" at timestamp 1 logger.

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

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes. Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1. It is possible that several hits arrive roughly at the same time. Example HitCounter counter = new HitCounter(); // hit at timestamp 1.

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

Cut Wood

Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get? Example 1 Input: wood = [5, 9, 7], k = 3 Output: 5 Explanation: 5 -> 5 9 -> 5 + 4 7 -> 5 + 2 Example 2 Input: wood = [5, 9, 7], k = 4 Output: 4 Explanation: 5 -> 4 + 1 9 -> 4 * 2 + 1 7 -> 4 + 3 Example 3 Input: wood = [1, 2, 3], k = 7 Output: 0 Explanation: We cannot make it.

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