SWE Interview preparation

https://leetcode.com/problems/plus-one/ Given a  non-empty  array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.

https://leetcode.com/problems/intersection-of-three-sorted-arrays/ https://github.com/openset/leetcode/tree/master/problems/intersection-of-three-sorted-arrays Given three integer arrays  arr1 ,  arr2  and  arr3   sorted  in  strictly increasing  order, return a sorted array of  only  the integers that appeared in  all  three arrays.   Example 1: Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] Output: [1,5] Explanation: Only 1 and 5 appeared in the three arrays.   Constraints: 1 <= arr1.length, arr2.length, arr3.length <= 1000 1 <= arr1[i], arr2[i], arr3[i] <= 2000

https://leetcode.com/problems/continuous-subarray-sum/ Given a list of  non-negative  numbers and a target  integer  k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of  k , that is, sums up to n*k where n is also an  integer .   Example 1: Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Example 2: Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.   Note: The length of the array won't exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer. ---

https://leetcode.com/problems/making-a-large-island/ In a 2D grid of  0 s and  1 s, we change at most one  0  to a  1 . After, what is the size of the largest island? (An island is a 4-directionally connected group of  1 s). Example 1: Input: [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3. Example 2: Input: [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. Example 3: Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.   Notes: 1 <= grid.length = grid[0].length <= 50 . 0 <= grid[i][j] <= 1 . ---

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/linked-list-random-node/ Given a singly linked list, return a random node's value from the linked list. Each node must have the  same probability  of being chosen. Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? Example: // Init a singly linked list [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. solution.getRandom(); --- Related problems 398-random-pick-index 528-random-pick-with-weight ---

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ https://workat.tech/problem-solving/practice/two-sum-sorted Given an array of integers that is already  sorted in ascending order , find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have  exactly  one solution and you may not use the  same  element twice. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. ---

https://leetcode.com/problems/split-array-largest-sum/ Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays. Note: If  n  is the length of array, assume the following constraints are satisfied: 1 ≤  n  ≤ 1000 1 ≤  m  ≤ min(50,  n ) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8] , where the largest sum among the two subarrays is only 18. --- Related problems 774-minimize-max-distance-to-gas-station 875-koko-eating-bananas 1011-capacity-to-ship-packages-within-d-days ---

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/merge-two-binary-trees/ Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7   Note:  The merging process must start from the root nodes of both trees. ---

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/first-missing-positive/ Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in  O ( n ) time and uses constant extra space. ---

https://leetcode.com/problems/valid-triangle-number/ Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3 Note: The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000].

https://leetcode.com/problems/partition-equal-subset-sum/ Given a  non-empty  array containing  only positive integers , find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200.   Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].   Example 2: Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets. ---

https://leetcode.com/problems/stickers-to-spell-word/ We are given N different types of stickers. Each sticker has a lowercase English word on it. You would like to spell out the given  target  string by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker. What is the minimum number of stickers that you need to spell out the  target ? If the task is impossible, return -1. Example 1: Input: ["with", "example", "science"], "thehat" Output: 3 Explanation: We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string. Example 2: Input: ["notice", "possible"], "basicbasic" Output: -1 Explanation: We ...

https://leetcode.com/problems/evaluate-division/ Equations are given in the format  A / B = k , where  A  and  B  are variables represented as strings, and  k  is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 . Example: Given  a / b = 2.0, b / c = 3.0. queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return  [6.0, 0.5, -1.0, 1.0, -1.0 ]. The input is:  vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> . According to the example above: equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], [...