28 April 2010

Find three numbers in an array which forms a maximum product

This problem again is asked as a coding question in one of the top companies. I have provided the solution for this in C++.

Question: 
Given an array of integers (unsigned integers > 0), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)


Solution:
The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.
I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman (My honorable room mate, college mate, work colleague)
// Version     : v1
// Copyright   : open
// Description : To find three largest numbers in an array in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main()
{
 int a[10] = {1,2,33,4,15,6,7,28,9,10};
 int largest_1 = 0, largest_2 = 0, largest_3 = 0;

 for(int i=0;i<10;i++)
 {
  if(a[i] > largest_3 && a[i] < largest_2)
  {
   largest_3 = a[i];
  }
  else if(a[i] > largest_2 && a[i] < largest_1)
  {
   largest_3 = largest_2;
   largest_2 = a[i];
  }
  else if(a[i] > largest_1)
  {
   largest_3 = largest_2;
   largest_2 = largest_1;
   largest_1 = a[i];
  }
 }
 cout << "largest :" << largest_1 << endl;
 cout << "2nd largest :" << largest_2 << endl;
 cout << "3rd largest :" << largest_3 << endl;
 return 0;
}

Cheers!!
Bragaadeesh

Find the last person seated around in a circle program/puzzle

This is a programming question asked at one of the class companies. Following is the question

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)


Me and my roommate both implemented a solution for the above problem one in Java and the other in C++ respectively. Please see the code and the ouput for the above problem below.

Implementation in Java

package brainteasers;

public class FindWinner {
 public static void main(String[] args) {
  FindWinner finder = new FindWinner();
  char winner = finder.findWinner(10,3);
  System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
 }
 
 private char findWinner(int n, int m){
  char[] people = getPeople(n);
  boolean[] eliminated = new boolean[n];
  //always start from 1st person
  int remainingGuys = n;
  int current = 0;
  
  while(remainingGuys>1){
   int inkiPinki=0;
   
   while( eliminated[current] || ++inkiPinki != m )
       current = (current+1) % n;
   
   eliminated[current] = true;
   printStatus( eliminated, people );
   remainingGuys--;
   
   while(eliminated[(current+1)%n]){
    current++;
   }
   
   current = (current+1)%n;
  }
  
  System.out.println();
  return people[current];
 }

 private void printStatus(boolean[] eliminated, char[] people) {
  System.out.println();
  for(int i=0;i<eliminated.length;i++){
   char output;
   if(eliminated[i]){
    output = people[i];
   }else{
    output = (char)(people[i] - 32);
   }
   System.out.print(output+" ");
  }
 }

 private char[] getPeople(int n) {
  char[] people = new char[n];
  System.out.println("Participants are...");
  for(int i=0;i<n;i++){
   people[i] = (char)(i+97);
   System.out.print((char)(people[i]-32)+" ");
  }
  System.out.println();
  return people;
 }
}
/*
Participants are...
A B C D E F G H I J 

A B c D E F G H I J 
A B c D E f G H I J 
A B c D E f G H i J 
A b c D E f G H i J 
A b c D E f g H i J 
a b c D E f g H i J 
a b c D E f g h i J 
a b c D e f g h i J 
a b c D e f g h i j 

And the winner is D!!
*/

Implementation in C++

//============================================================================
// Name        : puzzle.cpp
// Author      : Prabhu Jayaraman
// Version     : 0.1
// Copyright   : Free
// Description : Find Last man stand
//============================================================================

#include <iostream>
using namespace std;

int FindWinner(int n, int m)
{
 int a[n];
 for(int i=0;i<n;i++)
 {
  a[i] = 1;
 }
 int e = 0;
 int c = 0;
 for(int i=0;;i++)
 {
  if(e == (n-1))
   break;
  if(a[i%n] == 1)
   c++;
  if(c == m)
  {
   a[i%n] = 0;
   e++;
   c = 0;
  }
 }
 for(int i=0;i<n;i++)
 {
  if(a[i] == 1)
   return i+1;
 }
 return -1;
}

int main()
{
 int x = FindWinner(20,19);
 cout << x << endl;
 return 0;
}

Cheers,
Bragaadeesh

10 April 2010

TRIE data structure Part 6 : A Sample UI




Lets have a look at a sample application in Swing. We load the TRIE data structure using a dictionary word list. And using the application we can perform a search. This application is a very much prototypical just to check the insert() and search() operations.

Input file : words.txt

Sample Application


There are two possible outcomes to our search criteria, one true and another false. The following is the dialog shown when a word "article" is entered.

And when a word something like "dasdsa" is entered the following dialog is shown.


The Java code for the Trie Loader,

package dsa.tries;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class TrieLoader {
 
 public static Trie trieDSA;

 public static void main(String[] args) {
  TrieLoader trieLoader = new TrieLoader();
  trieLoader.load();
  new TrieTestFrame();
 }
 
 public void load(){
  trieDSA = new Trie();
  BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File("src/properties/words.txt")));
   String eachLine = null;
   while((eachLine=br.readLine())!=null){
    trieDSA.insert(eachLine);
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally{
   if(br!=null){
    try {
     br.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}

The TrieTestFrame,

package dsa.tries;

import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TrieTestFrame extends JFrame {

 private static final long serialVersionUID = 1L;
 
 private JPanel basePanel = new JPanel();
 private JTextField textField = new JTextField(20);
 private JButton button = new JButton("Check");

 public TrieTestFrame(){
  designUI();
 }
 
 private void designUI(){
  this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  this.setTitle("TRIE Test");
  
  button.addActionListener(new ActionListener() {
   @Override
   public void actionPerformed(ActionEvent e) {
    if(TrieLoader.trieDSA.search(textField.getText())){
     JOptionPane.showMessageDialog(basePanel, "The word you entered exist!!");
    }else{
     JOptionPane.showMessageDialog(basePanel, "The word you entered does not exist!!","Error",JOptionPane.ERROR_MESSAGE);
    }
   }
  });
  
  basePanel.add(textField);
  basePanel.add(button);
  
  add(basePanel);
  
  this.setSize(400,100);
  
  Toolkit tk = Toolkit.getDefaultToolkit();
     Dimension screenSize = tk.getScreenSize();
     int screenHeight = screenSize.height;
     int screenWidth = screenSize.width;
     setLocation(screenWidth / 2 - 200, screenHeight / 2 - 50);
  
  this.setVisible(true);
 }
}

For the Node and Trie class please click here.

Cheers,
Bragaadeesh.

TRIE data structure Part 5 : Complexity Analysis




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).

TRIE data structure Part 4 : The SEARCH Algorithm




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; 
 }

The above java code does the search operation in the TRIE data structure. We shall look more into the running time and efficiency of TRIE in the next part.

Cheers,
Bragaadeesh.

02 April 2010

TRIE data structure Part 3 : The INSERT Algorithm




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.


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.

Cheers,
Bragaadeesh.

TRIE data structure Part 2 : Node and TRIE class in Java




In the first part of the TRIE ADT, we saw the basics of the TRIE data structure. In this section, lets get our hands dirty by directly looking at the TRIE data structure implemented 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.

package dsa.tries;

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

/**
 * @author Braga
 */
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.

package dsa.tries;

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.

Cheers,
Bragaadeesh.

TRIE data structure Part 1: The TRIE ADT in Java





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<Node> 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.