Somewhere along the way we all agreed a blog should look one particular way. This caused all of the web to take a similar shape. And that way kindof sucks. I wanted something where emphasis was on typography and content more than graphics and styling while coping with the pace of modern life. This was when I found out about formatting blog in the form of issues and articles like print media. Because of this is has a large focus on text, and how ideas connect to each other. It instantly appealed to me and I have decided to give it a go.
-nomicon: Used to form nouns, referring to a book of knowledge on the specified topic
Hence, this Technonomicon is a blog-letter where I might release issues monthly or whenever I have sufficient content about my adventures and musings.
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)
The fallen leaves tell a story. Of how a tarnished became Elden Lord.
Blazingly fast ways to find all primes within a range.
Sieve of Erastosthenes is an algorithm for finding all the prime numbers in a segment [1,n] using O(n log log n) operations. Just your basic sieve, can probably find an explanation elsewhere.
Optimisation of Sieve of Erastosthenes, by optimising it until the root of max N.
int n;
vector<bool> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}Can be further optimised by i incrementing by 2 and making sure that only odd numbers are considered.
Utopia was to be a collaborative editor which would combine google docs with an local IDE. It should have had LSP support, Integrated VCS better than git, Low latency Websocket communications, Project Management and Admin support. It would have revolutionised pair programming where people could actually program together.
Truly an Utopia.
Should have included in the previous issue but couldn’t :(
Relational databases are also called a relational database management system (RDBMS) or SQL database. The most popular ones are MySQL, Oracle database, PostgresSQL, etc. Relational databases represent and store data in tables and rows. You can perform join operations using SQL across different database tables.
Non-Relational databases are also called NoSQL databases. Popular ones are CouchDB, Neo4j, Cassandra, MongoDB, Redis, etc. These databases are grouped into five categories:
The standard definition of NoSQL and SQL leaves much to be desired. The concept of relations and data which has no relations is not modeled accurately.