Topics 10
Last updated
Last updated
What are some of the algorithms you should know before taking system design interviews?
I put together a list and explained why they are important. Those algorithms are not only useful for interviews but good to understand for any software engineer.
One thing to keep in mind is that understanding “how those algorithms are used in real-world systems” is generally more important than the implementation details in a system design interview.
What do the stars mean in the diagram? It’s very difficult to rank algorithms by importance objectively. I’m open to suggestions and making adjustments.
Five-star: Very important. Try to understand how it works and why.
Three-star: Important to some extent. You may not need to know the implementation details.
One-star: Advanced. Good to know for senior candidates.
Over to you: did I miss anything important on the list? Which ones do you know and which you don’t?
A messaging solution (Firebase) can be used to support the notification push.
The diagram below shows how Firebase Cloud Messaging (FCM) works.
FCM is a cross-platform messaging solution that can compose, send, queue, and route notifications reliably. It provides a unified API between message senders (app servers) and receivers (client apps). The app developer can use this solution to drive user retention.
Steps 1 - 2: When the client app starts for the first time, the client app sends credentials to FCM, including Sender ID, API Key, and App ID. FCM generates Registration Token for the client app instance (so the Registration Token is also called Instance ID). This token must be included in the notifications.
Step 3: The client app sends the Registration Token to the app server. The app server caches the token for subsequent communications. Over time, the app server has too many tokens to maintain, so the recommended practice is to store the token with timestamps and to remove stale tokens from time to time.
Step 4: There are two ways to send messages. One is to compose messages directly in the console GUI (Step 4.1,) and the other is to send the messages from the app server (Step 4.2.) We can use the Firebase Admin SDK or HTTP for the latter.
Step 5: FCM receives the messages, and queues the messages in the storage if the devices are not online.
Step 6: FCM forwards the messages to platform-level transport. This transport layer handles platform-specific configurations.
Step 7: The messages are routed to the targeted devices. The notifications can be displayed according to the configurations sent from the app server [1].
Over to you: We can also send messages to a “topic” (just like Kafka) in Step 4. When should the client app subscribe to the topic?
VISA, Mastercard, and American Express act as card networks for clearing and settling funds. The card acquiring bank and the card issuing bank can be – and often are – different. If banks were to settle transactions one by one without an intermediary, each bank would have to settle the transactions with all the other banks. This is quite inefficient.
The diagram shows VISA’s role in the credit card payment process. There are two flows involved. Authorization flow happens when the customer swipes the credit card. Capture and settlement flow occurs when the merchant wants to get the money at the end of the day.
🔹Authorization Flow Step 0: The card issuing bank issues credit cards to its customers.
Step 1: The cardholder wants to buy a product and swipes the credit card at the Point of Sale (POS) terminal in the merchant’s shop.
Step 2: The POS terminal sends the transaction to the acquiring bank, which has provided the POS terminal.
Steps 3 and 4: The acquiring bank sends the transaction to the card network, also called the card scheme. The card network sends the transaction to the issuing bank for approval.
Steps 4.1, 4.2, and 4.3: The issuing bank freezes the money if the transaction is approved. The approval or rejection is sent back to the acquirer, as well as the POS terminal.
🔹Capture and Settlement Flow Steps 1 and 2: The merchant wants to collect the money at the end of the day, so they hit ”capture” on the POS terminal. The transactions are sent to the acquirer in batches. The acquirer sends the batch file with transactions to the card network.
Step 3: The card network performs clearing for the transactions collected from different acquirers, and sends the clearing files to different issuing banks.
Step 4: The issuing banks confirm the correctness of the clearing files, and transfer money to the relevant acquiring banks.
Step 5: The acquiring bank then transfers money to the merchant’s bank.
Step 4: The card network clears the transactions from different acquiring banks. Clearing is a process in which mutual offset transactions are netted, so the number of total transactions is reduced.
In the process, the card network takes on the burden of talking to each bank and receives service fees in return.
Over to you: Do you think this flow is way too complicated? What will be the future of payments in your opinion?
To understand the process involved, we need to divide the “scan to pay” process into two sub-processes:
Merchant generates a QR code and displays it on the screen
Consumer scans the QR code and pays
Here are the steps for generating the QR code:
When you want to pay for your shopping, the cashier tallies up all the goods and calculates the total amount due, for example, $123.45. The checkout has an order ID of SN129803. The cashier clicks the “checkout” button.
The cashier’s computer sends the order ID and the amount to PSP.
The PSP saves this information to the database and generates a QR code URL.
PSP’s Payment Gateway service reads the QR code URL.
The payment gateway returns the QR code URL to the merchant’s computer.
The merchant’s computer sends the QR code URL (or image) to the checkout counter.
The checkout counter displays the QR code.
These 7 steps are completed in less than a second. Now it’s the consumer’s turn to pay from their digital wallet by scanning the QR code:
The consumer opens their digital wallet app to scan the QR code.
After confirming the amount is correct, the client clicks the “pay” button.
The digital wallet App notifies the PSP that the consumer has paid the given QR code.
The PSP payment gateway marks this QR code as paid and returns a success message to the consumer’s digital wallet App.
The PSP payment gateway notifies the merchant that the consumer has paid the given QR code.
Over to you: I have detailed how to pay using a dynamic QR code. It is dynamic because the QR code is dynamically generated each time. But sometimes, you could pay by scanning a printed QR code in a merchant’s shop, which is called the static QR code. Do you know how a static QR code works?
Designing a system with extremely high concurrency, high availability, and quick responsiveness needs to consider many aspects 𝐚𝐥𝐥 𝐭𝐡𝐞 𝐰𝐚𝐲 𝐟𝐫𝐨𝐦 𝐟𝐫𝐨𝐧𝐭𝐞𝐧𝐝 𝐭𝐨 𝐛𝐚𝐜𝐤𝐞𝐧𝐝.
𝐃𝐞𝐬𝐢𝐠𝐧 𝐩𝐫𝐢𝐧𝐜𝐢𝐩𝐥𝐞𝐬:
Less is more. Fewer elements on the web page, fewer data queries to the database, fewer web requests, fewer system dependencies
Short critical path. Fewer hops among services or merge into one service
Async. Use message queues to handle high TPS
Isolation. Isolate static and dynamic contents, isolate processes and databases for rare items
Overselling is bad. When and how to manage the inventory is important
User experience is important. We don’t want to inform users that they have successfully placed orders but later tell them no items are available
Let’s try something different today.
Assuming in a system design interview, you are asked to design a distributed message queue. The following requirements are given:
Producers send messages to a message queue.
Consumers consume messages from a message queue.
Messages can be consumed repeatedly or only once.
The diagram below shows the naive design.
🔹Is the design correct? 🔹Do you think the design satisfies all the requirements? 🔹If not, what else should be added?
Feel free to make your assumptions, comment with anything you think might be helpful, or post your design.
Google authenticator is commonly used for logging into our accounts when 2-factor authentication is enabled. How does it guarantee security?
Google Authenticator is a software-based authenticator that implements a two-step verification service. The diagram below provides detail.
There are two stages involved:
Stage 1 - The user enables Google two-step verification
Stage 2 - The user uses the authenticator for logging in, etc.
Let’s look at these stages.
𝐒𝐭𝐚𝐠𝐞 1 Steps 1 and 2: Bob opens the web page to enable two-step verification. The front end requests a secret key. The authentication service generates the secret key for Bob and stores it in the database.
Step 3: The authentication service returns a URI to the frontend. The URI is composed of a key issuer, username, and secret key. The URI is displayed in the form of a QR code on the web page.
Step 4: Bob then uses Google Authenticator to scan the generated QR code. The secret key is stored in the authenticator.
𝐒𝐭𝐚𝐠𝐞 2 Steps 1 and 2: Bob wants to log into a website with Google two-step verification. For this, he needs the password. Every 30 seconds, Google Authenticator generates a 6-digit password using the TOTP (Time-based One Time Password) algorithm. Bob uses the password to enter the website.
Steps 3 and 4: The frontend sends the password Bob enters to the backend for authentication. The authentication service reads the secret key from the database and generates a 6-digit password using the same TOTP algorithm as the client.
Step 5: The authentication service compares the two passwords generated by the client and the server, and returns the comparison result to the frontend. Bob can proceed with the login process only if the two passwords match.
Is this authentication mechanism safe?
Can the secret key be obtained by others? We need to make sure the secret key is transmitted using HTTPS. The authenticator client and the database store the secret key, and we need to make sure the secret keys are encrypted.
Can the 6-digit password be guessed by hackers? No. The password has 6 digits, so the generated password has 1 million potential combinations. Plus, the password changes every 30 seconds. If hackers want to guess the password in 30 seconds, they need to enter 30,000 combinations per second.
You have just developed a new website. What does it take to be ranked at the top?
We need to understand how search engines rank websites and optimize our website to be search engine-friendly. This is called SEO (Search Engine Optimization).
A search engine works in 3 stages:
The crawler reads the page content (HTML code) and follows the hyperlink to read more web pages.
The preprocessor also works in 3 steps:
It removes HTML tags and ‘Stop’ words, which are words like ‘a’ or ‘an’ or ‘the.’ It also removes other noise that is not relevant to the web page's content, for example, the disclaimer.
Then the keywords form structured indices, called forward indices and inverted indices.
The preprocessor calculates the hyperlink relationships, for example, how many hyperlinks are on the web page and how many hyperlinks point to it.
When a user types in a search term, the search engine uses the indices and ranking algorithms to rank the web pages and presents the search results to the user.
How do we make our website rank higher in search results? The diagram below shows some ways to do this.
Optimize website structure:
We need to make it easier for the crawler to crawl our website. Remove anything the crawler cannot read, including flash, frames, and dynamic URLs. Make the website hierarchy less deep, so the web pages are less distant from the main home page.
The URLs must be short and descriptive. Try to include keywords in the URLs, as well. It will also help to use HTTPS. But don’t use underscore in the URL because that will screw up the tokenization.
Choose the keywords to optimize for:
Keywords must be relevant to what the website is selling, and they must have business values. For example, a keyword is considered valuable if it’s a popular search, but has fewer search results.
Optimize the web page
The crawler crawls the HTML contents. Therefore the title and description should be optimized to include keywords and be concise. The body of the web page should include relevant keywords.
Another aspect is the user experience. In May 2020, Google published Core Web Vitals, officially listing user experience as an important factor of page ranking algorithms.
External link
If our website is referenced by a highly-ranked website, it will increase our website’s ranking. So carefully building external links is important. Publishing high-quality content on your website which is useful to other users, is a good way to attract external links.
Over to you: What are your top SEO recommendations?
Companies are moving towards API-first.
Multi-cloud and hybrid architectures.
APIs as products.
Explosion of API gateways and service meshes.
More protocols and more choices for developers.
Shifting left on security.
