SWE Interview preparation

https://leetcode.com/problems/path-crossing/ Given a string  path , where  path[i] = 'N' ,  'S' ,  'E'  or  'W' , each representing moving one unit north, south, east, or west, respectively. You start at the origin  (0, 0)  on a 2D plane and walk on the path specified by  path . Return  True  if the path crosses itself at any point, that is, if at any time you are on a location you've previously visited. Return  False  otherwise.   Example 1: Input: path = "NES" Output: false Explanation: Notice that the path doesn't cross any point more than once. Example 2: Input: path = "NESWW" Output: true Explanation: Notice that the path visits the origin twice.   Constraints: 1 <= path.length <= 10^4 path  will only consist of characters in  {'N', 'S', 'E', 'W} ---

https://leetcode.com/problems/average-salary-excluding-the-minimum-and-maximum-salary/ Given an array of  unique  integers  salary  where  salary[i]  is the salary of the employee  i . Return the average salary of employees excluding the minimum and maximum salary.   Example 1: Input: salary = [4000,3000,1000,2000] Output: 2500.00000 Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively. Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500 Example 2: Input: salary = [1000,2000,3000] Output: 2000.00000 Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively. Average salary excluding minimum and maximum salary is (2000)/1= 2000 Example 3: Input: salary = [6000,5000,4000,3000,2000,1000] Output: 3500.00000 Example 4: Input: salary = [8000,9000,2000,3000,6000,1000] Output: 4750.00000   Constraints: 3 <= salary.length <= 100 10^3 <= salary[i] <= 10^6 salary[i]  is unique. Answers within  10^-5  of the act

https://leetcode.com/problems/valid-mountain-array/ Given an array  A  of integers, return  true  if and only if it is a  valid mountain array . Recall that A is a mountain array if and only if: A.length >= 3 There exists some  i  with  0 < i < A.length - 1  such that: A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1]   Example 1: Input: [2,1] Output: false Example 2: Input: [3,5,5] Output: false Example 3: Input: [0,3,2,1] Output: true   Note: 0 <= A.length <= 10000 0 <= A[i] <= 10000

https://leetcode.com/problems/minimum-time-difference/ Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum  minutes  difference between any two time points in the list. Example 1: Input: ["23:59","00:00"] Output: 1 Note: The number of time points in the given list is at least 2 and won't exceed 20000. The input time is legal and ranges from 00:00 to 23:59. ---

https://leetcode.com/problems/encode-and-decode-tinyurl/ Note: This is a companion problem to the  System Design  problem:  Design TinyURL . TinyURL is a URL shortening service where you enter a URL such as  https://leetcode.com/problems/design-tinyurl  and it returns a short URL such as  http://tinyurl.com/4e9iAk . Design the  encode  and  decode  methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. ---

https://leetcode.com/problems/01-matrix/ Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.   Example 1: Input: [[0,0,0], [0,1,0], [0,0,0]] Output: [[0,0,0],  [0,1,0],  [0,0,0]] Example 2: Input: [[0,0,0], [0,1,0], [1,1,1]] Output: [[0,0,0], [0,1,0], [1,2,1]]   Note: The number of elements of the given matrix will not exceed 10,000. There are at least one 0 in the given matrix. The cells are adjacent in only four directions: up, down, left and right. ---

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/ Given a n-ary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).   Example 1: Input: root = [1,null,3,2,4,null,5,6] Output: 3 Example 2: Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: 5   Constraints: The depth of the n-ary tree is less than or equal to  1000 . The total number of nodes is between  [0, 10^4] . ---

https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  25  representing the letters  'a'  to  'z' : a value of  0  represents  'a' , a value of  1  represents  'b' , and so on. Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root. (As a reminder, any shorter prefix of a string is lexicographically smaller: for example,  "ab"  is lexicographically smaller than  "aba" .  A leaf of a node is a node that has no children.)   Example 1: Input: [0,1,2,3,4,3,4] Output: "dba" Example 2: Input: [25,1,3,1,3,0,2] Output: "adz" Example 3: Input: [2,2,1,null,1,0,null,0] Output: "abc"   Note: The number of nodes in the given tree will be between  1  and  8500 . Each node in the tree will have a value between  0  and  25 .

https://leetcode.com/problems/sum-root-to-leaf-numbers/ Given a binary tree containing digits from  0-9  only, each root-to-leaf path could represent a number. An example is the root-to-leaf path  1->2->3  which represents the number  123 . Find the total sum of all root-to-leaf numbers. Note:  A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Therefore, sum = 12 + 13 = 25 . Example 2: Input: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026 .

https://leetcode.com/problems/length-of-last-word/ Given a string  s  consists of upper/lower-case alphabets and empty space characters  ' ' , return the length of last word (last word means the last appearing word if we loop from left to right) in the string. If the last word does not exist, return 0. Note:  A word is defined as a  maximal substring  consisting of non-space characters only. Example: Input: "Hello World" Output: 5 ---

https://leetcode.com/problems/balanced-binary-tree/ Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of  every  node differ in height by no more than 1.   Example 1: Given the following tree  [3,9,20,null,null,15,7] : 3 / \ 9 20 / \ 15 7 Return true. Example 2: Given the following tree  [1,2,2,3,3,null,null,4,4] : 1 / \ 2 2 / \ 3 3 / \ 4 4 ---

https://leetcode.com/problems/distinct-subsequences/ Given a string  S  and a string  T , count the number of distinct subsequences of  S  which equals  T . A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ACE"  is a subsequence of  "ABCDE"  while  "AEC"  is not). It's guaranteed the answer fits on a 32-bit signed integer. Example 1: Input: S = "rabbbit" , T = "rabbit" Output:  3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ Example 2: Input: S = "babgbag" , T = "bag" Output:  5 Explanation: As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters) bab

https://leetcode.com/problems/ugly-number/ https://github.com/openset/leetcode/tree/master/problems/ugly-number https://www.lintcode.com/problem/ugly-number/description Write a program to check whether a given number is an ugly number. Ugly numbers are  positive numbers  whose prime factors only include  2, 3, 5 . Example 1: Input: 6 Output: true Explanation: 6 = 2 × 3 Example 2: Input: 8 Output: true Explanation: 8 = 2 × 2 × 2 Example 3: Input: 14 Output: false Explanation: 14 is not ugly since it includes another pime factor 7 . Note: 1  is typically treated as an ugly number. Input is within the 32-bit signed integer range: [−2 31 ,  2 31  − 1] --- Time - log 2 N + log 3 N + log 5 N Space - O(1) ---

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone. Now, a  move  consists of removing a stone that shares a column or row with another stone on the grid. What is the largest possible number of moves we can make?   Example 1: Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5 Example 2: Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Example 3: Input: stones = [[0,0]] Output: 0   Note: 1 <= stones.length <= 1000 0 <= stones[i][j] < 10000 ---

https://leetcode.com/problems/longest-turbulent-subarray/ A subarray  A[i], A[i+1], ..., A[j]  of  A  is said to be  turbulent  if and only if: For  i <= k < j ,  A[k] > A[k+1]  when  k  is odd, and  A[k] < A[k+1]  when  k  is even; OR , for  i <= k < j ,  A[k] > A[k+1]  when  k  is even, and  A[k] < A[k+1]  when  k  is odd. That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray. Return the  length  of a maximum size turbulent subarray of A.   Example 1: Input: [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: (A[1] > A[2] < A[3] > A[4] < A[5]) Example 2: Input: [4,8,12,16] Output: 2 Example 3: Input: [100] Output: 1   Note: 1 <= A.length <= 40000 0 <= A[i] <= 10^9 ---