SWE Interview preparation

https://leetcode.com/problems/all-oone-data-structure/ Implement a data structure supporting the following operations: Inc(Key) - Inserts a new key  with value 1. Or increments an existing key by 1. Key is guaranteed to be a  non-empty  string. Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a  non-empty  string. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string  "" . GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string  "" . Challenge: Perform all these in O(1) time complexity. --- Related problems 146-lru-cache ---

https://leetcode.com/problems/max-stack/ https://github.com/openset/leetcode/tree/master/problems/max-stack https://www.lintcode.com/problem/max-stack/description Design a max stack that supports push, pop, top, peekMax and popMax. push(x) -- Push element x onto stack. pop() -- Remove the element on top of the stack and return it. top() -- Get the element on the top. peekMax() -- Retrieve the maximum element in the stack. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one. Example 1: MaxStack stack = new MaxStack(); stack.push(5); stack.push(1); stack.push(5); stack.top(); -> 5 stack.popMax(); -> 5 stack.top(); -> 1 stack.peekMax(); -> 5 stack.pop(); -> 1 stack.top(); -> 5 Note: -1e7 <= x <= 1e7 Number of operations won't exceed 10000. The last four operations won't be called when stack is empty. --- Related problems 155-min-stack ---

https://leetcode.com/problems/number-of-recent-calls/ Write a class  RecentCounter  to count recent requests. It has only one method:  ping(int t) , where t represents some time in milliseconds. Return the number of  ping s that have been made from 3000 milliseconds ago until now. Any ping with time in  [t - 3000, t]  will count, including the current ping. It is guaranteed that every call to  ping  uses a strictly larger value of  t  than before.   Example 1: Input: inputs = ["RecentCounter","ping","ping","ping","ping"] , inputs = [[],[1],[100],[3001],[3002]] Output: [null,1,2,3,3]   Note: Each test case will have at most  10000  calls to  ping . Each test case will call  ping  with strictly increasing values of  t . Each call to ping will have  1 <= t <= 10^9 .

https://leetcode.com/problems/time-based-key-value-store/ Create a timebased key-value store class  TimeMap , that supports two operations. 1.  set(string key, string value, int timestamp) Stores the  key  and  value , along with the given  timestamp . 2.  get(string key, int timestamp) Returns a value such that  set(key, value, timestamp_prev)  was called previously, with  timestamp_prev <= timestamp . If there are multiple such values, it returns the one with the largest  timestamp_prev . If there are no values, it returns the empty string ( "" ).   Example 1: Input: inputs = ["TimeMap","set","get","get","set","get","get"] , inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]] Output: [null,null,"bar","bar",null,"bar2","bar2"] Explanation:   TimeMa...

https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/ https://github.com/openset/leetcode/tree/master/problems/serialize-and-deserialize-n-ary-tree https://www.lintcode.com/problem/serialize-and-deserialize-n-ary-tree/description 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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure. For example, you may serialize the following  3-ary  tree     as  [1 [3[5 6] 2 4]] . You do n...

https://leetcode.com/problems/serialize-and-deserialize-bst/ 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 search tree . There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Note:  Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless. --- Related problems 297-serialize-and-deserialize-binary ---

https://leetcode.com/problems/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. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRand...

https://leetcode.com/problems/data-stream-as-disjoint-intervals/ Given a data stream input of non-negative integers a 1 , a 2 , ..., a n , ..., summarize the numbers seen so far as a list of disjoint intervals. For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be: [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]   Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size? --- ---

https://leetcode.com/problems/design-circular-queue/ Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values. Your implementation should support following operations: MyCircularQueue(k) : Constructor, set the size of the queue to be k. Front : Get the front item from the queue. If the queue is empty, return -1. Rear : Get the last item from the queue. If the queue is empty, return -1. enQueue(value) : Insert an element into the circular queue. Re...

https://leetcode.com/problems/nested-list-weight-sum-ii/ https://www.lintcode.com/problem/nested-list-weight-sum-ii/description Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Different from the  previous question  where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight. Example 1: Input: [[1,1],2,[1,1]] Output: 8 Explanation: F our 1's at depth 1, one 2 at depth 2. Example 2: Input: [1,[4,[6]]] Output: 17 Explanation: O ne 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17. --- Related problems 339-nested-list-weight-sum 341-flatten-nested-list-iterator ---

https://leetcode.com/problems/design-tic-tac-toe/ https://github.com/openset/leetcode/tree/master/problems/design-tic-tac-toe Design a Tic-tac-toe game that is played between two players on a  n  x  n  grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves is allowed. A player who succeeds in placing  n  of their marks in a horizontal, vertical, or diagonal row wins the game. Example: Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| toe.move(1, 1, 2); -> Retu...

https://leetcode.com/problems/exam-room/ In an exam room, there are  N  seats in a single row, numbered  0, 1, 2, ..., N-1 . When a student enters the room, they must sit in the seat that maximizes the distance to the closest person.  If there are multiple such seats, they sit in the seat with the lowest number.  (Also, if no one is in the room, then the student sits at seat number 0.) Return a class  ExamRoom(int N)  that exposes two functions:  ExamRoom.seat()  returning an  int  representing what seat the student sat in, and  ExamRoom.leave(int p)  representing that the student in seat number  p  now leaves the room.  It is guaranteed that any calls to  ExamRoom.leave(p)  have a student sitting in seat  p .   Example 1: Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"] , [[10],[],[],[],[],[4],[]] Output: [null,0,9,4,2,null,5] Explanation : ExamRoom(10) -> null seat() ...

https://leetcode.com/problems/build-an-array-with-stack-operations/ Given an array  target  and an integer  n . In each iteration, you will read a number from   list = {1,2,3..., n} . Build the  target  array using the following operations: Push : Read a new element from the beginning  list , and push it in the array. Pop : delete the last element of the array. If the target array is already built, stop reading more elements. You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to  n  inclusive. Return the operations to build the target array. You are guaranteed that the answer is unique.   Example 1: Input: target = [1,3], n = 3 Output: ["Push","Push","Pop","Push"] Explanation: Read number 1 and automatically push in the array -> [1] Read number 2 and automatically push in the array then Pop it -> [1] Read number 3 and automatically push in the array -...

https://leetcode.com/problems/implement-magic-dictionary/ Implement a magic directory with  buildDict , and  search  methods. For the method  buildDict , you'll be given a list of non-repetitive words to build a dictionary. For the method  search , you'll be given a word, and judge whether if you modify  exactly  one character into  another  character in this word, the modified word is in the dictionary you just built. Example 1: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Note: You may assume that all the inputs are consist of lowercase letters  a-z . For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest. Please remember to  RESET  your class variables declared in class MagicDictionary,...