The Polymathic Engineer

Share this post

Fast and Slow

newsletter.francofernando.com

Fast and Slow

How to manipulate linked lists using the fast and slow pointer method. Plus a beginner-friendly introduction to relational databases.

Franco Fernando
Jan 17
2
Share this post

Fast and Slow

newsletter.francofernando.com

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.

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

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.

Twitter avatar for @rpandey1234
Rahul Pandey (joinTaro.com) @rpandey1234
One year ago, I left a leadership role at Meta to go all-in on starting a company. We talked to 1000s of engineers, created 100s of videos, and built 3 apps in the pursuit of creating something meaningful. Here are the 10 lessons every entrepreneur needs to hear:
5:26 PM ∙ Jan 11, 2023
243Likes14Retweets

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.

Twitter avatar for @dmokafa
Daniel Moka⚡ @dmokafa
Don't pollute your tests with irrelevant test data! A test should read like a story containing all the details to grasp the story. Irrelevant data increases noise and decreases readability. You can use builder pattern to hide what is irrelevant, and reveal what is important.
Image
2:58 PM ∙ Jan 10, 2023
94Likes17Retweets

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.

Twitter avatar for @sarah_edo
Sarah Drasner @sarah_edo
When we play games, I don’t let my kids win. But I hope that they do.
5:00 AM ∙ Jan 12, 2023
542Likes11Retweets

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

Share this post

Fast and Slow

newsletter.francofernando.com
Comments
TopNewCommunity

No posts

Ready for more?

© 2023 Franco Fernando
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing