#quark.io

[coding-quark]

MinMax Binary Search : Aggressive Cows

Question 1: Aggressive Cows Problem Statement: You are given an array 'arr' of size 'n' which denotes the position of stalls. You are also given an integer 'k' which denotes the number of aggressive cows. You are given the task of assigning stalls to 'k' cows such that the minimum distance between any two of them is the maximum possible. Find the maximum possible minimum distance

APPROACH

Since it is max of min problem we can consider binary Search

Let's first figure out what the questions is saying a) arr[i] denotes the position of the stall b) k = number of cows c) Need to maximize the minimum distance d) So according to what we've learned i need to go over the minimum values and then find maximum among them.

Figure out Minimum Distance Values: a) Now the minimum distance will be between any 2 consecutive stalls b) So we need to go over the consecutive stalls only

Figure out high and low: a) low -> 1 (minimum distance of 1 between any two stalls) b) high -> Maximum Distance between any two stalls (max - min)

Think of the f(x) function that will help us determine the feasibity of a minimum distance x a) The minimum distance, as stated can be between any 2 consecutive stalls b) if keeping this minimum distance (note: min distance means it can take more than this as well), we can fit all k cows, then it is a possible answer.

Now the modified BS part: a) if f(x) is true, then x is a possible answer. However since we're looking for MAX, we move rightward: if stalls >= k : low = mid + 1 b) if f(x) is false, all cows did not fit. That means we need to descrease the distance: else high = mid - 1

In the beginning low was possible, high was impossible. so now its inverse and our ans will be high

[coding-quark]

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It's much like how you sort playing cards in your hands. We begin with an empty left hand. You start with an unsorted hand, remove one card at a time from (from the unsorted pile) and insert them in the correct position in the left hand (sorted array).

How It Works

Start from the second element (index 1). [one element is already sorted]

Compare the current element with the elements before it.

Move greater elements ahead to make space for the current element. (SHIFT) All the greater elements are moved one space to the RIGHT.

Insert the current element at its correct position. (INSERT)

Repeat for all elements.

Step-by-Step Example

Let's sort the array [5, 2, 4, 6, 1, 3].

Initial Array: [5, 2, 4, 6, 1, 3]

Step 1: i = 1 (key = 2)

Compare 2 with 5. Since 2 < 5, shift 5 to the right.

Insert 2 at position 0.

Array: [2, 5, 4, 6, 1, 3]

Step 2: i = 2 (key = 4)

Compare 4 with 5. Since 4 < 5, shift 5 to right.

Compare 4 with 2. Since 4 > 2, stop.

Insert 4 at position 1.

Array: [2, 4, 5, 6, 1, 3]

Step 3: i = 3 (key = 6)

6 > 5, no shifting needed.

Insert 6 at position 3.

Array: [2, 4, 5, 6, 1, 3]

Step 4: i = 4 (key = 1)

Compare 1 with 6: shift 6 to right. ()

Compare 1 with 5: shift 5 to right.

Compare 1 with 4: shift 4 to right.

Compare 1 with 2: shift 2 to right.

Insert 1 at position 0.

Array: [1, 2, 4, 5, 6, 3]

Step 5: i = 5 (key = 3)

Compare 3 with 6: shift 6 to right.

Compare 3 with 5: shift 5 to right.

Compare 3 with 4: shift 4 to right.

Compare 3 with 2: stop (3 > 2).

Insert 3 at position 2.

Array: [1, 2, 3, 4, 5, 6]

The left hand side array, till i at any given time is sorted.

[coding-quark]

Steps to Solve Min of Max or vice versa using BS

Max of Min:

To find the minimum of the maximum in the context of a binary search, we use binary search over the possible values of the maximum. The key idea is to search for the smallest value that satisfies a feasibility condition, where the feasibility is determined by whether the maximum can be bounded by that value. Here's a structured breakdown:

Steps to Solve the Problem

Define the Search Range:

Determine the minimum possible value (low) and maximum possible value (high) for the answer. These are often based on the problem constraints (e.g., the distance between the first and last element in a range).

Binary Search Loop:

While low < high:

Compute the midpoint (mid) of the current range.

Check Feasibility: Determine if it's possible to achieve a maximum value of mid (i.e., if the condition is satisfied).

Adjust the Search Range:

If feasible, set high = mid to search for a smaller value.

If not feasible, set low = mid + 1 to search for a larger value.

Return the Answer:

Once the loop ends, low (or high) is the minimum value of the maximum that satisfies the condition.

Key Concepts

Feasibility Check: For a given candidate value (e.g., a distance, a value in an array), the check function determines whether it's possible to achieve the desired condition. This function is typically monotonic—if a value is feasible, all larger values are also feasible.

Binary Search on the Maximum: The search is over the range of possible maximum values, not directly over the array elements. This is because the problem is to minimize the maximum, not to find a specific element in the array.

Example: Placing Cows in Stalls

Problem: Place k cows in n stalls such that the maximum distance between adjacent cows is minimized.

Steps:

Search Range: low = 0, high = max(stalls) - min(stalls).

Feasibility Check: For a given distance mid, check if it's possible to place k cows such that no two are more than mid apart.

Binary Search: Use the above logic to find the smallest mid that satisfies the condition.

Another Example: Minimizing Maximum Subarray Sum

Problem: Find the minimum possible maximum of the sum of any subarray of length k in an array.

Steps:

Search Range: low = 0, high = sum of all elements.

Feasibility Check: For a given value mid, check if there exists a subarray of length k whose sum is ≤ mid.

Binary Search: Adjust the search range to find the smallest mid that satisfies the condition.

Why Binary Search Works

Monotonicity: If a value is feasible, all larger values are also feasible.

Efficiency: Reduces the search space by half in each iteration, resulting in O(log(max_value)) complexity.

Conclusion

To find the minimum of the maximum in a problem, perform binary search over the possible values of the maximum. For each candidate value, use a feasibility check to determine if it's possible to satisfy the condition. The minimum feasible value is the answer. This approach is widely used in optimization problems where the goal is to minimize the worst-case scenario (e.g., maximum distance, maximum sum, etc.).

----

Max of Min

To solve the "max of min" problem, we use binary search to find the maximum possible value of the minimum value that satisfies a given condition. This is often used in optimization scenarios where the goal is to maximize the minimum value (e.g., maximizing the minimum distance between cows, or maximizing the minimum number of coins in a subset). Below is a structured explanation of the approach, including how to detect the problem and implement the solution.

Key Concepts for "Max of Min" Problem

Binary Search on the Minimum Value:

The search is over the possible values of the minimum (e.g., distances, values, etc.).

The goal is to find the largest value that can be achieved as the minimum under the problem's constraints.

Feasibility Check:

For a given candidate value mid, the feasibility check determines whether it is possible to achieve a minimum value of at least mid.

If feasible, we can try higher values (i.e., set low = mid). If not, we need to try lower values (i.e., set high = mid - 1).

Monotonicity:

The feasibility of a value mid implies that all values less than mid are also feasible. This ensures the binary search can proceed correctly.

Example: Maximize the Minimum Distance Between Cows

Problem: Place k cows in n stalls such that the minimum distance between any two cows is as large as possible.

Steps:

Search Range:

low = 0 (minimum possible distance).

high = max(stalls) - min(stalls) (maximum possible distance).

Binary Search Loop:

While low < high:

Compute mid = (low + high) // 2.

Feasibility Check: Can we place k cows such that the minimum distance between any two cows is ≥ mid?

If feasible, set low = mid (try larger values).

If not feasible, set high = mid - 1 (try smaller values).

Result:

After the loop, low (or high) is the maximum possible minimum distance.

Feasibility Check for "Max of Min"

The feasibility check is reversed compared to the "min of max" case. For example:

In the min of max problem, we check if it is possible to achieve a maximum distance ≤ mid.

In the max of min problem, we check if it is possible to achieve a minimum distance ≥ mid.

Example Feasibility Check:def is_possible(stalls, k, min_dist): count = 1 # Number of cows placed last_pos = stalls[0] for pos in stalls[1:]: if pos - last_pos >= min_dist: count += 1 last_pos = pos if count == k: return True return count >= k

This function checks if it's possible to place k cows such that the minimum distance between adjacent cows is ≥ min_dist.

How to Detect the Problem

The problem is typically detected by the following:

Goal: Maximize the minimum value (e.g., distance, number of coins, etc.).

Constraints:

The problem involves a trade-off between values (e.g., placing cows to maximize the minimum distance).

The feasibility check is monotonic (if a value is feasible, all smaller values are also feasible).

Example: Maximize the Minimum Number of Coins in Subsets

Problem: Given an array of coins, find the maximum value of the minimum number of coins in any subset of size k.

Approach:

Search Range: low = 1, high = max(coins).

Feasibility Check: Can we select k subsets such that the minimum number of coins in any subset is ≥ mid?

Binary Search: Adjust the search range based on the feasibility check.

Key Differences Between "Min of Max" and "Max of Min"

Conclusion

To solve the "max of min" problem:

Perform binary search over the possible values of the minimum.

Use a feasibility check to determine if a given minimum can be achieved.

Adjust the search range based on the feasibility result.

The final answer is the largest feasible minimum.

This approach is widely applicable to optimization problems where the goal is to maximize the minimum under certain constraints.

[coding-quark]

With DP, while I do think I am starting to understand and recognize the patterns, figure out the choice at any point, its the overlapping subproblems part that gives me some trouble. The solution might just be that I do more practise questions. not sure.

[coding-quark]

System Design Basics Summary

[coding-quark]

Interview Questions Part #1

Q. How to detect memory leaks in docker?

Docker Container Memory Leaks: Detection, Diagnosis, and Prevention

Memory leaks in Docker containers can quietly erode system performance, causing slowdowns, crashes, or even complete application failure…

Q. How to log success or failure of an api and send email

Read up on prometheus and grafana

Read up on sentry

Note: Should've used a database such as PostgreSQL or MongoDB to save the monitoring logs.

FULL PROCESS:

Middleware or Interceptor or Filter for catching the api status a) Filters in Java: https://jakarta.ee/specifications/servlet/6.0/apidocs/jakarta.servlet/jakarta/servlet/filter b) Middleware in python: https://fastapi.tiangolo.com/tutorial/middleware/

Q. Threading & Concurrency in Java 1. https://docs.oracle.com/javase/tutorial/essential/concurrency/guardmeth.html 2. https://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html 3. https://docs.oracle.com/javase/tutorial/essential/concurrency/

[coding-quark]

Flow Chart for Greedy Algos

[coding-quark]

Greedy Solution for Jump game - 2

Greedy choice: Similiar to Jump Game 1, I am trying to reach the furthest point possible from a give range, with the (correct) hope that it'll help me reach the end with minimum number of steps.

Step 1 : Backtracking

At step 1, we thought of a recursive backtracking solution where we try out all the possibilities.

Step 2 : Convert to Greedy

From this we realized there is a range of values we can traverse from any given i. The range is (l, r) = (i + 1, farthest range).

Then based on this, we try to locally maximize the farthest possible we can reach from a given indx, since reaching the maximum at any point means we will have to make less jumps in the future

3. As seen in drawing 1, we had a tree, but since we only care for maxium at the range, what we do is we convert the tree into a range and then try to jump to the next range with the maximum reach so we can reduce the minimum jumps.

Thoughts:

1. The greedy choice property says that making the locally optimal choice (choosing the farthest reach) leads to the globally optimal solution (minimum jumps). So, in this case, each time we choose the farthest possible reach, we are making the best possible decision for the current step, which leads to the minimal total jumps. 2. By picking from the entire range at each step, we are considering all possibilities within a range in one iteration and picking (greedily) the maximum one.