Find first occurrence of a string in another

Problem: Typical question for indexOf operation. Given two strings s1 and s2, find the first index of s2 in s1 in an efficient manner.

Solution: The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched. If found, then go ahead and look for other matches character by character. A code to do the same is as under,

public static int findStringInString(String stringToSearchIn,

String stringToSearchFor) {
  int lengthIn = stringToSearchIn.length();
  int lengthFor = stringToSearchFor.length();
   
  if(lengthFor > lengthIn) {
//   System.out.println("Sub-string candidate is larger than original string");
   return -1;
  }
   
  if(lengthFor == lengthIn) {
   for(int index = 0; index < lengthIn; index++) {
    if(stringToSearchIn.charAt(index) != stringToSearchFor.charAt(index)) {
     // no match found
     return -1;
    }
   }
   return 0;
  }
   
  // lengthFor < lengthIn
  for(int index = 0; index < (lengthIn - lengthFor); index++) {
   if(stringToSearchIn.charAt(index) == stringToSearchFor.charAt(0)) {
    boolean found = true;
    // first char match found
    // check if the string beyond this is equal
    for(int subIndex = 0; subIndex < lengthFor; subIndex++) {
     if(stringToSearchIn.charAt(index + subIndex) != 

stringToSearchFor.charAt(subIndex)) {
      // no match
      found = false;
      break;
     }
    }
    if(found) {
//     System.out.println("Match found at index: " + index + " 

                                          //in original string.");
//     System.out.println(stringToSearchIn.substring(index, index + lengthFor));
     return index;
    }
   }
  }
   
  return -1;
 }

Above is not the most efficient implementation. As strings get longer in length, one may employ various mechanisms to check for equality. One such method being checking for the first character - if that results in a match, compare the last character. If that succeeds as well, go ahead and check the second and then second last character. This way one can zero down to matches to the center of the string being searched for. This particular approach considers that some words are used again and again in a string, but the longer the strings the probability of repetition of the letter at same index zero's down.

Read More

Row consisting max continuous chain of 1’s in an n * n grid

Problem: Given an n * n grid consisting of only ZEROs and ONEs, such that if in a row a ZERO is present all elements to the right of it will be ZEROs. Thus, a row can start with ONEs and end in only ZEROs, there cannot be a mix and match. You need to find the row with maximum ONEs in a given row. For example in the grid below,

1 1 1 0 0
1 0 0 0 0
0 0 0 0 0
1 1 1 1 0
1 1 0 0 0

In the example above, row 4 has the maximum continuous chain of ONEs.
Solution: One’s first guess would be to crawl through each row, finding the maximum number of ONEs in each and keep traversing till the end. Considering the fact that finding ONEs in a given row will take O(n) time and traversing each row will take its own O(n) time, taking the total time complexity to O(n²), the solution, though perfect would not be optimal as the value of n tends to get larger.
A better solution is to find the position of last ONE in the first row, which takes O(n) time. Considering the example above, it is the 3rd element. Now traverse down row by row, checking the 3rd element of each row. In case the element is ONE, check the next element for being ONE. In the example above, we see that row 2 and row 3 do not yield a ONE on column 3. But row 4 does. Now the 4th element in row 4 is also a ONE, and thus, we move down on column 4 now. In row 5, it is a ZERO and hence, the row with maximum number of ONEs will be row 4.
This particular approach involves checking first x elements of row 1, and then crawling down through each row checking for one element, occasionally moving right if needed. Thus, considering the worst case where a row contains all ONEs, we will crawl n rows down, and n elements to the right. This lowers down the time complexity to O(n) which surely better than the first approach.
Hope this helps. 

Read More

Convert a Number (unknown base) to a Base 10 Number

Problem

Given an integer, write a program that converts the given number to a number (in base 10). The base of the given number is unknown.

Solution

The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3, 4, 5 - or base 6.

Working on this assumption, it becomes fairly simple to code a function that will return a number for the given string representation of the number. The following JAVA code sample does the same, extending the above assumption to include digits 0 to 9 and characters A to Z, where A represents 10, B represents 11 and so on.
Once we assume base b, we can do following:
From LSB to MSB, multiple the digit by Math.pow(base,position) and sum them up.

Example 1 :

   2123 = (2 * 32) + (1 * 31) + (2 * 30) 
        = (2 * 9) + (1 * 3) + (2 * 1)
        = 18 + 3 + 2
        = 2310

Example 2

   11A11 = (1 * 112) + (1 * 111) + (A * 110) 
        = (1 * 121) + (1 * 11) + (10 * 1)
        = 121 + 11 + 10
        = 14210

Here is the code :

public Double convertUnknownBaseNumberToBase10(String number) {
  // null check
  if(number == null || number.length() == 0) {
   return null;
  }
   
  // turn to upper case - so that our logic below is easy
  number = number.toUpperCase();
 
  // scan through the string to find out the maximum number or the character
  int maxAscii = 0;
  for(int i = 0; i < number.length(); i++) {
   int ascii = number.charAt(i);
   if(!(((ascii >= '0') && (ascii <= '9')) || ((ascii >= 'A') && (ascii <= 'Z')))) {
    System.out.println("Illegal number, can have only digits (0-9) and letters (A-Z)");
    return null;
   }
   maxAscii = Math.max(ascii, maxAscii);
  }
   
  // check if the number has letters or not
  double finalNumber = 0;
  int length = number.length();
  if(maxAscii >= 'A') {
   int maxNumber = maxAscii - 'A' + 10 + 1;
   for(int i = 0; i < length; i++) {
    int charCode = number.charAt(i);
    if(charCode >= 'A') {
     charCode = charCode - 'A' + 10;
    }
    int num = charCode;
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  } else {
   int maxNumber = maxAscii - '0' + 1;
   // just iterate over a normal loop
   for(int i = 0; i < length; i++) {
    int num = number.charAt(i) - '0';
    finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
   }
  }
   
  return finalNumber;
 }

Thanks.

Read More

Majority element in the array

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.

Example
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

METHOD 1 (Basic)
The basic solution is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break the loops and return the element having maximum count. If maximum count doesn’t become more than n/2 then majority element doesn’t exist.
Time Complexity: O(n*n).
Auxiliary Space : O(1).

METHOD 2 (Using Binary Search Tree)

We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. 
Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree
{
  int element;
  int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)


METHOD 3 (Using Moore’s Voting Algorithm)
Given the assumption that the element occurs more than N/2 times in the array simplifies the solution a lot. This is so because if more than N/2 elements are the same, it implies that all other elements combined are less than N/2. Hence, the difference between the count of majority element and the count of non-majority numbers will always be positive. This approach can significantly simplify our code to the problem.


This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.


In the solution we consider the first element as the majority element and keep the count as 1. Now we compare the second (next) element with this element. If it is the same element we increase the count to 2, else decrease the count to ZERO and keep the first element as the majority element. Check the next element. If it is equal increase the count, else set the majority element to be the given current element and make the count as ONE.


This way, at the end of the traversal of the list, we will have the majority element with us.

Time complexity - As comparison between two elements takes constant time, the code will run in O(n) time where n is the number of elements in the list.

public static void printMajorElement(String[] args) {
  int[] list = new int[] {1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2};
   
  int count = 1;
  int majorityElement = list[0];
  for(int index = 1; index < list.length; index++) {
   if(majorityElement != list[index]) {
    if(count == 0) {
     majorityElement = list[index];
     count++;
    } else {
     count--;
    }
   } else {
    count++;
   }
  }
   
  System.out.println("Majority Element: " + majorityElement);
 }

Dry running the above program:
Lets consider the array A = {1,2,3,4,2,3,2,1,2,3,4,2,2,2}

Initially, majority element = 1 i.e. list(0), count=1
Now we traverse through the array. As next eleement is 2, we decrement the count to 0 because majorityElement 1 is not equal to list[1];

Now, we have count = 0. Again 1 is not equal to 3 and this time count=0, hence we change majority element to 3, count =1.

Now we have 4, and as 3!=4, we decrement count again.

 Next time 3!=2, we again decrement count, and point majority element to 2, and increment count =2.

Hence we see depending on if count>0, we are getting a majority element.

Thanks.

Read More

encodeURIComponent and decodeURIComponent in Java

A very common task when working with Webservices, is to encode/decode specific URI components, and for there is no direct API in Java for the same, it gets a difficult. Below is the code piece that I have been using for quite some time now.

public static final String ALLOWED_CHARS = "abcdefghijklmnopqrstuvwxyz"+

"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_.!~*'()";
 
 public static String encodeURIComponent(String input) {
  if(StringUtils.isEmpty(input)) {
   return input;
  }
   
  int l = input.length();
  StringBuilder o = new StringBuilder(l * 3);
  try {
   for (int i = 0; i < l; i++) {
    String e = input.substring(i, i + 1);
    if (ALLOWED_CHARS.indexOf(e) == -1) {
     byte[] b = e.getBytes("utf-8");
     o.append(getHex(b));
     continue;
    }
    o.append(e);
   }
   return o.toString();
  } catch(UnsupportedEncodingException e) {
   e.printStackTrace();
  }
  return input;
 }
  
 private static String getHex(byte buf[]) {
  StringBuilder o = new StringBuilder(buf.length * 3);
  for (int i = 0; i < buf.length; i++) {
   int n = (int) buf[i] & 0xff;
   o.append("%");
   if (n < 0x10) {
    o.append("0");
   }
   o.append(Long.toString(n, 16).toUpperCase());
  }
  return o.toString();
 }
 
 public static String decodeURIComponent(String encodedURI) {
  char actualChar;
 
  StringBuffer buffer = new StringBuffer();
 
  int bytePattern, sumb = 0;
 
  for (int i = 0, more = -1; i < encodedURI.length(); i++) {
   actualChar = encodedURI.charAt(i);
 
   switch (actualChar) {
    case '%': {
     actualChar = encodedURI.charAt(++i);
     int hb = (Character.isDigit(actualChar) ? actualChar - '0'
       : 10 + Character.toLowerCase(actualChar) - 'a') & 0xF;
     actualChar = encodedURI.charAt(++i);
     int lb = (Character.isDigit(actualChar) ? actualChar - '0'
       : 10 + Character.toLowerCase(actualChar) - 'a') & 0xF;
     bytePattern = (hb << 4) | lb;
     break;
    }
    case '+': {
     bytePattern = ' ';
     break;
    }
    default: {
     bytePattern = actualChar;
    }
   }
 
   if ((bytePattern & 0xc0) == 0x80) { // 10xxxxxx
    sumb = (sumb << 6) | (bytePattern & 0x3f);
    if (--more == 0)
     buffer.append((char) sumb);
   } else if ((bytePattern & 0x80) == 0x00) { // 0xxxxxxx
    buffer.append((char) bytePattern);
   } else if ((bytePattern & 0xe0) == 0xc0) { // 110xxxxx
    sumb = bytePattern & 0x1f;
    more = 1;
   } else if ((bytePattern & 0xf0) == 0xe0) { // 1110xxxx
    sumb = bytePattern & 0x0f;
    more = 2;
   } else if ((bytePattern & 0xf8) == 0xf0) { // 11110xxx
    sumb = bytePattern & 0x07;
    more = 3;
   } else if ((bytePattern & 0xfc) == 0xf8) { // 111110xx
    sumb = bytePattern & 0x03;
    more = 4;
   } else { // 1111110x
    sumb = bytePattern & 0x01;
    more = 5;
   }
  }
  return buffer.toString();
 }

Read More

atoi() in Java

Problem: Write a function to convert an ASCII string to integer, similar to atoi() function of C++.

Solution: The solution is too simple, it's simple checks for erroneous inputs that makes writing such a function fun.

public class AsciiToInteger {
  
 public static void main(String[] args) {
  AsciiToInteger instance = new AsciiToInteger();
  int x = instance.atoi("-683");
  System.out.println("Conversion is: " + x);
 }
 
 private int atoi(String number) {
  // check for NULL or empty
  if(number == null || number.trim().length() == 0) {
   throw new IllegalArgumentException("Number cannot be null/empty.");
  }
 
  // create a variable to store the result
  int result = 0;
   
  // trim the number
  number = number.trim();
   
  // check for sign as the first character
  boolean negate = false;
  char sign = number.charAt(0);
   
  if(sign == '+' || sign == '-') {
   if(sign == '-') {
    negate = true;
   }
    
   number = number.substring(1);
  }
   
  int length = number.length();
  for(int index = 0; index < length; index++) {
   char digit = number.charAt(index);
    
   // sanitize the digit
   if(!(digit >= '0' && digit <= '9')) {
    throw new IllegalArgumentException("Number contains characters other than digits at index " + index);
   }
    
   digit = (char) (digit - '0');
    
   result += (digit * Math.pow(10, (length - index - 1)));
  }
   
  // if negative, do it
  if(negate) {
   result = 0 - result;
  }
   
  // return the final result
  return result;
 }
 
}

Read More

In-Place Character Array Compression

Problem: Given a character stream as an array, compress the characters in place appending the number of continuous characters by the numerical value and then the character. The array is terminated by a 0x00 character.

Solution: Another classic interview problem which tests multiple skills in a single problem, namely,

• Conversion from integer to ascii - the number returned is a integral value which needs to be converted to ascii and then put in place in stream
• Skills with pointers (not the real pointers) when operating on an array

The following JAVA code illustrates how to work up the given problem. It makes use of an itoa() method that was explained before here.

Code:

public class CharacterArrayCompression {
 
    public static void main(String[] args) {
        String stream = "aaaaaaaaaaaaaaaaaaaaabbbbbbssssskkkkjkkdkksdkkk"

                        +    "deeeekkllsssiii";
        char[] characters = stream.toCharArray();
        compress(characters);
        System.out.println(characters);
    }
 
    private static void compress(char[] characters) {
        if(characters == null || characters.length <= 1) {
            // do nothing if we are not provided with any data
            // or if we have a single character
            return;
        }
         
        char current = characters[0];
        int count = 1;
        int destination = 0;
        for(int index = 1; index < characters.length; index++) {
            char found = characters[index];
            if(current == found) {
                count++;
            } else {
                // compress and store the value
                if(count > 1) {
                    char[] value = IntegerToAscii.itoa(count);
                    for(int j = 0; j < value.length; j++) {
                        char temp = value[j];
                        if(temp != '\0') {
                            characters[destination++] = temp;
                        }
                    }
                }
                characters[destination++] = current;
                 
                // reset to the new occurence of character
                current = found;
                count = 1;
            }
        }
         
        for(int index = destination; index < characters.length; index++) {
            characters[index] = '\0';
        }
    }
 
}

Read More

itoa() in Java

Problem: Write a function to convert an integer value to its ASCII equivalent and return as a character array, similar to itoa() function of C++.

Solution: The solution may seem tricky at first because the array is constructed left-to-right, whereas the number is read right-to-left. The easiest approach is to construct an array with digits from right-to-left and then reverse the array itself. The result being the number representation in character array. The other point to note which most of the folks miss is to check for negative numbers. And that is the crucial thing, an interviewer is looking for.

public class IntegerToAscii {
 
    private static final int ASCII_VALUE_OF_ZERO = 48;
 
    /**
     * Test conversion of Integer to ASCII value.
     * 
     * @param args
     */
    public static void main(String[] args) {
        int x = -2147483647;
        char[] ascii = itoa(x);
        System.out.println(ascii);
    }
 
    /**
     * Convert the given integer number to its ASCII equivalent in a character array.
     * 
     * @param number given integer number
     * @return a character array representing ASCII form of the number
     */
    private static char[] itoa(int number) {
        boolean negative = false;
        if(number < 0) {
            negative = true;
            number = 0 - number;
        }
         
        if(number >= 0 && number <= 9) {
            char temp = (char) (ASCII_VALUE_OF_ZERO + number);
            if(!negative) {
                return new char[] { temp };
            }
             
            return new char[] { '-', temp };
        }
 
        // define an array of which can hold 12 characters
        // the max integer is 10 digits long - 1 for negative character
        char[] digits = new char[12];
 
        // now let's divide the number by 10 and keep adding the remainder
        int digitPosition = 0;
         
        do {
            int remainder = number % 10;
            number = number / 10;
             
            digits[digitPosition++] = (char) (ASCII_VALUE_OF_ZERO + remainder);
        } while(number > 0);
         
        // add negative sign if needed
        if(negative) {
            digits[digitPosition++] = '-';
        }
 
        // now reverse the array
        for(int i = 0; i < digitPosition / 2; i++) {
            char temp = digits[i];
            digits[i] = digits[digitPosition - i - 1];
            digits[digitPosition - i - 1] = temp;
        }
         
        return digits;
    }
 
}

Read More

Trie Operations Complexity

Now that we've seen the basic operations on how to work with a TRIE, we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.

INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the order of whatever operation we perform over that will be in O(1) time, whereas if we use a LinkedList the number of comparisons at worst will be 26 (the number of alphabets). So for moving from one node to another, there will be at least 26 comparisons will be required at each step.

Having these in mind, for inserting a word of length 'k' we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).

Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1).

References
http://www.technicalypto.com/2010/04/trie-data-structure-part-5-complexity.html

Read More

Trie : Searching in Trie

In the previous section we saw how to insert string into TRIE. In this section, we shall see how to perform a search in the TRIE when a string or key is passed.

Consider the following TRIE as usual.

The search alogirthm involves the following steps

1. For each character in the string, see if there is a child node with that character as the content.
2. If that character does not exist, return false
3. If that character exist, repeat step 1.
4. Do the above steps until the end of string is reached. 
5. When end of string is reached and if the marker of the current Node is set to true, return true, else return false.

Using the above algorithm, lets perform a search for the key "do".

1. See whether "d" is present in the current node's children. Yes its present, so set the current node to child node which is having character "d".
2. See whether "o" is present in the current node's children. Yes its present, so set the current node to child node which is having character "o".
3. Since "o" is the end of the word, see whether marker is set to true or false. Marker is set to false which means that "do" is not registered as a word in the TRIE. So, return false.

Using the same algorithm, lets perform a search for the key "ball"

1. See whether "b" is present in the current node's children. Yes its present, so set the current node to child node which is having character "b".
2. See whether "a" is present in the current node's children. Yes its present, so set the current node to child node which is having character "a".
3. See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
4. See whether "l" is present in the current node's children. Yes its present, so set the current node to child node which is having character "l".
5. Since "l" is the end of the word, see whether marker is set to true or false. Marker is set to true which means that "ball" is registered as a word in the TRIE. So, return true

public boolean search(String s){
  Node current = root;
  while(current != null){
   for(int i=0;i<s.length();i++){    
    if(current.subNode(s.charAt(i)) == null)
     return false;
    else
     current = current.subNode(s.charAt(i));
   }
   /* 
    * This means that a string exists, but make sure its
    * a word by checking its 'marker' flag
    */
   if (current.marker == true)
    return true;
   else
    return false;
  }
  return false; 
 }

Lets understand complexity in next post.

References
http://www.technicalypto.com/2010/04/trie-data-structure-part-4-search.html

Read More

Trie : Inserting in Trie

In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.

Before we begin, assume we already have an existing TRIE as shown below.

Lets see the steps on how to insert a word "bate". Any insertion would ideally be following the below algorithm.

1. If the input string length is zero, then set the marker for the root node to be true.
2. If the input string length is greater than zero, repeat steps 3 and 4 for each character
3. If the character is present in the child node of the current node, set the current node point to the child node.
4. If the character is not present in the child node, then insert a new node and set the current node to that newly inserted node.
5. Set the marker flag to true when the end character is reached.

Now if you go through the already written code for this, you can have a better understanding by comparing it with the above algorithm.

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 }

Now lets see how the word "bate" is getting inserted. Since the word "bate" is having length greater than zero, we can start inspecting each word.

• See whether "b" is present in the current node's children (which is root). Yes its present, so set the current node to the child node which is having the character "b".
• See whether "a" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "a".
• See whether "t" is present in the current node's children. Yes its present, so set the current node to the child node which is having the character "t".
• See whether "e" is present in the current node's children. No, its not present, so create a new node with character set to "e". Since "e" is the end of the word, set the marker flag to true.

Lets see pictorially the same:

The above picture shows how the word "bate" is inserted into the existing TRIE data structure. This example clearly shows how the insertion in a TRIE happens.
We shall take a look on the Search operation in the next part.

References
http://www.technicalypto.com/2010/04/trie-data-structure-part-3-inserting.html

Read More

Implementing the TRIE ADT in java

We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present.

Node.java

package com.vaani.ds.trie;

import java.util.Collection;
import java.util.LinkedList;

/**
 * @author kc
 */
public class Node {
    char content;
    boolean marker; 
    Collection<Node> child;

    public Node(char c){
        child = new LinkedList<Node>();
        marker = false;
        content = c;
    }

    public Node subNode(char c){
        if(child!=null){
            for(Node eachChild:child){
                if(eachChild.content == c){
                    return eachChild;
                }
            }
        }
        return null;
    }
}

Now that we've defined our Node, lets go ahead and look at the code for the TRIE class. Fortunately, the TRIE datastructure is insanely simple to implement since it has two major methods insert() and search(). Lets look at the elementary implementation of both these methods.
Trie.java

package com.vaani.ds.trie;

public class Trie{
    private Node root;

    public Trie(){
        root = new Node(' '); 
    }

    public void insert(String s){
        Node current = root; 
        if(s.length()==0) //For an empty character
            current.marker=true;
        for(int i=0;i<s.length();i++){
            Node child = current.subNode(s.charAt(i));
            if(child!=null){ 
                current = child;
            }
            else{
                current.child.add(new Node(s.charAt(i)));
                current = current.subNode(s.charAt(i));
            }
            // Set marker to indicate end of the word
            if(i==s.length()-1)
                current.marker = true;
        } 
    }

    public boolean search(String s){
        Node current = root;
        while(current != null){
            for(int i=0;i<s.length();i++){    
                if(current.subNode(s.charAt(i)) == null)
                    return false;
                else
                    current = current.subNode(s.charAt(i));
            }
            /* 
             * This means that a string exists, but make sure its
             * a word by checking its 'marker' flag
             */
            if (current.marker == true)
                return true;
            else
                return false;
        }
        return false; 
    }
}

We shall look into the detailed working of the insert() and search() methods in separate posts, but I will tell you the gist of both those methods here. The insert() methods adds a new words to the already existing TRIE data structure. The search() method would return true or false based on whether the search string we specified exist or not.

Take a quick look at the java code above because we are going to use this in the posts that follow.
Inserting in Trie

References
http://www.technicalypto.com/2010/04/trie-data-structure-part-2-node-and.html

Read More

Trie ADT

TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve. TRIE (pronounced as 'try') has a wide variety of applications in

• Spell checking
• Data compression
• Computational biology
• Routing table for IP addresses
• Storing/Querying XML documents etc.,

We shall see how to construct a basic TRIE data structure in Java.

The main abstract methods of the TRIE ADT are,

public void insert(String s);
public boolean search(String s);

In this data-structure, each node holds a character instead of a String. Each node has something called as 'marker' to mark the end of a word. And each node has a Collection of child nodes. This Collection can be either a Set or a List based on the speed vs space criterion.

The basic element - Node of a TRIE data structure looks like this,

char content;
boolean marker;
Collection child;

A TRIE tree would typically look like the following

The above TRIE is constructed by inserting the words ball, bat, doll, dork, do, dorm, send, sense. The markers are denoted on the Node using a red star(*). We shall look into more about the TRIE data structure in depth in the next post.

References
http://www.technicalypto.com/2010/04/trie-in-java.html

Read More

Four People on a Rickety Bridge

Problem : 

Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?

 

Solution : 

The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 mins. Is that it? No. That would make this question too simple even as a warm up question.
Let’s brainstorm a little further. To reduce the amount of time, we should find a way for 10 and 7 to go together. If they cross together, then we need one of them to come back to get the others. That would not be ideal. How do we get around that? Maybe we can have 1 waiting on the other side to bring the torch back. Ahaa, we are getting closer. The fastest way to get 1 across and be back is to use 2 to usher 1 across. So let’s put all this together.
1 and 2 go cross
2 comes back
7 and 10 go across
1 comes back
1 and 2 go across (done)
Total time = 2 + 2 + 10 + 1 + 2 = 17 mins

Read More

Globe Walker

Problem :

How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started?

Solution : 

The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again!

Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. So what if we were standing at any point one mile north of this ring? If we walked one mile south, we would be on the ring. Then one mile east would bring us back to same point on the ring (since it’s circumference is one mile). One mile north from that point would bring us back to the point were we started from. If we count, there would be an infinite number of points north of this one mile ring.
So what’s our running total of possible points? We have 1 + infinite points. But we’re not done yet!
Consider a ring that is half a mile in circumference near the South Pole. Walking a mile along this ring would cause us to circle twice, but still bring us to back to the point we started from. As a result, starting from a point that is one mile north of a half mile ring would also be valid. Similarly, for any positive integer n, there is a circle with radius

r = 1 / (2 * pi * n)

centered at the South Pole. Walking one mile along these rings would cause us to circle n times and return to the same point as we started. There are infinite possible values for n. Furthermore, there are infinite ways of determining a starting point that is one mile north of these n rings, thus giving us (infinity * infinity) possible points that satisfy the required condition.
So the real answer to this question is 1 + infinity * infinity = infinite possible points!

Read More

Trains and Birds

Problem :

A train leaves City X for City Y at 15 mph. At the very same time, a train leaves City Y for City X at 20 mph on the same track. At the same moment, a bird leaves the City X train station and flies towards the City Y train station at 25 mph. When the bird reaches the train from City Y, it immediately reverses direction. It then continues to fly at the same speed towards the train from City X, when it reverses its direction again, and so forth. The bird continues to do this until the trains collide. How far would the bird have traveled in the meantime? 

Solution : 

Yes, you read it right. The bird is actually the fastest moving object in the problem!
Knowing that the bird is the faster than both the trains, you would only imagine that theoretically, the bird could fly an infinite number of times between the trains before they collide. This is because you know that no matter how close the trains get, the bird will always complete its trip before the crash happens. At the time of the crash, the bird would probably get squashed between the trains!
I bet sometime in school, you learnt how to sum up an infinite series. But do we have to do that?
The concept of relative speed (rings a bell?) can work handy here. Let’s assume that the distance between City X and City Y is d miles. The trains are approaching each other at a relative speed of (20 + 15) = 35 mph. The sum of the distances covered by the trains when they collide is d (i.e. the distance between the cities). Since distance/speed gives us time, we know that the trains collide d/35 hours after they start.
Since the speed of the bird is constant at 25 mph, we know that the bird would have covered

25 * (d/35) miles = 5d/7 miles

before the trains collide

Another way to put the same problem
A Prince is going to a temple in a forest by his horse which travels at a speed of 60 km per hour. When he reached the entrance of the forest, he saw a girl who is going to the temple at a speed of 6 kms per hour. He visits the temple and returns to see the girl immediately. After he sees the girl, he goes again to the temple. He roams between the temple and girl, till the girl reaches the temple after one hour. How much distance the prince travelled by roaming between the girl and the temple?

Read More