SWE Interview preparation

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/next-greater-node-in-linked-list/ We are given a linked list with  head  as the first node.  Let's number the nodes in the list:  node_1, node_2, node_3, ...  etc. Each node may have a  next larger   value : for  node_i ,  next_larger(node_i)  is the  node_j.val  such that  j > i ,  node_j.val > node_i.val , and  j  is the smallest possible choice.  If such a  j  does not exist, the next larger value is  0 . Return an array of integers  answer , where  answer[i] = next_larger(node_{i+1}) . Note that in the example  inputs  (not outputs) below, arrays such as  [2,1,5]  represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.   Example 1: Input: [2,1,5] Output: [5,5,0] Example 2: Input: [2,7,4,3,5] Output: [7,0,5,5,0] Example 3: Input: [1,7,5,1,...

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/basic-calculator-iii/ https://www.lintcode.com/problem/basic-calculator-iii/description https://github.com/openset/leetcode/tree/master/problems/basic-calculator-iii Implement a basic calculator to evaluate a simple expression string. The expression string may contain open  (  and closing parentheses  ) , the plus  +  or minus sign  - ,  non-negative  integers and empty spaces  . The expression string contains only non-negative integers,  + ,  - ,  * ,  /  operators , open  (  and closing parentheses  )  and empty spaces  . The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of  [-2147483648, 2147483647] . Some examples: "1 + 1" = 2 " 6-4 / 2 " = 4 "2*(5+5*2)/3+(6/2+8)" = 21 "(2+6* 3+5- (3*14/7+2)*5)+3"=-12   Note:   Do not  use the  eval ...

https://leetcode.com/problems/basic-calculator/ Implement a basic calculator to evaluate a simple expression string. The expression string may contain open  (  and closing parentheses  ) , the plus  +  or minus sign  - ,  non-negative  integers and empty spaces  . Example 1: Input: "1 + 1" Output: 2 Example 2: Input: " 2-1 + 2 " Output: 3 Example 3: Input: "(1+(4+5+2)-3)+(6+8)" Output: 23 Note: You may assume that the given expression is always valid. Do not  use the  eval  built-in library function. --- Related problems 394-decode-string 227-basic-calculator-ii 772-basic-calculator-iii ---

https://leetcode.com/problems/maximum-frequency-stack/ 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"] , [[],[5],[7],[5],[7],[4],[5],[],[],[],[]] 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...

https://leetcode.com/problems/simplify-path/ Given an  absolute path  for a file (Unix-style), simplify it. Or in other words, convert it to the  canonical path . In a UNIX-style file system, a period  .  refers to the current directory. Furthermore, a double period  ..  moves the directory up a level. Note that the returned canonical path must always begin with a slash  / , and there must be only a single slash  /  between two directory names. The last directory name (if it exists)  must not  end with a trailing  / . Also, the canonical path must be the  shortest  string representing the absolute path. Example 1: Input: " /home/" Output: " /home" Explanation: Note that there is no trailing slash after the last directory name. Example 2: Input: " /../" Output: " /" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go. Example...

https://leetcode.com/problems/exclusive-time-of-functions/ On a  single threaded  CPU, we execute some functions.  Each function has a unique id between  0  and  N-1 . We store logs in timestamp order that describe when a function is entered or exited. Each log is a string with this format:  "{function_id}:{"start" | "end"}:{timestamp}" .  For example,  "0:start:3"  means the function with id  0   started at the beginning  of timestamp  3 .   "1:end:2"  means the function with id  1   ended at the end  of timestamp  2 . A function's  exclusive time  is the number of units of time spent in this function.  Note that this does  not  include any recursive calls to child functions. The CPU is  single threaded  which means that only one function is being executed at a given time unit. Return the exclusive time of each function, sorted by...

https://leetcode.com/problems/reconstruct-itinerary/ Given a list of airline tickets represented by pairs of departure and arrival airports  [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from  JFK . Thus, the itinerary must begin with  JFK . Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary  ["JFK", "LGA"]  has a smaller lexical order than  ["JFK", "LGB"] . All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"] Example 2: Input: [[...

https://leetcode.com/problems/evaluate-reverse-polish-notation/ Evaluate the value of an arithmetic expression in  Reverse Polish Notation . Valid operators are  + ,  - ,  * ,  / . Each operand may be an integer or another expression. Note: Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ...

https://leetcode.com/problems/design-a-stack-with-increment-operation/ Design a stack which supports the following operations. Implement the  CustomStack  class: CustomStack(int maxSize)  Initializes the object with  maxSize  which is the maximum number of elements in the stack or do nothing if the stack reached the  maxSize . void push(int x)  Adds  x  to the top of the stack if the stack hasn't reached the  maxSize . int pop()  Pops and returns the top of stack or  -1  if the stack is empty. void inc(int k, int val)  Increments the bottom  k  elements of the stack by  val . If there are less than  k  elements in the stack, just increment all the elements in the stack. Example 1: Input ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"] [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],...

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ Given a string  s , a  k   duplicate removal  consists of choosing  k  adjacent and equal letters from  s  and removing them causing the left and the right side of the deleted substring to concatenate together. We repeatedly make  k  duplicate removals on  s  until we no longer can. Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique. Example 1: Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete. Example 2: Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa" Example 3: Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps" Constraints: 1 <=...