Boris Coding Blog

5 years ago I wrote about a hypothetical problem related to super queens in chess. You can see the original post here . This post starts with a traditional CS algorithmic problem: the 8-queens problem . The idea is to place 8 queens in a chess board with no two queens threatening each other. I wanted to go a little beyond and redo this problem but now with super queens. To recap, a super queen contains all the powers of a regular queen, but it also has the knight powers. Can it be done then? Can we have an 8-super queens problem solved? Let's see. The idea is to use backtracking with tree pruning. But here is an interesting idea: all you need to solve this problem is actually 5 hash tables that will tell you which queens are dominating the following positions:  - The rows  - The columns  - The first diagonal  - The second diagonal  - And finally the fifth one, which is the tricky one, marks any square that it being attacked by any queen in a knight-like move. The image be

Another one from LeetCode:  https://leetcode.com/problems/beautiful-arrangement/?tab=Description , or with the description here: Suppose you have  N  integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these  N  numbers successfully if one of the following is true for the i th  position (1 ≤ i ≤ N) in this array: The number at the i th  position is divisible by  i . i  is divisible by the number at the i th  position. Now given N, how many beautiful arrangements can you construct? Example 1: Input: 2 Output: 2 Explanation: The first beautiful arrangement is [1, 2]: Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1). Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2). The second beautiful arrangement is [2, 1]: Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1). Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1. Note: N  is a positive integer and

From time to time one ends up facing a string manipulation problem, such as "find a certain pattern" and "replace parts of the pattern" or "operate in the characters within the pattern". For example, let's suppose that the problem that we want to solve is the following: Given a string, certain characters will be placed in between an adjacent sequence (with the same length) of the character '*'. For example: "this is a *** test ***". In this particular example, it just so happens that the string "test" is located in between the sequence "***". Anytime that you find a sub-string in between the '*'s, replace it with its uppercase form. Hence, in the given example, return "this is a *** TEST ***". It is easy to write the code to solve such a problem, and variations of the problem. But I find that, whenever you model such a category of problems using Finite-State Machines (or FSM) , it makes not on

Another one from LeetCode:  https://leetcode.com/problems/linked-list-random-node/ : Given a singly linked list, return a random node's value from the linked list. Each node must have the  same probability  of being chosen. Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? The solution here is very similar to a post about reading a random line from a file . The solution is linear and no extra space is needed. Basically have a counter starting at 0. Generate a number between between 0 and the counter, randomly. Whenever that number is 0, assign the current element to the return value. This is guaranteed to give you a fair choice of elements, assuming the random generator is statistically sound. Code is below, very short. Cheers, Boris.     public class Solution     {         private ListNode head = null;         private Random rd = new Random();         /** @param hea

From Leetcode, a classic interview problem:  https://leetcode.com/problems/maximum-subarray/ : Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array  [-2,1,-3,4,-1,2,1,-5,4] , the contiguous subarray  [4,-1,2,1]  has the largest sum =  6 . There are ways to do it in O(n)-time and O(1)-space. The method that is shown here is an O(n)-time, O(n)-space, but it exemplifies the usage of extra memory to minimize the execution time of an algorithm. The storage auxiliary memory will store the max value of the subarray ending at position i. With that information, all it needs to be done at position i+1 is look at the max array at position i and decide whether it is better to add that element or not. Faster than 87% of the c# submissions. Cheers, Boris.     public class Solution     {         public int MaxSubArray(int[] nums)         {             if (nums == null || nums.Length == 0) return 0

Problem comes from LeetCode:  https://leetcode.com/problems/relative-ranks/ , or copied/pasted: Given scores of  N  athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal". Example 1: Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output their relative ranks according to their scores. Note: N is a positive integer and won't exceed 10,000. All the scores of athletes are guaranteed to be unique. My solution is an NLogN one. Here is the approach: Create a mapping between the (unique) numbers and their indexes Sort the array (hence the