Design Circular Deque

Design your implementation of the circular double-ended queue (deque). Your implementation should support following operations: MyCircularDeque(k): Constructor, set the size of the deque to be k. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.

by lek tin in "algorithm" access_time 3-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

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

Shortest Subarray With Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is no non-empty subarray with sum at least K, return -1. Example 1 Input: A = [1], K = 1 Output: 1 Example 2 Input: A = [1,2], K = 4 Output: -1 Example 3 Input: A = [2,-1,2], K = 3 Output: 3 Note 1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9 Solution (sliding window using pointers) This version exceeds time limit Time: O(N)

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

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 Note You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

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