SWE Interview preparation

 https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ Given the  head  of a sorted linked list,  delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return  the linked list  sorted  as well .   Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] Example 2: Input: head = [1,1,1,2,3] Output: [2,3]   Constraints: The number of nodes in the list is in the range  [0, 300] . -100 <= Node.val <= 100 The list is guaranteed to be  sorted  in ascending order. ---- Intuition Maintain previous pointer - initialized to dummy node before head while head != null      if duplicates found          while duplicates               advance head          disconnect start of duplicate          prev.next = head.next      else ...

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/insert-into-a-sorted-circular-linked-list/ https://github.com/openset/leetcode/tree/master/problems/insert-into-a-sorted-circular-linked-list https://www.lintcode.com/problem/insert-into-a-cyclic-sorted-list/description Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to  any  single node in the list, and may not be necessarily the smallest value in the cyclic list. If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted. If the list is empty (i.e., given node is  null ), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node. The following example may help you understand the problem better:   In the...

https://leetcode.com/problems/intersection-of-two-linked-lists/ https://workat.tech/problem-solving/practice/intersection-two-linked-lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1.   Example 1: Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.   Example 2: Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Reference of the node with value = 2 Input Explanation:  The intersected node's value is 2 (note that this m...

https://leetcode.com/problems/swap-nodes-in-pairs/ Given a linked list, swap every two adjacent nodes and return its head. You may  not  modify the values in the list's nodes, only nodes itself may be changed.   Example: Given 1->2->3->4 , you should return the list as 2->1->4->3 . ---

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/ You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example 1: Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is as follows: After flattening the multilevel linked list it becomes: Example 2: Input: head = [1,2,null,3] Output: [1,3,2] Explanation: The input multilevel linked list is as follows: 1---2---NULL | 3---NULL Example 3: Input: head = [] Output: [] How...

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/ https://www.lintcode.com/problem/convert-binary-search-tree-to-sorted-doubly-linked-list/description Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let's take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element. The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list. Specifically, we want to do the transformation in place. After...

https://leetcode.com/problems/copy-list-with-random-pointer/ A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a  deep copy  of the list. The Linked List is represented in the input/output as a list of  n  nodes. Each node is represented as a pair of  [val, random_index]  where: val : an integer representing  Node.val random_index : the index of the node (range from  0  to  n-1 ) where random pointer points to, or  null  if it does not point to any node. Example 1: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Example 2: Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]] Example 3: Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]] Example 4: Input: head = [] Output: [] Explanation: Given linked list is empty (null pointer), so return null. Constraint...

https://leetcode.com/problems/remove-linked-list-elements/ Remove all elements from a linked list of integers that have value  val . Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 -- Intuition Have a prev pointer If head.val == target    Set the prev to head.next else    prev = prev.next Preprocess Corner case, while head.val == target at the beginning of list -- Related problems 237-delete-node-in-linked-list ---

https://leetcode.com/problems/delete-node-in-a-linked-list/ https://workat.tech/problem-solving/practice/delete-node-linked-list Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Given linked list -- head = [4,5,1,9], which looks like following: Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function. Example 2: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function. Note: The linked list will have at least two elements. All of the nodes' values will be unique. The given node will not be the tail and it will always be a valid node of the linked list. Do not return anything from your function. ---- Intuition We cannot s...

https://leetcode.com/problems/reorder-list/ Given a singly linked list  L :  L 0 → L 1 →…→ L n -1 → L n , reorder it to:  L 0 → L n → L 1 → L n -1 → L 2 → L n -2 →… You may  not  modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. ---

https://leetcode.com/problems/lru-cache/ Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a  positive  capacity. Follow up: Could you do both operations in  O(1)  time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 ca...