December 22, 2023
Problem # Given an integer n, find the nth Fibonacci number using dynamic programming. The first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two.
Solution # The Python code to find the nth Fibonacci number using dynamic programming is as follows:
def fibonacci(n): # Initialize a list to store the Fibonacci numbers up to n fib_sequence = [0, 1] # Dynamic programming approach for i in range(2, n + 1): next_fib = fib_sequence[i - 1] + fib_sequence[i - 2] fib_sequence.
...
December 21, 2023
Problem # Given a list of intervals (each interval represented by a pair of integers), merge overlapping intervals and return the result in sorted order.
Solution # The Python function merge_intervals successfully merges overlapping intervals and returns the result in sorted order. Here’s the code:
def merge_intervals(intervals): """ Merge overlapping intervals and return the result in sorted order. :param intervals: A list of intervals, each represented as a pair of integers :return: A list of merged intervals in sorted order """ # Sort the intervals based on the starting value of each interval intervals.
...
December 21, 2023
Problem # Given a string s and a dictionary of words, determine if it’s possible to break s into one or more words from the dictionary. Return true if such a break is possible, false otherwise
Solution # The Python function word_break successfully determines if a given string s can be segmented into one or more words from the provided dictionary. The function returns True if such a segmentation is possible, and False otherwise.
...
December 21, 2023
Problem # Given an array of integers, rearrange the elements such that all negative numbers appear before all positive numbers. The original relative order of elements must be preserved.
Solution 1 # def rearrange_negatives_first(arr): """ Rearrange the array so that all negative numbers appear before all positive numbers. The original relative order of the elements is preserved. """ # Separate negative and positive numbers while preserving their order negative_nums = [x for x in arr if x < 0] positive_nums = [x for x in arr if x >= 0] # Combine the separated lists return negative_nums + positive_nums # Example usage arr = [1, -3, 5, -2, 4, -6, 7, -9] rearranged_array = rearrange_negatives_first(arr) print(rearranged_array) This code works as follows:
...
December 21, 2023
Problem # Given a string s, partition the string into k non-empty substrings such that every substring is a palindrome. Return the minimum number of cuts needed to make this possible.
Solution # Here’s the Python code for the problem statement:
def is_palindrome(s): """Check if the given string is a palindrome.""" return s == s[::-1] def min_cuts_for_palindromes(s, k): """ Function to find the minimum number of cuts needed to partition the string into k palindromic substrings.
...
December 20, 2023
Problem # Given an array of integers, find the minimum cost to reach the top of the stairs. Each step costs some amount as described in the input array. You can either climb one or two steps at a time.
Solution # To solve the problem “Given an array of integers, find the minimum cost to reach the top of the stairs, where each step costs a certain amount and you can climb one or two steps at a time,” we can use dynamic programming.
...
December 20, 2023
Problem # Given an unsorted list of integers, find the k most frequent elements in the list. Return them as a list with each element’s frequency.
Solution # To solve the problem of finding the k most frequent elements in an unsorted list of integers, you can use a combination of a hash map (dictionary in Python) to store the frequency of each element and a heap to efficiently find the k most frequent elements.
...
December 20, 2023
Problem # Given an integer k and a list of integers, find if there exists k numbers in the list that add up to 0. Return true if such a set is possible, false otherwise.
Solution # def can_find_k_sum(nums, k, start, target): # If k is 0, then we have found a combination that sums up to the target if k == 0: return target == 0 # If we have run out of numbers to add, return False if start == len(nums): return False # Include the current number and check if a combination is possible if can_find_k_sum(nums, k - 1, start + 1, target - nums[start]): return True # Exclude the current number and check if a combination is possible return can_find_k_sum(nums, k, start + 1, target) def can_partition_k(nums, k): # Edge case: if we don't have enough numbers if len(nums) < k: return False return can_find_k_sum(nums, k, 0, 0) # Test the function with an example print(can_partition_k([-5, -3, -2, -1, 0, 1, 2, 3, 4, 5], 3)) # Should return True as there are combinations that sum up to 0 can_find_k_sum is a helper function that uses recursion and backtracking to find if there exists a combination of k numbers that sum up to the target (in this case, 0).
...
December 20, 2023
Problem # Given an array of integers and a sliding window of size k, find the maximum value in each window. The window slides one position to the right at a time.
Solution # import collections def max_sliding_window(nums, k): n = len(nums) if n == 0 or k == 0: return [] deque = collections.deque() result = [-1] * (n - k + 1) for i in range(n): while deque and deque[0] < i - k + 1: deque.
...
December 19, 2023
Problem # Find the longest increasing subsequence in a given sequence of numbers.
Solution # def longest_increasing_subsequence(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # Test the function with an example print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])) In this code, the longest_increasing_subsequence function takes a list of integers as input and returns the length of the longest increasing subsequence in that list.
...
December 19, 2023
Problem # Given K sorted arrays of integers, find the Kth largest element among all the elements in the arrays.
Solution # Here’s the Python code for finding the Kth largest element among all elements in given sorted arrays:
import heapq def kth_largest_in_sorted_arrays(arrays, k): # Create a min heap min_heap = [] # Initialize heap with the last element of each array for i, array in enumerate(arrays): if array: heapq.
...
December 18, 2023
Problem # Given a 2D board of letters and a target word, find all occurrences of the word in the board.
Solution # Below is the complete Python code for the function find_word_occurrences, which finds all occurrences of a given word in a 2D board of letters. You can use this code in your Python environment:
def find_word_occurrences(board, word): if not board or not word: return [] def dfs(board, word, index, x, y): if index == len(word): return True if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] !
...
December 17, 2023
Problem # Given an array of integers, count the number of inversions, where an inversion is a pair of integers (i, j) such that i < j and arr[i] > arr[j].
Solution # To solve the problem of counting the number of inversions in an array, where an inversion is defined as a pair of indices ((i, j)) such that (i < j) and (\text{arr}[i] > \text{arr}[j]), we can use a modified version of the merge sort algorithm.
...
December 16, 2023
Problem # Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list.
Solution 1 # class ListNode: def __init__(self, value=0, next=None, random=None): self.value = value self.next = next self.random = random def deep_clone(head): """ Deep clone a linked list where each node has a 'next' pointer and a 'random' pointer. :param head: Head node of the original linked list :return: Head node of the cloned linked list """ if not head: return None # Step 1: Create a new node for each node in the original list and insert it between the original node and its next node current = head while current: new_node = ListNode(current.
...
December 16, 2023
Problem # Given the root to a binary search tree, find the second largest node in the tree.
Solution # class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def find_second_largest(root): """ Function to find the second largest element in a binary search tree. :param root: Root node of the binary search tree :return: Value of the second largest node """ # Helper function to find the rightmost and the parent of rightmost nodes def find_rightmost_and_parent(node): parent = None while node.
...
December 16, 2023
Problem # Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.
Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.
Do this in O(N) time.
...
December 15, 2023
Problem # Sure, here’s a medium-level algorithm interview question that I’ve created:
Problem: “Array Rotation and Sum”
You are given an array of n integers and a number, k. Your task is to write a function that rotates the array to the right by k steps, and then finds the sum of a specific subarray.
Specifically, your function should implement the following steps:
Rotate the array to the right by k steps.
...
December 14, 2023
Problem # Scenario: You are a treasure hunter exploring a maze filled with rooms and tunnels. The maze is represented as a graph, where nodes are rooms and edges are tunnels connecting them. Some rooms contain treasure chests, and some may have locked doors requiring specific keys. You can only move through unlocked doors and have a limited carrying capacity for keys.
Your Task: Design an algorithm to find the shortest path from the entrance to the room containing the main treasure, collecting all necessary keys along the way.
...
December 14, 2023
Problem # Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Solution # Solution 1 # Here’s the Python code to find all unique triplets in an array that add up to zero:
def threeSum(nums): nums.sort() result = [] for i in range(len(nums) - 2): # Avoid duplicate solutions if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total < 0: left += 1 elif total > 0: right -= 1 else: result.
...
December 14, 2023
Problem # The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out.
More rigorously, we can define it as follows:
The horizontal distance of the root is 0. The horizontal distance of a left child is hd(parent) - 1. The horizontal distance of a right child is hd(parent) + 1. For example, for the following tree, hd(1) = -2, and hd(6) = 0.
...
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.
...