Hmmm… This is a sensitive and complex topic to address, especially before securing a place in the on-campus placement drive, but the process has truly humbled me. Watching random people get placed through cheating and malpractice has shaken both my self-confidence and my perspective on life. With my Commvault interview just two days away, the pressure isn’t easing, but bingeing The Way of Kings and Words of Radiance has offered much-needed solace. I’ve come to realize that Journey before Destination is the way forward. The strength to uphold what is right must always come before giving in to weakness.
This is only the start of my career. Temporary salary increments, which often become negligible in just two years, have already corrupted many of my batchmates. I want to resist that fate. My career as a software engineer will likely not be replaced by overhyped transformer models for at least a few decades. The algorithms and strategies I’m learning now will not only help in my daily work but also in building Pariah and the creative coding projects I will pursue in the future.
Well luck indeed plays a huge role, but it is indeed not as big as I had come to believe at first.
So Diophantine Equations…
My first encounter with Diophantine Equations was probably in my first year during Cirquit recruitment test. I was asked to solve a problem and having forgotten how to do modular arithmetic and find GCDs (Thank you JEE), sat and derived some crazy complicated equations to solve the problem. Right after that I had a Coding Club interview where I was asked to find the GCD of two numbers. Hmmm…, I just did this, let me do it again I thought. Shivam Birajdhar who was my interviewer told, hmmm… you are solving a diophantine equation and I was like “What??”
Given an array of length N, answer Q queries of the form [Li, Ri]. For each query q, find the value of f(Li,Li+1,…,Ri). The function f can vary according to the problem, e.g. min(..), sum(…).
The bruteforce appoarch would be to loop over all the element from Li to Ri and apply the function f on them. This approach would have a time complexity of O(N*Q). This is horrible for all practical reasons.
To solve this we have several ways
Both Segment trees and Sqrt trees are overkill for this problem unless there are very tight time constraints. Hence for range queries on immutable arrays, sparse tables are generally used.
Given Q ranges of the form [Li,Ri], for for each point x ∈ [1,N], find the number of ranges that contain that point.
A brute force solution would be to loop over each element for each range but this takes O(NQ) time. We can do better.
A BIT/Fenwick Tree can also be used to solve this problem with its own tradeoffs
Difference array is a technique used to perform range update queries is O(1), with an final overhead of O(N) to obtain the final result.
Given an array A and Q queries of two types:
A[i]=x has to be performed.when the value of f(Li,…,Ri) = f(0,…,Ri) - f(0,…,Li-1)
A brute force solution would be to loop over each element for each query but this takes O(NQ) time.
Sparse Tables cannot be used as they work only no immutable arrays and cannot handle point and range updates. This problem can be solved by using
Fenwick or Binary Indexed Trees
Complexity of O(log N) but not efficient for range updates and only support for prefix sum style queries
Seqment Trees
Complexity of O(log N), efficient for range updates and other types of queries but with a higher space complexity of O(4*N)