Introduction
What is system design?
System design is the process of designing the elements of a system such as the architecture, modules and components, the different interfaces of those components and the data that goes through that system. It is meant to satisfy specific needs and requirements of a business or organization through the engineering of a coherent and well-running system.
What is the purpose of system design
The purpose of the System Design process is to provide sufficient detailed data and information about the system and its system elements to enable the implementation consistent with architectural entities as defined in models and views of the system architecture.
What are the elements of a system?
- Architecture – This is the conceptual model that defines the structure, behavior and more views of a system. We can use flowcharts to represent and illustrate the architecture.
- Modules – This are components that handle one specific tasks in a system. A combination of the modules make up the system.
- Components – This provides a particular function or group of related functions. They are made up of modules.
- Interfaces – This is the shared boundary across which the components of a the system exchange information and relate.
- Data – This the management of the information and data flow.
How do you design a system?
(we are using a chat app as an example)
-
- Step #1 understand the requirements or the problem. In most cases, when you given a new feature or a new system to develop, you are not given all the little details that you need to know. It is always a good idea to ask questions about the requirements. You might not have the domain knowledge to even understand the requirements. For example, you have to design tinder but you have never used a dating app before. If that is the case, ask for more information. The better you understand the requirements the more likely you will design a system that meets the expected outcome. One of the many important things you need to know(from the beginning) is the scope of the problem. You have to figure out what you are working to solve and what can be pushed until later. You also need to know how you will need to scale the system.
Questions
– What kind of chat app shall we design? 1 on 1 or group based?
– Is this a mobile app? Or a web app? Or both?
– What is the scale of this app? A startup app or massive scale?
– For group chat, what is the group member limit?
– Is there a message size limit?
– How long shall we store the chat history?
– What network bandwidth usage are we expecting? This will be crucial in deciding how we will manage traffic and balance load between servers. - Step #2 propose high-level design. In this step, draw up a high-level design using wireframe or flow chart that represents the players/entities of the system. You should draw this flow chart from the requirements. Make sure you confirm with product owner that this is what he has in mind. For our example, here are the main entities we are dealing with: sender, receiver, and chat service which is what connects them. Don’t forget to focus on the main functionalities of the system and not the little details.
You also can walk through how the system will function from a very high level(1000 ft view).
- Step #1 understand the requirements or the problem. In most cases, when you given a new feature or a new system to develop, you are not given all the little details that you need to know. It is always a good idea to ask questions about the requirements. You might not have the domain knowledge to even understand the requirements. For example, you have to design tinder but you have never used a dating app before. If that is the case, ask for more information. The better you understand the requirements the more likely you will design a system that meets the expected outcome. One of the many important things you need to know(from the beginning) is the scope of the problem. You have to figure out what you are working to solve and what can be pushed until later. You also need to know how you will need to scale the system.
- Step #3 deep dive. In this step, you dive into APIs and endpoints. You also dive into the data model of each entity in the system.
For endpoints
Users: create, update
Messages: message, timeCreated, destination, etcFor data model
User: firstName, lastName, displayName, email, password, etc
Group: id, list of usersAlso talk about which programming language, framework, cloud infrastructure, etc to use.
You also walk through a happy path of how a user uses the system.
- Step #4 identify and resolve problems. Try to discuss as many bottlenecks as possible and different approaches to mitigate them.
Max Subset Sum No Adjacent
Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.
If the input array is empty, the function should return 0.
Sample input
[75, 105, 120, 75, 90, 135]
Sample output
330 = 75 + 120 + 135
Solution
Time Complexity: O(n)
Space Complexity: O(1)
static int maxSubsetSumNoAdjacent(int[] array) {
int answer = 0;
if (array.length == 0) {
return 0;
} else if (array.length == 1) {
return array[0];
}
int first = Math.max(array[0], array[1]);
int second = array[0];
int current = 0;
for (int i = 2; i < array.length; i++) {
current = Math.max(first, second + array[i]);
second = first;
first = current;
}
answer = first;
return answer;
}
Minimal Waiting Time
You’re given a non-empty array of positive integers representing the amounts of time that specific queries take to execute. Only one query can be executed at a time, but the queries can be executed in any order.
A query’s waiting time is defined as the amount of time that it must wait before its execution starts. In other words, if a query is executed second, then its waiting time is the duration of the first query; if a query is executed third, then its waiting time is the sum of the durations of the first two queries.
Write a function that returns the minimum amount of total waiting time for all of the queries. For example, if you’re given the queries of durations
[1, 4, 5], then the total waiting time if the queries were executed in the order of [5, 1, 4] would be (0) + (5) + (5 + 1) = 11. The first query of duration 5 would be executed immediately, so its waiting time would be 0, the second query of duration 1 would have to wait 5 seconds (the duration of the first query) to be executed, and the last query would have to wait the duration of the first two queries before being executed.
Note: you’re allowed to mutate the input array.
Solution
Use a map to store previous total waiting time per index.
Time Complexity: O(n log n)
Space Complexity: O(1)
Algorithm used: Greedy Algorithm
static int getMinimumWaitingTime(int[] queries) {
/**
* sort the array to help getting the minimum total waiting time
*/
Arrays.sort(queries);
int size = queries.length;
if (size <= 1) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
int totalWaitingTime = 0;
for (int i = 0; i < queries.length; i++) {
int currentWaitingTime = 0;
int previousTotalWaitingTime = 0;
if (i != 0) {
currentWaitingTime = queries[i - 1];
previousTotalWaitingTime = currentWaitingTime + map.get(i - 1);
}
map.put(i, previousTotalWaitingTime);
totalWaitingTime += previousTotalWaitingTime;
}
return totalWaitingTime;
}
Nth Fibonacci
The Fibonacci sequence is defined as follows: the first number of the sequence is 0, the second number is 1, and the nth number is the sum of the (n – 1)th and (n – 2)th numbers. Write a function that takes in an integer n and returns the nth Fibonacci number.
I have a solution here.
Palindrome Check
Write a function that takes in a non-empty string and that returns a boolean representing whether the string is a palindrome.
A palindrome is defined as a string that’s written the same forward and backward. Note that single-character strings are palindromes.
Solution
Loop through half of the string. Compare each character from one half to the each character from the other half.
static boolean isPalindrome(String str) {
for (int i = 0, x = str.length() - 1; i < str.length() / 2; i++, x--) {
if (str.charAt(x) != str.charAt(i)) {
return false;
}
}
return true;
}