Stacks/Queues Flashcards
- Valid Parentheses
Solved
Easy
Topics
Companies
Hint
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
https://leetcode.com/problems/valid-parentheses/description/
Map of close to open or open to close both work
class Solution:
def isValid(self, s: str) -> bool:
stack = []
close = {‘}’: ‘{‘, ‘)’: ‘(‘, ‘]’: ‘[’}
for p in s:
if p in close and stack:
if close[p] != stack.pop():
return False
elif p in close:
return False
else:
stack.append(p)
return not stack and True
class Solution(object):
def isValid(self, s):
“””
:type s: str
:rtype: bool
“””
opens = {‘{‘: ‘}’, ‘[’: ‘]’, ‘(‘:’)’}
stack = []
for c in s:
if c in opens:
stack.append(opens[c])
elif stack:
if c != stack.pop():
return False
else:
return False
return len(stack) == 0
- Min Stack
Solved
Medium
Topics
Companies
Hint
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.
Key is to only append to min stack if value on min stack’s head is = or > the incoming value. In other words min stack will be a monotonically decreasing stack from 0 to n
class MinStack:
def \_\_init\_\_(self):
self.stack = []
self.minstack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.minstack:
self.minstack.append(val)
elif val <= self.minstack[-1]:
self.minstack.append(val)
def pop(self) -> None:
popval = self.stack.pop()
if self.minstack and popval == self.minstack[-1]:
self.minstack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minstack[-1]
Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
- Evaluate Reverse Polish Notation
Solved
Medium
Topics
Companies
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,”13”,”5”,”/”,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Constraints:
1 <= tokens.length <= 104
tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
Only add numbers to stack, when math operation comes up, pop last 2 , do the operation and push the result back on the stack, return the last element of stack
class Solution(object):
def evalRPN(self, tokens):
“””
:type tokens: List[str]
:rtype: int
“””
symbols = {
‘+’: lambda a,b: a+b,
‘-‘: lambda a,b: a-b,
‘’: lambda a,b: ab,
‘/’: lambda a,b: a/(b * 1.0)
}
stack = []
for token in tokens:
if token not in symbols:
stack.append(token)
else:
b = int(stack.pop())
a = int(stack.pop())
stack.append(symbolstoken)
return int(stack[-1])
- Daily Temperatures
Solved
Medium
Topics
Companies
Hint
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
https://leetcode.com/problems/daily-temperatures/description/
Monotonic Decreasing Stack
# Stack will always have a descending order
class Solution(object):
def dailyTemperatures(self, temperatures):
“””
:type temperatures: List[int]
:rtype: List[int]
“””
answers = [0] * len(temperatures)
stack = []
for idx, temp in enumerate(temperatures):
if not stack:
stack.append((idx, temp))
continue
while stack and stack[-1][1] < temp:
i,t = stack.pop()
answers[i] = idx - i
stack.append((idx, temp))
return answers
- Car Fleet
Solved
Medium
Topics
Companies
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Example 1:
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Note that no other cars meet these fleets before the destination, so the answer is 3.
Example 2:
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.
Example 3:
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
https://leetcode.com/problems/car-fleet/
monotonic increasing stack keep an eye on speed calculations
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
eta = []
for pos, spd in zip(position, speed):
remaining = target - pos
time = remaining/(1.0 * spd)
eta.append((pos, time))
eta = sorted(eta, reverse=True)
fleet = 0
stack = []
fleetfound = False
for _, time in eta:
if not stack:
stack.append(time)
continue
if stack and stack[-1] < time:
stack.append(time)
return len(stack)
- Largest Rectangle in Histogram
Solved
Hard
Topics
Companies: Amazon
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
https://leetcode.com/problems/largest-rectangle-in-histogram/descriptio
monotonic increasing stacks
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
maxarea = 0
for idx, height in enumerate(heights):
position = idx
while stack and stack[-1][1] > height:
p, h = stack.pop()
wide = idx - p
high = h
maxarea = max(maxarea, wide * high)
position = p
stack.append((position, height))
while stack:
p, height = stack.pop()
wide = len(heights) - p
maxarea = max(maxarea, wide * height)
return maxarea
- Daily Temperatures
Solved
Medium
Topics
Companies Facebook, Amazon
Hint
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
https://leetcode.com/problems/daily-temperatures/description/
Monotonic decreasing stacks
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
ans = [0] * len(temperatures)
for idx, temp in enumerate(temperatures):
while stack and stack[-1][1] < temp:
i, _ = stack.pop()
ans[i] = idx - i
stack.append((idx, temp))
return ans
- Minimum Remove to Make Valid Parentheses
Solved
Medium
Topics
Companies
Hint
Given a string s of ‘(‘ , ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.
Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.
Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”
Example 3:
Input: s = “))((“
Output: “”
Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
Maintain stack of indices of open parentheses, (like to check if paraentheses is balanced)
if you encounter a closed , with no open, add it’s index to ignore else pop the open stack.
Once done, combine the remaining indices of unclosed parentheses and the invalid closed and re-create the string without those indices.
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
a = []
to_ignore = set()
i = 0
while i < len(s):
if s[i] == '(':
a.append(i)
elif s[i] == ')':
if a:
a.pop()
else:
to_ignore.add(i)
i+=1
for idx in a:
to_ignore.add(idx)
ret = ""
for i, c in enumerate(s):
if i in to_ignore:
continue
ret += c
return ret
10 Mins, never seen.
O(n), O(n)
- Buildings With an Ocean View
Medium
Companies: Facebook 2024
There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.
The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.
Example 2:
Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.
Example 3:
Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.
Constraints:
1 <= heights.length <= 105 1 <= heights[i] <= 109
https://leetcode.com/problems/buildings-with-an-ocean-view/description/
Monotonic Decreasing Stack, values are in descending order.
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
out = []
for i, h in enumerate(heights):
while out and heights[out[-1]] <= h:
out.pop()
out.append(i)
return out
More effecient solution, does not require popping values out of stack, basically only insert if its a valid value. Start with iterating over reverse of the list and only applend value to the left if last value is less than the incoming value.
Basically only adding the index if the building we are going to add is taller than the one we added before.
Clever solution, might not come up with it in interview but good to know for furture.
This solution is technically O(1) space as output array is not counted in space counsumed and our queue is the output and we only ever add values if they are going to be part of solution.
from collections import deque
class Solution(object):
def findBuildings(self, heights):
"""
:type heights: List[int]
:rtype: List[int]
"""
out = deque()
last_height = 0
for i in range(len(heights)-1, -1, -1):
if heights[i] > last_height:
out.appendleft(i)
last_height = heights[i]
return out
Optimal: 5 Minutes Max 10 minutes assigned.
O(n), Space: O(n) O(1) if output array not counted in second solution.
- Moving Average from Data Stream
Easy
Companies: Multiple, very common.
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:
MovingAverage(int size) Initializes the object with the size of the window size. double next(int val) Returns the moving average of the last size values of the stream.
Example 1:
Input
[“MovingAverage”, “next”, “next”, “next”, “next”]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]
Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3
Constraints:
1 <= size <= 1000 -105 <= val <= 105 At most 104 calls will be made to next.
Max 10 minutes. 5-7 Preferable.
https://leetcode.com/problems/moving-average-from-data-stream/submissions/1311885979/
from collections import deque
class MovingAverage(object):
def \_\_init\_\_(self, size):
"""
:type size: int
"""
self.size = size
self.nums = deque()
self.sum = 0
def next(self, val):
"""
:type val: int
:rtype: float
"""
self.nums.append(val)
self.sum += val
if len(self.nums) > self.size:
self.sum -= self.nums.popleft()
return self.sum/(1.0*len(self.nums))
Less code solution but the operation will be O(size) due to the sum operation.
import collections
class MovingAverage(object):
def \_\_init\_\_(self, size):
"""
Initialize your data structure here.
:type size: int
"""
self.queue = collections.deque(maxlen=size)
def next(self, val):
"""
:type val: int
:rtype: float
"""
queue = self.queue
queue.append(val)
return float(sum(queue))/len(queue)
10 mins max.
O(1) time, O(size) space.
- Simplify Path
Medium
Companies: Facebook 2024
Given an absolute path for a Unix-style file system, which begins with a slash ‘/’, transform this path into its simplified canonical path.
In Unix-style file system context, a single period ‘.’ signifies the current directory, a double period “..” denotes moving up one directory level, and multiple slashes such as “//” are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like “…”) as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
It must start with a single slash '/'. Directories within the path should be separated by only one slash '/'. It should not end with a slash '/', unless it's the root directory. It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
Example 1:
Input: path = “/home/”
Output: “/home”
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation:
Multiple consecutive slashes are replaced by a single one.
Example 3:
Input: path = “/home/user/Documents/../Pictures”
Output: “/home/user/Pictures”
Explanation:
A double period “..” refers to the directory up a level.
Example 4:
Input: path = “/../”
Output: “/”
Explanation:
Going one level up from the root directory is not possible.
Example 5:
Input: path = “/…/a/../b/c/../d/./”
Output: “/…/b/d”
Explanation:
“…” is a valid name for a directory in this problem.
Constraints:
1 <= path.length <= 3000 path consists of English letters, digits, period '.', slash '/' or '_'. path is a valid absolute Unix path.
10 Minutes, 15 Max.
https://leetcode.com/problems/simplify-path/description/
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
# replace // with /
stack = []
clear_split = path.split("/")
for p in clear_split:
if stack and p == '..':
stack.pop()
elif p and p not in {'.', '..'}:
stack.append(p)
return "/" + "/".join(stack)
O(n), O(n)
636 Exclusive Time of Functions
Solved
Medium
Topics
Companies
On a single-threaded CPU, we execute a program containing n functions. Each function has a unique ID between 0 and n-1.
Function calls are stored in a call stack: when a function call starts, its ID is pushed onto the stack, and when a function call ends, its ID is popped off the stack. The function whose ID is at the top of the stack is the current function being executed. Each time a function starts or ends, we write a log with the ID, whether it started or ended, and the timestamp.
You are given a list logs, where logs[i] represents the ith log message formatted as a string “{function_id}:{“start” | “end”}:{timestamp}”. For example, “0:start:3” means a function call with function ID 0 started at the beginning of timestamp 3, and “1:end:2” means a function call with function ID 1 ended at the end of timestamp 2. Note that a function can be called multiple times, possibly recursively.
A function’s exclusive time is the sum of execution times for all function calls in the program. For example, if a function is called twice, one call executing for 2 time units and another call executing for 1 time unit, the exclusive time is 2 + 1 = 3.
Return the exclusive time of each function in an array, where the value at the ith index represents the exclusive time for the function with ID i.
O(n), O(n) Read examples at Leetcode link
https://leetcode.com/problems/exclusive-time-of-functions/description/
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
ret = [0] * n
stack = []
for log in logs:
fid, state, ts = log.split(":")
fid = int(fid)
ts = int(ts)
if stack and state == "end":
sfid, start = stack.pop()
time = ts - start + 1
ret[sfid] += time
# remove this time from the previou's time span
if stack:
ret[stack[-1][0]] -= time
else:
stack.append([fid, ts])
return ret- Design Hit Counter
Medium
Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).
Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.
Implement the HitCounter class:
HitCounter() Initializes the object of the hit counter system.
void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).
Example 1:
Input
[“HitCounter”, “hit”, “hit”, “hit”, “getHits”, “hit”, “getHits”, “getHits”]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.
Constraints:
1 <= timestamp <= 2 * 109
All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
At most 300 calls will be made to hit and getHits.
Follow up: What if the number of hits per second could be huge? Does your design scale?
https://leetcode.com/problems/design-hit-counter/description/
from collections import deque
from collections import defaultdict
class HitCounter:
def \_\_init\_\_(self):
self.counter = deque()
def hit(self, timestamp: int) -> None:
while self.counter and timestamp - self.counter[0] >= 300:
self.counter.popleft()
self.counter.append(timestamp)
def getHits(self, timestamp: int) -> int:
while self.counter and timestamp - self.counter[0] >= 300:
self.counter.popleft()
return len(self.counter)
Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)- High-Access Employees
Solved
Medium
Topics
Companies
Hint
You are given a 2D 0-indexed array of strings, access_times, with size n. For each i where 0 <= i <= n - 1, access_times[i][0] represents the name of an employee, and access_times[i][1] represents the access time of that employee. All entries in access_times are within the same day.
The access time is represented as four digits using a 24-hour time format, for example, “0800” or “2250”.
An employee is said to be high-access if he has accessed the system three or more times within a one-hour period.
Times with exactly one hour of difference are not considered part of the same one-hour period. For example, “0815” and “0915” are not part of the same one-hour period.
Access times at the start and end of the day are not counted within the same one-hour period. For example, “0005” and “2350” are not part of the same one-hour period.
Return a list that contains the names of high-access employees with any order you want.
Example 1:
Input: access_times = [[“a”,”0549”],[“b”,”0457”],[“a”,”0532”],[“a”,”0621”],[“b”,”0540”]]
Output: [“a”]
Explanation: “a” has three access times in the one-hour period of [05:32, 06:31] which are 05:32, 05:49, and 06:21.
But “b” does not have more than two access times at all.
So the answer is [“a”].
Example 2:
Input: access_times = [[“d”,”0002”],[“c”,”0808”],[“c”,”0829”],[“e”,”0215”],[“d”,”1508”],[“d”,”1444”],[“d”,”1410”],[“c”,”0809”]]
Output: [“c”,”d”]
Explanation: “c” has three access times in the one-hour period of [08:08, 09:07] which are 08:08, 08:09, and 08:29.
“d” has also three access times in the one-hour period of [14:10, 15:09] which are 14:10, 14:44, and 15:08.
However, “e” has just one access time, so it can not be in the answer and the final answer is [“c”,”d”].
Example 3:
Input: access_times = [[“cd”,”1025”],[“ab”,”1025”],[“cd”,”1046”],[“cd”,”1055”],[“ab”,”1124”],[“ab”,”1120”]]
Output: [“ab”,”cd”]
Explanation: “ab” has three access times in the one-hour period of [10:25, 11:24] which are 10:25, 11:20, and 11:24.
“cd” has also three access times in the one-hour period of [10:25, 11:24] which are 10:25, 10:46, and 10:55.
So the answer is [“ab”,”cd”].
Constraints:
1 <= access_times.length <= 100
access_times[i].length == 2
1 <= access_times[i][0].length <= 10
access_times[i][0] consists only of English small letters.
access_times[i][1].length == 4
access_times[i][1] is in 24-hour time format.
access_times[i][1] consists only of ‘0’ to ‘9’.
from itertools import starmap, groupby
from collections import deque,defaultdict
class Solution:
def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
time_check = defaultdict(deque)
def std_time(mil_time):
mins = int(mil_time[2:])
hrs = int(mil_time[:2])
return mins + (hrs * 60)
entries_sorted = sorted(starmap(lambda emp, t: (emp, std_time(t)), access_times), key=lambda x:(x[0], x[1]))
hae = set()
for emp, time_mins in entries_sorted:
# We already marked this employe High Access, no need for further checks.
if emp in hae:
continue
if emp not in time_check:
time_check[emp].append(time_mins)
continue
else:
while time_check[emp] and time_mins - time_check[emp][0] >= 60:
time_check[emp].popleft()
time_check[emp].append(time_mins)
if len(time_check[emp]) >= 3:
hae.add(emp)
return list(hae)
- Stock Price Fluctuation
Solved
Medium
Topics
Companies
Hint
You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.
Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.
Design an algorithm that:
Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records.
Finds the minimum price the stock has been based on the current records.
Implement the StockPrice class:
StockPrice() Initializes the object with no price records.
void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock.
int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.
Example 1:
Input
[“StockPrice”, “update”, “update”, “current”, “maximum”, “update”, “maximum”, “update”, “minimum”]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]
Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5); // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current(); // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum(); // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3); // The previous timestamp 1 had the wrong price, so it is updated to 3.
// Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum(); // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2); // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum(); // return 2, the minimum price is 2 at timestamp 4.
Constraints:
1 <= timestamp, price <= 109
At most 105 calls will be made in total to update, current, maximum, and minimum.
current, maximum, and minimum will be called only after update has been called at least once.
https://leetcode.com/problems/stock-price-fluctuation
obj = StockPrice()
from sortedcontainers import SortedDict
class StockPrice(object):
def \_\_init\_\_(self):
self.lookup = SortedDict()
self.freq = SortedDict()
def update(self, timestamp, price):
"""
:type timestamp: int
:type price: int
:rtype: None
"""
if timestamp not in self.lookup:
self.lookup[timestamp] = price
if price not in self.freq:
self.freq[price] = 1
else:
self.freq[price] += 1
else:
if price not in self.freq:
self.freq[price] = 1
else:
self.freq[price] += 1
old_price = self.lookup[timestamp]
self.freq[old_price] -= 1
if not self.freq[old_price]:
del(self.freq[old_price])
self.lookup.update({timestamp:price})
def current(self):
"""
:rtype: int
"""
return self.lookup.peekitem(-1)[1]
def maximum(self):
"""
:rtype: int
"""
return self.freq.peekitem(-1)[0]
def minimum(self):
"""
:rtype: int
"""
return self.freq.peekitem(0)[0]
Your StockPrice object will be instantiated and called as such:
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()
Can do using heap, just save the price,timestamp in min and max heap.
When you are returning max value, pop the items in max heap, till the price associated with the timestamp in the lookup map is the same, then return that value (be sure to peek at the heap)
To track current timestamp, just update the current timestamp whenver the update time is called with the max seen so far.
eg.
~~~
while self.max_heap[0][0] != self.lookup[self.max_heap[0][1]]:
pop(maxheap)
~~~
nLog(n) for heap solution Log(n) for sortedContainer as peek is log(n)
