# Posts published in “Desgin”

There is an ATM machine that stores banknotes of 5 denominations: 2050100200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

• For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
• However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote. Implement the ATM class: • ATM() Initializes the ATM object. • void deposit(int[] banknotesCount) Deposits new banknotes in the order $20$50$100$200, and $500.
• int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20$50$100$200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case). Example 1: Input ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"] [[], [[0,0,1,2,1]], , [[0,1,0,1,1]], , ] Output [null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]] Explanation ATM atm = new ATM(); atm.deposit([0,0,1,2,1]); // Deposits 1$100 banknote, 2 $200 banknotes, // and 1$500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote // and 1$500 banknote. The banknotes left over in the
// machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50,$200, and $500 banknote. // The banknotes in the machine are now [0,1,0,3,1]. atm.withdraw(600); // Returns [-1]. The machine will try to use a$500 banknote
// and then be unable to complete the remaining $100, // so the withdraw request will be rejected. // Since the request is rejected, the number of banknotes // in the machine is not modified. atm.withdraw(550); // Returns [0,1,0,0,1]. The machine uses 1$50 banknote
// and 1 \$500 banknote.

Constraints:

• banknotesCount.length == 5
• 0 <= banknotesCount[i] <= 109
• 1 <= amount <= 109
• At most 5000 calls in total will be made to withdraw and deposit.
• At least one call will be made to each function withdraw and deposit.

## Solution:

Follow the rules. Note: total count can be very large, use long instead.

Time complexity: O(1)
Space complexity: O(1)

## C++

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to adderase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

• bool search(int target) : Return whether the target exists in the Skiplist or not.
• void add(int num): Insert a value into the SkipList.
• bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Constraints:

• 0 <= num, target <= 20000
• At most 50000 calls will be made to searchadd, and erase.

## Python3

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
Output:
Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"


Constraints:

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage and url consist of  ‘.’ or lower case English letters.
• At most 5000 calls will be made to visitback, and forward.

## Solution: Vector

Time complexity:
visit: Amortized O(1)
back: O(1)
forward: O(1)

## C++

Python的官方实现是C语言，所以叫cpython。这也就意味着只要Python还在，C就会不消失。其他实现还有jython(Java), IronPython (.Net), PyPy (Python)。

ob_refcnt引用计数 8个字节，ob_type类型信息 8个字节（指针），ob_size变长部分元素的个数，8个字节。ob_digit变长的数据部分，字节数为4*abs(ob_size)，ob_size可以为0，所以最少8+8+8=24字节，每次增量都是4 (unsigned int) 的倍数。这和我们之前观察到的实验结果吻合。

32位就要比64位小很多了，最少12个字节，增量为2个字节。

# Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
• If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],,,,,,,[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].


Note:

• Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
• It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
• The total number of FreqStack.push calls will not exceed 10000 in a single test case.
• The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

# Solution 1: Buckets

We have n  stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x)  # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

# Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)