Archive for Programming

[coding-quark]

Learning Tags

Learning Resources

System Design

Approach -> Tag for improvements/how to solve problems while detecting pattern

DP

Data Structures a) Arrays

Algorithms a) Binary Search b) Recursion c) Backtracking d) Greedy Problems

Useful links

[sqrt-73]

I believe one of the most underrated math/coding websites of all time is projecteuler.net. As one of the top 2000 ranked in this website, I feel like I can say just how amazing this website is. Here is a list of everything I love about it.

Well thought out idea: This website is full of math problems in which (almost) all of them can only be solved by code, but you cannot just use brute force. You need to use the best of math and CS to solve the problems.

Good problems, and not just a couple. This website has >900 well thought out problems that can be solved in under a minute even on incredibly slow computers

Variance in difficulty: There are problems that will take you under 5 minutes to complete, and others will take you weeks without making a lick of progress (looking at you #177). Even if you don't know anything bout number theory or CS, there will be problems you can solve and learn new concepts with. Just dost skip to the recent problems, they're VERY hard.

Price: I won't sugarcoat it. It's free. Completely. No need to pay for problems. No missing features. No ads. Anyone can make a free account and have the exact same experience. This might be it's biggest selling point in my opinion.

These problems have made me spend hundreds of hours confused and dumbfounded until I find a solutions. Now, there are definitely sites you can find that will give you the answers But don't use them for solutions or else you'll be cursed for life. They're good places if you want to see how others solved it, but it is 233168% better to just skip on these websites and solve them yourselves. Even after all of this time, I have never copy-pasted an answer, purely because I prefer the struggle, and I believe that I learn more by finding out the necessary info myself.

Overall, stop reading this and go to the website (projecteuler.net). It deserves all the praise it can get. I hope you enjoy the problems like I do :)

[sqrt-73]

Some of my personal favorites:

A website dedicated to the fascinating world of mathematics and programming

The first “hard” problem, but becomes simple once you find out a clever algorithm.

A website dedicated to the fascinating world of mathematics and programming

This one took me a while since I was new to competition coding, but it is overall a very fun exercise.

A website dedicated to the fascinating world of mathematics and programming

Mathematically, the hardest problem in the first 100. I think that is a valid label.

A website dedicated to the fascinating world of mathematics and programming

The problem I find hardest in the first 100. This one is just 60 but much harder. Good luck.

[sqrt-73]

A website dedicated to the fascinating world of mathematics and programming

This problem either takes you an hour or a week. I am the latter.

A website dedicated to the fascinating world of mathematics and programming

Very clever problem, that’s all I’ll say.

A website dedicated to the fascinating world of mathematics and programming

This is my favorite introduction to a mathematical concept (if you solved it, you know what it is).

A website dedicated to the fascinating world of mathematics and programming

Everyone I’ve seen since this one has solved it differently.

A website dedicated to the fascinating world of mathematics and programming

Mathematically, the hardest problem in the first 150. I think #147 is harder

A website dedicated to the fascinating world of mathematics and programming

The hardest for me personally in the first 150. Don’t overthink this one, yet overthink this one.

[locally-normal]

I did this one back in high school and it absolutely fascinated me. It's not all that hard but it does teach you a cool fact about pascal's triangle.

A website dedicated to the fascinating world of mathematics and programming

[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.

[coding-quark]

Greedy Choice for problems solved

Assign Cookies based on size and greed factor - Greedy choice: Give each child the minimum size cookie so larger size cookies are present for future children - Optimal Substructure: the same locally optimal choice made for n children, then n-1 children and so on.

Fractional Knapsack Problem - Greedy Choice: Pick the maximum value/wt at each step to maximise the elements that can be held in the knapsack - Optimal Substructure: same applied for 1,2...n item to be polaced in bag.

Greedy algorithm to find minimum number of coins - Greedy Choice: Since we want to minimize the number of coins, we can start with the maximum currency value that can be provided

Lemonade Change Greedy Choice Property: - Using larger denominations (e.g., $10) for $20 change is better than using smaller ones because it preserves $5 bills for future $10 transactions - For example, if you use three $5s for a $20 bill, you might not have enough $5s to serve a later customer who pays with a $10. Optimal Substructure: - The problem can be decomposed into steps where each decision (giving back $5 or $10) affects the availability of bills for future customers. - The greedy choice of using larger bills first ensures that the solution is globally optimal.

Valid Paranthesis checker:

This approach satisfies the greedy choice property because each decision (treat '' as ')' or '(') is made based on the current state, and the algorithm proceeds step by step, trying to make the best possible choice at each step. The optimal substructure here is that the decision to use a '' as a ')' or '(' at each step affects the remaining possibilities, and the greedy choice leads to the correct overall solution.

So the problem satisfies the greedy property because the algorithm makes choices that are locally optimal (using '' as a closing bracket first) and these choices lead to a globally optimal solution (valid string). The key is that the greedy choice of using '' as a closing bracket first ensures that we have the best chance of meeting the required number of closing brackets, and if that's not possible, using it as an opening bracket allows for more flexibility.

6. N meeting room: - Greedy Choice: We pick the meeting with the minimum ending time, as it leaves the maximum possible time for future meetings to be held.

7. Jump Game:

1. In the greedy approach, maybe the algorithm is not about choosing the maximum possible step each time, but rather keeping track of the maximum reachable index 2. The greedy choice is to always track the farthest you can reach. The key is that at each step, you don't need to look ahead to choose the best path, but rather just keep track of the maximum reach. Because if you can reach a certain index, you can take the maximum possible step from there, which would be the optimal choice. 3. Greedy Choice: At each index i, the best choice is to jump to the farthest reachable index from i. This ensures that we maximize the range of reachable positions, increasing the chance of reaching the end. 4. Optimal Substructure: The problem can be broken down into subproblems where the optimal solution is determined by the farthest reachable index at each step. If the current index is beyond the farthest reachable index, it's impossible to proceed further. 5. No Need for Backtracking: The greedy approach doesn't require checking all possible paths, as it only tracks the farthest reachable index

8. Jump Game - 2

1. 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. 2. See Separate approach post for this under approach.,

[coding-quark]

Greedy Algorithm

A greedy algorithm is a problem-solving approach that makes the locally optimal choice at each step, with the hope that these choices will lead to a globally optimal solution. Unlike brute-force or dynamic programming methods, greedy algorithms do not explore all possible options but instead make decisions based on the best immediate choice. This approach is efficient but may not always yield the optimal result, depending on the problem's structure.

How Greedy Algorithms Work

Step-by-Step Decision-Making:

At each step, the algorithm selects the best possible option based on the current state of the problem.

This decision is made without considering future consequences, which can sometimes lead to suboptimal results.

No Backtracking:

Once a choice is made, the algorithm does not revisit earlier decisions. This makes greedy algorithms efficient but potentially limited in scope.

Local vs. Global Optimality:

A greedy algorithm relies on the greedy choice property: the locally optimal choice at each step leads to a globally optimal solution.

This is not always guaranteed, but when it holds, the algorithm is effective.

Key Characteristics of Problems Solved by Greedy Algorithms

A problem can be solved using a greedy algorithm if it satisfies the following two properties:

1. Greedy Choice Property

The optimal solution can be constructed incrementally by making the locally optimal choice at each step.

Example: In the activity selection problem, selecting the activity that ends the earliest ensures maximum flexibility for future choices.

2. Optimal Substructure

The optimal solution to the problem can be decomposed into subproblems that also have optimal solutions.

Example: In Huffman coding, the optimal encoding tree is built by repeatedly combining the two nodes with the smallest frequencies.

How to Identify a Problem for a Greedy Algorithm

To determine if a problem is suitable for a greedy algorithm, ask:

Can the problem be broken into steps where each step makes a locally optimal choice?

Does the choice at each step affect the remaining problem in a predictable way?

Is the problem structured such that the greedy choice leads to the global solution?

Examples of Problems Solved by Greedy Algorithms:

Activity Selection Problem:

Goal: Select the maximum number of non-overlapping activities.

Greedy Strategy: Always pick the activity that ends earliest.

Huffman Coding:

Goal: Compress data with minimum total encoded length.

Greedy Strategy: Combine the two nodes with the smallest frequencies.

Dijkstra’s Algorithm:

Goal: Find the shortest path in a graph.

Greedy Strategy: Always select the node with the smallest tentative distance.

Prim’s/Kruskal’s Algorithm:

Goal: Find the minimum spanning tree (MST) of a graph.

Greedy Strategy: Add edges or nodes that minimize the total weight.

Job Scheduling:

Goal: Schedule jobs to minimize lateness.

Greedy Strategy: Sort jobs by deadlines or processing times.

Steps to Apply a Greedy Algorithm

Define the Problem:

Identify the objective and constraints (e.g., maximize profit, minimize cost, etc.).

Identify the Greedy Choice:

Determine the rule for making the locally optimal choice (e.g., "always pick the smallest element").

Implement the Greedy Strategy:

Use a loop or recursive function to apply the greedy choice step-by-step.

Verify the Solution:

Check if the greedy choice leads to the global optimal solution (using examples or proofs).

When Greedy Algorithms Fail

Greedy algorithms may fail if:

The locally optimal choice does not lead to the global solution (e.g., the Traveling Salesman Problem).

The problem requires considering future choices (e.g., scheduling with dependencies).

Comparison with Dynamic Programming

How do I differentiate between greedy and dynamic programming? Because both use optimal substructure. But greedy algorithms make decisions without looking ahead, while dynamic programming considers all possibilities. So the key is that for a problem with the greedy choice property, you can make a choice that leads to the optimal solution without needing to check all possibilities. Greedy Algorithm : 1. Approach : Makes one choice at a time 2. Efficiency : Fast (O(n)) 3. Optimality: May not always be optimal 4. Use Case: Problems with clear greedy choice property

Dynamic Programming: 1. Approach : Explores all possibilities 2. Efficiency Slower (O(n²) 3. Optimality: Always optimal (for problems with optimal substructure) 4. Use Case Problems requiring exploration of all subproblems

Summary

Greedy algorithms are efficient but not always optimal.

They work best when the greedy choice property and optimal substructure hold.

Use them for problems where local choices directly lead to global solutions (e.g., activity selection, Huffman coding).

Always validate the solution with examples or proofs to ensure correctness.

[coding-quark]

Sudoku Solver Matrix Representation

Tree Representation:

Arrays for storing info

rows[9][9] cols[9][9] blocks[3][3][9]

[coding-quark]

TODOs

Read up on 3D arrays

Try Sudoku Solver again

[coding-quark]

Useful Link for Backtracking

Coding interviews stressing you out? Get the structure you need to succeed. Get Interview Ready In 6 Weeks.

[coding-quark]

Flowchart for algorithm and pattern detection:

Coding interviews stressing you out? Get the structure you need to succeed. Get Interview Ready In 6 Weeks.

[coding-quark]

Recursion Patterns

[coding-quark]

I don't want to do recursion someone kill me so i don't have to do recursion.

[coding-quark]

Approach for recursive problems

Understand the problem and the constraints.

Identify the base case and the recursive case.

Determine the parameters needed to track the state of the recursion (like the last character in this case).

Implement the recursion with the base case and the recursive steps, making sure that each step adheres to the constraints.

[coding-quark]

TODOs

Revise Binary Search and Linked List this weekend

Do at least 2 system design chapters

FINISH BUILDING RESUME

[coding-quark]

Linked List Resources for python impl

Learn everything you need to know about linked lists: when to use them, their types, and implementation in Python.

Linked Lists in Python – Explained with Examples

By Fakorede Damilola Different programming languages offer different ways to store and access data. Some of the data structures you can use

[coding-quark]

String Notes

Resources: - https://www.techinterviewhandbook.org/algorithms/string/ - https://www.youtube.com/watch?v=hHAyVC1m_H0&list=PL_z_8CaSLPWc63FA_sPOjysCdwWT-IQBd&index=10&ab_channel=AdityaVerma

Counter for Hashing: - https://pythongeeks.org/python-counter-class/

the Counter Space Complexity is O(1)