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. Solution Java class Trie { class TrieNode { private TrieNode[] children; private final int R = 26; private boolean isWord; public TrieNode() { children = new TrieNode[R]; } public boolean containsKey(char ch) { return children[ch -'a'] !

by lek tin in "algorithm" access_time 3-min read

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1 Input: 1 Output: "A" Example 2 Input: 28 Output: "AB" Example 3 Input: 701 Output: "ZY" Solution class Solution: def convertToTitle(self, n): """ :type n: int :rtype: str """ digit = 1 res = "" while n > 0: # Because we start from A.

by lek tin in "algorithm" access_time 1-min read

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. Solution

by lek tin in "algorithm" access_time 1-min read

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Note Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1 Input: [1,2,3,4,5] Output: true Example 2 Input: [5,4,3,2,1] Output: false Solution import math class Solution: def increasingTriplet(self, nums: List[int]) -> bool: if not nums or len(nums) < 3: return False # min_1 < min_2 min_1, min_2 = math.

by lek tin in "algorithm" access_time 1-min read

Simplify Path

Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" path = "/a/../../b/../c//.//", => "/c" path = "/a//b////c/d//././/..", => "/a/b/c" In a UNIX-style file system, a period ('.') refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period ("..") moves up a directory, so it cancels out whatever the last directory was.

by lek tin in "algorithm" access_time 1-min read

Sqrtx

Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. Example 1 Input: 4 Output: 2 Example 2 Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.

by lek tin in "algorithm" access_time 1-min read

Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note You are not suppose to use the library’s sort function for this problem. Example Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Follow-up A rather straight forward solution is a two-pass algorithm using counting sort.

by lek tin in "algorithm" access_time 1-min read

Missing Words

Julia and Samantha are playing with strings. Julia has a string S, and Samantha has a string T which is a subsequence of string S. They are trying to find out what words are missing in T. Help Julia and Samantha to solve the problem. List all the missing words in T, such that inserting them at the appropriate positions in T, in the same order, results in the string S.

by lek tin in "algorithm" access_time 1-min read

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6]. Solution 1 Time: O(n) Space: O(n) class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: left, right = [nums[0]], [nums[-1]] N = len(nums) if N <= 1: return 0 res = [] for i in range(1, N-1): left.

by lek tin in "algorithm" access_time 1-min read

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note You must do this in-place without making a copy of the array. Minimize the total number of operations. Credit Special thanks to @jianchao.

by lek tin in "algorithm" access_time 2-min read