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.

 

The N Transmitters Problem

The Problem:
                 There is a one-dimensional road of infinite length, which extends from -∞ to +∞. There are "n' one-dimensional transistors placed on the road at various points. Each transistor emits a signal. For every transistor, the signal can be transmitted across a region "r" which may differ from transmitter to transmitter. Since the road is one-dimensional, by radius "r", we mean that the signal can be received up to "r" distance to its left and "r" distance to its right.
                 There is a group of one-dimensional beings that wish to stay on this one-dimensional road. A region on this road is said to be habitable if and only if it can get at least "k" signals from "k" different transmitters. Given the road and the transmitters and their signal radius and the value of "k", we need to find out all the regions that can be considered habitable.

Assumptions: 
                 1) There is no concept of signal strength in our world. A signal will have full strength up to its radius "r" and beyond that, it will have zero strength.
                 2) We have considered, without the loss of generality in the algorithm, the coordinates and the ranges of the transmitters to be purely integers. There will be no change in the algorithm in case we take them as floats, or doubles.
                 3) There will not be more than one transmitter on a point. If that is the case, the transmitter whose signal can travel farthest will be considered.

Brute Force Approach:
                The brute force approach would be to keep a set of each n transmitters and the regions to which each can provide signals. In this case, the required answer would be the intersection of any k sets of the n total sets just formed. The time complexity of this approach is O(ⁿC_k)

O(nLogn) Approach:

                 Algorithm Axiom: Solutions become much more efficient when the data is arranged in some particular order.
                Imagine us being a part of the one-dimensional world mentioned above. We have an infinite road in front of us. Beginning our search from somewhere in the middle is difficult because we do not know about the transmitters to our left and right. So we can make no sound decision about which direction to start looking for habitable regions in, If however, say, someone tells us that the region we are currently in is the left-most end of the range of the left-most transmitter, we know for a fact that there can be no habitable regions to our left. This makes our next step clear - to go to the right in the search of habitable regions.
                 Coming back to our algorithm, if we sort the input transmitters in the non-decreasing order of their coordinates. If we start from the first transmitter, we will traverse the list of transmitters in one direction, along with keeping a track of whether the region we are currently in habitable or not. The only question that now remains is how to keep track of habitable regions. It is impossible to keep a count of all the signals available at every point on the road, as there are infinite points.
                  Point to be noted: All habitable regions will begin from a transmitter's left-most signal limit and end at (possible another) transmitter's right-most signal limit.
                  Our task is simplified if we take into consideration the above point. To identify a region, we only require its start and end points, and these points will only be the let and right limits of some transmitters. Hence, instead of analyzing all points, we analyze only those points where a transmitters range ends or begins. There are maximum "2n" such points for "n" transmitters.

Algorithm NTransmitters (transmittersList, Integer k):
1) sortAscending(transmittersList) on their coordinates;

2) beginsEnds := list of all the left-limits and right-limits of all the transmitter signals;
3) Traverse only begin and end lists from beginsEnds[0]; //beginsEnds[0] will hold the left-most end of                                                                                           the road where a signal is being received. The                                                                                           traversal will not include all the points, just the                                                                                          "begin" and "end" points of the list.
4) If beginsEnds[i] = "begin":
               count := count+1
    Else:
               count := count-1   
5) If count >= k :
               output region as habitable; 

Following is a well-commented Java code for the above algorithm. The only other noteworthy thing is that we have maintained a TreeMap instead of the usual HashMap. TreeMap extends HashMap, but sorts the data on their key value. This is needed so that we start from the left-most begin point. (it will be the one with the least coordinate value). Also, we have maintained 2 separate lists of begin and end to optimize memory requirements, As always, anyone is free to ask any doubts or share any comments in the comments section.