## Palindrome Substring Queries

Given a string and several queries on the substrings of the given input string to check whether the substring is a palindrome or not.

Examples :
Suppose our input string is “abaaabaaaba” and the queries- [0, 10], [5, 8], [2, 5], [5, 9]

We have to tell that the substring having the starting and ending indices as above is a palindrome or not.

[0, 10] → Substring is “abaaabaaaba” which is a palindrome.
[5, 8] → Substring is “baaa” which is not a palindrome.
[2, 5] → Substring is “aaab” which is not a palindrome.
[5, 9] → Substring is “baaab” which is a palindrome.

Let us assume that there are Q such queries to be answered and N be the length of our input string. There are the following two ways to answer these queries

Method 1 (Naive)

One by one we go through all the substrings of the queries and check whether the substring under consideration is a palindrome or not.

Since there are Q queries and each query can take O(N) worse case time to answer, this method takes O(Q.N) time in the worst case. Although this is an in-place/space-efficient algorithm, but still there are more efficient method to do this.

Method 2 (Cumulative Hash)

The idea is similar to Rabin Karp string matching. We use string hashing. What we do is that we calculate cumulative hash values of the string in the original string as well as the reversed string in two arrays- prefix[] and suffix[].

How to calculate the cumulative hash values ?

Suppose our string is str[], then the cumulative hash function to fill our prefix[] array used is-

```prefix[0] = 0
prefix[i] = str[0] + str[1] * 101 + str[2] * 1012 +
...... + str[i-1] * 101i-1

For example, take the string- “abaaabxyaba”

prefix[0] = 0
prefix[1] = 97  (ASCII Value of ‘a’ is 97)
prefix[2] = 97 + 98 * 101
prefix[3] = 97 + 98 * 101 + 97 * 1012
...........................
...........................
prefix[11] = 97 + 98 * 101 + 97 * 1012 +
........+ 97 * 10110```

Now the reason to store in that way is that we can easily find the hash value of any substring in O(1) time using-

``` hash(L, R) = prefix[R+1] – prefix[L]
```

For example, hash (1, 5) = hash (“baaab”) = prefix[6] – prefix[1] = 98 * 101 + 97 * 1012 + 97 * 1013 + 97 * 1014 + 98 * 1015 = 1040184646587 [We will use this weird value later to explain what’s happening].

Similar to this we will fill our suffix[] array as-

```suffix[0] = 0
suffix[i] = str[n-1] + str[n-2] * 101 + str[n-3] * 1012 +
...... + str[n-i] * 101i-1

For example, take the string- “abaaabxyaba”

suffix[0] = 0
suffix[1] = 97  (ASCII Value of ‘a’ is 97)
suffix[2] = 97 + 98 * 101
suffix[3] = 97 + 98 * 101 + 97 * 1012
...........................
...........................
suffix[11] = 97 + 98 * 101 + 97 * 1012 + ........+ 97 * 10110```

Now the reason to store in that way is that we can easily find the reverse hash value of any substring in O(1) time using

`reverse_hash(L, R) = hash (R, L) = suffix[n-L] – suffix[n-R-1]`

where n = length of string.

For “abaaabxyaba”, n = 11
reverse_hash(1,5) = reverse_hash(“baaab”) = hash(“baaab”) [Reversing “baaab” gives “baaab”]

hash(“baaab”) = suffix[11-1] – suffix[11-5-1] = suffix[10] – suffix[5] = 98 * 1015 + 97 * 1016 + 97 * 1017 + 97 * 1018 + 98 * 1019 = 108242031437886501387

Now there doesn’t seem to be any relation between these two weird integers – 1040184646587 and 108242031437886501387

Think again. Is there any relation between these two massive integers ?

Yes, there is and this observation is the core of this program/article.

1040184646587 * 1014 = 108242031437886501387

Try thinking about this and you will find that any substring starting at index- L and ending at index- R (both inclusive) will be a palindrome if

```(prefix[R + 1] – prefix[L]) / (101L)  =
(suffix [n - L] – suffix [n – R- 1] ) / (101n – R - 1)
```

The rest part is just implementation.

The function computerPowers() in the program computes the powers of 101 using dynamic programming.

Overflow Issues:
As, we can see that the hash values and the reverse hash values can become huge for even the small strings of length – 8. Since C and C++ doesn’t provide support for such large numbers, so it will cause overflows. To avoid this we will take modulo of a prime (a prime number is chosen for some specific mathematical reasons). We choose the biggest possible prime which fits in an integer value. The best such value is 1000000007. Hence all the operations are done modulo 1000000007.

However Java and Python has no such issues and can be implemented without the modulo operator.

The fundamental modulo operations which are used extensively in the program are listed below.
(a + b) %M = (a %M + b % M) % M
(a + b + c) % M = (a % M + b % M + c % M) % M
(a + b + c + d) % M = (a % M + b % M + c % M+ d% M) % M
…. ….. ….. ……
…. ….. ….. ……

2) Multiplication-
(a * b) % M = (a * b) % M
(a * b * c) % M = ((a * b) % M * c % M) % M
(a * b * c * d) % M = ((((a * b) % M * c) % M) * d) % M
…. ….. ….. ……
…. ….. ….. ……

This property is used by modPow() function which computes power of a number modulo M
3) Mixture of addition and multiplication-
(a * x + b * y + c) % M = ( (a * x) % M +(b * y) % M+ c % M ) % M

4) Subtraction-
(a – b) % M = (a % M – b % M + M) % M [Correct]
(a – b) % M = (a % M – b % M) % M [Wrong]

5) Division-
(a / b) % M = (a * MMI(b)) % M

Where MMI() is a function to calculate Modulo Multiplicative Inverse. In our program this is implemented by the function- findMMI().

`/* A C++ program to answer queries to check whether`
`   ``the substrings are palindrome or not efficiently */`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`#define p 101`
`#define MOD 1000000007`
`// Structure to represent a query. A query consists`
`// of (L,R) and we have to answer whether the substring`
`// from index-L to R is a palindrome or not`
`struct` `Query`
`{`
`    ``int` `L, R;`
`};`
`// A function to check if a string str is palindrome`
`// in the ranfe L to R`
`bool` `isPalindrome(string str, ``int` `L, ``int` `R)`
`{`
`    ``// Keep comparing characters while they are same`
`    ``while` `(R > L)`
`        ``if` `(str[L++] != str[R--])`
`            ``return``(``false``);`
`    ``return``(``true``);`
`}`
`// A Function to find pow (base, exponent) % MOD`
`// in log (exponent) time`
`unsigned ``long` `long` `int` `modPow(unsigned ``long` `long` `int` `base,`
`                              ``unsigned ``long` `long` `int` `exponent)`
`{`
`    ``if` `(exponent == 0)`
`        ``return` `1;`
`    ``if` `(exponent == 1)`
`        ``return` `base;`
`    ``unsigned ``long` `long` `int` `temp = modPow(base, exponent/2);`
`    ``if` `(exponent %2 ==0)`
`        ``return` `(temp%MOD * temp%MOD) % MOD;`
`    ``else`
`        ``return` `((( temp%MOD * temp%MOD)%MOD) * base%MOD) % MOD;`
`}`
`// A Function to calculate Modulo Multiplicative Inverse of 'n'`
`unsigned ``long` `long` `int` `findMMI(unsigned ``long` `long` `int` `n)`
`{`
`    ``return` `modPow(n, MOD-2);`
`}`
`// A Function to calculate the prefix hash`
`void` `computePrefixHash(string str, ``int` `n, unsigned ``long` `long`
`                       ``int` `prefix[], unsigned ``long` `long` `int` `power[])`
`{`
`    ``prefix[0] = 0;`
`    ``prefix[1] = str[0];`
`    ``for` `(``int` `i=2; i<=n; i++)`
`        ``prefix[i] = (prefix[i-1]%MOD +`
`                    ``(str[i-1]%MOD * power[i-1]%MOD)%MOD)%MOD;`
`    ``return``;`
`}`
`// A Function to calculate the suffix hash`
`// Suffix hash is nothing but the prefix hash of`
`// the reversed string`
`void` `computeSuffixHash(string str, ``int` `n,`
`                       ``unsigned ``long` `long` `int` `suffix[],`
`                       ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``suffix[0] = 0;`
`    ``suffix[1] = str[n-1];`
`    ``for` `(``int` `i=n-2, j=2; i>=0 && j<=n; i--,j++)`
`        ``suffix[j] = (suffix[j-1]%MOD +`
`                     ``(str[i]%MOD * power[j-1]%MOD)%MOD)%MOD;`
`    ``return``;`
`}`
`// A Function to answer the Queries`
`void` `queryResults(string str, Query q[], ``int` `m, ``int` `n,`
`                  ``unsigned ``long` `long` `int` `prefix[],`
`                  ``unsigned ``long` `long` `int` `suffix[],`
`                  ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``for` `(``int` `i=0; i<=m-1; i++)`
`    ``{`
`        ``int` `L = q[i].L;`
`        ``int` `R = q[i].R;`
`        ``// Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `hash_LR =`
`            ``((prefix[R+1]-prefix[L]+MOD)%MOD *`
`             ``findMMI(power[L])%MOD)%MOD;`
`        ``// Reverse Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `reverse_hash_LR =`
`            ``((suffix[n-L]-suffix[n-R-1]+MOD)%MOD *`
`             ``findMMI(power[n-R-1])%MOD)%MOD;`
`        ``// If both are equal then the substring is a palindrome`
`        ``if` `(hash_LR == reverse_hash_LR )`
`        ``{`
`            ``if` `(isPalindrome(str, L, R) == ``true``)`
`                ``printf``(``"The Substring [%d %d] is a "`
`                       ``"palindrome\n"``, L, R);`
`            ``else`
`                ``printf``(``"The Substring [%d %d] is not a "`
`                       ``"palindrome\n"``, L, R);`
`        ``}`
`        ``else`
`            ``printf``(``"The Substring [%d %d] is not a "`
`                   ``"palindrome\n"``, L, R);`
`    ``}`
`    ``return``;`
`}`
`// A Dynamic Programming Based Approach to compute the`
`// powers of 101`
`void` `computePowers(unsigned ``long` `long` `int` `power[], ``int` `n)`
`{`
`    ``// 101^0 = 1`
`    ``power[0] = 1;`
`    ``for``(``int` `i=1; i<=n; i++)`
`        ``power[i] = (power[i-1]%MOD * p%MOD)%MOD;`
`    ``return``;`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``string str = ``"abaaabaaaba"``;`
`    ``int` `n = str.length();`
`    ``// A Table to store the powers of 101`
`    ``unsigned ``long` `long` `int` `power[n+1];`
`    ``computePowers(power, n);`
`    ``// Arrays to hold prefix and suffix hash values`
`    ``unsigned ``long` `long` `int` `prefix[n+1], suffix[n+1];`
`    ``// Compute Prefix Hash and Suffix Hash Arrays`
`    ``computePrefixHash(str, n, prefix, power);`
`    ``computeSuffixHash(str, n, suffix, power);`
`    ``Query q[] = {{0, 10}, {5, 8}, {2, 5}, {5, 9}};`
`    ``int` `m = ``sizeof``(q)/``sizeof``(q[0]);`
`    ``queryResults(str, q, m, n, prefix, suffix, power);`
`    ``return` `(0);`
`}`

Output :

```The Substring [0 10] is a palindrome
The Substring [5 8] is not a palindrome
The Substring [2 5] is not a palindrome
The Substring [5 9] is a palindrome

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/palindrome-substring-queries/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find if there is a subarray with 0 sum

Given an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum.

Examples:

```Input: {4, 2, -3, 1, 6}
Output: true
There is a subarray with zero sum from index 1 to 3.

Input: {4, 2, 0, 1, 6}
Output: true
There is a subarray with zero sum from index 2 to 2.

Input: {-3, 2, 3, 1, 6}
Output: false
There is no subarray with zero sum.```

simple solution is to consider all subarrays one by one and check the sum of every subarray. We can run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i. Time complexity of this method is O(n2).

We can also use hashing. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.

Example :

```arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum.
```

Following is implementation of the above approach.

`// A C++ program to find if there is a zero sum`
`// subarray`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`bool` `subArrayExists(``int` `arr[], ``int` `n)`
`{`
`    ``unordered_map<``int``,``bool``> sumMap;`
`    ``// Traverse throught array and store prefix sums`
`    ``int` `sum = 0;`
`    ``for` `(``int` `i = 0 ; i < n ; i++)`
`    ``{`
`        ``sum += arr[i];`
`        ``// If prefix sum is 0 or it is already present`
`        ``if` `(sum == 0 || sumMap[sum] == ``true``)`
`            ``return` `true``;`
`        ``sumMap[sum] = ``true``;`
`    ``}`
`    ``return` `false``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `arr[] =  {-3, 2, 3, 1, 6};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``if` `(subArrayExists(arr, n))`
`        ``cout << ``"Found a subarray with 0 sum"``;`
`    ``else`
`        ``cout << ``"No Such Sub Array Exists!"``;`
`    ``return` `0;`
`}`

Output:

`Found a subarray with 0 sum`

Time Complexity of this solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Wildcard Pattern Matching

Given a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text).

The wildcard pattern can include the characters ‘?’ and ‘*’
‘?’ – matches any single character
‘*’ – Matches any sequence of characters (including the empty sequence)

For example,

```Text = "baaabab",
Pattern = “*****ba*****ab", output : true
Pattern = "baaa?ab", output : true
Pattern = "ba*a?", output : true
Pattern = "a*ab", output : false```

Each occurrence of ‘?’ character in wildcard pattern can be replaced with any other character and each occurrence of ‘*’ with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement.

Let’s consider any character in the pattern.

Case 1: The character is ‘*’
Here two cases arise

1. We can ignore ‘*’ character and move to next character in the Pattern.
2. ‘*’ character matches with one or more characters in Text. Here we will move to next character in the string.

Case 2: The character is ‘?’
We can ignore current character in Text and move to next character in the Pattern and Text.

Case 3: The character is not a wildcard character
If current character in Text matches with current character in Pattern, we move to next character in the Pattern and Text. If they do not match, wildcard pattern and Text do not match.

We can use Dynamic Programming to solve this problem –
Let T[i][j] is true if first i characters in given string matches the first j characters of pattern.

DP Initialization:

```// both text and pattern are null
T[0][0] = true;

// pattern is null
T[i][0] = false;

// text is null
T[0][j] = T[0][j - 1] if pattern[j – 1] is '*'```

DP relation :

```// If current characters match, result is same as
// result for lengths minus one. Characters match
// in two cases:
// a) If pattern character is '?' then it matches
//    with any character of text.
// b) If current characters in both match
if ( pattern[j – 1] == ‘?’) ||
(pattern[j – 1] == text[i - 1])
T[i][j] = T[i-1][j-1]

// If we encounter ‘*’, two choices are possible-
// a) We ignore ‘*’ character and move to next
//    character in the pattern, i.e., ‘*’
//    indicates an empty sequence.
// b) '*' character matches with ith character in
//     input
else if (pattern[j – 1] == ‘*’)
T[i][j] = T[i][j-1] || T[i-1][j]

else // if (pattern[j – 1] != text[i - 1])
T[i][j]  = false
```

Below is the implementation of above Dynamic Programming approach.

`// C++ program to implement wildcard`
`// pattern matching algorithm`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Function that matches input str with`
`// given wildcard pattern`
`bool` `strmatch(``char` `str[], ``char` `pattern[],`
`              ``int` `n, ``int` `m)`
`{`
`    ``// empty pattern can only match with`
`    ``// empty string`
`    ``if` `(m == 0)`
`        ``return` `(n == 0);`
`    ``// lookup table for storing results of`
`    ``// subproblems`
`    ``bool` `lookup[n + 1][m + 1];`
`    ``// initailze lookup table to false`
`    ``memset``(lookup, ``false``, ``sizeof``(lookup));`
`    ``// empty pattern can match with empty string`
`    ``lookup[0][0] = ``true``;`
`    ``// Only '*' can match with empty string`
`    ``for` `(``int` `j = 1; j <= m; j++)`
`        ``if` `(pattern[j - 1] == ``'*'``)`
`            ``lookup[0][j] = lookup[0][j - 1];`
`    ``// fill the table in bottom-up fashion`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`    ``{`
`        ``for` `(``int` `j = 1; j <= m; j++)`
`        ``{`
`            ``// Two cases if we see a '*'`
`            ``// a) We ignore ‘*’ character and move`
`            ``//    to next  character in the pattern,`
`            ``//     i.e., ‘*’ indicates an empty sequence.`
`            ``// b) '*' character matches with ith`
`            ``//     character in input`
`            ``if` `(pattern[j - 1] == ``'*'``)`
`                ``lookup[i][j] = lookup[i][j - 1] ||`
`                               ``lookup[i - 1][j];`
`            ``// Current characters are considered as`
`            ``// matching in two cases`
`            ``// (a) current character of pattern is '?'`
`            ``// (b) characters actually match`
`            ``else` `if` `(pattern[j - 1] == ``'?'` `||`
`                    ``str[i - 1] == pattern[j - 1])`
`                ``lookup[i][j] = lookup[i - 1][j - 1];`
`            ``// If characters don't match`
`            ``else` `lookup[i][j] = ``false``;`
`        ``}`
`    ``}`
`    ``return` `lookup[n][m];`
`}`
`int` `main()`
`{`
`    ``char` `str[] = ``"baaabab"``;`
`    ``char` `pattern[] = ``"*****ba*****ab"``;`
`    ``// char pattern[] = "ba*****ab";`
`    ``// char pattern[] = "ba*ab";`
`    ``// char pattern[] = "a*ab";`
`    ``// char pattern[] = "a*****ab";`
`    ``// char pattern[] = "*a*****ab";`
`    ``// char pattern[] = "ba*ab****";`
`    ``// char pattern[] = "****";`
`    ``// char pattern[] = "*";`
`    ``// char pattern[] = "aa?ab";`
`    ``// char pattern[] = "b*b";`
`    ``// char pattern[] = "a*a";`
`    ``// char pattern[] = "baaabab";`
`    ``// char pattern[] = "?baaabab";`
`    ``// char pattern[] = "*baaaba*";`
`    ``if` `(strmatch(str, pattern, ``strlen``(str),`
`                         ``strlen``(pattern)))`
`        ``cout <<    ``"Yes"` `<< endl;`
`    ``else`
`        ``cout << ``"No"` `<< endl;`
`    ``return` `0;`
`}`

Output :

`Yes`

Time complexity of above solution is O(m x n). Auxiliary space used is also O(m x n).

Further Improvements:

We can improve space complexity by making use of the fact that we only uses the result from last row.
One more improvement is yo merge consecutive ‘*’ in the pattern to single ‘*’ as they mean the same thing. For example for pattern “*****ba*****ab”, if we merge consecutive stars, the resultant string will be “*ba*ab”. So, value of m is reduced from 14 to 6.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/wildcard-pattern-matching/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Check whether a given string is an interleaving of two other given strings

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B.
C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.

Solution:
Pick each character of C one by one and match it with the first character in A. If it doesn’t match then match it with first character of B. If it doesn’t even match first character of B, then return false. If the character matches with first character of A, then repeat the above process from second character of C, second character of A and first character of B. If first character of C matches with the first character of B (and doesn’t match the first character of A), then repeat the above process from the second character of C, first character of A and second character of B. If all characters of C match either with a character of A or a character of B and length of C is sum of lengths of A and B, then C is an interleaving A and B.

`// C/C++ program to check if given string is an interleaving`
`// of the other two strings`
`#include<stdio.h>`
`// Returns true if C is an interleaving of A and B,`
`// otherwise returns false`
`bool` `isInterleaved (``char` `*A, ``char` `*B, ``char` `*C)`
`{`
`    ``// Iterate through all characters of C.`
`    ``while` `(*C != 0)`
`    ``{`
`        ``// Match first character of C with first character`
`        ``// of A. If matches them move A to next `
`        ``if` `(*A == *C)`
`            ``A++;`
`        ``// Else Match first character of C with first `
`        ``// character of B. If matches them move B to next `
`        ``else` `if` `(*B == *C)`
`            ``B++;`
` `
`        ``// If doesn't match with either A or B, then return`
`        ``// false`
`        ``else`
`            ``return` `false``;`
`        `
`        ``// Move C to next for next iteration`
`        ``C++;`
`    ``}`
`    ``// If A or B still have some characters, then length of`
`    ``// C  is smaller than sum of lengths of A and B, so `
`    ``// return false`
`    ``if` `(*A || *B)`
`        ``return` `false``;`
`    ``return` `true``;`
`}`
`// Driver program to test above functions`
`int` `main()`
`{`
`    ``char` `*A = ``"AB"``;`
`    ``char` `*B = ``"CD"``;`
`    ``char` `*C = ``"ACBG"``;`
`    ``if` `(isInterleaved(A, B, C) == ``true``)`
`        ``printf``(``"%s is interleaved of %s and %s"``, C, A, B);`
`    ``else`
`        ``printf``(``"%s is not interleaved of %s and %s"``, C, A, B);`
`    ``return` `0;`
`}`

Output:

```  ACBG is not interleaved of AB and CD
```

Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.

Note that the above approach doesn’t work if A and B have some characters in common. For example, if string A = “AAB”, string B = “AAC” and string C = “AACAAB”, then the above method will return false.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## JavaScript Backend basics

The following article is to get started with back end development using JavaScript. This article would cover the basics and rules used in JavaScript.

JavaScript Engine

Each browser has its own JavaScript engine which is used to support the JavaScript scripts in order for them to work properly. Below are the names of the JavaScript engines used in some of the most popular browsers out there.

• Chrome: V8
• Firefox: SpiderMonkey
• Safari: JavaScript Core
• Microsoft Edge/ Internet Explorer: Chakra

ECMA Script Standard: The ECMA Script standard is a trademark scripting-language specification standardized by European Computer Manufactures Association. The ECMA Script standard sets the standard for JavaScript which is used throughout the web browsers available out there.

Types definitions in JavaScript

Dynamic Typing: The interpreter figures out the type of the variable dynamically based on certain conditions.

Primitive Data Types: The primitive data types are the data types which have no methods attached to it i.e. some defined methods cannot be used with them and they are used in isolation. Though there are ways to use those methods by wrapping these primitive data type variables (covered in the next article). The following are the data types that comes under the primitive category:

1. undefined:- If variable exists but is not defined the it is categorized under undefined.
2. null:- If variable exists but is not explicitly set the it comes under null category.
3. boolean:- The Boolean data type is to define if a variable is True or False.
4. number:- number is the data type to define a number which can be integer, floating point, double. The only problem here is that we have to allocate a memory equivalent to a double variable every time we define a number.
5. string:- This is used to define string values of a character.
6. symbol:- This is a special data type which is new in ECMA Script 6. The data type “symbol” is a primitive data type having the quality that values of this type can be used to make object properties that are anonymous.

Object
Everything in JavaScript is an object. That is each variable, string, array or any other structure that we know comes under the category of object. Java Script object can be understood by almost every language and are easy to read.

Creating objects: – There are 3 ways to create objects:
1. Using the Object() Constructor

2.Using Object literal

3. Directly specifying the values

Coercion: What we call typecasting in C, C++, Java, it is called coercion in JavaScript.
Coercion is of two types:

•  Explicit Coercion
Explicit coercion is the process by which we explicitly define a variable to a data type.
• Implicit Coercion Implicit Coercion is the process by which the interpreter dynamically type casts the variable under certain conditions.

Scope

Variable lifetime: – The variable lifetime is from where they are declared until their function ends. If no function is defined then scope of the variable is global.

Hoisting: – Function definitions are hoisted but not variable declarations. This means that when a function is declared, it is usable from anywhere within your code.

Example of hoisting: –

The above function is executed successfully when called. But if we call the function first and then define it, then also it is successfully executed. This is called function hoisting.

However variable initialization are not hoisted.

The above example is the part which proves that variable hoisting is not possible in JavaScript.
But look at the next example which is another type of hoisting defined in JavaScript.

The above output errors as undefined and as we know that undefined type is when the variable exists but is not defined. So the question is how does the variable exists even if it is declared and initialized later?
This is another type of hoisting just like function hoisting i.e. the variable ‘x’ is available to us previously.

The JavaScript engine works in two different phases:

1. Creation Phase: Before executing the code, the engine reads through the entire file and will throw a syntactic error if one is found. While it does that, any function definitions will just be saved in memory. Any variable initialization will not be run but variable names will be declared.
2. Execution Phase: The execution phase is the phase in which the code is run and hence the above variable hoisting example errors as undefined since in creation phase, the variable has been declared but not defined in the creation phase.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Linux File Hierarchy Structure

The Linux File Hierarchy Structure or the Filesystem Hierarchy Standard (FHS) defines the directory structure and directory contents in Unix-like operating systems.It is maintained by the Linux Foundation.

• In the FHS, all files and directories appear under the root directory /, even if they are stored on different physical or virtual devices.
• Some of these directories only exist on a particular system if certain subsystems, such as the X Window System, are installed.
• Most of these directories exist in all UNIX operating systems and are generally used in much the same way; however, the descriptions here are those used specifically for the FHS, and are not considered authoritative for platforms other than Linux.

1. / (Root) : Primary hierarchy root and root directory of the entire file system hierarchy.

• Every single file and directory starts from the root directory
• Only root user has the right to write under this directory
• /root is root user’s home directory, which is not same as /

2. /bin : Essential command binaries that need to be available in single user mode; for all users, e.g., cat, ls, cp.

• Contains binary executables
• Common linux commands you need to use in single-user modes are located under this directory.
• Commands used by all the users of the system are located here e.g. ps, ls, ping, grep, cp

3. /boot : Boot loader files, e.g., kernels, initrd.

• Kernel initrd, vmlinux, grub files are located under /boot
• Example: initrd.img-2.6.32-24-generic, vmlinuz-2.6.32-24-generic

4. /dev : Essential device files, e.g., /dev/null.

• These include terminal devices, usb, or any device attached to the system.
• Example: /dev/tty1, /dev/usbmon0

5. /etc : Host-specific system-wide configuration files.

• Contains configuration files required by all programs.
• This also contains startup and shutdown shell scripts used to start/stop individual programs.
• Example: /etc/resolv.conf, /etc/logrotate.conf.

6. /home : Users’ home directories, containing saved files, personal settings, etc.

• Home directories for all users to store their personal files.
• example: /home/kishlay, /home/kv

7. /lib : Libraries essential for the binaries in /bin/ and /sbin/.

• Library filenames are either ld* or lib*.so.*
• Example: ld-2.11.1.so, libncurses.so.5.7

8. /media : Mount points for removable media such as CD-ROMs (appeared in FHS-2.3).

• Temporary mount directory for removable devices.
• Examples, /media/cdrom for CD-ROM; /media/floppy for floppy drives; /media/cdrecorder for CD writer

9. /mnt : Temporarily mounted filesystems.

• Temporary mount directory where sysadmins can mount filesystems.

10. /opt : Optional application software packages.

• Contains add-on applications from individual vendors.
• Add-on applications should be installed under either /opt/ or /opt/ sub-directory.

11. /sbin : Essential system binaries, e.g., fsck, init, route.

• Just like /bin, /sbin also contains binary executables.
• The linux commands located under this directory are used typically by system aministrator, for system maintenance purpose.
• Example: iptables, reboot, fdisk, ifconfig, swapon

12. /srv : Site-specific data served by this system, such as data and scripts for web servers, data offered by FTP servers, and repositories for version control systems.

• srv stands for service.
• Contains server specific services related data.
• Example, /srv/cvs contains CVS related data.

13. /tmp : Temporary files. Often not preserved between system reboots, and may be severely size restricted.

• Directory that contains temporary files created by system and users.
• Files under this directory are deleted when system is rebooted.

14. /usr : Secondary hierarchy for read-only user data; contains the majority of (multi-)user utilities and applications.

• Contains binaries, libraries, documentation, and source-code for second level programs.
• /usr/bin contains binary files for user programs. If you can’t find a user binary under /bin, look under /usr/bin. For example: at, awk, cc, less, scp
• /usr/sbin contains binary files for system administrators. If you can’t find a system binary under /sbin, look under /usr/sbin. For example: atd, cron, sshd, useradd, userdel
• /usr/lib contains libraries for /usr/bin and /usr/sbin
• /usr/local contains users programs that you install from source. For example, when you install apache from source, it goes under /usr/local/apache2
• /usr/src holds the Linux kernel sources, header-files and documentation.

15. /proc : Virtual filesystem providing process and kernel information as files. In Linux, corresponds to a procfs mount. Generally automatically generated and populated by the system, on the fly.

• Contains information about system process.
• This is a pseudo filesystem contains information about running process. For example: /proc/{pid} directory contains information about the process with that particular pid.
• This is a virtual filesystem with text information about system resources. For example: /proc/uptime

Modern Linux distributions include a /run directory as a temporary filesystem (tmpfs) which stores volatile runtime data, following the FHS version 3.0. According to the FHS version 2.3, such data were stored in /var/run but this was a problem in some cases because this directory is not always available at early boot. As a result, these programs have had to resort to trickery, such as using /dev/.udev, /dev/.mdadm, /dev/.systemd or /dev/.mount directories, even though the device directory isn’t intended for such data.Among other advantages, this makes the system easier to use normally with the root filesystem mounted read-only. For example, below are the changes Debian made in its 2013 Wheezy release:

• /dev/.* ? /run/*
• /dev/shm ? /run/shm
• /dev/shm/* ? /run/*
• /etc/* (writeable files) ? /run/*
• /lib/init/rw ? /run
• /var/lock ? /run/lock
• /var/run ? /run
• /tmp ? /run/tmp

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Supervised and Unsupervised learning

Supervised learning as the name indicates a presence of supervisor as teacher. Basically supervised learning is a learning in which we teach or train the machine using data which is well labeled that means some data is already tagged with correct answer. After that, machine is provided with new set of examples(data) so that supervised learning algorithm analyses the training data(set of training examples) and produces an correct outcome from labeled data.

For instance, suppose you are given an basket filled with different kinds of fruits. Now the first step is to train the machine with all different fruits one by one like this:

• If shape of object is rounded and depression at top having color Red then it will be labelled as –Apple.
• If shape of object is long curving cylinder having color Green-Yellow then it will be labelled as –Banana.

Now suppose after training the data, you have given a new separate fruit say Banana from basket and asked to identify it.

Since machine has already learnt the things from previous data and this time have to use it wisely. It will first classify the fruit with its shape and color, and would confirm the fruit name as BANANA and put it in Banana category. Thus machine learns the things from training data(basket containing fruits) and then apply the knowledge to test data(new fruit).

Supervised learning classified into two categories of algorithms:

• Classification: A classification problem is when the output variable is a category, such as “Red” or “blue” or “disease” and “no disease”.
• Regression: A regression problem is when the output variable is a real value, such as “dollars” or “weight”.

Unsupervised learning

Unsupervised learning is the training of machine using information that is neither classified nor labeled and allowing the algorithm to act on that information without guidance. Here the task of machine is to group unsorted information according to similarities, patterns and differences without any prior training of data.

Unlike supervised learning, no teacher is provided that means no training will be given to the machine. Therefore machine is restricted to find the hidden structure in unlabeled data by our-self.
For instance, suppose it is given an image having both dogs and cats which have not seen ever.

Thus machine has no any idea about the features of dogs and cat so we can’t categorize it in dogs and cats. But it can categorize them according to their similarities, patterns and differences i.e., we can easily categorize the above picture into two parts. First first may contain all pics having dogs in it and second part may contain all pics having cats in it. Here you didn’t learn anything before, means no training data or examples.

Unsupervised learning classified into two categories of algorithms:

• Clustering: A clustering problem is where you want to discover the inherent groupings in the data, such as grouping customers by purchasing behavior.
• Association: An association rule learning problem is where you want to discover rules that describe large portions of your data, such as people that buy X also tend to buy Y.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Binary Tree to Binary Search Tree Conversion

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.

Examples.

```Example 1
Input:
10
/  \
2    7
/ \
8   4
Output:
8
/  \
4    10
/ \
2   7

Example 2
Input:
10
/  \
30   15
/      \
20       5
Output:
15
/  \
10    20
/      \
5        30```

Solution
Following is a 3 step solution for converting Binary tree to Binary Search Tree.
1) Create a temp array arr[] that stores inorder traversal of the tree. This step takes O(n) time.
2) Sort the temp array arr[]. Time complexity of this step depends upon the sorting algorithm. In the following implementation, Quick Sort is used which takes (n^2) time. This can be done in O(nLogn) time using Heap Sort or Merge Sort.
3) Again do inorder traversal of tree and copy array elements to tree nodes one by one. This step takes O(n) time.

Following is C implementation of the above approach. The main function to convert is highlighted in the following code.

`/* A program to convert Binary Tree to Binary Search Tree */`
`#include<stdio.h>`
`#include<stdlib.h>`
`/* A binary tree node structure */`
`struct` `node`
`{`
`    ``int` `data;`
`    ``struct` `node *left;`
`    ``struct` `node *right;`
`};`
`/* A helper function that stores inorder traversal of a tree rooted`
`  ``with node */`
`void` `storeInorder (``struct` `node* node, ``int` `inorder[], ``int` `*index_ptr)`
`{`
`    ``// Base Case`
`    ``if` `(node == NULL)`
`        ``return``;`
`    ``/* first store the left subtree */`
`    ``storeInorder (node->left, inorder, index_ptr);`
`    ``/* Copy the root's data */`
`    ``inorder[*index_ptr] = node->data;`
`    ``(*index_ptr)++;  ``// increase index for next entry`
`    ``/* finally store the right subtree */`
`    ``storeInorder (node->right, inorder, index_ptr);`
`}`
`/* A helper function to count nodes in a Binary Tree */`
`int` `countNodes (``struct` `node* root)`
`{`
`    ``if` `(root == NULL)`
`     ``return` `0;`
`    ``return` `countNodes (root->left) +`
`           ``countNodes (root->right) + 1;`
`}`
`// Following function is needed for library function qsort()`
`int` `compare (``const` `void` `* a, ``const` `void` `* b)`
`{`
`    ``return` `( *(``int``*)a - *(``int``*)b );`
`}`
`/* A helper function that copies contents of arr[] to Binary Tree. `
`   ``This functon basically does Inorder traversal of Binary Tree and `
`   ``one by one copy arr[] elements to Binary Tree nodes */`
`void` `arrayToBST (``int` `*arr, ``struct` `node* root, ``int` `*index_ptr)`
`{`
`    ``// Base Case`
`    ``if` `(root == NULL)`
`      ``return``;`
`    ``/* first update the left subtree */`
`    ``arrayToBST (arr, root->left, index_ptr);`
`    ``/* Now update root's data and increment index */`
`    ``root->data = arr[*index_ptr];`
`    ``(*index_ptr)++;`
`    ``/* finally update the right subtree */`
`    ``arrayToBST (arr, root->right, index_ptr);`
`}`
`// This function converts a given Binary Tree to BST`
`void` `binaryTreeToBST (``struct` `node *root)`
`{`
`    ``// base case: tree is empty`
`    ``if``(root == NULL)`
`       ``return``;`
`    ``/* Count the number of nodes in Binary Tree so that`
`       ``we know the size of temporary array to be created */`
`    ``int` `n = countNodes (root);`
`    ``// Create a temp array arr[] and store inorder traversal of tree in arr[]`
`    ``int` `*arr = ``new` `int``[n];`
`    ``int` `i = 0;`
`    ``storeInorder (root, arr, &i);`
`    ``// Sort the array using library function for quick sort`
`    ``qsort` `(arr, n, ``sizeof``(arr[0]), compare);`
`    ``// Copy array elements back to Binary Tree`
`    ``i = 0;`
`    ``arrayToBST (arr, root, &i);`
`    ``// delete dynamically allocated memory to avoid meory leak`
`    ``delete` `[] arr;`
`}`
`/* Utility function to create a new Binary Tree node */`
`struct` `node* newNode (``int` `data)`
`{`
`    ``struct` `node *temp = ``new` `struct` `node;`
`    ``temp->data = data;`
`    ``temp->left = NULL;`
`    ``temp->right = NULL;`
`    ``return` `temp;`
`}`
`/* Utility function to print inorder traversal of Binary Tree */`
`void` `printInorder (``struct` `node* node)`
`{`
`    ``if` `(node == NULL)`
`        ``return``;`
`    ``/* first recur on left child */`
`    ``printInorder (node->left);`
`    ``/* then print the data of node */`
`    ``printf``(``"%d "``, node->data);`
`    ``/* now recur on right child */`
`    ``printInorder (node->right);`
`}`
`/* Driver function to test above functions */`
`int` `main()`
`{`
`    ``struct` `node *root = NULL;`
`    ``/* Constructing tree given in the above figure`
`          ``10`
`         ``/  \`
`        ``30   15`
`       ``/      \`
`      ``20       5   */`
`    ``root = newNode(10);`
`    ``root->left = newNode(30);`
`    ``root->right = newNode(15);`
`    ``root->left->left = newNode(20);`
`    ``root->right->right = newNode(5);`
`    ``// convert Binary Tree to BST`
`    ``binaryTreeToBST (root);`
`    ``printf``(``"Following is Inorder Traversal of the converted BST: \n"``);`
`    ``printInorder (root);`
`    ``return` `0;`
`}`

Output:

```Following is Inorder Traversal of the converted BST:
5 10 15 20 30

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all nodes at distance k from a given node

Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.

```Consider the tree shown in diagram

Input: target = pointer to node with data 8.
root = pointer to node with data 20.
k = 2.
Output : 10 14 22

If target is 14 and k is 3, then output
should be "4 20"

```

There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.

Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed . Here we call the function as printkdistanceNodeDown().

How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.

Following is the implementation of the above approach.

`#include <iostream>`
`using` `namespace` `std;`
`// A binary Tree node`
`struct` `node`
`{`
`    ``int` `data;`
`    ``struct` `node *left, *right;`
`};`
`/* Recursive function to print all the nodes at distance k in the`
`   ``tree (or subtree) rooted with given root. See  */`
`void` `printkdistanceNodeDown(node *root, ``int` `k)`
`{`
`    ``// Base Case`
`    ``if` `(root == NULL || k < 0)  ``return``;`
`    ``// If we reach a k distant node, print it`
`    ``if` `(k==0)`
`    ``{`
`        ``cout << root->data << endl;`
`        ``return``;`
`    ``}`
`    ``// Recur for left and right subtrees`
`    ``printkdistanceNodeDown(root->left, k-1);`
`    ``printkdistanceNodeDown(root->right, k-1);`
`}`
`// Prints all nodes at distance k from a given target node.`
`// The k distant nodes may be upward or downward.  This function`
`// Returns distance of root from target node, it returns -1 if target`
`// node is not present in tree rooted with root.`
`int` `printkdistanceNode(node* root, node* target , ``int` `k)`
`{`
`    ``// Base Case 1: If tree is empty, return -1`
`    ``if` `(root == NULL) ``return` `-1;`
`    ``// If target is same as root.  Use the downward function`
`    ``// to print all nodes at distance k in subtree rooted with`
`    ``// target or root`
`    ``if` `(root == target)`
`    ``{`
`        ``printkdistanceNodeDown(root, k);`
`        ``return` `0;`
`    ``}`
`    ``// Recur for left subtree`
`    ``int` `dl = printkdistanceNode(root->left, target, k);`
`    ``// Check if target node was found in left subtree`
`    ``if` `(dl != -1)`
`    ``{`
`         ``// If root is at distance k from target, print root`
`         ``// Note that dl is Distance of root's left child from target`
`         ``if` `(dl + 1 == k)`
`            ``cout << root->data << endl;`
`         ``// Else go to right subtree and print all k-dl-2 distant nodes`
`         ``// Note that the right child is 2 edges away from left child`
`         ``else`
`            ``printkdistanceNodeDown(root->right, k-dl-2);`
`         ``// Add 1 to the distance and return value for parent calls`
`         ``return` `1 + dl;`
`    ``}`
`    ``// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE`
`    ``// Note that we reach here only when node was not found in left subtree`
`    ``int` `dr = printkdistanceNode(root->right, target, k);`
`    ``if` `(dr != -1)`
`    ``{`
`         ``if` `(dr + 1 == k)`
`            ``cout << root->data << endl;`
`         ``else`
`            ``printkdistanceNodeDown(root->left, k-dr-2);`
`         ``return` `1 + dr;`
`    ``}`
`    ``// If target was neither present in left nor in right subtree`
`    ``return` `-1;`
`}`
`// A utility function to create a new binary tree node`
`node *newnode(``int` `data)`
`{`
`    ``node *temp = ``new` `node;`
`    ``temp->data = data;`
`    ``temp->left = temp->right = NULL;`
`    ``return` `temp;`
`}`
`// Driver program to test above functions`
`int` `main()`
`{`
`    ``/* Let us construct the tree shown in above diagram */`
`    ``node * root = newnode(20);`
`    ``root->left = newnode(8);`
`    ``root->right = newnode(22);`
`    ``root->left->left = newnode(4);`
`    ``root->left->right = newnode(12);`
`    ``root->left->right->left = newnode(10);`
`    ``root->left->right->right = newnode(14);`
`    ``node * target = root->left->right;`
`    ``printkdistanceNode(root, target, 2);`
`    ``return` `0;`
`}`

Output:

```4
20```

Time Complexity: At first look the time complexity looks more than O(n), but if we take a closer look, we can observe that no node is traversed more than twice. Therefore the time complexity is O(n).

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Custom Tree Problem

You are given a set of links, e.g.

```a ---> b
b ---> c
b ---> d
a ---> e```

Print the tree that would form when each pair of these links that has the same character as start and end point is joined together. You have to maintain fidelity w.r.t. the height of nodes, i.e. nodes at height n from root should be printed at same row or column. For set of links given above, tree printed should be –

```-->a
|-->b
|   |-->c
|   |-->d
|-->e```

Note that these links need not form a single tree; they could form, ahem, a forest. Consider the following links

```a ---> b
a ---> g
b ---> c
c ---> d
d ---> e
c ---> f
z ---> y
y ---> x
x ---> w```

The output would be following forest.

```-->a
|-->b
|   |-->c
|   |   |-->d
|   |   |   |-->e
|   |   |-->f
|-->g

-->z
|-->y
|   |-->x
|   |   |-->w
```

You can assume that given links can form a tree or forest of trees only, and there are no duplicates among links.

Solution: The idea is to maintain two arrays, one array for tree nodes and other for trees themselves (we call this array forest). An element of the node array contains the TreeNode object that corresponds to respective character. An element of the forest array contains Tree object that corresponds to respective root of tree.

It should be obvious that the crucial part is creating the forest here, once it is created, printing it out in required format is straightforward. To create the forest, following procedure is used –

```Do following for each input link,
1. If start of link is not present in node array
Create TreeNode objects for start character
Add entries of start in both arrays.
2. If end of link is not present in node array
Create TreeNode objects for start character
Add entry of end in node array.
3. If end of link is present in node array.
If end of link is present in forest array, then remove it
from there.
4. Add an edge (in tree) between start and end nodes of link.
```

It should be clear that this procedure runs in linear time in number of nodes as well as of links – it makes only one pass over the links. It also requires linear space in terms of alphabet size.

Following is Java implementation of above algorithm. In the following implementation characters are assumed to be only lower case characters from ‘a’ to ‘z’.

`// Java program to create a custom tree from a given set of links.`
`  `
`// The main class that represents tree and has main method`
`public` `class` `Tree {`
`    `
`    ``private` `TreeNode root;`
`  `
`    ``/* Returns an array of trees from links input. Links are assumed to `
`       ``be Strings of the form "<s> <e>" where <s> and <e> are starting`
`       ``and ending points for the link. The returned array is of size 26`
`       ``and has non-null values at indexes corresponding to roots of trees`
`       ``in output */`
`    ``public` `Tree[] buildFromLinks(String [] links) {`
`          `
`        ``// Create two arrays for nodes and forest`
`        ``TreeNode[] nodes = ``new` `TreeNode[``26``];  `
`        ``Tree[] forest = ``new` `Tree[``26``];          `
`  `
`        ``// Process each link `
`        ``for` `(String link : links) {`
`              `
`            ``// Find the two ends of current link`
`            ``String[] ends = link.split(``" "``);`
`            ``int` `start = (``int``) (ends[``0``].charAt(``0``) - ``'a'``); ``// Start node`
`            ``int` `end   = (``int``) (ends[``1``].charAt(``0``) - ``'a'``); ``// End node             `
`                        `
`            ``// If start of link not seen before, add it two both arrays`
`            ``if` `(nodes[start] == ``null``) `
`            ``{                `
`                ``nodes[start] = ``new` `TreeNode((``char``) (start + ``'a'``));   `
`                `
`                ``// Note that it may be removed later when this character is`
`                ``// last character of a link. For example, let we first see`
`                ``// a--->b, then c--->a.  We first add 'a' to array of trees`
`                ``// and when we see link c--->a, we remove it from trees array.`
`                ``forest[start] = ``new` `Tree(nodes[start]);                                            `
`            ``} `
`             `
`            ``// If end of link is not seen before, add it to the nodes array`
`            ``if` `(nodes[end] == ``null``)                             `
`                ``nodes[end] = ``new` `TreeNode((``char``) (end + ``'a'``));                                 `
`            `
`            ``// If end of link is seen before, remove it from forest if `
`            ``// it exists there.`
`            ``else` `forest[end] = ``null``; `
` `
`            ``// Establish Parent-Child Relationship between Start and End`
`            ``nodes[start].addChild(nodes[end], end);`
`        ``}        `
`        ``return` `forest;`
`    ``}`
`  `
`    ``// Constructor `
`    ``public` `Tree(TreeNode root) { ``this``.root = root;  }  `
`   `
`    ``public` `static` `void` `printForest(String[] links)`
`    ``{`
`        ``Tree t = ``new` `Tree(``new` `TreeNode(``'\0'``));`
`        ``for` `(Tree t1 : t.buildFromLinks(links)) {`
`           ``if` `(t1 != ``null``)  `
`           ``{  `
`              ``t1.root.printTreeIdented(``""``);`
`              ``System.out.println(``""``);`
`           ``}  `
`        ``}`
`    ``}        `
`  `
`    ``// Driver method to test`
`    ``public` `static` `void` `main(String[] args) {`
`        ``String [] links1 = {``"a b"``, ``"b c"``, ``"b d"``, ``"a e"``};`
`        ``System.out.println(``"------------ Forest 1 ----------------"``);`
`        ``printForest(links1);       `
`        `
`        ``String [] links2 = {``"a b"``, ``"a g"``, ``"b c"``, ``"c d"``, ``"d e"``, ``"c f"``,`
`                            ``"z y"``, ``"y x"``, ``"x w"``};`
`        ``System.out.println(``"------------ Forest 2 ----------------"``);`
`        ``printForest(links2);      `
`    ``}`
`}`
`// Class to represent a tree node`
`class` `TreeNode {    `
`    ``TreeNode []children;`
`    ``char` `c;`
`    `
`    ``// Adds a child 'n' to this node`
`    ``public` `void` `addChild(TreeNode n, ``int` `index) { ``this``.children[index] = n;}  `
`    `
`    ``// Constructor`
`    ``public` `TreeNode(``char` `c) { ``this``.c = c;  ``this``.children = ``new` `TreeNode[``26``];}`
`    `
`    ``// Recursive method to print indented tree rooted with this node.`
`    ``public` `void` `printTreeIdented(String indent) {        `
`            ``System.out.println(indent + ``"-->"` `+ c);`
`            ``for` `(TreeNode child : children) {`
`              ``if` `(child != ``null``)  `
`                ``child.printTreeIdented(indent + ``"   |"``);`
`            ``}        `
`    ``}    `
`}`

Output:

```------------ Forest 1 ----------------
-->a
|-->b
|   |-->c
|   |-->d
|-->e

------------ Forest 2 ----------------
-->a
|-->b
|   |-->c
|   |   |-->d
|   |   |   |-->e
|   |   |-->f
|-->g

-->z
|-->y
|   |-->x
|   |   |-->w```

Exercise:
In the above implementation, endpoints of input links are assumed to be from set of only 26 characters. Extend the implementation where endpoints are strings of any length.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at