# Leetcode 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Since Java doesn’t have unsigned numbers, this task becomes a way more interesting. The simplest way would be to operate with bits, I’ve added a bunch of comments to the code to make it clear

`public class Solution {    // you need treat n as an unsigned value    public int reverseBits(int n) {        int res = 0;        for (int i = 0; i < 32; i++) {            // shift to the left, i.e. ...001 is changed into ...010            res <<= 1;             // n&1 - keep 1 at the end of n if it ends with 1            // | if n ends with 1, then res is also ends with 1            res = res | (n & 1);             n >>= 1; // shift n to the right for 1 position        }        return res;            }}`

# Leetcode 239. Sliding Window Maximum [Hard]

Not so hard for people familiar with streaming processing: You are given an array of integers `nums`, there is a sliding window of size `k`which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

`Input: nums = [1,3,-1,-3,5,3,6,7], k = 3Output: [3,3,5,5,6,7]`

Solution is based on using Deque where we keep only indeces of elements that are max in given window and remove everything smaller on each iteration. …

# Leetcode 1774. Closest Dessert Cost

To my surprise, brute force solution worked for this task. The idea to combine all possible topping costs in a form of set and then combine topping costs with base costs and simply select the closest one.

`class Solution {    // [4,5]    // 0,4,5,4*4, 4+5, 5*5    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {        Set<Integer> topings = new HashSet<>();        topings.add(0);        // all possible combinations…`

# Leetcode 1696. Jump Game VI [Medium]

According to leetcode tags Jump Game VI can land your dream job at either AQR Capital Management or Uber:)

My first attempt was to simply apply dynamic programming and dp[i] has the max score possible to achieve on that step. To initialize dp[i], we calculate: max{dp[i-k]+nums[i], dp[i-k+1]+nums[i],…dp[i-1]+nums[i]}

In code it looks like:

`class Solution {    public int maxResult(int[] nums, int k) {        int[] dp = new int[nums.length];        dp = nums;                for(int i = 1; i < nums.length; i++) {            int j = Math.max(0, i-k);            int maxDp = dp[j]+nums[i];            for(j++; j < i; j++ ) {                maxDp=Math.max(maxDp, dp[j]+nums[i]);            }            dp[i]=maxDp;        }…`

# Leetcode 317. Shortest Distance from All Buildings [Hard]

I wasn’t able to come up with better idea than brute force, surprisingly it worked. The idea of solution for this task is the foloowing:

1. From every empty piece of land, let’s try to reach all building and calculate a distance.
2. When we calculating a distance, I imagine that I make step in all available directions (similar like water moves from point in all directions)
3. If on my move I find a building, than number of steps is a distance to this building, so I increate total number of steps to reach all building by this value.

Beside that, the…

# Leetcode 547. Number of Provinces

The solution would be starting with city 1 and assigning this city province 1, go recursevely to all cities this city is connected to and assign province to all of them.

`class Solution {    public int findCircleNum(int[][] isConnected) {        int[] clusters = new int[isConnected.length+1];        Arrays.fill(clusters, -1);        int nextCluster = 0;        for(int i = 0; i < isConnected.length; i++) {            if(clusters[i+1]==-1){                ++nextCluster;                visit(isConnected, clusters, i, nextCluster);            }                    }        return nextCluster;    }        void visit(int[][] isConnected, int[] clusters, int i, int nextCluster) {        clusters[i+1]=nextCluster;        for(int j = 0; j < isConnected.length; j++) {            if(isConnected[i][j]==0) continue;            if(clusters[j+1]==-1) visit(isConnected, clusters, j, nextCluster);        }    }}`

# Performance lesson from Leetcode 1770. Maximum Score from Performing Multiplication Operations

Excellent performance lesson I’ve got today from leetcode challenge: I’ve created correct algo to solve 1770. Maximum Score from Performing Multiplication Operations during context but wasn’t able to get it to pass Time Limit during the context, no score for me today :(

My solution was based on simple backtracking and recursion, let’s pick the max between:

• nums[l] * multiplicator[i] + F(l+1, r, i+1)
• nums[r] * multiplicator[i] + F(l, r-1, i+1)

To cache result I used Map where String key was formed as l+”.”+r

`class Solution {    Map<String, Integer> cache = new HashMap<>()…`

# Leetcode 939. Minimum Area Rectangle [Medium]

Another kind of leetcode tasks without proper description: when I read the minimum area of a rectangle formed from these points my imagination built a rectangle that covers all these points. However, in reality, the task meant minimum rectangle that can be formed from any of these points!

After struggling a bit, mine not the fastest but still good enough approach (beats 28% of submissions):

1. Build a hash map that for every x coordinate records a set of y coordinates
2. Iterate through points and compare all pairs (O(n²))
3. For each pair, calculate the lenght of a side to make sure…

# 1326. Minimum Number of Taps to Open to Water a Garden [Leetcode Hard]

One of the biggest mysteries in the world: how leetcode assigns a level to the task — please comment if you have an insight.

This one is a classic example of such question: there are a lot of similar tasks with Medium level. Solution is simpler than one can expect from Hard task:

1. Create intervals from input and sort by beginning of the interval
2. Starting from the left, select the new interval (or call it a jump) that has the most right end; on new iteration, look for intervals that have intersection with current point and repeat a jump to…

# Leetcode 1226. The Dining Philosophers (Medium)

This is a kind of task that real leetcoder has a hard time to deal with :) Instead of academic algorithms this is more focused on understanding how real computers work. Meet The Dining Philosophers https://leetcode.com/problems/the-dining-philosophers/. The actual problem is very old, solved in real OSs and described in Operating Systems Design and Implementation by A. Tanebaum.

I read through discussion to the task and apparently most of people are posting clearly not working solutions that leads to deadlock and they seems to pass only because of concurrent programing is hard, but testing is even harder.

Here is my take… ## Kostya

Java, start-up, hiking, photos, bicycle,journey