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.

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.

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.

In our previous article we learnt how to find the middle node in a singly linked list. In this article we will discuss how to reverse a given singly linked list. Problem Statement Write an algorithm to reverse the given singly linked list. Examples Example 1: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 5 -> 4 -> 3 -> 2 -> 1 Example 2: Input: 2 -> 4 -> 6 Output: 6 -> 4 -> 2 Prerequisites Fundamental understanding of singly linked lists. Solution 1: Using Stack We can use the properties of a stack data structure to reverse a given linked list. Problems involving reversing something (strings, series of characters, numbers, lists etc), can mostly be solved using stacks. Stack is a last in first out (LIFO) data structure. We push and pop elements from the top of stack. We can use this to our advantage to reverse the given list. Notice: We will soon publish a detailed article on stack data structure. The idea is to first push all the nodes of the given linked list into the stack, then pop them one by one and reconnect the nodes thereby reversing the list. The intuition behind this approach is based on the fact that the list nodes that are pushed into stack (from start to end) when popped out will be in reverse order. For a given linked list this algorithm does the following steps: Traverse the given singly linked list starting from the head node. As we visit each node, we add it to the top of stack. We need to do this for all the nodes in the list. Once all the nodes are added to stack, pop them one be one. Make the first node to be popped from stack as the head of linked list (this is the last node in the original list). For all the other popped nodes, connect the next pointer of previously popped node to the current popped node. Lets understand this with an example. Consider you are given the below linked list: Lets take a stack to store these nodes. Initially the stack is empty as shown below: Traverse the linked list starting from the head node and add them to stack. So we begin by adding node 1 to stack. Next we move our current pointer to node 2, add node 2 to stack. Finally we add node 3 to stack. Now that all the linked list nodes are added to stack, we need to pop them one by one from stack. First we pop node 3 from stack. Since node 3 is the first node to be popped, we make it the head node of the linked list. Next we pop node 2 from stack. Also we need to connect the next of previously popped node, node 3, to the current node, node 2. Finally we pop node 1 from stack and connect the next of node 2 to node 1. As you can see, we have successfully reversed the given linked list using stack. Implementation Language: Go Stack Implementation Complexity Analysis Time Complexity: O(n) In this approach we need to visit each node in the list twice to reverse it (once to add it to the stack, and again to pop it from stack). So, the time complexity is O(n) + O(n) = 2 * O(n) which in general can be represented as O(n). Space Complexity: O(n) Space complexity is also O(n) since we store each node in stack. 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: Flipping the next pointer Solution 1 reverses the list in O(n) time but it also needs O(n) space because we use stack to store nodes. Also we need to visit each node twice. This problem can be efficiently solved by simply flipping the next pointer of each node (to point to the previous node). For a given linked list, this algorithm does the following steps: Take 3 pointer variables: current, previous and next each of which point to the current, previous and next nodes respectively. Initially current points to the head node and previous points to null. In each iteration, point next to current.next, and connect current.next to previous which flips the next pointer of the current node. After that move the next and previous pointers ahead by one node. Repeat this for all the nodes in the list. Finally make the last node as the new head of the list. Let us understand this with an example. Consider you are given the below linked list: Iteration 1 To begin with current points to head node and previous points to null as shown in the figure below: Now flip the next pointer of the current node by first pointing next to current.next and then pointing current.next to previous. Node 1 is now completely processed, so move the current and previous pointers ahead by one step. Iteration 2 Now node 2 is the current node. Process node 2 similar to node 1 to flip its next pointer. Move the current and previous pointer to the next node. Iteration 3 Finally process node 3 in the same way by pointing next to current.next, current.next to previous. Since node 3 is the last node in our list, we stop our algorithm here. Also one final thing we need to do is to make the last node as our new head as shown in figure below: Implementation Language: Go Language: Java Complexity Analysis Time Complexity: O(n) In this algorithm we need to visit each node in the given linked list only once. So time complexity is O(n). Space Complexity: O(1) No extra space is used. Now you know how to reverse a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists. 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. 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 learnt what a singly linked list is and how to implement it in various languages. In this article we will see how to find the middle element or middle node in a singly linked list. Note: Same approach can be used to find the middle element in a doubly linked list as well. Problem Statement Given a singly linked list, find the middle element in it. If there are even number of nodes in the given linked list then return the ceil value node as the middle element. E.g. if there are 6 nodes in the given linked list, then node 4 should be considered as the middle node. Examples Example 1: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 3 Example 2: Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 Output: 8 Solution 1: Counting Nodes This method works on the idea of counting the total no. of nodes in the given linked list and using this information to find out which is the middle element. This algorithm involves the following steps: Traverse all the nodes in the given linked list starting from the head node. Take a variable to keep track of the count of total nodes traversed. Lets call this variable nodeCount. Once you have the count of total nodes in a linked list, you can get the middle node using middleNode = nodeCount/2. Now traverse the linked list again from the head node until middleNode. To do this take a variable currentNodeCount to keep track of the current node count. As you visit each node, increment this counter by 1. When currentNodeCount is equal to middleNode we have reached the middle node, return the middle node. Implementation Note: For linked list, node class/struct definitions please refer our singly linked list article. Language: Go Language: Java Complexity Analysis Time Complexity: O(n) Since we make 2 passes (one full pass and one pass till the middle node) on the given linked list, time complexity is O(n) + O(n/2) which in general can be represented as O(n). 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: Two Pointer Technique As you might have noticed in solution 1, we have to traverse the given linked list twice in order to find the middle node, first to count the total number of nodes and then till the middle element to return the result. This problem can be solved more efficiently using the two pointer technique. In this method we have to traverse the list just once to arrive at the result. This approach works on the idea that, when we move the two pointers, one pointer twice as fast as the other, by the time the fast pointer reaches the end of the list, the slow pointer would have moved till the middle of the list. This algorithm involves the following steps: Take two pointers variables, lets call them fast and slow. Initially both fast and slow points to the head node of the given linked list. slow pointer moves one step at a time and fast pointer moves two steps at a time. We need to move the fast and slow pointers from the head node until the fast pointer reaches end of the list. When the fast pointer reaches the last node, slow pointer would have reached the middle node since it is moving at half the pace as the fast pointer. So when the fast pointer reaches the last node, return the slow pointer node as your result. Lets understand this with an example. Consider you are given the below linked list: We point the slow and fast pointers initially to the head node as shown in figure below: Now, in each iteration we move the slow pointer one step at a time and fast pointer two steps at a time until fast pointer reaches the last node. Same is shown in the below diagrams. Iteration 1 Iteration 2 Once the fast pointer reaches the last node (node 5 in this case) we return the slow pointer which is currently pointing to the middle node (node 3 in this case) as the result. Implementation Language: Go Language: Java Complexity Analysis Time Complexity: O(n) Time complexity is O(n) since we need to make one pass on the given linked list. Space Complexity: O(1) No extra space is used. Now you know how to find middle element in a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists. 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. 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 Linked list is a linear data structure. Each element in a linked list is an individual object. These individual objects are called nodes. As the name suggests a linked list is formed by interconnecting a series of such nodes. Nodes are connected using pointers. Each node internally contains data and a link to the next node (address of the next node). In general a node in a linked list appears as shown in figure below: The first node in a linked list is called a head node. The head node is the entry point to a linked list. Unlike arrays linked list elements are not indexed, we cannot access any random element using an index like arrays. We always start traversing the linked list from the head node no matter which element we need to access in the list. The last node in a linked list is not connected to any node. The next pointer of the last node always points to null. Linked list can contain any type of data like int, string, character etc. Elements can all be unique or it can also contain duplicates. Also the elements in a linked list can be sorted or unsorted. Unlike arrays elements in a linked list are not stored in contiguous locations in memory. Each node is stored in arbitrary location in memory and connected to each other using next pointer. Why Linked List? Arrays are fixed size structures. Once an array is declared you cannot change its size. If the array is full and a new element needs to be added, you need to declare a new array (of larger size) and copy all the elements from the old array into the new array. This can be an expensive operation especially for large arrays. Linked list unlike arrays are dynamic in nature, they do not have a fixed size. We just a have to create a new node and link it to our list each time a new element needs to be added. Another scenario where a linked list is useful is when you do not know the size of input beforehand, declaring a large array to accommodate such an input is a waste of memory. For such use cases linked list is useful because you need not specify the size while declaring a linked lists. Linked lists (especially doubly linked list) are often used because of their efficient insert and delete operations. Linked list allows you to efficiently add a new node between existing nodes in a list. This cannot be efficiently done in case of arrays. If a new element is to be added in between existing elements in arrays, you need to shift all the other elements to make space for the new element. Linked List Drawbacks Unlike arrays linked lists do not support indexing. To find nth element in a linked list we have the traverse the list from first node till nth node. Linked lists use comparatively more space than arrays since each node needs to store a link to the next or previous node in addition to storing the actual data. Arrays have a good locality of reference since the elements are stored in contiguous location in memory. But linked list nodes are placed in arbitrary locations in memory. As a result CPU can't efficiently cache linked lists like arrays. Linked List vs Arrays Arrays give you the ability to access elements in O(1) time. In linked lists you start the traversal from the first element, so the worst case time complexity for search an element in linked list is O(n). Arrays have fixed size. Linked lists have no size constraints, any number of new elements can be added to a linked list (as long as you have memory). Since linked list nodes need to store pointer to the next node in the list, they comparatively take more space as compared to arrays. Linked lists give you the flexibility to easily add and remove elements from the middle (between any nodes) as compared to arrays where you will have to shift all other elements in order to achieve this. Unlike arrays, elements in a linked list are not stored at contiguous location in memory. Elements are connected using pointers. Types Of Linked List Depending on how the nodes are connected there are various types of linked lists: Singly linked list Doubly linked list Circular linked list In this article we will discuss about singly linked list. We will cover doubly and circular linked lists in detail in a separate article. Singly Linked List A singly linked list is formed by connecting nodes using a single link between them. This single link is formed using the next pointer of the node. A singly linked list looks as shown in figure below: To implement singly linked list we need to define two structures, one for the node and one for the linked list itself. Lets define the structure for linked list first: type LinkedList struct { head *Node } The LinkedList structure has one field head which is a pointer to head node (address of the head node). As stated earlier a head node is an entry point to a linked list. So when a linked list is first created we store the address of the head node in this field and we always start traversing the linked list from the head node using the address defined in head. Next lets define the linked list node: type Node struct { data int next *Node } Node structure contains two fields: data which represents the node data (for simplicity lets assume it is of int type) and next which is a pointer to the next node in the list. In an object oriented language like Java, Python we use Class instead of struct to represent the linked list. Linked List Class Node Class 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 Inserting A Node Usually we insert new data at the end of the linked list. But there are cases where we may have to insert at head, insert after a specified node, insert before a specified node or insert at a specific position in the given linked list. Insert At The End To insert an element at the end of singly linked list we need to do the following steps: Take a temporary node pointer. We need to move this pointer from start of the list to end. Lets call this temporary node as currentNode. At the beginning currentNode points to the head node. Keep moving the currentNode pointer until it reaches the last node. Once the currentNode reaches the last node in the list, make the next pointer of the last node to point to the new node to be added i.e. currentNode.next = newNode. Implementation Language: Go Language: Java Insert Before A Node To insert a new node before a certain node, traverse the list until the node just before the specified node, then point the next of current node to the new node and next of new node to the before node. To insert a new node before a certain node in a singly linked list we need to do the following steps: Let beforeNode be the node before which we have to insert the new node and let the new node to be inserted be called newNode. Take a temporary node pointer. Lets call this temporary node as currentNode. To begin with currentNode points to the head node. Move the currentNode pointer from start of the list until the node just before the beforeNode. Now connect the next of currentNode to newNode and next of newNode to the previous next of currentNode. Lets understand this with an example. Consider you are given the below linked list: Lets say we have to add a new node with data = 3 before node 4( with data = 4). First we need to traverse the list from head the head node until node 2 (node before beforeNode). Once we reach node 2 we break the link between node 2 and 4 as show in figure below: Then we connect the next of node 2 to node 3 (new node). After that we connect the next of node 3 to node 4 as shown in figure below: As you can see in above figure node 3 is now inserted in the list before node 4. Implementation Language: Go Language: Java Insert After A Node Similarly to insert a new node after a specified node we have to traverse the list from head node until the afterNode. After that, we need to point the next of the afterNode to the newNode and next of newNode to the node previously pointed to by the afterNode. Lets understand this with an example. If we were given the below linked list and we had to insert a new node with data = 3 after node with data=2: We traverse the list from head node to until node 2. Then point next of node 2 to newNode and next of newNode to node 4. Implementation Language: Go Language: Java Deleting A Node Deleting a node from a linked list is straight forward. We need to check if the given node is present in the list. If present remove it from the list and return the deleted node. Else return null. Language: Java Get All Elements To get a list of all elements present in a linked list we need to traverse the list from the head node to the last node and return the values present. Implementation Language: Go Complexity Analysis Time Complexity Search : O(n) Worst case time complexity for search operation is O(n) as we may end up checking each node to find an element in the worst case. Worst case time complexity occurs when the node to be searched is the last node in the list or if the given node is not present in the list. Insert: O(n) Insert operation also has a worst case of O(n) as we have to go through all the nodes before inserting the new node similar to search operation. Delete: O(n) Worst case complexity of delete is also O(n). Space Complexity: O(n) Each node in a linked list needs to store link to the next node along with the actual data. This means the space needed increases linearly for each new node added. Therefore, space complexity for a singly linked list is O(n). Now you know what a singly linked list is and how to implement it. Do not stop here, deepen your knowledge by exploring more articles on linked lists. 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. 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.

Algorithm In our last article we discussed the bubble sort sorting algorithm. This is another article in the series sorting algorithms. In this article we will discuss insertion sort. Insertion sort is an in-place sorting algorithm. Insertion sort works by picking each unsorted element and placing it in its correct sorted position in the array. During its execution insertion sort divides the array into two portions, sorted portion and unsorted portion. Sorted elements will be on the left side of the array and unsorted elements will be on the right side. In each iteration one element is picked from unsorted portion and moved to its correct position in the sorted portion on the left. For a given input array arr that needs to be sorted in ascending order, insertion sort does the following steps: We assume that the first element is already sorted and start from the second element in the array. We compare the second element to the element before it. If the current element is less than the element before it, we swap the two elements. Next we move on to the third element and compare to all elements before it and swap if it is less than those elements. We need to do the above steps for all the elements in the array. To implement this algorithm we need to run two loops, an inner loop and an outer loop. Let i and j be the indexes of inner and outer loops respectively. i points to the last sorted element in the sorted portion of the array. j points to the first unsorted element in the unsorted portion in the array. To begin with we assume that the first element in the given array is sorted, so i points to the first element in the given array and j points to the second element. We fix the outer loop and iterate through the inner loop. At the start of the inner loop we assign i to j, i.e j=i. In each iteration of the inner loop check if arr[j] < arr[j-1]. As long as arr[j] < arr[j-1] we swap arr[j] and arr[j-1] decrement j. Else we break the inner loop and move on to the next iteration of the outer loop. We repeat these steps until all the elements in the given array are processed. Simulation Consider we are given the below input array: Below is a simulation of how insertion sort sorts the given array in each iteration. Element marked in green is the element under consideration for the current iteration that needs to be moved to its correct position in the sorted portion. Elements marked in grey are the elements that are already sorted. Iteration 1 To start with we assume that the first element is already sorted. We start the iteration with the second element 19 (since we assumed the first element is already sorted). We compare 19 with every element on its left until it reaches the correct sorted position or there are no more elements to compare with. First we compare 19 with the element before it, 17. Since 19 > 17, so there is no need to swap. Since there are no more elements to compare we mark 17 and 19 as sorted as shown below: Iteration 2 After the first iteration 1st two elements of the given array are sorted. In the second iteration we process the next unsorted element 4. Compare 4 with all elements on its left starting from 19 until it moves to its correct sorted position. Compare 4 with 19. 4 < 19, so swap. Next compare 4 with 17. 4<17, so swap. There are no more elements to compare with, therefore we mark 4, 17, 19 as sorted. Iteration 3 Next unsorted element is 9. As earlier we compare it with 19, 17 and 4 and move it to its correct position in the array. Now 9 is in its correct position in the array, we mark 4, 9, 17, 19 as sorted. Iteration 4 Finally we compare 7 with elements before it 19, 17, 9, 4. Mark 4, 7, 9, 17, 19 as sorted. Now all the elements in the array are sorted, so we stop our algorithm. 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 Implementation Code Language: Go Language: Python Language: Java Complexity Analysis Time Complexity: O(n^2) The worst case time complexity of the algorithm is O(n^2) since it uses two loops to arrive at the result. The worst case occurs when the array is sorted in descending order, in this case we end up making maximum number of comparisons to sort the array. Space Complexity: O(1) No extra space is used. Now you know how insertion sort works. Don't stop here, you can explore more sorting algorithms from code recipe here. 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. 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.

In our earlier article we had an overview on caching and a brief introduction to various cache eviction policies. In this article we will have a detailed discussion on LRU or Least Recently Used cache eviction policy. Introduction LRU cache or least recently used cache is one of the most popular cache eviction strategies. It is also a very commonly asked interview question. LRU cache keeps track of the order in which items in the cache were accessed. It stores items in the order in which they were requested. So the most recently used item will be at the top of the cache and the least recently used item will be at the end of the cache. In LRU strategy, when the cache is full, the item that hasn't been used for the longest time (least recently used item) will be eliminated or evicted from cache. It also provides a quick constant time access to items in cache. The idea behind LRU cache is simple, if the cache has a capacity to store n items, then LRU cache stores the n most recently used items in cache. And when the cache is full and a new item needs to be added, it makes space for the new item by evicting the least recently used item. Example Lets understand LRU cache with an example. Consider we have an application where our users can read from a collection of books. For the ease of understanding let us assume that our application has 4 books in database: book1, book2, book3 and book4 and our cache limit is 3 (3 times can be stored at max in cache). Initially the cache is empty since no requests have been made for any book. Lets look at how LRU cache stores and evicts items from cache as we try to access data from it. To begin with lets say a user makes a request for book1 from our application. Our application will check to see if the data is available in cache, since book1 is not available in cache it fetches it from database and an entry for "book1" is now stored in cache as shown below. Next we get a request for book2. Again book2 is stored in cache. Also since book2 is the most recently used item now, it is placed at the top of cache and book1 is pushed down in cache as shown in diagram below. And we get a third request for book3, so book3 is now placed at the top of cache. Now imagine we get a request for book2 again. Since book2 is already in cache our application responds to this request from cache instead of database. Also book3 is bumped down and book2 is now moved to the top of our cache since it is the most recently used item. Same is shown in diagram below: Now lets say we get a 5th request for book4. Since the cache is full, it wont be able to store book4 unless it evicts an already existing item from cache. And as per LRU cache policy, the least recently used item is the one which should be evicted in order to make space for the new item. The item at the bottom of cache is the least recently used item. So we evict book1, from cache and put book4 at the top of cache. This how a LRU cache works. It repeats the above steps for each subsequent request. Now that we know how an LRU cache works, lets see how it can be implemented. Implementation We need to implement two methods (functions), one for putting items into cache and one for getting items for cache. Lets call these methods Put() and Get() respectively. Caches in general are key-value based. This means every item in cache is stored against a key. When the item is needed we get that item from cache using the corresponding key. So, Put() will take two arguments, "key" of the item to be stored and actual "value" of the item to be stored. And Get() will take one argument, "key" of the item to be retrieved. It will also return the item corresponding to that key. So, in general our Put() and Get() methods will look like this: Put(key, value) Get(key) return value We need to consider a few things while implementing LRU cache. The data structure/structures that we choose to implement LRU cache should have the following properties: We should be able to store a list of items in cache. We should be able to keep track of items in the cache. Items should be stored in cache in the order in which they were accessed or requested. When an item is accessed from cache (new item or item already in cache) we should be able to efficiently move it to the front of cache. When an item is requested from cache we should be able to retrieve that item in constant time, O(1). We should be able to efficiently evict the least recently used item from cache when the cache is full. From the list of requirements above, one of the requirements is to have fast access to items in cache. The data structure that comes to mind when we think of constant time access to items is a hashmap or hashtable. Okay, we will store our cache items in hashmap so that it can be retrieved in O(1) time. But if you remember there is also a requirement where our cache should be able to store the order in which the items were accessed/requested. How can we maintain this order? Hashmap cannot keep track of the order of items. So how can we achieve this? We will have to use another data structure to keep track of the order in which the items were accessed. What data structure can we use to maintain order of items? For maintaining this list we can use multiple data structures like array, queue, singly, doubly linked list etc. But the important thing is whatever data structure we choose should allow us to perform write, update and delete (evict) operations efficiently to ensure that our cache is performant. Doubly linked list can perform update, write, push to front, delete operations in constant time if we have access to doubly linked list node on which these operations need to be performed. We can achieve O(1) access to doubly linked list nodes by storing the node itself in a hashmap. So in our earlier hashmap instead of storing the cache item value we store a reference to doubly linked list node (which in turn will have the cache item value). In summary, we will be using a combination of doubly linked list and hashmap to implement LRU cache. Hashmap enables fast access to items in cache and doubly linked list keeps track of the order in which the items in the cache were accessed. Key to hashmap is the cache item key and value will be doubly linked list node reference, which in turn has the cache item value. Note: Cache item "Key" can be any unique value. For example if our requirement is to store user details in cache, item "key" can be any unique value like email ID, user UUID, user name etc. One last thing that we need to consider is what happens if multiple users/threads try to write to write the same item into cache in parallel as this can lead to data corruption. We can overcome this situation using mutex locks. However introducing a global level mutex lock in Put() can prove expensive as this would block all users from writing into cache even if they are writing different items. For this reason we introduce a lightweight key based mutex lock which blocks users only when they try to write the same item at the same time. Key based mutex locks block only when two concurrent threads try to write to the same key concurrently. 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 If we consider our previous book example, LRU cache internally stores the data as shown in below diagrams and for the same sequence of requests LRU cache goes through the following changes: Request for book 1: Request for book 2. Order of items in map does not matter, it is to be ignored. Order is maintained by doubly linked list. Request for book 3. Request for book 2. Request for book 4. Code Language: Go Lets define the structures needed for implementing LRU cache. Next we will create a method which initializes and returns a new LRU cache object. Below is the implementation for put method for adding items into cache. Below is the implementation for get method for retrieving items from cache. Dummy method that simulates fetching values from database: Key based mutex locking implementation: Language: Java Coming soon... Language: Python Coming soon... Time Complexity Both the get and put methods contain constant time operations and hence the overall time complexity for both Get() and Put() is 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, 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.