Search Results

Hello coders! Today, let's solve yet another leetcode problem, Longest Common Prefix. This is an article in our series leetcode problem solutions, so make sure to check out other leetcode problem solutions in this series, after you finish this one 😉. Problem Statement Find the longest common prefix from the given array of strings. Return an empty string "", if no common prefix is found. Example 1: Input: strs = ["preview","prepare","prevent"] Output: "pre" Example 2: Input: strs = ["pan","can","dog"] Output: "" Explanation: There is no common prefix among the input strings. Constraints: 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lowercase English letters. Solution This is marked as an easy problem on leetcode, and it is indeed an easy solution except for a couple of edge cases that we have to cover. Here we are asked to find the longest common prefix from the given array of strings. A prefix is a continuous sequence of letters at the beginning of the string. For instance, for string "leetcode" these are the possible prefixes: "l" "le" "lee" "leet" "leetc" and so on. We need to find the common prefix that is longest among all the strings in the given string array. For example, if strs = ["can", "cant", "candy"], the longest common prefix here is "can". Similarly for strs = ["bad", "bat", "bank"], the longest common prefix is "ba". This problem can be easily solved using a O(m*n) solution. In this solution, we compare each character in the first string with the corresponding characters in all the others strings in the given string array. If all corresponding characters match we continue checking. We stop checking and return the result as soon as a mismatch is found. Algorithm Here is how the algorithm works: Create two for loops. Outer loop iterates through the characters in the first string in the array. Inner loop iterates through the characters in all the others strings in the array. In each iteration, we check if each character in the first string matches the corresponding characters in all the others strings in the array. If they match, continue iterating. If there is a mismatch in any of the strings, stop the iteration and return the prefix up to which there was a match as the result. Simulation Lets understand this algorithm with an example. Consider strs=["flower", "flow", "flight"]. The expected result here is "fl" which is the longest common prefix among the three strings in the input array. Lets see how our algorithm works to arrive at the result. The algorithm uses two for loops. Outer loop is used to keep track of the letter in the strings we compare. Inner loop keeps track of the strings in the array. i is the outer loop index and it runs from 1st letter in the 1st string till the last letter (Index 0 to n-1. Where n is the length of the first string). j is the in inner loop index and it runs from 2nd string in the array till the last string (Index 1 to m-1. Where m is the length of the array). Initially we start i=0 and j=1, which means that we will be comparing the first letter in the first string i.e. "f" with the first letter in the 2nd string "f". As you can see the first letters of both strings match, so we increment j by 1. Now i=0 and j=2. Again the first letters in both these strings match. Now, we have reached the end of the array, and the first characters in all the strings match. Therefore, we can consider it for our result. So, our current result="f". We now move to the next iteration of the outer loop i=1 and j=1. Again, the 2nd characters of first and second strings match, so increment j by 1. Now i=1 and j=2. As you see from above diagram, the second letters of all strings in the array match, hence we add it to our result. We perform similar steps in the third iteration of the outer loop i=2 and j=1. Again as seen in above diagram 3rd characters of 1st and second strings match. So, we move to i=2 and j=2. Now if you observe, 3rd character of first string is "o", but the 3rd character of third string is "i". Clearly they do not match, which means that the 3rd character is not same in all strings in the given input array, hence it cannot be part of our result. At this point we need to stop the algorithm and return "fl" as the result. One edge that we need to cover here for other examples is if i goes out of bounds in either strings that we are comparing. In such cases we need to stop the iteration and return the matched prefix so far as result. We can detect such cases using the condition i>=length(strs[j]) as shown in code below. Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Code Complexity Analysis Time Complexity In this algorithm, we iterate through the characters in the first string and compare it with the corresponding characters in the rest of the strings. So, if m is the length of the first string and n is the total number of strings in the array, in the worst case outer loop runs m times and inner loop runs (n-1) times. So the worst case time complexity of this solution is O(m*n). Space Complexity The space complexity is O(1) because the algorithm does not use any extra space. That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers. If you found value in this article, we encourage you to subscribe to both our website and YouTube channel. Your support fuels our motivation to continue producing more insightful articles like this one in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.

In our last article we solved Roman to Integer problem. Today let's discuss another leetcode problem Integer to Roman. Problem Statement Convert the given integer to a roman numeral. As we saw in our previous article, roman numerals are represented using seven different symbols as shown below: For example, in Roman numerals: 1 is written as I. 2 is written as II i.e. by adding two "ones" I+I together. 12 is written as XII which is X + II. Number 27 is XXVII, which is XX + V + II. Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting 1 from 5 (i.e. V - I). Similarly, 9 is written as IX i.e. X - I. There are six such instances in roman numerals where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Note: For a quick recap of roman numerals you can refer this article. Constraints: 1 <= num <= 3999 Examples Example 1: Input: num = 3 Output: "III" Explanation: 3 is represented as 3 ones. Example 2: Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3. Example 3: Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. Solution To solve this problem, we need to first extend the given roman to integer table to include all the exceptional cases. We also need to arrange the values in this table in decreasing order (we will see why this is needed in more detail later in this article). With these changes our new table would look like this: Now with the modified table in place let's see how we can convert a given integer value to roman numeral. next to map the given integer to roman numeral we break the given integer first and then map it to the respective roman numeral. We can break any given integer by dividing it with appropriate values. For example, if 153 is the given integer, the corresponding roman value is CLIII. To get this, we first break 153 into 3 parts: 100, 50 and 3. Next, we map each of these parts into roman values i.e. 100 is mapped to C, 50 is mapped to L and 3 is mapped to III, which in turn gives us CLIII. Similarly, if 2024 is the given integer we break it into 2000, 20 and 4. This in roman numerals is MM, XX and IV respectively or MMXXIV. I hope you get an idea of how we need to approach this problem statement. Now let's see how we can translate this logic into code. Below algorithm shows how we can do this through code. Algorithm Create a list/array to store the extended integer to roman mapping, let call it intToRomanList. Store the integer to roman mapping in this list in decreasing order. Create a variable, let's say result to store the final result. Next, we traverse intToRomanList from start to end, and in each iteration, we perform the following steps: Divide the given number with the integer from intToRomanList. This will give us the no. of times we have to append the roman numeral. Example, if num=2000, if we divide it with M or 1000 from intToRomanList we get 2000/1000 = 2. This 2 is an indication that we need to append two M's i.e. MM in order to make a 2000. We will store this in a variable called count. Now, only if count is greater than 0 we need to append the corresponding roman numeral to the result variable. Example, if num=500, for intToRomanList values M:1000, count = (num / intToRomanList integer) = 500/1000 = 0, Therefore, we need not append it to the result variable. In the next iteration, intToRomanList key:value is 500:D, so, count = (num / intToRomanList integer) = 500/500 = 1, Now count is greater than 0, therefore we need to add it to result. After this we mod num with intToRomanList integer value to process its remaining part. Repeat a-c until we reach the end of intToRomanList. Finally return the value in result variable. I know this is a bit confusing 😁. To make it easier let me explain it with the help of an example. Let's say num=2024. First step is to create a list, lets create a list and name it intToRomanList. We will fill the list with the following key value pairs/values: {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Let's also declare a variable result and initialize it to "". Next traverse intToRomanList starting from the first pair 1000:M. {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Now, divide num with the current intToRomanList integer value i.e. 1000. This will give us the count (i.e. no. of times we need to append the current roman numeral to result). count = (num / intToRomanList integer) = (2024/1000) = 2 This indicates that we need to add the current roman numeral in intToRomanList which is M, twice to result. Therefore, we append result with MM. Now result=MM. Since 1000th place is now processed, we need to remove it from num, so mod it with 1000: num = num % 1000 = 2024 % 1000 = 24 After this we move to the next pair in intToRomanList 900:CM. {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Repeat the previous steps again: count = (num / intToRomanList integer) = (24/900) = 0 Now since count=0, no need to append anything to result. num = num % 900 = 24 % 900 = 24 Again, we move ahead in intToRomanList by one: {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} We follow the same procedure again: count = 24/500 = 0, hence result remains unchanged and, num = 24 % 500 = 24. In the same way count, result and num remain unchanged for 400:CD, 100:C, 90:XC, 50:L, 40:XL. So, let's skip to 10:X. {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} Now, count = 24/10 = 2, therefore result = "MM" + "XX"= "MMXX" num = 24 % 10 = 4. For 9:IX and 5:V again count, result and num remain unchanged. Now when our iteration reaches 4:IV, {1000:M, 900:CM, 500:D, 400:CD, 100:C, 90:XC, 50:L, 40:XL, 10:X, 9:IX, 5:V, 4:IV, 1:I} count = 4/4 = 1, therefore result = "MMXX" + "IV"= "MMXXIV" num = 4 % 4 = 0. We stop the iteration, after we process the last element in rMap 1:I and return whatever is present in result as the final result. Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python Solution Java Solution JavaScript Solution C Solution C++ Solution C# Solution Complexity Analysis Time Complexity: O(1) In this algorithm we iterate over a list of size 13, which does not depend on the input size of num. Inside the loop, it performs division and modulus operations, which are constant time operations. The code where we append to result also runs in constant time because the maximum possible value of count is limited and does not have any considerable impact on time complexity. Therefore, regardless of the value of num, the number of operations is bounded by a constant, leading to a time complexity of O(1). Space Complexity: O(1) The space complexity is also O(1) since the algorithm uses a fixed size list for its computation. That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers. If you found value in this article, we encourage you to subscribe to both our website and YouTube channel. Your support fuels our motivation to continue producing more insightful articles like this one in the future. Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there! Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.

This is another article in the series leetcode problem solutions. In this article we will be solving leetcode problem 13 Roman to Integer. Problem Statement Convert the given roman numeral into an integer value. Roman numerals are represented using seven different symbols as shown below: For example, in Roman numerals: 1 is written as I. 2 is written as II i.e. by adding two "ones" I+I together. 12 is written as XII which is X + II. Number 27 is XXVII, which is XX + V + II. Roman numerals are usually written from largest to smallest from left to right. However, there are certain exceptions to this rule, for example, 4 is not written as IIII, instead it is IV. This is written by subtracting one from five (i.e. V - I). Similarly 9 is written as IX i.e. X - I. There are six such instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Note: For a quick recap of roman numerals you can refer this article. Constraints: 1 <= s.length <= 15 s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). It is guaranteed that s is a valid roman numeral in the range [1, 3999]. Examples Example 1: Input: s = "III" Output: 3 Explanation: III = 3. Example 2: Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. Example 3: Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. Solution So, how can we approach the problem statement? Our objective here is to convert the given roman numeral to an equivalent integer value. If you observe carefully, you can see that we can get the required result by simply adding up all the roman numerals in the input. For example, if s="LVIII" is the given input, its equivalent integer value is 58, which can get by adding all roman numerals in the given input, i.e. result = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58. Similarly if CCLXXXIII is the input, the result would be, result = C + C + L + X + X + X + I + I + I = 100 + 100 + 50 + 10 + 10 + 10 + 1 + 1 + 1 = 283. But (It cannot be that simple! There is always a "but" isn't it 😉), as stated in the problem statement, there are exceptions, we cannot always get the required result simply by adding up all the roman literals in the given input all the time. For instance if s="CDXCVII" is the input, the correct result is 497, but if we do result = C + D + X + C + V + I + I, we get 100 + 500 + 10 + 100 + 5 + 1 + 1=717, which obviously is not the correct answer. The correct result should be (-C + D - X + C + V + I + I) = 497. So, how can we detect and handle such scenarios in our code where we have to subtract some values in order to get the needed output? Again, if you analyze the given input, for all cases where we have to do "addition only" to get the result, the adjacent numerals in the input are in decreasing order from left to right. If we consider our previous example again of s="LVIII", if we scan the input from left to right: L >= V >= I >= I >= I Similarly, for input s="CCLXXXIII", C >= C >= L >= X >= X >= X >= I >= I >= I Now, if you check the same for inputs where we have to do subtraction, you can see that it does not follow this decreasing order rule. For example, in case of s="CDXCVII", C < D and X < C. And you will observe a similar trend if you take any other input involving subtraction. So, what is the conclusion? From all the above observations, we can conclude that, if s="[N1][N2][N3]...."as we read adjacent values in the given input from left to right, as long as the left numeral >= right numeral, we add the left numeral to result, otherwise we subtract it from the result. We have to repeat this procedure for all the roman numerals in input to get the final result. Algorithm With the understanding that we have so far, we can use the sliding window algorithm to solve this problem. For any input s our algorithm needs to do the following set of steps: First, take a variable to store our result, lets name this variable as result. Traverse the given input s from left to right and compare each adjacent roman numerals. During comparison, If N1 >= N2, add N1 to result. If N1 < N2, subtract N1 from result. Move the window to the next set of adjacent numerals N2 and N3 and repeat step 3. Once all the numerals in s are compared, result will have the final answer, return result. To make it easier for you to understand, let me explain this algorithm with the help of an example. Example 1 Consider s="LVIII" which is the roman numeral for 58. First step is to create a result variable. Initially result=0. First we compare L and V as shown in below diagram. L > V (50 > 5), therefore we add L i.e. 50 to the result. Next we move our window ahead by one and compare V and I. V > I, hence we add V or 5 to the result. Now result = 50 +5 = 55. Again we move window ahead and compare I and I. I is equal to I, so we I to result. result = 55+1=56. We again move the window and compare the remaining 2 numerals, Since I is equal to I we add 1 again to the result making result=57. Finally we add the last remaining I to the result. Now result = 57 + 1 = 58 which is the required answer, so we return it as the final result. Example 2 Lets now take an example involving subtraction, s="DXCIX" which is 599. First we create variable result=0. Next we compare D and X. D > X, therefore we add D to result. result = 0 + 500=500 Next we compare X and C. X < C, therefore we subtract X from result. result = 500 - 10 = 490 Next we compare C and I. C > I, add C to result. result = 490 + 100 = 590 Next compare I and X. I < X, subtract I from result. result = 590 - 1 = 589 Finally add the remaining X to the result. result = 589 + 10 = 599, which is the required result. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Code Go Solution Python 3 Solution Java Solution JavaScript Solution C++ Solution C Solution Complexity Analysis Time Complexity: O(n) Since we iterate the given string s only once to get the result, if n is the length of s, the time complexity of this algorithm is O(n). Space Complexity: O(1) This algorithm uses a HashMap to store roman numerals. But since this is a fixed value (7 roman numerals) the space complexity is O(7) or in general we can say O(1). That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website and YouTube channel, your support motivates us to bring out more such articles in future. You can explore more such amazing articles from code recipe in our blogs section. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us on social media: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.

Introduction In the previous article we delved into the fascinating world of Go Generics and learnt how to incorporate it in our go programs. In this article we will explore yet another cool feature in Go, the go embed directive. Go has been one of the fastest growing programming languages in the recent years. It is known for its simplicity, robustness and performance. When it comes to features, the Go language is rapidly expanding with new features being added in each new release. The go:embed directive was one such feature which was introduced in go 1.16. This simple yet powerful feature lets you access and manage static assets such as configuration files, certificates and much more like never before! This article will help you with everything you need to know about the go:embed directive in order to leverage its benefits in your day to day work. What is go:embed directive? The first thing we need to know is that, the go:embed is a compiler directive. What this means is, all of the processing that happens when we use the go:embed directive in go, happens at compile time. It is a special directive that is used to include/embed files or directories directly into the compiled binary of our go program. How to use go:embed directive? Using the go embed feature is simple. To use this feature in our go program we simply need to add a comment line `// go:embed`, followed by a space and the path to the file or folder which needs to be embeded. This comment must be added directly above the variable into which we want to our embed files or folders. Both files and folders can be embeded. We can also use patterns or wildcard characters (such as *) along with the file/folder paths. The syntax for using go embed directive is as shown below: Syntax //go:embed var variableName embed.FS Patterns will be useful in cases where we have to embed multiple files or folders. For example to embed all the .txt files whose name starts with "config", you need to specify the following: //go:embed config*.txt var variableName embed.FS When the go compiler sees the `// go:embed` comment anywhere in the go code, it interprets it as a special comment. The compiler processes this comment and embeds the files mentioned in the directive directly into the variable that we have defined. This is particularly useful in scenarios where we have to bundle static assets, configuration files, templates, or any other type of data directly into our program binary. Remember all of this happens at compile time. So, you need to have these files in the mentioned path at compile time. Note: Go makes use of the embed package for processing the go embed directive. Example Lets understand this with the help of an example. Lets create a sample go project named sample-project. Create a text file example.txt in the current working directory where the main.go file is located. Your project structure should now look something like this: Now lets add some text to our example.txt file. sample-project/example.txt And then add following code to main.go. sample-project/main.go In the above example, the //go:embed example.txt comment indicates that the file example.txt in the projects' root directory should be embedded into the content variable. content is a variable of type embed.FS from embed package, which is a go core library. Now that example.txt is embeded into the content variable, we can access it using the ReadFile() method (from embed package) as shown in line 12 in the above code. Remember, the embed package needs to be imported (line 4) in order to use this feature. The embed directive and package are available from Go 1.16. So, you will only be able to use this feature if you are using Go 1.16 or later versions. Are you looking to learn new skills and crack interviews in top tech companies? Explore the materials below designed exactly for this purpose: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Reading files using os or ioutil package vs using go:embed Using Go os or ioutil Libraries When we use the go os or ioutil library to read files (method 1, method2), we are accessing those files at runtime. The file must be present on the file system when the program is executed. This method is suitable for use cases where our program needs to read files that are dynamic in nature (files whose content keeps changing) or to read files that are not available at the time of compilation (Only available at runtime). Using go:embed Directive The go:embed directive as mentioned earlier is used to embed files or folders at the time of compilation, directly into the compiled binary of the go program. This is the recommended approach for reading files with static content. Summary In summary, the decision on whether to choose approach 1 or approach 2 depends on our use case and we can choose either of them by considering the following main factors: Whether we want to perform read operation at compile time or runtime. Is it a file with frequently changing content or file with static content. Limitations The go:embed directive offers significant advantages, but it is also important for us to understand its limitations: Large Binaries: Since go:embed is a compile time directive it will have an impact on the size of our compiled binary (built using go build command), especially if the embeded files/folders are large. So, it is important that we take this into consideration and embed only those files/folders that our application really needs. Security: Since go:embed is usually used to store static files such as certificates, configurations and these files are directly stored within the binary, it is our responsibility to secure any sensitive information contained within these files. Not for Dynamic Content: As discussed earlier, go:embed directive is used for static files. If your application involves dynamically changing files, go:embed might not be the right choice, in such cases it is better considering the go os or io packages for reading files. Empty folders: Currently embedding empty folders is not supported by this feature. The go embed feature can only be used to embed files in the current working directory or subdirectories under it. It cannot be used to embed files outside the current directory. Conclusion The go:embed directive is a powerful tool that redefines the way developers manage static assets and resources. It simplifies deployment, reduces external dependencies and enables self contained applications. By understanding its benefits, knowing when to use it and recognizing its limitations, we as developers can harness the full potential of the go embed feature. We hope this article has helped you in this aspect and you will be able to make an informed choice the next time you have to use this feature in your go project. That's all we had to cover in this article, thank you for your time. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to Code Recipe, your support motivates us to bring out more such articles and videos in the future. You can explore more such amazing articles from code recipe in our blogs section and by visiting our Youtube channel. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited no. of users - Join now. Follow us on social media: Facebook, Twitter, LinkedIn, Tumblr, Instagram.

Problem Statement In our previous article we solved the string to integer problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 9 problem. Given an integer x, return true if x is a palindrome integer. An integer is a palindrome when it reads the same backward as forward. Example, 121 is a palindrome while 123 is not. Constraints: -2^31 <= x <= 2^31 - 1 Example Example 1 Input: x = 121 Output: true Example 2 Input: x = -121 Output: false Example 3 Input: x = 10 Output: false Solution This is one of the easier problems on leetcode and also an important one because the solution involves ingredients necessary to solve similar problems around number manipulation. Lets understand the problem statement first. In this problem we are given an integer value as input, our task is to write an algorithm that tells us whether the given number is a palindrome or not. So, what are palindromic numbers? A number is a palindrome if it remains same when its digits are reversed. In other words a number is a palindrome if we get the same sequence of digits whether we read the number from left to right or right to left. For example 121, 99, 2332 etc. are palindromic numbers. Solution 1 The first solution that might come to your mind when you look at this problem is to convert the given integer number to a string first, reverse it and then check if it is a palindrome or not as it is easier to reverse and compare individual characters in a string as compared to an integer. But converting an integer to a string is an extra overhead, is it possible to solve this problem by avoiding this extra overhead? It turns out this problem can be efficiently solved using the divide and mod operations. The idea is to reverse the given number by applying the divide (/) and mod (%) operations on it and then compare the reversed number with original number to see if it is a palindrome. If both original and reversed numbers are equal, then the given number is a palindrome, otherwise it is not a palindrome. To reverse the given number we need to do the following steps: Get individual digits from the given number from right to left using the mod operator. Put the digit obtained in step 1 into correct position in the reversed number. Discard the currently processed digit from the original number. Lets understand this with an example: Consider x = 123 is the given number. Lets take a temporary variable to store this given number, lets say tmp (this step is necessary because we need the original number x unmodified so that it can be compared with the reversed number in the final step). Also take a variable to store the reversed number, lets call it reversedNum. Initially reversedNum = 0. One by one we process each digit in tmp starting with the last digit 3. Extract last digit from tmp using the mod operator i.e. lastDigit = tmp%10 = 123 % 10 = 3. Next step is to move lastDigit to its correct base position in reversedNum. This step is similar to the leetcode 8 problem where we had to move converted digit to its correct base position. As in leetcode 8 problem we can accomplish this by multiplying reversedNum with 10 and then adding the lastDigit to it. So reversedNum = reversedNum * 10 + lastDigit = 0 * 10 + 3 = 3. Now that we have processed the last digit completely we need to remove it from tmp. We can do this using the divide operation, tmp = tmp/10 = 123/10 = 12. Repeat the above three steps again for digit 2 in tmp = 12. lastDigit = tmp%10 = 12 % 10 = 2 reversedNum = reversedNum * 10 + lastDigit = 3 * 10 + 2 = 32 tmp = tmp/10 = 12/10 = 1. Again we repeat these steps for the final digit in tmp = 1. lastDigit = tmp%10 = 1 % 10 = 1 reversedNum = reversedNum * 10 + lastDigit = 32 * 10 + 1 = 321 tmp = tmp/10 = 1/10 = 0 As you can see we have successfully reversed the given number 123. Now we compare the reversedNum 321 with original number x = 123, clearly these two are not equal, so it is not a palindrome, therefore we return a boolean false as result. We do all these operations in a loop. Once tmp = 0 we stop our loop. Note: We perform mod the given number specifically with 10 (and not some other number) because, when we do mod on any given number the remainder would result in the unit's place digit of that number. For Example: 123%10 = 3 (% is the mod or modulus symbol, which gives the remainder of the division as the result). We use %10 in this case to extract the unit's place digit in the number. But if we use any other number, it would not give us the exact digit. Implementation Language: Go Complexity Analysis Time Complexity: O(d) d here is the no. of digits in the given input number. Time complexity is O(d) because we have to check each digit in the given number at least once to determine if the given number is a palindrome. Space Complexity: O(1) No extra space is used. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Solution 2: Optimized solution 1 In solution 1 we are using extra space to store the input number in a temporary variable tmp. We do this because we need the original number x in order to compare it with the reversed number and therefore cannot manipulate the original number x. However we can avoid using the tmp variable by slightly modifying solution 1. The idea is to do the steps mentioned here to reverse the given number only up to the middle digit in x and then compare x with the reversedNum. Basically what we do here is reverse only half of the given number x and compare x with reversed number. This algorithm involves the following steps: Reverse half of the digits of the given number x. (Reversing is done using same steps described in solution 1). Once half of the digits in x are reversed, reversedNum will contain the reversed second half of the original input number and x (modified) will contain the first half of the original input number. For example if the given input is x = 123321, then after reversing half of the digits, reversedNum will be 123 and modified x will be 123. Now compare the modified x with the reversedNum. If both x and reversedNum are equal then return true as result, otherwise return false. Let take one more example to understand this. Consider x = 1221 is the given number, our algorithm reverses the last two digits in x i.e. 21 (until middle digit). So, at the end of our loop x = 12 and reversedNum = 12. Now compare (x, reversedNum) and return the result. Note: If x contains odd number of digits as in x = 12321, at the end of our loop reversedNum = 123 and x = 12. So we need to divide reversedNum by 10 if x contains odd number of digits before comparing x and reversedNum. Implementation Language: Go Language: Python Language: Java Complexity Analysis Time Complexity: O(d/2) d here is the no. of digits in the given input number. Time complexity of this algorithm is O(d/2) because we only have to check half of the digits in the given number x (last to middle) to determine if the given number is a palindrome. Space Complexity: O(1) No extra space is used. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section. Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Problem Statement ​ This is another article in the series leetcode problem solutions and this article is a solution to leetcode 1 two sum problem. Once you have a good understanding of two sum problem, it should help you solve advanced level problems like three sum which in some ways a continuation of the two sum problem. Consider you are given an array of integers and a target sum, return indices of two numbers in the array such that they add up to the given target. You may assume that each input would have exactly one solution. Also, you cannot use the same element twice. You are allowed to return the answer in any order. Example ​ Example 1: Input: nums = [7,2,13,11], target = 9 Output: [0,1] Example 2: Input: nums = [7,3,5], target = 8 Output: [1,2] Solution Let us try to understand the problem statement first. Here we are given an array of integer elements and a target sum. Our job is to write an algorithm which returns indices of two elements in this array such that, when we add these two elements it should be equal to the target sum given. For instance, in example 1 [7,2,13,11] is the given array and the given target sum = 9. If we take a look at the given array, the pair which adds to the target sum 9 is (7,2) i.e. 7+2 = 9. So our algorithm should return (0,1) as the result because these are the indexes of elements 7 and 2 respectively in the given array. Similarly for the array in example 2 [7,3,5] output is (1,2) because these are the indexes of elements 3 and 5 respectively which add up to the target sum 8. Note: If there are multiple such pairs we need to return the indexes of first pair we find from left. It is stated in the problem statement that we can return the indices in any order, what does this mean? Let us understand this with example 1. The output for this example is [0,1], so when the problem statement says we can return the indices in any order what it means is that we can return either [0,1] or [1,0] as our output, both will be considered correct. Same for example 2, we can return either [1,2] or [2,1]. Solution 1: Brute Force A straight forward solution to this problem is to check for every possible pair present in the given array. For a given input array nums we need to do the following steps: Run two loops and check for every combination in the given array. Fix the outer loop at a specific index and move the inner loop to get all the possible pairs. The outer loop runs from i=0 to i=n-2 and inner loop runs from j=i+1 to j=n-1. In each iteration of the inner loop check if the numbers represented by the outer and inner loop indexes add up to the target sum. If nums[outerLoopIndex] + nums[innerLoopIndex] is equal to target, return {outerLoopIndex, innerLoopIndex} as result. Else continue iteration to check for the next pair. Repeat the above steps until you find a combination that adds up to the given target. For example, for array [7,2,13,11] and target sum 24, we fix the outer loop at index i=0 i.e element 7 and check it with all possible values of the inner loop from j=i+1 to j=n-1, i.e from index 1 to 3. So, we will be checking the following pair of elements in the first iteration of outer loop: (7,2) (7,13) and (7,11). Now we increment the outer loop index i by 1 and check it with indices 2 to 3 (i+1 to n-1) of the inner loop. We repeat this until we find the required answer. Note: n here is the size of the array. Code Language: Go In the worst case, this algorithm has a running time complexity of O(n^2). The worst case would occur when the required combination is the last combination to be checked by our loops. Complexity Analysis Time Complexity: O(n^2) Space Complexity: O(1) Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Solution 2: Using Hashmap It is possible to solve this problem in linear time. The idea is to make use of a hashmap to store the indices of the elements that are already visited. Hashmap "key" is the number in the given input array (You add this to the hashmap as you visit each element). Hashmap "value" is the index of the number in the array represented by the hashmap key. For a given input array this algorithm does the following steps: Create a hashmap which accepts integer datatype as key and value. Iterate through each element in the given array starting from the first element. In each iteration check if required number (required number = target sum - current number) is present in the hashmap. If present, return {required number index, current number index} as result. Otherwise add the current iteration number as key and its index as value to the hashmap. Repeat this until you find the result. Simulation Consider you are given the below input array and target = 24. Let currIdx be the variable representing current element under process and let idxMap be our index map. Cells marked in orange indicate the currently processed array element. At the beginning, currIdx = 0 and idxMap is empty as shown in first figure below. Next we check if the required number = target - current number is present in the idxMap. Required number = 24 - 7 = 17 is not present in our hashmap, so we add 7 as idxMap key and 0 as idxMap value (0 is the index of 7 in input array) as shown in figure 2 below. Next we move on to the second element in the array by incrementing current index. So currIdx = 1 which points to element 2 in array. Again we check if required number is present in idxMap, required number = 24 - 2 = 22 is not in our hashmap so we add to 2 to the hashmap along with its index 1. Increment current index, currIdx = 2, which is element 13 in input array. Again required number = 24 - 13 = 11 is not in hashmap. Add {13:2} to idxMap. Same is shown in below diagram. Our hashmap now contains 3 elements 7, 2 and 13 along with their indexes. Again we increment currIdx, currIdx = 3 which is element 11 in array. Now required number = 24 - 11 = 13 is present in idxMap (shown by cell highlighted in green in the second figure below). That means we have found the pair which adds up to the target sum 24, i.e. (11 , 13). Therefore we return the indexes of 11 and 13 as our result. Index of 11 is nothing but currIdx which is 3 and index of 13 can be found from hashmap which is 2, therefore we return (3 , 2) or (2 , 3) as our result. Code Language: Go Language: Python Language: Java Complexity Analysis Time Complexity: O(n) Space Complexity: O(n) The running time complexity of this solution is O(n) since we would have to go through all array elements in the worst case. As described in two sum solution 1, the worst case occurs when the required combination is the last combination to be checked. Also the auxiliary space required is O(n) since we store the array elements in hashmap and in the worst case we would end up storing all values in the given array in hashmap. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

In our previous article we studied Netflix system design. In this article we will discuss how to design a high performance tiny URL or URL shortener service. Problem Statement Design a URL shortner service. Functional Requirements For a given input URL (long URL) our service should generate and return a shortened URL to the user. When the user clicks on the shortened URL, our service should redirect the user to the original URL. Non-Functional Requirements The system should be scalable, highly available. Our system should be performant. For security purposes, the generated short URL should be as random as possible, it should not be predictable. Introduction A tiny URL or URL shortener is a service which takes a long URL and converts it into an equivalent short URL containing lesser characters. When the user clicks this shortened URL, he would be redirected to the same destination address as the original URL. For example, lets say our original URL is: If we pass this long URL to a URL shortner service, it would return you a shortened URL that looks something similar to this: Why URL shortening is necessary? There are several use cases where a shortened URL is preferred over a long URL: Short URLs look clean when they are placed on websites, files, social media etc. Shortened URLs are useful on services that have a restriction on number of characters that can be posted on them. Ex: Tweets on Twitter. To mask a URL. Sometimes you would not want to expose the original URL as is to the end users. Short URLs in such a case do the job of masking the original URL while preserving the destination address. Ex: For masking affiliate links. Some URLs are just too long and it is better off having a shortened version to represent them. Short URLs in such a case can be used as a placeholder. Shortened URLs can also be used for tracking purposes. Most URL shortner services usually provides us with additional metrics on the shortened URL like number of clicks etc, which can be extremely useful for business insights. Social campaigns with shorter URLs perform better. People tend to trust short URLs as compared to longer ones, especially when the long URL contains special characters. As a result shortened URLs produce better social engagement. Data Estimates For our design it is safe to assume that a system like this would be read heavy i.e. the probability of users creating a short URL from long URL will be less as compared to users clicking on a short URL and getting redirected to the original URL. For the purpose of this example let us assume that the read to write ratio is 100:1 which means for every short URL created there will be 100 redirections or 100 clicks on that short URL. Another important metric that will be useful for our design is the number of short URL generation requests that our service is expected to receive per month. It is important that we clarify all these details with the interviewer beforehand because it will give us better clarity to proceed with our design. For our case let us assume our service gets 100 million requests per month on an average. Traffic Estimates Considering all the above assumptions: Total no. short URL generation requests per month = 100 million. Therefore no. short URL requests per second = 100 million /(30 days * 24 hours * 3600 seconds ) ~ 40 URLs/sec. Total short URL clicks or redirections per second (assuming 100:1 read to write ratio) = 40 URLs/sec * 100 = 4000 URLs/sec. Data Estimates Most popular browsers support 2000 characters in a URL. So, lets say our long URL will at max take up to 2000 characters or 2KB. Most URL shortener services create a short URL with 15-16 characters (We will see more on this later in our discussion). So we can say the short URL size is ~ 16 bytes. Additionally we might need few more bytes to store metadata like creation timestamp, user details etc, lets say 50 bytes. So, total storage needed per shortened URL ~ 2.1 KB. Storage needed for 1 month = 2.1 KB * 100 million = 210 GB. Storage needed for 1 year = 210 GB * 12 months ~ 2.5 TB. For 5 years this will be 12.5 TB and 25 TB for 10 years. System Design At first look designing a URL shortner service may not look like a big deal. All that we need is a server that runs the logic for converting the long URL to short URL, a database to store the mapping of long URL to short URL and when the user requests for the short URL you redirect the user to its corresponding long URL using this mapping data. Simple right? Yes, this approach works fine as long as we have to serve only a small set of users. But what if our service gets thousands of requests per second? Will our server be able to handle the load? Will our database be able to handle the volume of data? How do we ensure that the short URLs generated are all unique? How to make sure that the data stored on our database is not corrupted? All these subtle aspects associated with designing a URL shortner service makes it such a popular system design interview question as it allows the interviewer to test the candidate on various design aspects. Interview Tip: In most system design interviews you will be given a loose ended or generic problem statement (similar to the one given here). It is your job as an interviewee to ask relevant follow up questions and streamline the requirements. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others For this particular use case, an immediate question to start with could be, what is the scale that our service needs to operate at? What are the monthly active users and what are the number of requests/second our service can expect? This will help us decide on the design aspects like server specification, type of database to use, length of the shortened URL that our service has to create and also calculate the data estimates. We will start with a simple approach first and evolve our design incrementally as we move along. First, let us think of what components we need in order to build a service like this. Users send request to our service from a mobile or desktop browser, our service should have the logic/code to convert this long URL to short URL. We will get into the details of how we can build this logic later in our discussion, for now let us consider that we need some kind of logic and this logic has to be hosted somewhere on a server for our users to reach us. Once the request reaches the server, the code on the server runs to generate the short URL and this will be sent back to the user as a response. We would also need to store this short URL to long URL mapping data in a database so that the next time when the user clicks on the short URL our service redirects the user to the original URL destination. We will see what type of database to use for our service later in our discussion, for now lets just assume we need some kind of a database to store this data. With the above design, now when the user clicks on the short URL, the request reaches the server, the server then connects to the database to get the short to long URL mapping and redirects the request to long URLs destination address and there you go, we have our URL shortner service! As you can see, the above approach is simple, we just need to have a sever and a database to make this work. However, this approach of a single server hosting the shortening logic and a database to store the mapping works fine only for a small system that has to serve less number of requests, but it wont scale. If our service becomes really popular and if we start getting thousands of request per second, this design wont work, lets see why. As we start getting thousands of requests per second, a single server instance may not be able to handle all the load. The increased load may cause the server to crash resulting in downtime in our service and bad experience to users of our service. We can overcome this problem either by scaling up (vertical scaling) or scaling out (horizontal scaling). In vertical scaling we use a bigger machine having more memory and CPU to cope with the increased load. As the numbers of requests grow, we add more memory and CPU to the existing machine (server instance) to meet the demand. However this approach has a limitation, we can keep adding more memory and CPU only up to a certain extent because of hardware the limits. Another approach to scale the system is using horizontal scaling. In horizontal scaling as the load increases we add more machines as opposed to using bigger machines. This approach works really well for large systems serving huge number of requests. To optimize this further, we could use a hybrid model having a mix of horizontal and vertical scaling approaches, i.e. we keep adding more machines to meet the demand (horizontal scaling) and each of these machines is a big machine with adequate CPU and memory depending on our cost estimates. With all of these ideas in place our system would look as shown below: You might be wondering looking at the above diagram, when there are n server instances, how does the system know which server has to handle which request. This is a valid point, we just cannot have multiple servers and expose them as end points to users. We need to have an intermediate component which interprets the requests and re-directs them to specific server instance using some of kind of a logic. This job is done by the load balancer. Load balancer as the name suggests, balances the load by distributing the requests across our servers. There are various kinds of load balancers, each type having its own logic on how to distribute the load, but for our use case lets keep this simple by assuming the load balancer redirects the requests depending on which server is free or available to process the request. The load balancer also acts as a single point of contact for all our users, they don't have to know the individual server IP addresses of our sever instances. All the user requests land on the load balancer and the load balancer is responsible for re-routing these requests to a specific server instance. So far our system looks as shown below: We can optimize this design further by adding a caching layer to our service. With the current design our servers have to talk to the database every time the user clicks on the short URL, in order to retrieve the short URL to long URL mapping. Database calls can be slow and expensive as compared to fetching the data from a cache which is essentially an in-memory storage. We can improve the response time of our APIs by caching frequently accessed short URLs so that when we get a request for a short URL our servers will first check to see if the data is available in cache, if yes it retrieves the data from cache, otherwise it fetches it from database. Apart faster reads, cache can also help reduce the load on our database. This is because data available in cache can be served from the cache itself without having to reach to the database, this in turn reduces the number of calls that we make to the database, thereby reducing the load on our database. There various caching solutions available in the market. Few popular ones include Redis, Memcached, Varnish etc. We can pick any one them for our use case. If you want to learn more about caching, when to use a cache and various caching strategies, we highly encourage you to go through this article on caching. Short URL Logic We now have most of the components in place to build our system, but we have still not discussed the most important aspect. How do we convert the given long URL to a short URL? Short URL Composition Before understanding how to convert a long URL to short URL, let us go a level above and discuss how the shortened URL should look like. Most popular URL shortening services have two parts to a shortened URL. The first part is the domain name of the service and the second part is a set of random characters. It is important we ensure that the domain name of our service is crisp, yet meaningful. For the purpose of this example, let us assume the domain name of our service is urls.com (short form for URL shortner). The second part of the short URL is a string formed by a set of random characters. This random string should be unique for each short URL created for a long URL. Random String Length What should be the length of the randomly generated string? Length of the random string should be such that it is not so long that it defeats the purpose of having a shortened URL, nor too small either, otherwise we would run out of combinations after a certain point. We can generate random characters using algorithms like base62 or md5. Both base62 and MD5 algorithm outputs consist of 62 character combinations (a-z A-Z 0-9). Lets say we decide to go with random character string of length 7, we would have 62^7 ~ 3.5 trillion combinations to work with. This looks sufficient because even if our system gets 1000 requests per second, it would take 110 years to exhaust these many combinations. So if we combine both the parts (domain name+random string) the total length of the short URL that our service creates would be equal to 15 characters, , 8 characters for the first part, 7 characters for the second part, plus an additional 1 character for '/' in between, which seems acceptable (Ex: urls.com/3NVyw2j). How to generate random string? Now lets see which algorithm to choose for generating the random string. There are various hashing or encoding algorithms which we can be used for this purpose. Base62 and MD5 are the popular ones. Both base62 and MD5 produces output consisting of 62 characters combinations (a-z, A-Z and 0-9). Base62 takes a integer input and MD5 takes string as the input and generates a random string output. For base62 algorithm, we need to convert our long URL string into an integer first and then pass it to the algorithm and for MD5 algorithm we can directly pass the long URL as input. Most languages have ready to use implementation (core/third party libraries) for both the algorithms. Now lets us analyze each of these algorithms and see which one would fit better for our use case. Using MD5 Algorithm MD5 algorithm takes a string as input and produces a fixed length output. For each input string MD5 algorithm mostly produces unique output, there is still a chance of it producing the same output for two different inputs, but this is very rare. But the thing with MD5 algorithm is that it produces a really long output. This is a problem because we have a restriction of 7 characters for our random string. We can solve this problem by taking only a part of the output produced by MD5 algorithm, say for instance we consider only the first 7 characters of the MD5 output. But there is a problem with this approach as well. The chances of collision increases if we consider only the first 7 characters of the MD5 output, meaning for different long URLs we might end up with the same 7 characters as output which is not what we want. For each long URL we always need to have a unique set of 7 characters in the short URL or it will result in data corruption. Lets see if we can do this more efficiently using base62 algorithm. Using Base62 Algorithm Base62 also produces an output consisting of a combination of same 62 letters as md5. Base62 takes integer type as input. So we need to first convert the long URL to a random number then pass this random number to the base62 algorithm. Can we use the output of base62 as is and store it into the database? The answer is no because, if you notice we first convert the long URL to random number and then pass it to base62 algorithm. So there is a possibility that we end up getting the same random number for different long URLs and therefore if we store the output of base62 algorithm directly into the database it can lead to data corruption. This means, each time we generate random characters using base62, we first need to check if that data is already present in database, if yes we regenerate the random number and again pass it to base62 algorithm. We repeat this until we obtain a unique random string and then store it in the database. Now this is clearly not an efficient approach. Also apart from being inefficient, the above approach works if our service is just hosted on a single server instance. If we have multiple servers running to meet the demand, this approach may not always work. Imagine having two replicas of the server running, and a request comes into to each of these servers simultaneously, assume the base62 generates the same random string for both the long URLs. Now when each of these servers try to save this data into the database which can lead to data corruption. This can be solved by using constraints in DB query like insert if not present, and if this query fails regenerate the random string, but again we are adding to the inefficiency and complexity. How can we make this work efficiently? If you look at the problem at its core, the reason why we end up with duplicate random string is because we pass duplicate random number to base62 algorithm. If we can somehow pass a unique random number to base62 every time which can avoid this problem completely. And this brings us to our final approach which is the counter based approach. Counter Based Approach The idea is to make use of a counter instead of generating the random number each time. When the server gets a request to convert a long URL to short URL, it first talks to the counter to get a count value, this value is then passed to the base62 algorithm to generate random string. Making use of a counter to get the integer value ensures that the number we get will always be unique by default because after every request the counter increments its value. For example, lets assume our counter starts from 1. Upon getting the first request to convert a long URL to short URL, our service will ask counter to provide a unique number, counter returns 1 to our service, it then increments its current value. Next time our service requests the counter for a unique number, it returns 2, for the 3rd request it returns 3 and so on. As you can seen this is a much efficient compared to our previous approaches where we had to check if the random string obtained is unique or duplicate each time before we could write it to our database. Challenges Even with the counter based approach we have to take care of few things. For instance, the here counter is a single point of failure, if the counter goes down our entire service stops working. What if the counter runs out of numbers? Also if our service has multiple server instance running to manage the load and if two or more servers request the counter for number at the same time, will the counter be able to handle this by properly incrementing and send them unique numbers? Solution If we plan to implement the counter ourselves, we would have to handle all these complexities ourselves and for that reason we would be making use of a third party service called Apache Zookeeper which takes care of all these complexities for us so that we just have to focus on the core business logic. Zookeeper Let us briefly understand Zookeeper. Zookeeper is an open-source distributed service which can be used for maintaining configurations, managing co-ordination between services in a cluster, distributed synchronization, naming nodes in a cluster and many other things. In addition to the above functionalities zookeeper also provides a shared counter. The counter provided by zookeeper contains a range of values within it. For each new server created in our service, zookeeper assigns one of these ranges. If a server runs out of counter range assigned to it, zookeeper assigns it a new range. Zookeeper is a distributed service, if the counter node fails, zookeeper automatically spins up a new counter instance. Also as we get more users using our service, we can add as many servers as we want to handle this load, zookeeper takes care of assigning and maintaining the counter values for all these servers. Database What database would be ideal for our service? Should it be SQL or No-SQL? In order to be able to make this choice, we need to understand the type of data that we need to store in our database and also the scale. Coming to the type of data, we only need to store the short URL to long URL mapping. When the user gives us the short URL, we just need to get the long URL using the 7 character random string in the short URL. We do not need to perform any relational queries or joins to store or get this data. So we do not need a SQL database. As far as No-SQL databases are concerned, there are various types of No-SQL databases like document database, graph database, column database, key-value database etc. As we can clearly see, our service uses a simple key value mapping. Therefore we can go with a No-SQL key-value pair database. Some of the popular ones are Amazon DynamoDB, Oracle NoSQL Database, InfinityDB, Aerospike etc. As far as the scale is concerned, most of these No-SQL solutions scale well with increasing data. Scaling Servers It is a good practice to keep the number of active server instances in our system elastic. During peak hours we need to have more server instances running to cope with the increased load, other times we reduce this count to a preset value. Having this flexibility with the number of server instances is important for various reasons: Makes sure our system does not go down when the number of requests spike during peak hours. On cloud we are mostly billed per hour or on demand basis. So, if deploy our service on cloud, running extra server instances, more than what is needed, can have an impact on cost. If we do not run our service on cloud, we will have to bare the cost of having extra reserved servers upfront, to ensure our service is always available. Most popular cloud solutions provide the auto scaling feature. If we deploy our service to a popular cloud provider like AWS we can easily leverage its auto scaling capability. Once integrated, it will automatically increase or decrease the number of active server instances depending on the number of requests we get. Final Design Now putting together everything we have discussed so far together, our URL shortner service design looks as shown below: Summary Lets summarize what we have studied so far and how the final design works. URL Shortening Request When our service gets a request for converting a long URL to short URL, for the sake of simplicity lets assume the long URL in request is www.google.com. When this request reaches our service it first hits the load balancer. Load balancer scans through all the available server instances, checks which server is free to take the incoming request and forwards the request to the appropriate server instance. The server then performs the following steps: Contacts zookeeper to get the counter value and passes the obtained counter value as input to the base62 algorithm. Base62 returns a unique random string which is then appended to create a short URL. For the purpose of this example let us assume the random string obtained is 3NVyw2j, so the short URL will be urls.com/3NVyw2j. This long URL to short URL mapping is stored in the database. . User Clicks On The Short URL When this short URL is clicked or pasted in browser, the request will again hit the load balancer which forwards the request to an appropriate server instance. The server now does the following steps: Extract the random string from short URL (3NVyw2j in our case). Using this random string, retrieve the corresponding long URL from database. Redirect the request to the original long URL destination address. Save the short URL to long URL mapping in cache so that the next time the user requests this short URL we can quickly get it from cache instead of querying the database. And finally lets analyze if our design accomplishes all the functional and non-functional requirements. Our design covers both the points mentioned as part of the functional requirement. As far as the non-functional requirements are concerned, our design ensures that the system is scalable, we have seen throughout our design discussion how the system can increase the number of server instances when there is an increased load and how the load balancers does the job of balancing the load among the available server instances. Also our choice of database is made keeping scalability in mind. Is our system highly available? Yes, if one of our server instances goes down, the load balancer re-directs the request to one of the other available ones. Also our auto scaling policy ensures a new server instance is created to replace the failed instance. The counter that we used is a distributed counter and the zookeeper ensures it is always available and not a single point of failure. The system is performant. The algorithm for long URL to short URL conversion is an efficient one. We have also made use of caching, to cache the most frequently requested short URLs which also helps improve the performance. And for the third non-functional requirement, since we use a counter value as input to the base62 algorithm we are guaranteed to get a random short URL each time. And with this we have covered all the design objectives. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from Code Recipe in our topics section. You can find more system design questions in our System Design Questions Section. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer ends soon - Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

What is caching? A cache is a hardware or software component that acts as a temporary storage allowing fast access to data stored in it. The primary objective behind using a cache in any application is to improve performance. The process of storing and accessing the data from cache is known as caching. Caching is used everywhere. It is used in different layers like operating systems, CDN, DNS and also by various applications and services. If the requested data or item is available in the cache it is called a cache hit and if the requested data is not available in the cache it is called a cache miss. If implemented correctly, caches can help improve response times, reduce load on database, and save computation costs. Retrieving data from a persistent storage like database can take a considerable amount of time, caches reduce the response time of our API by providing fast access to data. Mainly caches are used to avoid frequency of network calls to database and to store the results of operations that are computationally expensive. Caches can help bring down the computation costs especially if your application is running on a cloud. How caching is useful? There are a wide variety of use cases where caching can be applied. Some of the scenarios where caching is useful are: Frequently Requested Data One of the popular scenarios where caching is useful is if you have to frequently query for some commonly used data. For example, in a service like twitter each time when we open a user profile, a common query is to get the count of followers/following for that user. This is not a very frequently changing data and is a good candidate for caching. You can fetch this data from database the first time when any user tries to access it, after which it can be cached and each subsequent request thereafter can be served from cache until the data becomes stale, which helps us avoid network calls to database for each request. Also, if you remember we have made use of caching in our URL shortener system design to cache the most frequently used short URLs, this is another example which shows the real life use case of a cache. Expensive Computations Some APIs are simple and have fast response times, while others might require you to do multiple intermediary steps involving slow and heavy operations that might delay the response time. A good example for this is a user feed API in a service like instagram or facebook. Displaying user feed for a particular user is mostly based on custom algorithms that may involve several computationally expensive operations like fetching all the people, public pages that a particular user follows from database, separating out the most recent posts made by his followers and pages, aggregating all of these posts and building a time sorted list using all of this data. Since we may have to make multiple calls to database and a lot of computation in order to get, aggregate and sort this data, our API response time can take a hit if we try to compute this on the go (as and when we get the request from user). And since a user feed is the first page that loads when we open an application like facebook or instagram, this can lead to a bad user experience. So in order to improve the performance and reduce the response time, we can precompute user feed for a particular user beforehand and store it in the cache (even before a request for user feed is made). We can serve this data to users directly from cache when he requests for it. This can potentially reduce the response time of our API from several seconds to few milliseconds. Avoid Load On Database If our service has a large number of users, and there are multiple microservices or replicas handling user requests which in turn call the database, this can put a lot of load on our database (especially during peak hours). This situation can be avoided by having a cache (most likely a distributed cache) which can ease the load on our database. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Why not cache everything? You might be wondering, if caches are so fast and efficient why not store all our data in cache instead of putting it in the database? Wouldn't that be an ideal thing to do? There are a few reasons mainly why we cannot do this: Firstly, the hardware used by caches are expensive as compared to the hardware used by traditional databases. Traditional databases mostly run on commodity hardware which are relatively inexpensive. So we may have to shell out a ton of money if we were to store everything in cache. Second, storing all our data on cache instead of a database is counter-intuitive because this defeats the purpose of using a cache in the first place. This is so because as you store more and more data on cache, this might increase the time needed to fetch the data from cache making it redundant. Where do a caches fit in? A typical web application backed by a data store would look like this: This data store can be a traditional database or another microservice. When client makes a request to our service, it initially hits one of the microservices responsible for handling the request. This microservice in turn connects to database to retrieve the data requested by the client. Calls to database can be slow and can utilize a lot of system resources. It would be a good idea to store at least some of these items in memory so that we don't have to reach the database for each and every request. What this does is firstly it can improve the response time of our API since we are responding directly from cache. Second even if our database is down due to some failure our service might still be able to serve some of the user requests. Also if there are lots of clients requesting for the same data again and again, having a cache in between can reduce load on our database. When we get a client request, our service first check to see if that data is present in cache, if yes our service directly responds from cache. If the data is not present or if the data is outdated it fetches the data from database. Cache Invalidation Ideally the data that is stored in cache is transient and not meant to be there forever. This data has to be cleaned up or updated from time to time to keep it coherent with the datasource. Data in cache can go stale if the original data (in database for instance) is changed or removed. The process of cleaning up or updating the data in cache with new values to keep it in sync with the original data is known as cache invalidation. One of the popular ways to invalidate a cache entry is by using the TTL strategy. In Time to live or TTL strategy each entry in cache is associated with a specific time after which the data is considered stale. Once the data expires, we can flush these stale entries using one of two ways: When the user requests for a stale data, we can actively expire it. We can also do this passively with the help of a job that runs periodically at specified intervals. Cache Eviction Policies Cache eviction policies control the way in which items are removed from cache, when the cache is full. Based on the algorithm selected a cache eviction policy decides which item to remove from cache when the cache limit is reached. Why is it needed? It is important that we store data in cache in such a way that no matter how much data is stored in our database, our cache only has relevant items considering the future requests that are expected to come into our system. While predicting the future requests we need to consider two things mainly: 1. When to add items to cache 2. When do we remove items from cache. Our cache performance almost entirely depends on our cache policy. Imagine having a very poor eviction policy, every time the service requests for some data from cache, it results in a cache miss. So hitting the cache is of no use in this case. Call to a cache is an extra step, and every time if it responds with no data, you would end up pulling data from the database almost all the time with an additional redundant call to cache as well, which can add to the delays instead of improving performance. In such a case having a cache becomes an extra overhead instead of improving application performance. Also as mentioned earlier hardware used by cache are expensive, so storing a ton of items in cache would not make any sense both in terms of budget as well as performance. So we need to set a limit on the maximum number of items that can be stored in a cache at any given time. When the cache is full we eliminate or remove certain items depending on the cache eviction policy selected. Some of the well known cache eviction policies are: LRU - Least Recently Used: In this policy, the oldest item is removed from cache when the cache is full. We have described LRU cache in detail in a separate article. LFU - Least Frequently Used: In this policy, items are evicted based on the frequency of usage. Each item in cache has a count of how many times it is requested, when the cache is full the item with the least count is evicted. MRU - Most Recently Used: This is exactly opposite to the LRU policy. When the cache is full, the item that is most recently requested is evicted from cache. RR - Random Replacement: When the cache is full, a random item is evicted from cache. FIFO - First In First Out: Items are evicted in the order in which they were added to cache. LIFO - Last In First Out: The cache evicts item that was added most recently regardless of how many times it was accessed before. Note: It is important to note that cache invalidation is different from cache eviction. We invalidate data from cache because it is either stale or has expired, but we evict data from cache when the cache limit is reached (memory is full). Distributed Cache If the amount of data from a service or an application is too large to be stored on cache memory of a single machine, the data in this case has to be distributed across multiple machines. Distributed cache is an extension of traditional cache. While a traditional cache is mostly a single server or machine, a distributed cache is can grow beyond the memory limits of a single machine, formed by the interlinking of multiple cache servers or cache clusters. A distributed cache has its data spread across several nodes (servers) in a cluster. It can also be across several clusters across geographically distributed data centers. Distributed caches have the ability to scale horizontally. As the data grows, we can add more machines (cache servers/nodes) to our cluster allowing our cache to grow along with the growing data requirements. Distributed caches are especially useful for applications with large data volumes. Some of the popular distributed cache solutions are Memcahed, Redis, Hazelcast. How cache is different from a CDN? CDNs are geographically distributed network of servers that work together to provide content (videos, images etc) to users more quickly. CDN acts as an intermediate layer between the end user and the server minimizing the number of requests that need to be served from the origin server. Consider a service like Netflix having origin server in United States. For a user viewing content say from India, if you have to serve this content from the origin server, this could result in a lot of delays and buffering for the user viewing the content because of distance the data has to travel from server to end user. This is where CDN comes to rescue. CDNs have servers distributed all over the world. These servers cache data and when user requests for data, instead of serving this data from origin server it is served from the CDN server nearest to the user thereby reducing the delay. The main difference between a cache and CDN is that while CDNs do perform caching, not everything that performs caching is a CDN. Also CDN servers are strategically placed at the network exchange points (IXPs) to avoid network round trips, while this may not always be true with a regular cache. Note: Internet exchange points (IXPs) are points where different internet providers connect to exchange traffic originating on their network. Caching Strategies There are a number of caching strategies and choosing the right one is an important step when you decide to incorporate caching into your system. Some of the popular caching strategies are: Write through cache: In this strategy data is written to both cache and database asynchronously. Write back cache: Service writes data to cache and it immediately responds back to the user. This data is written to the database after a specified interval or under certain condition. Write around cache: In this strategy data is directly written to database. When the user requests for this data at a later point, it is written into the cache. We will be explaining caching strategies in detail in our upcoming article. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section. Code Recipe New Year Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Problem Statement This is another article in the series leetcode problem solutions and this article is a solution to leetcode 15 three sum problem. We solved the two sum problem in our earlier article, and this problem in some ways is a continuation of the two sum problem. So, if you have not yet solved the two sum problem we advice you to do so because it will help you understand the 3 sum problem better. Given an array of integers, nums, return all the triplets in the given array nums[i], nums[j], nums[k] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice: The solution set must not contain duplicate triplets. Example Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Example 2: Input: nums = [0] Output: [] Solution Let us try to understand the problem statement. The first part of the problem statement is clear, we are asked to find out all the triplets in the given array whose sum is equal to zero. A triplet is nothing but a set of three numbers in the given array. For example, if nums=[1,2, 3,4] is the given array, [1,2,3] [2,3,4] [1,3,4] etc are its triplets. What does the condition i != j, i != k, and j != k mean? It means that we are not allowed to reuse any number from the array within a triplet. Example, for the given array nums = [1,2,3,4], triplets [1,1,1] or [1,1,2] or [1,2,2] etc are not considered valid triplets. The last condition that we need to consider is that we cannot have duplicate triplets in our final result. Example if [-2,-2,0,2] is the given array, we can only consider one of [-2,0,2] from indexes 0, 2, 3 and [-2,0,2] from indexes 1, 2, 3 in our final result. Solution 1: Brute Force The most simple and straight forward solution to this problem is to find every possible triplet from the given array, see if its sum is equal to zero and return the result (ensuring there are no duplicate triplets in the result). This algorithm involves the following steps: Use three loops to generate all possible triplets for the given array, with each loop variable keeping track of 1 triplet element each. Next we calculate the sum for each triplet generated in step 1. If the sum is equal to 0 we need to check if it is a unique triplet (not already in our result set). We can ensure the triplets in our result set are unique by sorting the triplets and adding it to a hashmap (hashmap overwrites data if same value is written to the same key multiple times thereby eliminating duplicates). Once we have added all the triplets whose sum is equal to 0 into the hashmap, we iterate through the hashmap and add it to our result array. Finally we return the result array. Implementation Below is the implementation for this solution: Language: Go Language: Java Complexity Analysis Time Complexity: O(n^3) Time complexity is O(n^3) since the algorithm uses 3 loops to arrive at the result. Space Complexity: O(k) Space complexity is O(k) since we use hashmap to store unique triplets. k here is the number of unique triplets with sum = 0 for the given array. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Solution 2: Efficient Solution We can sort the given array and use the three pointer approach to improve the time complexity of our solution as compared to the previous approach. The idea is to sort the array first, then run two loops to process the triplets. We fix the outer loop and move the two pointers (indexes) of the inner loop inwards to arrive at the result. The intuition behind this algorithm is simple, when we sort the array all the duplicate elements are grouped together. And if we use two pointers from left and right to traverse the array while processing the triplets, we can easily avoid duplicate triplets that would occur because of these duplicate elements. For example is nums = [-2, 1, -3, 5, -3, 5] is the given array, when we sort this array we get: nums = [-3, -3, -2, 1, 5, 5]. As you can see all the duplicate elements [-3, -3] and [5,5] are grouped together. If were to consider all of these duplicate elements, it would result duplicate triplets like [-3, -2, 5] and [-3, -2, 5]. We can easily avoid this if we use two pointers to traverse the array from either sides (one from start and one from end). We process only the 1st element and skip all the duplicate elements that appear after it. For the given input array nums of size n this approach does the following steps: First step is to sort the given array nums. Sorting the array helps us identify duplicate triplets using our loops by skipping certain numbers that would result in duplicate triplets. This helps us avoid using a hashmap to identify the duplicates (like in solution 1) there by improving the space complexity(Keep reading to know how duplicate triplets can be skipped). Also sorting the array helps efficiently increment/decrement our index variables depending on whether the sum is less than or greater than 0. Next we need two loops. Outer loop index num1Idx represents the index of the first element in the triplet. Inner loop contains two indexes num2Idx and num3Idx representing the indexes of the 2nd and 3rd triplet elements respectively. Initially num1Idx points to the first element in the given array and num2Idx, num3Idx point to the 2nd and last elements in the given array. We fix the outer loop index num1Idx and move the two inner loop indexes inwards as long as num3Idx > num2Idx. Once the condition num3Idx > num2Idx is false we stop the inner loop and increment the outer loop index num1Idx, also update num2Idx and num3Idx, num2Idx=num1Idx+1 and num3Idx=n-1. Take a variable sum to store the triplet sum. sum = nums[num1Idx] + nums[num2Idx] + nums[num3Idx]. Now there are three possibilities: a. If sum is equal to 0 we add it to our result. b. If sum is greater than 0 we need to decrease the sum value to make it equal to 0, so we decrement num3Idx index. c. If sum is less than 0 we need to increase sum value to make it equal to 0, so we increment num2Idx index. The inner loop should run as long as num3Idx > num2Idx for each iteration of the outer loop. We return the result once all the triplet combinations are processed. The above 4 steps ensure that we find all triplets whose sum is equal to 0. But it will also add duplicates to the result array. To skip duplicate triplets we need to add two conditions to our algorithm, one in the outer loop and one in the inner loop. In the outer loop if nums[num1Idx] == nums[num1Idx-1] i.e. if current num1Idx value is same as previous number (num1Idx-1) we skip the current number (we don't have to consider the current number for calculating our result). This condition ensures that we skip all duplicates from the left side of the array. Similarly to skip all numbers from the right side of the array, once we find a triplet with sum equal to zero we keep decrementing num3Idx until nums[num3Idx] != nums[num3Idx +1] (in the inner loop). Simulation To make this more clear let us understand this algorithm with a simulation. Consider you are given the below input array nums of size n = 5: The first step is to sort the given array. After sorting nums will be: Iteration 1 For the 1st iteration of the outer loop num1Idx = 0, num2Idx = num1Idx + 1 = 1 and num3Idx = n-1 = 4. Same is show in figure below: Now we calculate the sum for array elements at current num1Idx, num2Idx and num3Idx. sum = nums [num1Idx] + nums [num2Idx] + nums [num3Idx] sum = nums[0] + nums[1] + nums[4] = (-1) + (-1) + 2 = 0 As you can see for the current values of num1Idx, num2Idx and num3Idx sum = 0, so we add it to our result. So result = [[-1, -1, 2]] and also decrement num3Idx. There is no need to make the duplicate check in the inner loop as num3Idx is the last element in the array. Now the updated values of index variables are num1Idx = 0, num2Idx = 1 and num3Idx = 3. Again calculate sum, sum = nums[0] + nums[1] + nums[3] = (-1) + (-1) + 1 = -1. Sum is less than 0, so we increment num2Idx. Now sum = nums[0] + nums[2] + nums[3] = (-1) + 0 + 1 = 0. Sum is equal to 0, so we add the current triplet [-1, 0, 1] to the result and decrement num3Idx. Also make the duplicate check in the inner loop, nums[num3Idx ] != nums[num3Idx+1], so there is no possibility of a duplicate for the current value of num3Idx, therefore no need to decrement num3Idx further. The updated values of index variables are num1Idx = 0, num2Idx = 2 and num3Idx = 2. As you can see num2Idx is equal to num3Idx, so we stop our inner loop and increment the outer loop index num1Idx by 1. Iteration 2 For the second iteration of the outer loop, the updated values for indexes are num1Idx=1, num2Idx=num1Idx+1=2 and num3Idx= n-1 = 5-1 = 4. Since the value of num1Idx is same as the previous iteration num1Idx value, we end up with duplicate triplets if consider this value again. Therefore we need to skip the current num1Idx, so increment num1Idx. Now num1Idx = 2, num2Idx = 3 and num3Idx = 4. And sum = nums[2] + nums[3] + nums[4] = 0 + 1 + 2 = 3 is greater than 0, so we decrement num3Idx. Again num2Idx is equal to num3Idx, therefore we stop the inner loop, also we have reached the end of array, so we stop our algorithm and return the result. Implementation Language: Go Language: Java Language: Python Complexity Analysis Time Complexity: O(n^2) Time complexity is O(n log n) for sorting the input array + O(n^2) since for the two loops. So the overall time complexity is O(n^2). Space Complexity: O(1) No extra space is used. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe here. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Introduction Generics is one of the most anticipated and long awaited features in go. Some also argue that it is in some ways a controversial feature since it seems to go against one of the go language's core design principle "simplicity". This however is a topic of discussion for another day, in this article we will go through everything that you need to get up and running with go generics. Also we will delve into some of the finer details and best practices of go generics to get you an advanced level knowledge on this topic. The go generics is finally here! The generics feature was added to the language in the Go release, version 1.18. What is generics in a programming language? Generics is a programming language paradigm that gives us a way to write code that is not tied to any specific type. It gives us the ability to define a generic or common data structure/function that allows us to work with multiple data types (like int, float, string etc). Why generics is needed? Let us understand this with an example. Assume we have a function Add(), that adds two integer types and returns the result as an integer as shown below: The above function works fine as long as our use case is only to add two integer values. Suppose, tomorrow we have a new requirement where in we are required to support float type addition as well, how can we handle this? We cannot use our earlier function because it takes only integer types as input. Prior to Go generics this could be solved in one of the two ways: Defining multiple functions, one for each type. Using an empty interface and type asserting. Approach 1: A natural tendency to solve this is to define a new function that does the exact same thing as our earlier Add() function but with float64 type as shown below. As you can see this is unnecessary duplication of code. It may not seem like a big deal for the above example as our function only involves a simple logic to add two numbers. But in the real world we may have to deal with a much more complicated logic containing hundreds of lines of code and duplicating these complex functions is a waste of time and effort. Also this introduces a maintenance overhead because every time we need to improve or update some piece of code we would have to do this in all the duplicated blocks, which of course is not the best way to handle this. Approach 2: In this approach we use an empty interface that can accept values of any type and in the function body we use type assertion to extract the required type and perform necessary actions. While this looks cleaner than the first approach, it still involves a lot of boilerplate code and is not the most efficient solution to our problem. Scenarios like these is exactly where generics comes into play. Go Generics The generics feature in Go is a major release, according to the official documentation this is the biggest change made to the language since the first open source release. The good news however is that it is fully backward compatible with the code written using earlier versions of Go. In Go a generic type is generally denoted using the notation T, however we are not restricted to using that, we can name it anything. Fig.1 shows a sample Go generic function along with its components. Compared to a normal (non-generic) Go function, you can see there is an additional square bracket between the function name and the parameter list. Also the parameter list contains the generic type parameters (denoted by T). Go generics can be broadly broken down into 3 components: Type parameters Type sets or type constraints Type inferences Lets discuss each of these components in detail. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Type Parameters In Fig. 1, the square brackets and the elements inside it together is called a type parameter or type parameter list. Type parameter defines information about the generic type. It contains information like the name of the generic type, data types supported by the generic type etc. A type parameter is defined using the syntax: [T1 constraints, T2 constraints, ...] Here are a few type parameter definition examples: Example 1: [T int | int32 | int64] Example 2: [T1 int32 | float64, T2 string | float64] Example 3: [T constraints.Ordered] Note: constraints.Ordered is a type of constraint provided by Go and it is defined in the package golang.org/x/exp/constraints, it supports Integer, Float and string types (More details on the constraints.Ordered type can be found here). Type parameters can be applied to Go functions and Go types (go type keyword). 1. Type Parameter on Go Functions The sample function shown in Fig. 1 is an example of how a type parameter can be applied to a Go function. Let us understand this more clearly by studying how we can redefine our earlier Add() function to support integer and float types using Go generics. As you can see we can convert our non-generic Add() function to a generic Add() function by adding a type parameter definition after the function name and replacing the specific types (int, float64) with generic type T. This generic Add() function can be called using both integer and float data types, there is no need to redefine or duplicate the function body like we saw earlier. How to call a generic function? Calling a generic function involves two steps: 1. Instantiation 2. Function call Instantiation In this step we tell the compiler what specific type we want to pass into our generic type. The compiler then checks whether this data type satisfies the type parameter constraints. For example the constraints, constraints.Integer and constraints.Float types used in our above generic Add() function, supports Integer, Float data types. If anything other than these types is used during instantiation, it throws a compile time error. The syntax for instantiation is: funcVariable := function_name[data_type] For example we can instantiate our above generic add function with int data type as shown below: AddFunc := Add[int] For float64 type we need to use float64 inside the square brackets as shown below: AddFunc := Add[float64] Function call The instantiation step returns a func type variable. In this step we call the generic function using this func type variable that we obtained during the instantiation step as shown below: result := AddFunc(10, 20) So to summarize, in order to call a generic function we need to first instantiate and then call the function as shown below: AddFunc := Add[int] result := AddFunc(10, 20) Go also supports a simplified syntax where we can combine the instantiation step and function call step into a single line of code: result := function_name[data_type](argument_list) This means we can call our Add() function using a single line of code as shown below: result := Add[int](10, 20) 2. Type Parameter on Go Types Type parameters can also be applied to types defined using the Go type keyword. Let us understand this again by taking the addition example: Let us define a custom add type (a generic type) using type parameters. The custom add type struct should have two fields for storing the numbers to be added. The Add() function should add the values in these two fields and return the result. In above example we have defined a custom struct type CustomAddType that has two fields num1 and num2. Both num1 and num2 are of type T (generic type). The type parameter is defined after the type name inside square brackets. We have defined an Add() method for this generic struct type. This method adds the generic types num1 and num2 and returns the result. To call this add method we need to instantiate the CustomAddType type first and then call the Add() method on it as shown below: Since num1 and num2 are generic types we can pass both int and float (defined by type constraints) values to it. Type Sets In the previous section we have learnt that type parameters can be defined with the syntax: [T constraints] The "constraints" part in the type parameter syntax is what we refer to as the type sets or type constraints. In simple words type sets define the range of types or set of types a generic type T supports. The benefit of using type constraint is that it allows us to define a set of supported types. This approach is unlike the generics implementation in other languages like C#, C++ where type parameters are completely type agnostic. The type constraint way of implementation is intentionally added to Go generics to reduce misuse. Type Sets are Interfaces An important thing to note is, everything that we define as a type set is an interface! Yes that's right, every type set is an interface. For example the constraints.Ordered type set we saw earlier, is an interface defined in constraints package. The definition of constraints.Ordered is as shown below: Similarly, constraints.Integer and constraints.Float types that we used in our generic Add() function are also interfaces. New Interface Syntax If you have been using Go for a while now, the interface syntax you see above might look a bit weird to you. Interfaces in Go used to have only methods and other interfaces embedded in them, but this is a little different. That's because, this is a new syntax introduced in Go 1.18 for use in generics. Now we are allowed to have types inside interfaces as well. We are also allowed to specify multiple types inside interfaces separated by the union operator as shown in the example below: The MyInteger interface shown above defines a new type set with int, int8 and int16 as possible types. The | symbol denotes a union, meaning the MyInteger interface is a union of int, int8 and int16 types. Similarly we can have interfaces with other types like string, float64 etc. We can also embed interfaces/type sets inside other interfaces/type sets. Example, In fact if you observe carefully, constraints.Ordered itself is a union of Integer and Float type sets which are in turn interfaces. Tilde Operator If you look at the constraints.Ordered type definition there is a ~ symbol before the string type. A tilde before a data type means the following things: Allow all values corresponding to that data type. Allow all values whose underlying type is the current data type. For example a ~string means 1. Allow all values of string type. 2. Allow all values whose underlying type is string (Ex: type customString string). Custom Type As Type Constraint We are also allowed to define our own custom constraints as shown in example below: type CustomConstraint interface { int | string } We can use these custom type sets in our type parameter declaration as shown below: [T CustomConstraint] Interface Literal As Type Constraint We can also use interface literals as type sets. For example, [T interface{ int | int8 | int16 }] Go allows us to simplify the interface literal syntax, we are allowed to skip the interface{} part from the above syntax: [T int | int8 | int16] If you go back to Fig.1, this is the reason why we where able to specify [T int | int32 | float64] without the interface{}. Inbuilt/Pre-Defined Type Constraints You might aware of the empty interface usage in Go. An empty interface i.e. interface{} in general means that it satisfies all types (since it has no methods inside it). Similarly in the context of type parameters, an empty interface represents a generic type which can be instantiated using any type. For example, the generic add function given below can take any type like int, int32, float32, string etc. Go 1.18 has introduced a new keyword called any to represent an empty interface, interface{}. Using this keyword, the above add function can be equivalently written as: In addition to any, Go provides another pre-defined type constraint comparable. comparable denotes the set of all non-interface types that are comparable. Specifically, a type T implements comparable if: T is not an interface type and T supports the operations == and != or T is an interface type and each type in T's type set implements comparable. comparable can also be embedded in other constraints since it is a constraint. That's it for the type sets section. Yes it can be quite overwhelming at first, given so many syntaxes and shorthands, but you will get used to it as you practice it more and more. Type Inference Type inference in the context of Go generics means how the compiler interprets the types that are being passed to a generic type. We can broadly classify type inference in go generics into two categories: Function argument type inference Constraint type inference Let us discuss each of them in detail. Function argument type inference We have seen in the previous sections how we can instantiate and call a generic function. Say for example if we have a generic function for multiplying two numbers: To instantiate and call the above generic function, we would write the following lines of code: multiply := Multiply[int] multiply(10,20) This is one way of doing it. As we learnt the syntax can be simplified by combining the two steps into a single step: Multiply[int](10,20) While this is shorter than the first syntax and easier to read, it is still cumbersome. Go simplifies this further by allowing us to skip the type argument instantiation part as shown below: Multiply(10,20) As you can see, with this syntax, we do not have to specify [int] while calling our generic multiply function and with this the syntax now is exactly same as a normal function call. How this works is, when you call a generic function this way the compiler internally infers the type from the arguments provided in the function call. In our example above, the compiler sees that the arguments (10,20) is passed to the function, so it infers the type to be int and substitutes this type for num1 and num2 parameters in the generic function. This way of inferring the type by the compiler in a generic function call by looking at its arguments is called function argument type inference. The limitation with this approach however is that, if we need a specific type, say for example int32, we will still have to explicitly mention it using the earlier syntax itself. But for other cases this helps us further simplify the syntax and improve the code readability. One thing to remember about function argument type inference is that it only works for type parameters that are used in the function parameters. This does not apply for type parameters used only in function results or type parameters used only in the function body. For example, it does not apply to functions like, that only uses T for result. Constraint type inference Another kind of type inference that is supported by Go generics is the constraint type inference. Look the sample generic function above, you can see the type of the parameter U is defined as ~[]T and the type of parameter T is any. In such cases the compiler infers the type of the parameter U using the type of the parameter T when GenericFunc() is called. For example lets say we call this function like: The compiler now see that the type U is a slice of T and the type of the parameter T is int. Therefore it can determine from the call the type of the parameter U is of type []int. This way of inferring the the types is referred to as constraint type inference in Go generics. Go Generics Best Practices 1. Use ~ in type set definition for predefined types When creating a constraint, that has builtin types and methods in the interface, ensure the constraint specifies any builtin type using the ~ token. If ~ is missing for any of the builtin types, the constraint can never be satisfied since Go builtin types cannot not have methods. For example lets define a constraint called SampleConstraint that has a String() method in the interface: Let us write a generic function that uses SampleConstraint: Now let us define a type called TestType that implements SampleConstraint: When you run this code using: you will see the following error: ./prog.go:15:10: TestType does not implement MyConstraint (possibly missing ~ for string in constraint MyConstraint) Go build failed. To fix this we need to add a ~ before the string data type as show below: 2. Type parameter constraints should be narrow and explicit This means when we write a new generic function, when we know what the expected types are, it is better to explicitly specify the type constraints that we expect our generic function to be called with like int, int32, float32 etc. rather than using "any" or interface{} as type constraints. This would allows us to seamlessly add new functionality to our generic function in future without breaking the existing code or having backward compatibility issues. For example, let say we write a new generic function to display the price of a product and we know for a fact that the type of price we get as input is expected to be of type int64 or float64. But we still go ahead and use "any" as the type constraint: Now suppose we get a requirement tomorrow to add tax to the price before displaying it, we need to make the following change to our code: But when we try to compile the code we get the following error: ./prog.go:31:18: cannot convert price (variable of type T constrained by any) to type int Go build failed. Instead if we had explicitly constrained our type parameter to int64 or float64 as shown below, our function would have worked as expected. This is one of many scenarios where having a generic function with explicit type constraints helps. The other thing is, giving a broader range of values (more than what is needed) gives scope for unexpected errors. This means that our implementation is expected to ensure that we have written all the code needed to handle failure cases for all the types specified by our type constraints. When Not To Use Generics Generics is a great tool for writing reusable code, however, it does not mean that it is always the best tool. Majority of situations that we encounter on a daily basis do NOT require generics. As a guideline if you see lots of duplicated code blocks, you could consider replacing it with generic code. If the code you are writing can be constrained down to a couple of types, then perhaps it is better to use interfaces instead. Summary Generics is a big feature introduced in go 1.18 and is an important one. Compared to other languages the Go generics implementation is much more intuitive and easy to read. Go generics implementation is designed in such a way that type parameters are not type agnostic, the constraint based implementation that Go follows is a result of years of experimentation in order of to find the right approach by the Go team. The main aim of this approach is to prevent confusion and misuse of generic types. However, Go generics is still a new feature and it has a long way to go before it could confidently use in production. We are sure, there will be improvements and new code added in the coming days to enhance the stability of the existing version. We will make sure to keep this article updated in case of any new updates or announcements. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to Code Recipe, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section. Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Problem Statement ​ Design a video streaming service like Netflix, Amazon Prime, Youtube. For your Netflix system design you can assume our platform needs to support a total 1 billion users, with 500 million being daily active users. Functional Requirements Our platform should allow users to upload videos. Users should be able to watch videos on our platform. Users should be able to search for videos. User should be able to see likes/dislikes, view count for videos. Non-Functional Requirements High availability. Our system should be reliable (We should make sure uploaded videos are not lost). Low latency (Users should not experience lag while watching videos). Consistency is important, but not at the cost of availability. It's okay if one user sees a video little later than the other user. Netflix System Design ​ Netflix system design is a common question asked in interview these days. Before we begin with the Netflix system design it is important to understand the general behavior of the system we are trying to design. Systems like Netflix, Youtube etc are generally read heavy i.e. there would lesser number of people uploading the video as compared to people viewing it. So there would be higher number of reads on our database or storage where we store our videos(a and video metadata) than writes to it. We need to keep this in mind while designing our system. We will be using microservice based architecture to design our system as compared to a monolith because of the obvious benefits. Now coming to the choice of storage, we have different kinds of data to store like user data, video metadata and the video file itself. Where does our onboarding service save the uploaded video? Can we store this in a database? It is generally not a good practice to store video files in a database because this can put a lot of pressure on our database and consume a of lot of bandwidth since fetching a video can be a slow and heavy operation(in terms of bandwidth). Distributed storage like amazon S3 are designed to store flat files like images and videos. So we would store our actual video file on S3 and store only the link to S3 on our database. Coming to user data and video metadata, data, considering the size of the user data may not be that huge we could store this on a SQL database. But we are talking about 1 billion user here, the amount of data is still considerable and can only grow overtime. Using No-SQL database would provide us better flexibility in terms of scaling horizontally or sharding if there comes a need to do so at a later point. Also looking at the use case we don't see a requirement to make complex relational queries or ones requiring joins here. So no-SQL would be a better choice. Which No-SQL solution would be a better choice for our use case? Since we know read to write ratio is high for our use case, a wide column database like Cassandra which is optimized for fast reads would suit our needs. Also since we are looking for high availability and consistency can take a back step in the interest of availability for our use case, Cassandra makes a ideal choice. Having said that it is important to note that Cassandra does promise eventual consistency. High Level View At a high level our service need to support the following main functionalities: 1. Upload videos 2. Search for videos 3. Stream videos To start with let us have three microservices to handle each of these responsibilities. We will call them onboarding service, video search service, streaming service. Let's see each of these functionalities in detail. Onboarding Videos(Uploading Videos) Uploading a video would be done by content creators. In case of a service like youtube it could be the individual creators, in Netflix it could be done by production houses. Also the length of the uploaded videos might vary slightly from platform to platform. We would not get into the details of user type discussion here, also we will assume the videos uploaded are fairly large(movies, web series etc). In either case this should not majorly impact the way we design our system. When the user uploads a video, the request hits the onboarding service. The onboarding service is responsible for uploading this video into s3. Uploading to a object storage is important because, If the size of the video is more, this would consume a lot of resources(memory) if it was to be stored in memory in video processing service during processing. It would serve as a back up in case our video processing service goes down due to some failure while processing the video. Object storage services like amazon s3 are mostly distributed services, so the chances of the uploaded videos getting lost is extremely low. After this the onboarding service saves the video metadata to our metadata database. Video Processing Once the video is uploaded to S3, we need to process the video further before making it available to our viewers. Processing a video can be a time consuming task, we may have to pass the video through multiple intermediate stages before it is ready for consumption for viewers. It would be a good idea to distribute various responsibilities involved in processing a video into different microservices because some stages of the processing might be computationally intensive and take more time, other stages might finish faster. So having a microservice to handle each stage of processing gives us more control if we had to selectively scale specific stages to improve performance. For instance, for the stages that are slow and require more time, we can have more replicas of that microservice to handle the job. Other stages that are faster may not require that many replicas. Also having a microservice to handle each stage helps in parallel processing, a faster stage does not have to wait for a slower stage until it finishes its job, after a stage finishes its job it can simply put that event in queue and take up the next task. Once the other stage is ready it can poll it from the queue. Doing a parallel processing of stages reduces the overall time needed to process the video. Video Splitter Service In system like Netflix, the size of the uploaded videos can be very large, and we would not want our microservices processing the video to have the whole video in memory for the duration of processing. Processing the whole video can increase the time needed to process the video. If the processing fails midway for some reason we would have to process the whole video again. Also having a large video in memory during processing can be expensive in terms of memory. Therefore we need to split the video into chunks and do our processing on these chunks, rather than processing the whole video. Splitting the video this way helps distribute the work and also process in parallel. In case of a failure we don't have to start from the beginning but start from the chunk until which we have successfully processed. Client apps these days have the ability to request for video of various quality and formats while viewing the video, dividing the video into chunks helps better the viewing experience as our service doesn't have to respond with the whole video again, it only needs to respond with the chunk for the requested quality and format that the user has requested. Let's call this service responsible for dividing the video into chunks as video splitter service. The video splitter service is responsible for dividing the given video into multiple chunks of smaller size. Once the video is divided into chunks the video splitter service uploads these chunks into S3. Also it updates the split video metadata in the metadata database. But you may ask how does the video splitter know when the video is uploaded to S3. And also how does the next stage(microservice) in video processing know when the video splitter service has successfully completed its job? That is a valid question. One way to achieve this is, onboarding service can explicitly notify this to video splitter service via a REST or gRPC call when it finishes its job, same can be done by video splitter service and so on. This approach works fine and should serve the purpose. But the problem with this approach is that our microservices needs to be aware of the next microservice in the video processing queue. Also this approach tightly couples the video processing stages to the microservices involved, which is something which we might not want especially when we have to scale our services later. Another way to achieve this is using a pub sub mechanism using a distributed queue like Apache Kafka. Each microservice that needs co-ordination in this case needs to register with Kafka queue. After a microservice has done its part of processing it registers a completed event in Kafka queue. The microservices in the next stage of processing poll/listen to these events and take it forward from there. In this approach each microservice need not know other microservices in the processing stage, neither do they need to communicate with them. Microservices only communicate with Kafka and hence this would also scale well. If tomorrow we had to add another microservice into our video processing sequence, all that we have to do is add another microservice to handle the processing for that stage and register it with Kafka, the next service can listen to this even and take it further from there. We need not have knowledge of other microservices or what they do. Video Encoder Service The next step in our video processing sequence is to encode these chunks. We can have another microservice, lets say video encoder service, that handles this part of the processing. The video encoder service is responsible for encoding the video into different formats, quality and resolution. This is necessary because, Our video will be viewed on multiple types of devices. By users with different network bandwidth, so users might request for video of various quality depending upon their network speed. Once the encoder service successfully encodes each of these chunks into various combinations of video format, quality and resolution it registers a completed event in the Kafka queue. It updates the encoded video metadata in the metadata database. Content Verification Service The next stage in our processing is verification of the contents of the video. The content verification service is responsible for checking the video for restricted content like violence, nudity etc. If this check fails a notification will be sent to the uploader of the video along with the reason for rejection. If the video is successfully verified, content verification service registers a completed event in the Kafka queue. Video Tagging service Video tagging service is responsible for creating tags for uploaded videos. These tags could be created based on the description provided by the client during video upload among other things. All the created tags are then pushed to the elastic service. These tags can be used at a later point during video search, video recommendations etc. Once it finishes its task the video tagging service registers an event in queue. Also it uploads the fully processed video into S3. Note: We have covered some of the general steps for processing a video. Actual stages may vary for depending on the requirements. The idea is to give a general perspective on how this requirement can be handled irrespective of the stages involved. Video Distribution Service So now we have a fully processed video ready to be viewed by ours users in S3. A platform like Netflix or youtube has a global audience. If our servers and infrastructure is located in United States, someone requesting for a video from India for instance would face a lot of delay because of the network round-time. To serve our audience worldwide without delays, it may not be feasible for us to place our servers in each of these locations. This is where the video distribution service comes into play. Video distribution service is responsible for picking up the final processed video and pushing it to our caching servers(CDN). There are several strategies how we can cache our data in these CDN servers located worldwide. We can employ a push model where we push the data into these CDN servers. There is also a pull model, in which data is pulled into the cache servers when the user requests for it the first time. Both approaches have their own pros and cons. The choice to select between the two really depends on what suits our requirements. Suppose we decide to go with the push model, it is important to consider that it may not be a good idea to push our content to all CDN servers. For instance, a bollywood released in India being cached in African CDN might not be of that much useful. The video distribution service should intelligently push these video to specific CDNs based on some intelligent algorithm. One such way may be to ask the uploader to provide target audience for the video during upload and we push only to CDN servers in provided as target regions. For a region where the content is not cached in a CDN, the first user might experience some delays while requests for the video since it has to be streamed from our servers, but later ones wont see the delay since the request would be served from nearest cached CDN server. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Video Search Video search is made simple because of the processing and tag creation done by Video tag service. Whenever a user searches for a video it is passed to the video search service and this service talks to elastic search. Remember we have provided elastic all the tags it needs during video tagging process. Elastic search provides out of the box solution for searching the given text(JSON input/output). Streaming video and managing likes, dislikes, views count When the user requests to view a video, the request is first sent to the nearest CDN server. If the video is cached, it is served from CDN. Also a copy of the video metadata containing the total likes, dislikes and views for that video is sent to the user. If the video is not cached in CDN, both the video and metadata has to be obtained from the origin server. The request hits the video streaming service which queries the metadata database which contains the URL for the requested chunk of video. The video streaming service then pulls this chunk from S3 based on the URL obtained from metadata database. Also since this data was not found in the CDN this can now be cached in the CDN server so that the next user requesting for this video doesn't have to reach the origin server to get the content. Below is the final design diagram: Netflix System Design Diagram Summary So did we cover all the functional and non-functional requirements? Our design supports uploading, streaming, searching searching videos and also viewing the like/dislike , view counts. So functional requirements are covered. Our system is reliable, Amazon S3 is promises to provide 99.999999999% durability of objects over a given year. So the chances of a video getting lost is very low. Pushing our content to CDN servers distributed across geographies ensures our users face minimum latency while streaming videos. For availability we have multiple replicas of a service running so that if one of them goes down it doesn't result in downtime for the users. Also we can take availability to another level by having multiple data centers distributed across regions, so that even if a data center in a goes down users can still be served from the other available data center. They might experience slight delays due to network round time but our service will still be available. So this covers all the functional and non functional requirements mentioned. Let me know if you have any questions by commenting below. Make sure you checkout our other posts. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. You can explore more such amazing articles from code recipe in our blogs section. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.

Introduction Singleton Design Pattern is a creational design pattern. Singleton pattern lets you ensure that only one instance of a class (struct in go) is created. This single instance created is called singleton object or singleton instance. Singleton pattern lets you ensure that a class has only one instance, thereby providing a global access to this instance. The singleton pattern usually provides a global method which is responsible for creating and returning this singleton instance. This global method wraps the object creation logic thereby hiding the complexity from the client. The user of this object might not even realize that he is working with a singleton object. When we say singleton object is accessible globally, it is important we make sure that we wont allow clients to modify this global object. Once the singleton object is created the pattern should ensure that it is immutable. Otherwise the client or application may end up seeing an unexpected behaviour while using this object. The singleton pattern ensures that the object is created only once, and once it is created the pattern returns the same object without any modification, no matter how many times the client tries to get the object. To ensure that the singleton object is accessed globally and that it cannot be modified once created, singleton pattern encapsulates the singleton object inside a globally accessible method, also you need to make the instance unexported which guarantees it is not accessible directly outside the package. Use cases where singleton pattern is useful: Database connection object: In case of a database, creating a database connection object is usually an expensive operation since it needs a lot of heavy-lifting to be done in the background. So, ideally what we would want in this case is to create the database connection object once and reuse it across our application rather than creating a new object for each call. This makes singleton pattern an ideal choice for this use case. Logger: Even in case of logging for an application, enabling or disabling logs, changing the severity of logged messages etc needs to be done on a single instance which makes singleton pattern suitable for this case. Implementation As mentioned earlier, we need to provide a global GetInstance() method to our users. The first caller who calls this method creates the singleton instance. For rest of the callers we return the same instance which was created earlier. As simple as it may seem, it is very easy to get the singleton pattern wrong. Lets discuss some of the correct ways to create the singleton pattern in go. In go the singleton pattern can be implemented in two ways mainly: Using mutex locks. Using the Once.Do() method in sync package. Using Mutex Locks One way to implement the singleton pattern in go is to make use of mutex locks. You can find the mutex lock methods (Lock and Unlock) in go "sync" package. Below is a implementation using mutex locks: The idea here is simple. During the program execution, the first thread or go routine to call the GetInstance() method acquires the lock and continues execution to the next line of code. After this point no matter how many threads try to call the GetInstance() method, they will be locked at line 13 in code, they wont be allowed to proceed further since the first thread has already acquired the lock. The first thread satisfies "if instance == nil" condition and therefore enters the if block and creates a singleton instance (line 17) and returns it (line 19). Once the first thread returns from GetInstance() method the mutex lock is released and next thread (in order as they are called) acquires the lock. But now onward "if instance == nil" condition is always false since the first thread has already created a singleton instance. Therefore all threads after the first thread simply return from the GetInstance() method without creating a new instance. Thus the GetInstance() method returns a single instance of singleton struct no matter how many times it is called. This approach works fine and does serve its purpose of creating a singleton instance. But there is one slight drawback in the above implementation. Mutex locks can be expensive because it needs to do some bookkeeping in the background to ensure that no more than one thread or go routine acquires lock at a time, among other things. This is especially true when there are multiple threads trying to acquire a lock. In the above implementation, if there are 100 calls to GetInstance() method, all 100 threads will acquire a lock before returning the singleton instance. But we know acquiring a lock after the first thread (after the singleton instance is created) is unnecessary. The purpose of using mutex lock is to ensure that if multiple threads try to access the GetInstance() method at the same time, in parallel, the GetInstance() methods doesn't create multiple instances (multiple copies) of our singleton struct. However, we can modify the above implementation slightly to overcome this drawback. All that we have to do is wrap lines 13-18 within another "instance == nil" check. This way all calls to GetInstance() method that come after the first call doesn't have to acquire a lock, our GetInstance() method can simply return the singleton instance after the outer "instance == nil" check. Below is the modified solution: The first (outer) if statement checks if the thread needs to acquire lock, and the second (inner) if statement tell us if the singleton instance is already created or we need to create it. Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses: Udemy Video Tutorials - Available at 95% off System Design Interview Complete Guide Cracking The Coding Interview - Most Preferred Book For Coding Interviews Data Structures And Algorithms - A Complete Guide Learn In-Demand Tech Skills And Stay Ahead Of Others Using "Once.Do()" Method Another way to implement the singleton pattern in golang is by using the Once.Do() method in sync package. The library ensures that the code within once.Do() block is executed only once, this guarantee is implicitly provided by go. Note: To know more about the internal working of Once.Do() method refer this. Below is the implementation using Once.Do(): In this method we place the singleton instance creation code inside the Once.Do() block instead of using the mutex locks. The Once.Do() method also uses mutex locks internally, so it is necessary to use the outer if statement even for this approach. Output We can test both these implementations using the the below code snippet: The above snippet creates 1000 go routines which call the GetInstance() method almost in parallel. You can notice from the below output that both of our solutions print the "Creating a new singleton instance" message only once indicating only one instance of the singleton struct is created even though 1000 goroutines are invoking the GetInstance() method. That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you. If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form). You can explore more such amazing articles from code recipe in our blogs section. Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time. Join now. Follow us on social media: Facebook, Twitter, Linkedin, Tumblr, Instagram.