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 ):
...
December 9, 2023
Problem # Given an array of numbers of length N, find both the minimum and maximum using less than 2 * (N - 2) comparisons.
Solution # def find_min_max(arr): n = len(arr) # Initialize min and max if n % 2 == 0: if arr[0] > arr[1]: current_min, current_max = arr[1], arr[0] else: current_min, current_max = arr[0], arr[1] start = 2 # Start from the third element else: current_min = current_max = arr[0] start = 1 # Start from the second element # Iterate in pairs for i in range(start, n, 2): if arr[i] < arr[i + 1]: local_min, local_max = arr[i], arr[i + 1] else: local_min, local_max = arr[i + 1], arr[i] # Update global min and max if local_min < current_min: current_min = local_min if local_max > current_max: current_max = local_max return current_min, current_max # Test the function test_array = [3, 2, 5, 1, 8, 7, 4, 6] find_min_max(test_array) This function divides the array into pairs, compares the elements in each pair, and then updates the global minimum and maximum accordingly.
...