SWE Interview preparation

https://leetcode.com/problems/concatenated-words/ Given a list of words ( without duplicates ), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. Example: Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat". Note: The number of elements of the given array will not exceed  10,000 The length sum of e...

https://leetcode.com/problems/stream-of-characters/ Implement the  StreamChecker  class as follows: StreamChecker(words) : Constructor, init the data structure with the given words. query(letter) : returns true if and only if for some  k >= 1 , the last  k  characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.   Example: StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary. streamChecker.query('a'); // return false streamChecker.query('b'); // return false streamChecker.query('c'); // return false streamChecker.query('d'); // return true, because 'cd' is in the wordlist streamChecker.query('e'); // return false streamChecker.query('f'); // return true, because 'f' is in the wordlist streamChecker.query('g'); //...

https://leetcode.com/problems/add-and-search-word-data-structure-design/ Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter. Example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You may assume that all words are consist of lowercase letters  a-z . --- Intuition Build a trie to store words, mark word with boolean, not string since exact match will not be useful with wildcard . Use Hash Map / array of length 26 for storing children, keeps code clean and readable Build the trie iteratively, check if current character exists, if not create it. set current to child node.. iterate Search - rec...

https://leetcode.com/problems/longest-word-in-dictionary/ Given a list of strings  words  representing an English Dictionary, find the longest word in  words  that can be built one character at a time by other words in  words . If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string. Example 1: Input: words = ["w","wo","wor","worl", "world"] Output: "world" Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl". Example 2: Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] Output: "apple" Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple...

https://leetcode.com/problems/implement-trie-prefix-tree/ Implement a trie with  insert ,  search , and  startsWith  methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters  a-z . All inputs are guaranteed to be non-empty strings. --- Related problems 211-add-and-search-word-data-structure ---