SWE Interview preparation

https://leetcode.com/problems/open-the-lock/ You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . The wheels can rotate freely and wrap around: for example we can turn  '9'  to be  '0' , or  '0'  to be  '9' . Each move consists of turning one wheel one slot. The lock initially starts at  '0000' , a string representing the state of the 4 wheels. You are given a list of  deadends  dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it. Given a  target  representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible. Example 1: Input: deadends = ["0201","0101","0102","1212",...

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/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,...

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/ Given an array of integers  nums  and an integer  limit , return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to  limit . In case there is no subarray satisfying the given condition return 0. Example 1: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff...

https://leetcode.com/contest/weekly-contest-187/problems/destination-city/ You are given the array  paths , where  paths[i] = [cityA i , cityB i ]  means there exists a direct path going from  cityA i  to  cityB i .  Return the destination city, that is, the city without any path outgoing to another city. It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city. Example 1: Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] Output: "Sao Paulo" Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo". Example 2: Input: paths = [["B","C"],["D","B"],["C","A"]] Output...

https://leetcode.com/problems/reverse-vowels-of-a-string/ Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Input: "hello" Output: "holle" Example 2: Input: "leetcode" Output: "leotcede" Note: The vowels does not include the letter "y". ---

https://leetcode.com/problems/remove-invalid-parentheses/ Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note:  The input string may contain letters other than the parentheses  (  and  ) . Example 1: Input: "()())()" Output: ["()()()", "(())()"] Example 2: Input: "(a)())()" Output: ["(a)()()", "(a())()"] Example 3: Input: ")(" Output: [""] --- Related problems 1249-minimum-remove-to-make-valid 1021-remove-outermost-parentheses --- Intuition Minimum removals => BFS Find the level at which valid sub string is found, all valid combinations are of same length, and at same level isValid helper function     if ( count++     if ) count--     if count < 0 => return false return count == 0 BFS - Q and visited set hold both valid, and invalid strings if current is valid, mark isValid, and simply poll from Q, no m...

https://leetcode.com/problems/clone-graph/ Given a reference of a node in a  connected  undirected graph. Return a  deep copy  (clone) of the graph. Each node in the graph contains a val ( int ) and a list ( List[Node] ) of its neighbors. class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with  val = 1 , the second node with  val = 2 , and so on. The graph is represented in the test case using an adjacency list. Adjacency list  is a collection of unordered  lists  used to represent a finite graph. Each list describes the set of neighbors of a node in the graph. The given node will always be the first node with  val = 1 . You must return the  copy of the given node  as a reference to the cloned graph. Example 1: Input: adj...

https://www.interviewbit.com/problems/knight-on-chess-board/ Given any source point,  (C, D)  and destination point,  (E, F)  on a chess board, we need to find whether Knight can move to the destination or not. The above figure details the movements for a knight (  8  possibilities ). If yes, then what would be the  minimum  number of steps for the knight to move to the said point. If knight can not move from the source point to the destination point, then return  -1 . Note:  A knight cannot go out of the board. Input Format: The first argument of input contains an integer A. The second argument of input contains an integer B. => The chessboard is of size A x B. The third argument of input contains an integer C. The fourth argument of input contains an integer D. => The Knight is initially at position (C, D). The fifth argument of input contains an integer E. The sixth argument of input contains an intege...

https://leetcode.com/problems/word-ladder/ Given two words ( beginWord  and  endWord ), and a dictionary's word list, find the length of shortest transformation sequence from  beginWord  to  endWord , such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that  beginWord  is  not  a transformed word. Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume  beginWord  and  endWord  are non-empty and are not the same. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",...

https://leetcode.com/problems/network-delay-time/ There are  N  network nodes, labelled  1  to  N . Given  times , a list of travel times as  directed  edges  times[i] = (u, v, w) , where  u  is the source node,  v  is the target node, and  w  is the time it takes for a signal to travel from source to target. Now, we send a signal from a certain node  K . How long will it take for all nodes to receive the signal? If it is impossible, return  -1 . Example 1: Input: times = [[2,1,1],[2,3,1],[3,4,1]] , N = 4 , K = 2 Output: 2 Note: N  will be in the range  [1, 100] . K  will be in the range  [1, N] . The length of  times  will be in the range  [1, 6000] . All edges  times[i] = (u, v, w)  will have  1 <= u, v <= N  and  0 <= w <= 100 . --- Related problems 787-cheapest-flights-within-k-stops 1514-path-with-maximum-probability ...

https://leetcode.com/problems/find-eventual-safe-states/ In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop. Now, say our starting node is  eventually safe  if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number  K  so that for any choice of where to walk, we must have stopped at a terminal node in less than  K  steps. Which nodes are eventually safe?  Return them as an array in sorted order. The directed graph has  N  nodes with labels  0, 1, ..., N-1 , where  N  is the length of  graph .  The graph is given in the following form:  graph[i]  is a list of labels  j  such that  (i, j)  is a directed edge of the graph. Example: Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]...