Non-Intrusive Linked List

Non-Intrusive Linked List
Long time back I have seen some interesting implementation of linked list.
Recently I saw some discussion on hackernews, got again intested to understand that list implementation.
Similar implementation is used by Linux kernel linked list

Normally when a developer defines a linked list, he/she will add data part as member of linked list node
say you want to create linked list of Integers then one would have struct as follows

struct intList {
   int data;
   struct intList *prev;
   struct intList *next;
}

– Now this list is attached to data-type integer.
– You cannot have same node part of two different list.
– This is called as Intrusive Linked List.
– You have to do lot of careful surgery of list, need to check pointers is null or not.

Non-Intrusive Linked list is amazing way of getting rid of these restrictions.

Let us define a new Non-Intrusive linked list which will work with any POD in C language.

struct llhead {
  struct llhead *prev, *next;
};

Note that there is no mention of the type it is storing. This seems strange at first.
Intrusive linked lists flip the memory layout inside out. Instead of the list node providing memory for
a POD, POD provides memory for a list node. The ‘intrusive’ part of the name comes from the fact that
we store the list node inside the type POD.

Let us define some operation on this list

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)

Remember this is actually Circular doubly linked list.

Now I want to create a list of integers, this is how I will be writing my POD

struct integerList {
  struct llhead link;
  int data;
};

Initialize the head of the list.

LL_HEAD(mylist);

Here is the complete working example.

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include "ilist.h"


struct llhead {
  struct llhead *prev, *next;
};

#define LL_INIT(N)      ((N)->next = (N)->prev = (N))
#define LL_HEAD(H)      struct llhead H = { &H, &H }
#define LL_ENTRY(P,T,N) ((T *)((char *)(P) - offsetof(T, N)))
#define LL_TAIL(H, N)                   \
  do {                                  \
    ((H)->prev)->next = (N);            \
    (N)->prev = ((H)->prev);            \
    (N)->next = (H);                    \
    (H)->prev = (N);                    \
  } while (0)
#define LL_DEL(N)                       \
  do {                                  \
    ((N)->next)->prev = ((N)->prev);    \
    ((N)->prev)->next = ((N)->next);    \
    LL_INIT(N);                         \
  } while (0)
#define LL_FOREACH(H,N) for (N = (H)->next; N != (H); N = (N)->next)
#define LL_FOREACH_SAFE(H,N,T)         \
  for (N = (H)->next, T = (N)->next; N != (H);     \
      N = (T), T = (N)->next)


struct integerList {
  struct llhead link;
  int data;
};

int main(int argc, char **argv) {
  int k = 0; 
  struct llhead *head;
  static LL_HEAD(mylist);

  for ( k = 0; k < 10; k++) {
    struct integerList *elem = 
          (struct integerList *)malloc(sizeof(struct integerList));
    elem->data = k;
    LL_TAIL(&mylist, &elem->link);
  }

  LL_FOREACH(&mylist, head) {
    struct integerList *elem = LL_ENTRY(head, struct integerList, link);
    printf("%d\n", elem->data );
  }

  return 0;
}

Try me Trie

Have you ever used Auto-complete feature ?
It’s implemented using Trie. Trie is a data structure which is very efficient for searching word .
However, it has one very big disadvantage of using a lot of memory as every node contains character array of alphabet size.
It marks down the ending of word by assigning it as leaf node.
Searching a word in trie has complexity of O(n) ,where n is the length of a word searched.
Time as well as space complexity can be reduced by using Compressed Trie.

Let us write a code for Trie Datastructure

Here are some pre-processors defined which will be used later.

#define ALPHABETS_SIZE (94)
#define PIVOT_CHARACTER ((int)'!')
#define TRIE_NODE_NULLPTR (trie_t*)0
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define FOUND 1
#define NOT_FOUND 0
#define INVALID_WORD -1
#define BUFFERSIZE (1024)

C structure definition is as follows

typedef struct trie_t {
  char value;
  int isLeaf;
  int count;
  struct trie_t *trieArray[ALPHABETS_SIZE];
} trie_t;

How to create a new node of Trie.

trie_t *getNewNode() {
  int index = 0;
  trie_t *tmp = (trie_t*) malloc ( sizeof ( trie_t));
  tmp->isLeaf = 0;
  tmp->count =  0;
  for ( index = 0; index < ALPHABETS_SIZE; index++){
    tmp->trieArray[index] = TRIE_NODE_NULLPTR;
  }
  return tmp;
}

How to get the position of new character in the trieArray

int getPosition(char ch ) {
  int pos = (ch) - PIVOT_CHARACTER;
#ifdef DEBUGME 
  if ( pos > ALPHABETS_SIZE ) {
    printf("RANGE ERROR for ALPHABETS_SIZE\n");
  }
#endif
  return pos;
}

How to insert new character in the Trie

void insert(const char *word) {
  int charIndex = 0;
  trie_t *pCurrentNode = gRoot;
  if ( !word && strlen(word) != 0 ) {
    return;
  }
#ifdef DEBUGME 
  printf("Word -> %s\n", word);
#endif

  for ( charIndex = 0; charIndex < strlen(word); charIndex++) {
    /* Find the position where new character will be stored */
    int position = getPosition(word[charIndex]);
    /* If current slot is NULL create new one */
    if ( pCurrentNode->trieArray[position] ==  TRIE_NODE_NULLPTR) {
        pCurrentNode->trieArray[position] = getNewNode();
    }
    pCurrentNode->value = word[charIndex];
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  pCurrentNode->isLeaf = 1;
  pCurrentNode->count++;
}

How to search a string in trie

int search(const char *word) {
  int length = 0;
  int index = 0;


  trie_t *pCurrentNode = gRoot;

  if ( !word && strlen(word) != 0 ) {
    return INVALID_WORD;
  }
  length = strlen(word);
  for ( index = 0; index < length; index++) {
    int position = getPosition(word[index]);
    if ( pCurrentNode->trieArray[position] == TRIE_NODE_NULLPTR ) {
      return NOT_FOUND;
    }
    pCurrentNode = pCurrentNode->trieArray[position];
  } 
  
#ifdef DEBUGME 
  printf("Count for %s = %d\n", word, pCurrentNode->count);
#endif        
  return FOUND;
}       

Here is running program

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ALPHABETS_SIZE (94)
#define PIVOT_CHARACTER ((int)'!')
#define TRIE_NODE_NULLPTR (trie_t*)0
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define FOUND 1
#define NOT_FOUND 0
#define INVALID_WORD -1
#define BUFFERSIZE (1024)


typedef struct trie_t {
  char value;
  int isLeaf;
  int count;
  struct trie_t *trieArray[ALPHABETS_SIZE];
} trie_t;

trie_t *gRoot = (trie_t*)0;

trie_t *getNewNode() {
  int index = 0;
  trie_t *tmp = (trie_t*) malloc ( sizeof ( trie_t));
  tmp->isLeaf = 0;
  tmp->count =  0;
  for ( index = 0; index < ALPHABETS_SIZE; index++){
    tmp->trieArray[index] = TRIE_NODE_NULLPTR;
  }
  return tmp;
}

int getPosition(char ch ) {
  int pos = (ch) - PIVOT_CHARACTER;
#ifdef DEBUGME 
  if ( pos > ALPHABETS_SIZE ) {
    printf("RANGE ERROR for ALPHABETS_SIZE\n");
  }
#endif
  return pos;
}

void insert(const char *word) {
  int charIndex = 0;
  trie_t *pCurrentNode = gRoot; 
  if ( !word && strlen(word) != 0 ) {
    return;
  }
#ifdef DEBUGME 
  printf("Word -> %s\n", word);
#endif

  for ( charIndex = 0; charIndex < strlen(word); charIndex++) {
    /* Find the position where new character will be stored */
    int position = getPosition(word[charIndex]);
    /* If current slot is NULL create new one */
    if ( pCurrentNode->trieArray[position] ==  TRIE_NODE_NULLPTR) {
        pCurrentNode->trieArray[position] = getNewNode();
    }
    pCurrentNode->value = word[charIndex];
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  pCurrentNode->isLeaf = 1;
  pCurrentNode->count++;
}

int search(const char *word) {
  int length = 0;
  int index = 0;


  trie_t *pCurrentNode = gRoot; 

  if ( !word && strlen(word) != 0 ) {
    return INVALID_WORD;
  }
  length = strlen(word);
  for ( index = 0; index < length; index++) {
    int position = getPosition(word[index]);
    if ( pCurrentNode->trieArray[position] == TRIE_NODE_NULLPTR ) {
      return NOT_FOUND;
    }
    pCurrentNode = pCurrentNode->trieArray[position];
  }
  
#ifdef DEBUGME 
  printf("Count for %s = %d\n", word, pCurrentNode->count);
#endif
  return FOUND;
}

int main( int argc, char **argv) {
  gRoot = getNewNode();

  char buffer[BUFFERSIZE];
  while ( 1 ) {
    printf("TrieShell > ");
    fgets(buffer, BUFFERSIZE, stdin);

    if (buffer[strlen(buffer) - 1] == '\n') {
        buffer[strlen(buffer) - 1] = '\0';
    }

    if(!strcmp(buffer, "exit") || 
       !strcmp(buffer, "quit") || 
       !strcmp(buffer, "q")) {
      exit(0);
    }

    if(strstr(buffer, "insert")) {
      char *token;
      const char delim[2] = " ";
      token = strtok(buffer, delim);
      token = strtok(NULL, delim);
      while( token != NULL )  {
        insert(token);
        token = strtok(NULL, delim);
      }
    }


    if(!strcmp(buffer, "help")) {
      printf("Commands :\n");
      printf("insert <string|URL>:\n");
      printf("quit | exit | q <To exist from the shell>\n");
    }
  }
#ifdef DEBUGME 
  char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
  gRoot = getNewNode();
  int index;
  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    insert(keys[index]);
  }
  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    insert(keys[index]);
  }
  printf("Insert Done !!! \n");

  for(index = 0; index < ARRAY_SIZE(keys); index++) {
    int found = search(keys[index]);
    printf("%s --> %s\n", keys[index], found == FOUND ? "FOUND" : "NOT FOUND");
  }
  
#endif
  return 0;
}

Magical C Language, Loop Un-Rolling and Duffs Device

After so many years of working with C language. It always Surprises me. Today I came across Duff’s Device. It is really a cleaver technique.
Suppose you want to copy a buffer of 100 bytes, typical code you will write will have following construct

for ( int i = 0; i < 100; i++ ) {
    *dest++ = *source++
}

There are bunch of instruction involves here, Compare Instruction, Increment Instruction …
But important thing is this all is done for 100 times.

Duff’s Device is intelligent method of solving this following as given in following code.

#include <stdio.h>
#include <string.h>

#define SIZE 10000

void duffsDevice(const char *source, char *destination, int length) {
  int numberOfPass = 0;
  int n = (length + 7) / 8;
  switch (length % 8) {
    case 0:
      do {
        *destination++ = *source++; 
        case 7:   *destination++ = *source++; 
        case 6:   *destination++ = *source++; 
        case 5:   *destination++ = *source++; 
        case 4:   *destination++ = *source++; 
        case 3:   *destination++ = *source++; 
        case 2:   *destination++ = *source++; 
        case 1:   *destination++ = *source++; 
      } while (numberOfPass++,--n > 0);
  }

  printf("Number of Loops = %d\n", numberOfPass);

}


int main(int argc, char** argv) {
  char source[SIZE + 1] = { 'a' };
  char destination[SIZE + 1] = { 'c' };

  memset(source, 'x', SIZE);
  memset(source, 'z', SIZE);

  printf("Source = [%s]\n", source);

  memcpy(destination, source, SIZE);

  duffsDevice(source, destination, SIZE);
  destination[SIZE] = '\0';

  printf("Destination = [%s]\n", destination);
}

For copying 10000 bytes it take only 1250 loops.

Ohh !!! and I thought do…while(0) is just useless

Over the period of years, I saw following kind of code in many places

#define FOO(X) do { f(X); g(X); } while (0)

But this is not useless but a clear trick to avoid unwanted Empty Expression

Consider you have defined the same macro as follows

#define BAR(X) f(x); g(x)

and you are using the same as follows in your main code

if (corge)
  BAR(corge);
else
  gralt();

Above code would be expanded as follows

if (corge)
  f(corge); g(corge);
else
  gralt();

This would cause compiler to cry from bottom of its neck. This is not what you wanted, and this is where do…while(0) trick comes as a savior.

Smallest Zero One Number of multiples of n

ZeroOne is the number, whose digits are either 0 or 1. You have given a number n and need to find the smallest multiplier which is ZeroOne Number

For example for 4 smallest possible ZeroOne Multipler is 100

Solution

I have tried to solve this but really could not find the optimize solution.

#include <stdio.h>
int getZeroOneMultipler(int number) {
  long multiplier = 1;
  while(1) {
    long product = multiplier++ * number;
    long temp = product;
    while ( temp != 0 ) {
      int digit = temp % 10;
      if ( digit != 0 && digit != 1 ) {
        break;
      }
      temp /= 10;
    }
    if ( temp == 0 ) {
      return product;
    }
  }
}

int main(int argc, char** argv) {
  int i = 0;
  for ( i = 0; i < 100; i++) {
      printf("%d = %d\n", i, getZeroOneMultipler(i));
  }
  return 0;
}

British computer magazine had a programming contest [ Updated ]

Friend ( Rishitesh Mishra ) suggested to increment counter by 9, as he believe that 9 is magic number and to my surprise I could get the result in less than a second.

package avdongre.bcm.puzzle;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		int[] set = new int[10];
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i = i + 9) {
			if (solutionFound) {
				break;
			}
			Arrays.fill(set, 0);
			int temp = i;
			boolean validNumber = true;
			while (temp != 0) {
				int digit = temp % 10;
				if (digit == 0) {
					validNumber = false;
					break;
				}
				if (set[digit] == 0) {
					set[digit] = 1;
				} else {
					validNumber = false;
					break;
				}
				temp /= 10;
			}
			if (validNumber) {
				counter++;
				if (counter == 100000) {
					System.out.println(i);
					solutionFound = true;
				}
			}
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: "
				+ ((end - start) * 0.001) + " seconds");
	}
}

British computer magazine had a programming contest

Objective

25 years ago, a British computer magazine had a programming contest and this was one of the puzzles.
There are a large number of 9 digit integers in the range 123456789 to 987654321 where each digit only appears once. What is the 100,000th number in this sequence?

Example

The first number is 123456789, the second is 123456798, the third is 123456879 and so on. No digit can repeat so 122345675 is not a valid number in this sequence.
The problem was “Write a program that outputs the 100,000th number as fast as possible. Use any algorithm, except you cannot pre-calculate the answer and then write a program that just prints the result. Your entry must calculate the number!”. This ran through June 2007

Approach
I am sure this has something to do with permutation, but I could not figure out the same. I went ahead with simple brute-force approach.

1. Iterate over the range 123456789 to 987654321
2. Get all the digits of the number
3. Store each digit into a set and check for uniqueness
4. If the digit is 0 ignore that number
5. If the digit is repeated ignore that number.

Here is my first Java version

package avdongre.bcm.puzzle;

import java.util.HashSet;
import java.util.Set;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		Set<Character> uniqueCheckSet = new HashSet<Character>();
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i++) {
			if ( solutionFound ) {
				break;
			}
			char[] digits = String.valueOf(i).toCharArray();
			boolean validNumber = true;
			for (int j = 0; j < digits.length; j++) {
				if (digits[j] == '0') {
					validNumber = false;
					break;
				}
				if ( false == uniqueCheckSet.add(digits[j])) {
					validNumber = false;
					break;
				}
				
			}
			if (validNumber) {
				counter++;
				if ( counter == 100000) {
					System.out.println(i);		
					solutionFound = true;
				}
			}
			uniqueCheckSet.clear();
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: " + ((end - start) * 0.001) + " seconds");
	}
}

This code took around 35 seconds to finish.

My friend force me to try the same for C++, but we come up with new approach of not using set but simple array in which if the digit is already seen the just set the value to 1 and continue.
With Optimization flag on following C++ code took around 3 seconds to finish

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char ** argv) {
  int counter = 0;
  bool solutionFound = false;
  std::vector<int> set(10);  
  for (int i = 123456789; i < 987654321; ++i) {
    if ( solutionFound ) {
      break;
    }
    int temp = i;
    bool validNumber = true;    
    std::fill(set.begin(), set.end(), 0);    
    while (temp)
    {
      int digit = temp % 10;
      if (digit == 0) {
        validNumber = false;
        break;
      } 
      if ( set[digit] == 0 ) {
         set[digit] = 1;
      } else {
        validNumber = false;
        break;
      }
      temp /= 10;
    }        
    if (validNumber) {
      counter++;
      if ( counter == 100000) {
        cout << i << endl;
        solutionFound = true;
      }
    }
  }
}

Done the same with java and it has dramatically improved performance to 5 seconds

package avdongre.bcm.puzzle;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		int[] set = new int[10];
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i++) {
			if (solutionFound) {
				break;
			}
			Arrays.fill(set, 0);
			int temp = i;
			boolean validNumber = true;
			while (temp != 0) {
				int digit = temp % 10;
				if (digit == 0) {
					validNumber = false;
					break;
				}
				if (set[digit] == 0) {
					set[digit] = 1;
				} else {
					validNumber = false;
					break;
				}
				temp /= 10;
			}
			if (validNumber) {
				counter++;
				if (counter == 100000) {
					System.out.println(i);
					solutionFound = true;
				}
			}
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: "
				+ ((end - start) * 0.001) + " seconds");
	}
}

[LeetCode #5] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

public class LRUCache {
	class Node {
		int key;
		int value;
		Node prev;
		Node next;
	}
	
	private int lruCapacity;
	private Map<Integer, Node> lruCache;
	private Node head;
	private Node tail;

	public LRUCache(int capacity) {
		this.lruCapacity = capacity;
		this.lruCache = new HashMap<Integer, Node>();
	}

	public int get(int key) {
		// Existing key
		if (this.lruCache.containsKey(key)) {
			// Move to first place
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			// Return the value
			return node.value;
		}
		// Not found
		return -1;
	}

	private void add(Node node) {
		// Reset position
		node.next = null;
		node.prev = null;
		// First element
		if (null == this.head) {
			this.head = node;
			this.tail = node;
			return;
		}
		// Existing element
		this.head.prev = node;
		node.next = this.head;
		this.head = node;
	}

	private void remove(Node node) {
		// Nothing to do
		if (this.head == null || null == node) {
			return;
		}
		// The only one item
		if (this.head == this.tail && this.head == node) {
			this.head = null;
			this.tail = null;
			return;
		}
		// Remove from head
		if (node == this.head) {
			this.head.next.prev = null;
			this.head = this.head.next;
			return;
		}
		// Remove from end
		if (node == this.tail) {
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			return;
		}
		// Remove in the middle
		node.prev.next = node.next;
		node.next.prev = node.prev;

	}

	private void removeLast() {
		this.remove(this.tail);
	}

	private void moveFirst(Node node) {
		this.remove(node);
		this.add(node);
	}

	public void set(int key, int value) {
		if (this.lruCache.containsKey(key)) {
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			node.value = value;
			return;
		}
		// Out of capacity, cleaning the oldest slot
		if (this.lruCache.size() >= this.lruCapacity) {
			int id = this.tail.key;
			this.removeLast();
			this.lruCache.remove(id);
		}

		// New slot
		Node node = new Node();
		node.key = key;
		node.value = value;
		this.add(node);
		this.lruCache.put(key, node);
	}
}

Google Code Jam Practice Problem – File Fix-it

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.

package avdongre.google.code.jam;

import java.util.HashSet;
import java.util.Scanner;

public class Solution {
	private static void solve(String[] existingDirectories,
			String[] directoriesTobeCreated) {
		HashSet<String> availableDirectories = new HashSet<String>();
		for ( int i = 0; i < existingDirectories.length; i++) {
			String[] splits = existingDirectories[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {					
					availableDirectories.add(sb.append("/").append(splits[j]).toString());
				} 
			}
			sb.setLength(0);
		}
		int mkdirCount = 0;
		for ( int i = 0; i < directoriesTobeCreated.length; i++) {
			String[] splits = directoriesTobeCreated[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {
					String possibleNewDirectory = sb.append("/").append(splits[j]).toString();
					if ( availableDirectories.contains(possibleNewDirectory) == false) {						
						availableDirectories.add(possibleNewDirectory);						
						mkdirCount++;
					} else {
					}
				}
			}
			sb.setLength(0);
		}
		System.out.println(mkdirCount);
	}

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int T = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < T; i++) {
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			int N = Integer.parseInt(next_split[0]);
			int M = Integer.parseInt(next_split[1]);

			String[] existingDirectories = new String[N];
			for (int j = 0; j < N; j++) {
				existingDirectories[j] = stdin.nextLine();
			}
			String[] directoriesTobeCreated = new String[M];
			for (int k = 0; k < M; k++) {
				directoriesTobeCreated[k] = stdin.nextLine();
			}
			System.out.print("Case #" + ( i + 1) + ": ");
			solve(existingDirectories, directoriesTobeCreated);
		}

	}

}

Google Code Jam Practice Problem – T9 Spelling

Problem

The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ‘ ‘ should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Old_Phone

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	static Map<Character, String> keyToNumberMap = new HashMap<Character, String>();
	static Map<Character, Integer> keyOnSameButtton = new HashMap<Character, Integer>();

	static {
		keyToNumberMap.put('a', "2");
		keyToNumberMap.put('b', "22");
		keyToNumberMap.put('c', "222");

		keyToNumberMap.put('d', "3");
		keyToNumberMap.put('e', "33");
		keyToNumberMap.put('f', "333");

		keyToNumberMap.put('g', "4");
		keyToNumberMap.put('h', "44");
		keyToNumberMap.put('i', "444");

		keyToNumberMap.put('j', "5");
		keyToNumberMap.put('k', "55");
		keyToNumberMap.put('l', "555");

		keyToNumberMap.put('m', "6");
		keyToNumberMap.put('n', "66");
		keyToNumberMap.put('o', "666");

		keyToNumberMap.put('p', "7");
		keyToNumberMap.put('q', "77");
		keyToNumberMap.put('r', "777");
		keyToNumberMap.put('s', "7777");

		keyToNumberMap.put('t', "8");
		keyToNumberMap.put('u', "88");
		keyToNumberMap.put('v', "888");

		keyToNumberMap.put('w', "9");
		keyToNumberMap.put('x', "99");
		keyToNumberMap.put('y', "999");
		keyToNumberMap.put('z', "9999");

		keyToNumberMap.put(' ', "0");

		keyOnSameButtton.put('a', 1);
		keyOnSameButtton.put('b', 1);
		keyOnSameButtton.put('c', 1);

		keyOnSameButtton.put('d', 2);
		keyOnSameButtton.put('e', 2);
		keyOnSameButtton.put('f', 2);

		keyOnSameButtton.put('g', 3);
		keyOnSameButtton.put('h', 3);
		keyOnSameButtton.put('i', 3);

		keyOnSameButtton.put('j', 4);
		keyOnSameButtton.put('k', 4);
		keyOnSameButtton.put('l', 4);

		keyOnSameButtton.put('m', 5);
		keyOnSameButtton.put('n', 5);
		keyOnSameButtton.put('o', 5);

		keyOnSameButtton.put('p', 6);
		keyOnSameButtton.put('q', 6);
		keyOnSameButtton.put('r', 6);
		keyOnSameButtton.put('s', 6);

		keyOnSameButtton.put('t', 7);
		keyOnSameButtton.put('u', 7);
		keyOnSameButtton.put('v', 7);

		keyOnSameButtton.put('w', 8);
		keyOnSameButtton.put('x', 8);
		keyOnSameButtton.put('y', 8);
		keyOnSameButtton.put('z', 8);

		keyOnSameButtton.put(' ', 9);

	}

	private static String solve(String nextLine) {
		char[] nextLineCharArray = nextLine.toCharArray();
		char previous = nextLineCharArray[0];
		StringBuilder sb = new StringBuilder();
		sb.append(keyToNumberMap.get(previous));
		for (int i = 1; i < nextLineCharArray.length; i++) {
			char current = nextLineCharArray[i];
			if (keyOnSameButtton.get(previous) == keyOnSameButtton.get(current)) {
				sb.append(" ");
			}
			previous = current;
			sb.append(keyToNumberMap.get(previous));
		}
		return sb.toString();
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			System.out.println("Case #" + (i + 1) + ": "
					+ solve(stdin.nextLine()));
		}
	}

}

Follow

Get every new post delivered to your Inbox.

Join 574 other followers