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

Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following: 1 11 21 1211 111221 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n where 1 ≤ n ≤ 30, generate the nthterm of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.

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

Implement Strstr

Implement strstr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1 Input: haystack = "hello", needle = "ll" Output: 2 Example 2 Input: haystack = "aaaaa", needle = "bba" Output: -1 Clarification What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle is an empty string.

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

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index. According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.” Example Input: citations = [3,0,6,1,5] Output: 3 Explanation [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.

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

Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

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

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1 Input: num1 = "2", num2 = "3" Output: "6" Example 2 Input: num1 = "123", num2 = "456" Output: "56088" Note The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

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

Compare Version Numbers

Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

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

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Solution Time: O(n * 2^n) Space: O(n * 2^n) keep all the subsets of length N, since each of N elements could be present or absent. class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: results = [] subset = [] # Edge case 1 if nums == None: return results # Edge case 2 if len(nums) == 0: results.

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

Restore Ip Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] Solution class Solution: def restoreIpAddresses(self, s: str) -> List[str]: results = [] self.backtrack(results, s, 0, "", 0) return results def backtrack(self, results, s, start, partial, segment_count): # pruning for performance improvement if (4 - segment_count) * 3 < len(s) - start or (4 - segment_count) > len(s) - start: return # base case goal if start == len(s) and segment_count == 4: results.

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