Balancing Lru And Lfu
Both LRU and LFU have advantages for particular data access patterns, so its common to see them combined in various ways to optimize performance. An LFRU replacement policy is one such example. It takes into account both recency and frequency by starting with LFU, and then moving to LRU if the data is used frequently enough.
To respond to changing data access patterns, an ARC takes the LFRU approach and then dynamically adjusts the amount of LFU and LRU cache space based on recent replacement events. In practice, ARC will outperform LFU and LRU, but requires the system to tolerate much higher complexity which isnt always feasible.
ARCs are valuable when access patterns vary, for example a search engine where sometimes requests are a stable set of popular websites, and sometimes requests cluster around particular news events.
Clarify The Problem And Establish Design Scope
The first thing you’ll want to do after your interviewer gives you the problem is to take a few minutes to ask some clarifying questions and figure out what exactly they are looking for.
The worst thing you could do here is just start off in the completely wrong direction because you didn’t take the time to ask a few questions. You have a limited amount of time during the interview, so you want to make sure you focus on what’s important.
Here are some examples of questions you might ask:
What are the use cases / features of the app?
In this article we will be using YouTube as an example. There are hundreds of different features you could design like ad delivery, authentication, recommendation algorithms, comments, video upload, video processing, and many others.
During an interview you only have time to cover a few of those, so make sure to ask the interviewer questions to figure out what they want you to focus on designing.
How many users are expected / what is the likely traffic volume?
The complexity of the system will depend on the amount of traffic it needs to handle, so make sure to gather this information.
You don’t want to over-engineer things if the traffic is relatively low and you also don’t want to get stuck with an app that can’t scale because you didn’t design it properly.
Ask questions like how many users the app will have, the average amount of data per request, how long data needs to be stored, and how reliable and available does the system need to be?
Design An Api Rate Limiter System For Github Or Firebase Sites
API Rate Limiters limit the API calls that a service receives in a given time period for avoiding request overload. This question can start with the coding algorithm on a single machine to the distributed network.
- What are some of the Required Features?
- What is the required request count per hour or second? Let us assume that the requirement can be 10 requests per second.
- Should the limiter notify the user if the requests are blocked?
- The limiter should handle traffic suitable according to the scale.
Also Check: What Questions Will I Be Asked In An Interview
Determine Rough Capacity Estimates
Using the information you gathered during the first step, you can begin to make some rough estimates and generalizations for things like storage and bandwidth requirements.
This process will involve some basic math like multiplying the number of users by the average request size and the amount of requests each user is expected to make daily.
Design Dropbox/google Drive/google Photos
Design a file or image hosting service that allows users to upload, store, share, delete and download files or images on their servers and provides synchronization across various devices.
Things to discuss and analyze:
- Approach to upload/view/search/share/download files or photos from any device.
- Service should support automatic synchronization between devices, i.e., after updating a file on one device, it should get synchronized on all devices.
- ACID property should be present in the system.
- Approach to track permission for file sharing.
- Allowing multiple users to edit the same document.
- The system should support storing large files up to a GB.
Summarize And Answer Questions
Last but not least is the final step of your system design interview answer. This concluding step will consist of, once more, reviewing the system requirements and summarizing and justifying all the design decisions you made along the way.
Be sure to thoroughly explain why you think these decisions are the most prudent regarding their tradeoffs. Don’t forget to mention possible alternatives you could have taken along with their tradeoffs.
It is likely your interviewer will ask you questions about aspects of your design here, as well.
Design Facebooks Newsfeed System
Facebooks newsfeed allows users to see what is happening in their friend’s circle, liked pages and groups followed.
- What are some of the Required Features?
- Generate newsfeed using posts from other system entities that the user follows.
- Newsfeed posts can be of text, image, audio or video format.
- Append new posts to the users newsfeed in close to real-time.
Don’t Miss: What Is One Way Video Interview
Tradeoffs And Resolving Bottleneck
Design interviews are open-ended conversations so there is no single answer and every decision will have a tradeoff when you will present your architecture and your thought process to the interviewer. The complex system always requires compromises so you need to tell them different approaches, their pros, and cons, and why would you choose one over another.
- Which database fits in your system and why?
- Why would you choose a specific technology in different layers or components?
- Which frameworks can be good for your design and which one do you need to choose?
- What are the different security options available to keep your data safe and which one you would choose?
You also need to think about and resolve the bottlenecks like what kind of failure can occur in your system and whats the solution for that. Do you need to keep a backup or you will take the help of any other resources? Do you have any backup for your data in case your server crashes and you lose the entire data? How would you monitor the performance of the service? If any component fails then whats the solution to run your system smoothly and properly? Basically, you should have an organized and clear plan to deal with all these kinds of critical failures in your system. Quick Tips:
Grokking The Advanced System Design Interview
This is an advanced course to learn about Software architecture and System Design from Educative, one of my favorite interactive learning platforms, and this course is like the advanced version of their popular Grokking The System Design course.
Designing systems and architecting software is one of the key responsibilities of a senior software engineer. But itâs difficult to master without practice, and few people have the chance to work on large-scale projects from the ground up.
This advanced System design course solves that problem. It provides you a chance to dive deep into the most common types of distributed systems including key-value store, distributed messaging and streaming system, distributed file storage systems, and more.
Along the way, you will also learn about a set of design patterns that are used to solve some of the most common problems in distributed systems. These are especially handy in system design interviews.
If you have an interview coming up, or youâre interested in software design/architecture, then you can use this course to level up your system design skills and prepare better.
Here is the link to join this course â Grokking the Advanced System Design Interview
Read Also: How To Interview A Babysitter Or Nanny
What Is Cap Theorem
CAP theorem says that a distributed system cannot guarantee C, A and P simultaneously. It can at max provide any 2 of the 3 guarantees. Let us understand this with the help of a distributed database system.
- Consistency: This states that the data has to remain consistent after the execution of an operation in the database. For example, post database updation, all queries should retrieve the same result.
- Availability: The databases cannot have downtime and should be available and responsive always.
- Partition Tolerance: The database system should be functioning despite the communication becoming unstable.
The following image represents what databases guarantee what aspects of the CAP Theorem simultaneously. We see that RDBMS databases guarantee consistency and Availability simultaneously. Redis, MongoDB, Hbase databases guarantee Consistency and Partition Tolerance. Cassandra, CouchDB guarantees Availability and Partition Tolerance. Complete Video Tutorial.
How Would You Design A Search Engine
Sometimes search engines are needed within a specific department of a company to systematically locate an item or important employee information. Hiring managers want to see that you can tailor designs to the needs of the company. You can detail some of the overall architecture and explain it, using the foundation below. You can also consider discussing any other relevant issues such as website front-end performance, testing search engine improvements and integrating previous search data and trends in indexing.
Example:”Before I relocated here, I was working on a project similar to this one. The search engine I had been enlisted to create needed to work with keyword searches. I began by building an indexer, which is a piece of software that crawls and produces results in a data structure. The crawler would put web page links together and group them or dump them into sets. Then the indexer ran as part of a reduce job to single things out. For each website, the number of links was calculated and analyzed for presentation. I had the crawl set for H1 and H2, rather than H3s. Then I checked outbound links to avoid spammers. Lastly, I checked the serving results to verify that the design was working at optimal capacity and relevancy.”
You May Like: How To Prepare For An Engineering Interview
System Design Problem Solving Approach
To have a structured way to approach system design problems, you can follow these steps. Try to follow them when solving practice system design problems.
Ask clarifying questions. Specify all requirements to understand what exactly your design should do.
Often, system design problems are very vague, like “Design Twitter”. It is your responsibility to scope what exactly Twitter functionality is, how many users we will need to support, and so on.
Scope business requirements.
It is a good idea to think about what your design should achieve from the business perspective. What would we or potential stakeholders mostly care about? Should we be able to handle millions of users? Should your service have 99.99% uptime? Should each request be processed in 300ms? Should the data be safely replicated and never lost?
System design is about engineering, but behind most systems, there are real-world and business requirements. Show that you understand this and care about it.
Do estimations. Estimate the number of users you will need to support, disk space and network bandwidth you will need, and so on.
Before designing a performant system, it is good to have an idea of how performant it really should be. Designing Twitter for 10 and 1000000 people are two very different tasks. Use the requirements from the previous two steps for your estimations.
Think about the extra details of your system.
How would you test it? What about security? What are alternative designs?
How To Approach A System Design Interview Question
How to tackle a system design interview question.
The system design interview is an open-ended conversation. You are expected to lead it.
You can use the following steps to guide the discussion. To help solidify this process, work through the System design interview questions with solutions section using the following steps.
You May Like: What Answers To Give In A Job Interview
What Do You Understand By Content Delivery Network
Content delivery network or in short CDN is a globally distributed proxy server network that serves content from locations close by to the end-users. Usually, in websites, static files like HTML, CSS, JS files, images and videos are served from CDN.
Using CDN in delivering content helps to improve performance:
- Since users receive data from centres close to them as shown in the image below, they don’t have to wait for long.
- Load on the servers is reduced significantly as some of the responsibility is shared by CDNs.
There are two types of CDNs, they are:
- Push CDNs: Here, the content is received by the CDNs whenever changes occur on the server. The responsibility lies in us for uploading the content to CDNs. Content gets updated to the CDN only when it is modified or added which in turn maximises storage by minimising the traffic. Generally, sites with lesser traffic or content work well using push CDNs.
- Pull CDNs: Here new content is grabbed from the server when the first user requests the content from the site. This leads to slower requests for the first time till the content gets stored/cached on the CDN. These CDNs minimizes space utilized on CDN but can lead to redundant traffic when expired files are pulled before they are changed. Websites having heavy traffic work well when used with pull CDNs.
Top 25 System Design Interview Questions For Programmers
Without any further ado, here is the list of some of the most popular System design or Object-oriented analysis and design questions to crack any programming job interview.
1. How do you design the Vending Machine in Java? You need to write code to implement a Vending machine that has a bunch of products like chocolates, candy, cold-drink, and accept some coins like Nickle, Dime, Quarter, Cent, etc. Make sure you insert a coin, get a product back, and get your chance back. Also, write the Unit test to demonstrate that these common use cases work. If you get stuck you can read my two-part articles about solving these classical system design questions.
2. How do you design a URL Shortening service like goo.gl or bit.ly? This one is another common System design question. You have given a long URL, how would you design a service that would generate a shorter and unique alias for it? If you are not familiar with URL shortener service have a look at some of the popular ones like goo.gl from Google and bit.ly which is used by Twitter.
Make sure to provide database schema and rationale behind some design decisions like how long you keep the data, how to get stats and analytics etc. If you get stuck, you can follow the solution given on Grokking the System Design Interview course on Educative.
If you need a refresher on Data Structure then you can check out Data Structure and Algorithm in Java course and If you feel stuck you can check out my solution here.
You May Like: What To Say After Interview Email
Design A Parking Lot System
- What are some of the Required Features?
- The parking lot can have multiple levels where each level has multiple rows for parking spots.
- The parking lot can support parking for cars, buses, motorcycles hence spots can be of multiple sizes.
- Consider the parking lot capacity at the time of designing the system.
- Design appropriate pricing for each parking spot.
How Do You Prepare For A System Design Interview
Unlike a coding interview question, System Design Interviews are free-form discussions, and theres no right or wrong answer. Instead, the interviewer is trying to evaluate the candidates ability to hold a conversation about the different aspects of the system and assess the solution based on the requirements that might evolve during the conversation.
The best way to think about the conversation is to imagine that you and a colleague are asked to design a large-scale system, and you are hashing out the details on the whiteboard. You are understanding the requirements, scope, and constraints before proposing a solution.
So how do you design a system in an interview if you have never built one in real life? To crack your system design interview, youll need to prepare in three areas:
Each of these dimensions flows into the next.
If you dont know the fundamentals, you wont be prepared to architect a service if you dont know how to put those systems together, you wont be able to design a specific solution once youve designed large-scale systems, you can take lessons learned and integrate them into your base knowledge.
Lets look at each of these dimensions in order.