Binary Search Tree Algorithms

Just developed a reasonably well-commented code for algorithms involving Binary Search Trees. You can find it on Github with the following link:

https://github.com/Tejash241/BinarySearchTreeAlgos

It includes basic algorithms like insert, search and delete. Also including slightly advanced algorithms like height-balancing the tree in O(n) and post-order, pre-order and in-order traversals. Since some interview questions include slightly funky questions like "bottom-top view of BST", I am planning to include few of those as well. As always, all code is documented and the time and space complexity are included wherever possible. Any doubts/comments/questions/suggestions, please feel free to reach out in the comment section.

Translate Numbers to Their English Phrases

Problem Statement:
                    Write a program that takes an integer between 0-99,999 as input and output its English phrase.
For example :

             Input: 77890
             Output: Seventy Seven Thousand, Eight Hundred, and Ninety

Breaking down the problem:
              Such programs are commonly used in NLP to communicate with a user. They rarely use complex data structures or the programs are rarely complicated by themselves. They mostly are a chain of if-else conditions that handle particular cases. However, the sharpness of the programmer is tested here in the sense that he/she should handle all the possible inputs.

              If one observes above output, the commas and the word "and" are not associated with any digit in the number. However, according to the problem statement, they are very important. Such elements of the program, which need to be added for the sake of making the output "look better" or "closer to English" are often the main hurdles.
             
              Hence, there are 2 main sub-problems here. The first is to interpret the digits and convert them into their English words (taking care of their place in the number like the unnits place, tens place, etc.) and second is to take into account all the commas and the word "and" along with their placement.

Approach:
              The main hint here is the range of inputs - from 0 to 99,999. If one observes carefully, the last two digits and the first two digits always make one phrase in English. In the above input, the last digits "90" form Ninety and the first two digits "77" form Seventy Seven (along with thousand - their place value, but thats easy to predict). Hence, these will be considered in pairs. The third digit i.e. the digit in the hundred's place, is always alone. There is always a "Seven Hundred" or a "Three Hundred". There is never a "Seventy Three Hundred". Hence, logically, this is to be considered alone.

               Our first step should be to teach our program the English words, starting with the basics. The program needs to know that 0 becomes "Zero" and 1 becomes "One" and so on. Additionally, it also needs to know that 2 in tens place (or in the higher position whenever pairs are considered by the above logic) becomes "Twenty", 3 in similar position becomes "Thirty" and so on.

                English is a funny language. It is widely regarded as the toughest language for a program to learn, because of its sudden and seemingly illogical variations. For example, 11 has to become "Eleven" and not "Onety One". There is no reason why it cannot be "Onety One" for the sake of symmetry. But, such is life, and hence our program has to now learn about the phrases for the numbers from 11-19.

Trivia: The oldest Indian language, Sanskrit, is widely regarded as the easiest language for a program to learn owing to its symmetry.

                The next step is to implement the above approach. This is easy enough to do with a nested if-else tree. However, identifying the boundary conditions and all the cases and accomodating them was a pain to the author himself. For example, it is easy to overlook a small flaw in the above approach. If we take digits in pairs and check for words for them in an array, it becomes difficult for numbers with 0 as the lower number. For example, 77 becomes "Seventy Seven" by 70 is just "Seventy" and not "Seventy Zero". Hence, we need to make the 0th index of our array "unitsPlace" as an empty string. However, another issue now arises - how to handle if the input itself is just 0? This can be handles by adding yet another condition which checks if the input is 0, if it is - it simply prints "Zero" and exits. Any other 0s that might come will be translated to the null string.

                  The final step for ", and" is added to check if a phrase is not left hanging with those words as its last. There needs to be some word after "and" or else the program has some error.

Triplets of Ones

Problem Statement:

There is a String s which has a few (maybe none) '1's in it. Get all triplets of such '1's which are equidistant to each other. Output the triplet with the maximum distance 'k' between them.

Solution:

We first need to find the maximum value of distance 'k' between triplets of '1's present in the String. Obviously, the maximum possible value of k will be half the string length. So we will iterate over the value of k from s.length()/2 down to 1. We then iterate over the string to check for '1's and checking whether the characters at distances of k and 2k are also '1's.

Clearly, there are 2 variables whose iterations will determine the time complexity of the problem viz. 'k' and the string itself which needs to be traversed. Thus, one solution could be to decide on a value of 'k' in the outer loop and then traverse the string to see if this 'k' contains triplets of one.

Algorithm1{
              for k = string.length/2 down to 1 :
                   for i = 0 up to string.length-2k :
                       if string[i]=string[i+k]=string[i+2k]=1 :
                             output k;
}

Another solution could be to decide on an index in the string and then traverse over the string using different values of 'k'.

Algorithm2{
              for i = 0 upto string.length-2 :
                     for k = string.length/2 down to 1 :
                          if i+2k < string.length AND string[i]=string[i+k]=string[i+2k]=1 :
                               maxK = k; break;
              output maxK;
}

Both the solutions are asymptotically equally fast and have a time complexity of O(n²) in the average case.

However, if one observes carefully, the former method might yield faster results in cases where the answer is closer to the length of the string. This is because 'k' is decremented steadily in the former algorithm and is oputputted as soon as the condition is satisfied. This results in lesser conditional checks and in turn lesser array elements accesses leading to lesser running time.This fact, however, will not be reflected in the asymptotic performance of the algorithm, since asymptotically, it will remain O(n²) owing to the nested for loops.

Below is the Java code for the former algorithm:
 

Mapping in Java

Mapping:
                 The basic idea behind mapping is to establish a relation between two or more seemingly unrelated set of data structures. A common example of mapping is when a word string is mapped to its integer equivalent based on the ASCII values of it's characters. At a first glance, it might make little sense to develop a relationship between a string and an integer. However, mapping is very useful in programming and is, in fact, very common. 
                The main attraction to mapping is the reduced search time. While a linear search requires O(n) in the average case, search in mapping takes O(n) in worst case, only if the hashing function is not carefully chosen.

A mapping overview - buckets (ranges/numbers) mapped to keys (Strings)

(Image courtesy - Wikipedia)

Types of Mapping and Data Structures in Java:

1) One-to-one Map - java.util.hashmap:
                    HashMap is the most commonly used data structure that maps an object with a key. Both the object and the key can be of any data type, provided that the data type extends Object. Thus, primitive data types like int, float, double, etc. are not used as object and keys. Their corresponding wrapper classes like Integer, Float, Double, etc., however, can be used since they all extend Object.
                    HashMap maps any object using a key. Both the object and the key can be determined by the programmer, provided that the key is unique. Every key in the HashMap maps to one object only. Thus, this is a one-to-one mapping kind of data structure.
                     Already hashed objects can be retrieved from a key by the Map.get() method. Map.put() assigns an object to a key.

2) One-to-one bidirectional Map - org.apache.commons.collections.BidiMap:
                      One shortcoming of java.util.HashMap is that one cannot retrieve a key from its value. This is logical in the sense that the value is derived from the key, and hence the value should depend on the key and not the other way around. If, we try to search a key from a value, we may need to traverse the entire HashMap, which takes O(n) and defeats the purpose of a HashMap.
                       However, there may be times when we need to establish a bidirectional relationship between 2 objects whilst preserving the fast searching of a HashMap. Fortunately, BidiMap becomes useful in such cases. Note that in the case of BidiMap, the words "key" and "value" do not hold their semantic value. Since, both depend on each other, neither is a key. Both are simply values, strictly speaking.
                       BidiMap gives a convenient function getKey() which returns the key for the value argument. Both the key and value can be anything that extends the Object class. Again, "key" and "values" should not be taken literally.


3) One-to-many Map using java.util.hashmap:
                         Although generally used for one-to-one mapping, we can implement one-to-many mapping using java.util.hashmap. As mentioned earlier, the value can be anything that extends Object, we can use a List, or an ArrayList, or any other Collection for that matter as value, thus making the map one-to-many.
                          One key will thus map to one list of values. These values may now be arranged in any order as possible. If there is a specific order in the values, then an ArrayList is preferred, since it provides arbitrary access via indexes. In any case, the primary point of consideration here should be that the values must be arranged in a way that the main advantage of using a Map i.e. O(1) average search time should not be compromised to a large extent.

Traversing through a Map in Java:
                           There are a few ways to traverse through a map in Java, but the one we suggest is using an Iterator via a Map.Entry of the map. After assigning an iterator to a map, it traverses through the map via its next() method. A Map.Entry will create an Entry object from which the key and the value of the Entry can be easily obtained via the getKey() and getValue() methods. Both HashMap and BiDiMap can be traversed in the same way.

 

Arbitrary Precision Types In Java

QUESTION : 
What will be the output in the following code snippet?

Here's the snapshot of the output of the above function

NOTE : 
For built-in primitive data types such as int, long, double, etc. Java never throws any overflow or underflow exception, even though the size and the bounds for these data types is defined. 

Why? Because all data is internally stored by the JVM in binary-format. Thus, in actual memory, each variable, whether int or double is stored as a string of 1's and 0's. There is no concept of a "negative sign" in binary system. Negative numbers are stored in a special format called 2's complement . 

Hence, when the bound on any data type is reached and exceeded, the JVM simply reverses the sign of the number and prints the largest number in that sign. For example, in the above example, if we exceed 2147483647 which is the upper bound on int, the sign is reversed to negative and the value of smallest possible int is printed.

How do we avoid this? By casting the number into a larger data type and checking its value. If indeed, overflow or underflow has occurred, we can throw an exception and take the necessary rectification. Following is a code snippet which illustrates this.

What if overflow/underflow is a valid case in my problem?
Overflow is a valid case practically when problems involving very large numbers are present. In such cases, a way to implement variables is to use Arbitrary Precision Data Types. Java offers 2 arbitrary precision types : BigInteger and BigDecimal in java.math library.

The word "arbitrary precision" means that a variable of such type uses exactly as much space as required or mentioned. Thus, the precision is "set" according to our needs. Theoretically, there is no limitation to the size, the only limitations being that of insufficient memory. 

It is important to note that these data types are implemented internally as a collection of primitive data type. Thus, BigInteger is implemented as an array of ints. Also, these are implemented classes and not default and Java does not allow operator overloading. Thus, primitive operations such as addition, multiplication, power, etc. although present for these classes, do not use operators such as "+", "*" etc. Instead, they use functions such as a.add(b), a.multiply(b), etc. Since the use of functions is involved, the operations tend to be slower.

BigInteger is generally used for large integers and BigDecimal is used when extremely high levels of precisions is required (1000th decimal place of π).

Number Of Possible Triangles In An Array

We have "n" sticks with us. The length of each stick is known to us. We need to find the number the triangles that can possibly be made from these sticks. The condition for making a triangle is that the sum of any two sides of the triangle should be greater than the third side. i.e. if a, b, c form a triangle, then :
1) a+b>c
2) b+c>a
3) a+c>b

INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".

OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.

BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have ⁿC₃ = ϴ(n³) comparisons. Following is the brute force approach:

Algorithm bruteForce(int[n] a)

1. For (i = 0 upto n-3)
2.      For(j = i+1 upto n-2)
3.           For(k = j+1 upto n-1)
4.                  if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5.                        count++

A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then  (a, b, c) can form a triangle.

This manipulation is illustrated as follows : 
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.

The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.

Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n³. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.

Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).