Fast and Slow
Fast and Slow
How to manipulate linked lists using the fast and slow pointer method. Plus a beginner-friendly introduction to relational databases.
Hi Friends,
Welcome to the 8th edition of the Polymathic Engineer newsletter. It is common for everyone to have "fast" phases where you feel more productive and motivated and "slow" phases where you feel less so. But there is nothing wrong with having slow phases.
When this happens, I usually embrace this, prioritizing physical and mental self-care. This can include getting enough sleep, eating well, and engaging in activities that I enjoy more. Being kind and patient with myself usually helps me to get through this quickly.
Today we will talk about:
relational databases in the context of system design interviews
using the fast and slow pointers method to manipulate linked lists
coding challenge
three interesting tweets
Relational Databases
Relational databases are one of the most commonly used data storage systems and frequently come during systems design interviews. Here are the principal concepts you need to be familiar with while designing a system:
definitions and query language
ACID transactions
Indexes
Definitions and query languages
Relational databases impose on the data a tabular-like structure. Data is stored in tables, and each table represents a specific entity. The columns represent attributes of the entity. The rows (or records) are instances of the entity.
All tables are defined according to a set of rules known as schema. Every record in each table needs to conform to the specific schema. Most relational databases support SQL (Structured Query Language). SQL enables powerful queries to retrieve data.
In theory, it is also possible to implement application-side queries using a programming language. But large-scale systems have TB of data, so you should load them in memory to query that data. Unfortunately, this is often non-trivial or impossible.
Transactions
A transaction is a combination of operations satisfying 4 properties:
• Atomicity: all the operations are treated as a unit, and they all succeed or fail. In case of failures, changes are undone.
• Consistency: any application-level state is invariant after a transaction execute.
• Isolation: the concurrent execution of the transaction doesn't cause race conditions
• Durability: the effect of a transaction is permanent
Indexes
A database index is an additional data structure optimized for fast searching on a specific attribute in a table. This data structure stores the attribute entries in sorted order, pointing them to the corresponding row in the original table.
Since entries are sorted, the query can be executed in O(logN) or O(1) instead of in O(N).
The trade-offs are that:
• the additional data structure takes up more space
• write operations are slower because also the index needs to be updated
Relational databases are a good fit when:
- very powerful queries must be executed (i.e., multi-rows SQL transactions).
- strong consistency is required
Non-relational databases are not fully ACID compliant and guarantee only eventual consistency.
Fast and Slow pointers
Fast and slow pointers are a great technique to manipulate linked lists. It is an extension of the arrays 2 pointers method to linked list and it comes in very handy in solving interview problems.
The idea is to iterate through the list with 2 pointers moving at different speeds. The pointers are usually called fast and slow. Let's consider an example where we want to find the node in the middle of a list. The brute force approach would first find the list's length and then the middle node.
Fast and slow pointers give a more efficient and elegant solution with only one iteration. On each step, the fast pointer advance by 2 nodes and the slow pointer by 1 node. This way, the slow pointer reaches the middle node while the fast one reaches the end. This is because the slow pointer moves at half the speed.
Of course, the fast and slow pointers approach has some variants. For example, the pointers can start at different locations or have different speeds ratio. Other common problems that can be solved with this method are:
remove duplicates from a sorted list
find if a list has a cycle (Floyd's tortoise and hare algorithm)
Coding challenge
The coding challenge of last week was Unique Number of Occurrences. The problem asks to check if the number of occurrences of each value in an array of integers is unique.
The problem is simple, but it’s necessary to be careful. Indeed, the problem asks to check if the frequencies of the elements are unique and not if the elements are unique.
The best approach is to use a hash table to count the frequencies of each number and a hash set to check if there are duplicated frequencies. Here is the code for the solution.
The coding challenge of next week is Pascal's Triangle.
Interesting Tweets
Being an entrepreneur requires a different skill set than being an engineer. Here is an excellent summary that I found very valuable and insightful.
Design patterns can be helpful not only for productive code but also for testing. For example, here is an excellent example of using the builder pattern. With builders, you only need to set those values required for the test. Others are automatically initialized with default values. The resulting code is much more readable.
Every parent went through a phase where their kids struggled to accept losses when we played games. It also happened to my son. He started crying and didn't want to play anymore. But every time, I pointed out how fun we were playing and showed how I was accepting to lose every time this happened. So now he can control his reactions much better.
