December 11, 2023
Problem # Given a mapping of digits to letters (as in a phone number), and a digit string, return all possible letters the number could represent. You can assume each valid number in the mapping is a single digit.
For example if {“2”: [“a”, “b”, “c”], 3: [“d”, “e”, “f”], …} then “23” should return [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf"].
Solution # To solve this problem, we can use a technique called backtracking, which is a form of recursion.
...
December 10, 2023
Problem # Given a list of words, return the shortest unique prefix of each word. For example, given the list:
dog cat apple apricot fish Return the list:
d c app apr f Solution # To solve this problem, we can use a trie, which is a tree-like data structure used for storing a dynamic set of strings where the keys are usually strings. Each node of the trie marks the end of a particular word and also contains links to nodes representing the next possible character in a word.
...
December 10, 2023
Kadane’s algorithm is a dynamic programming approach used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It’s renowned for its efficiency, solving the problem in ( O(n) ) time, where ( n ) is the number of elements in the array. Here’s a breakdown of how it works:
Basic Idea # Kadane’s algorithm iterates through the array, calculating the maximum subarray sum ending at each position.
...
December 10, 2023
Problem # Given a circular array, compute its maximum subarray sum in O(n) time. A subarray can be empty, and in this case the sum is 0.
For example, given [8, -1, 3, 4], return 15 as we choose the numbers 3, 4, and 8 where the 8 is obtained from wrapping around.
Given [-4, 5, 1, 0], return 6 as we choose the numbers 5 and 1.
Solution # To solve this problem, we can use Kadane’s algorithm to find the maximum subarray sum for a linear array.
...
December 9, 2023
Problem # We say a number is sparse if there are no adjacent ones in its binary representation. For example, 21 (10101) is sparse, but 22 (10110) is not. For a given input N, find the smallest sparse number greater than or equal to N.
Do this in faster than O(N log N) time.
Solution # Here is the Python code for finding the smallest sparse number greater than or equal to a given number ( N ):
...