Sunday, May 22, 2011

You have a note to write by cutting and pasting necessary letters from the book, write an algorithm to see if you can write the note.

import java.util.*;
import java.io.*;

public class NoteChecker
{

private final File noteFile;
private final File bookFile;

private int noteTotalLength = 0;

private void checkIfFileExists(File file)
{
if( ! file.exists() )
{
throw new IllegalArgumentException("File doesn't exists '" + file.getPath() + "'");
}
}

public NoteChecker(String noteFilePath, String bookFilePath){
super();

noteFile = new File(noteFilePath);
checkIfFileExists(noteFile);

bookFile = new File(bookFilePath);
checkIfFileExists(bookFile);
}

private int[] getRequiredLetters()
{

final int[] requiredLetters = new int[128];

Scanner noteSc = null;

try{

noteSc = new Scanner(noteFile);

while( noteSc.hasNextLine() ){
String line = noteSc.nextLine();

for(int i =0; i < line.length(); i++ ){
char ch = line.charAt(i);
++requiredLetters[ch];
++noteTotalLength;
}
}
}
catch(Exception ex ){
ex.printStackTrace();
return requiredLetters;
}
finally {
if( noteSc != null ){
noteSc.close();
}
}

return requiredLetters;
}

public boolean canCreateNote()
{

final int[] requiredLetters = getRequiredLetters();

Scanner bookSc = null;

try
{

bookSc = new Scanner(bookFile);

while( bookSc.hasNextLine() )
{
String line = bookSc.nextLine();

for(int i =0; i < line.length() && noteTotalLength > 0; i++ )
{
char ch = line.charAt(i);

if( requiredLetters[ch] > 0 )
{
--requiredLetters[ch];
--noteTotalLength;
}
}
}
}
catch(Exception ex)
{

ex.printStackTrace();
return false;
}
finally
{
if( bookSc != null )
{
bookSc.close();
}
}
return noteTotalLength == 0 ? true : false;
}



public static void main(String a[])
{

NoteChecker ob=new NoteChecker("E:/ubuntu/note.txt","E:/ubuntu/Input.txt");
System.out.println(ob.canCreateNote());


}
}
Above Solution is provided By Max

TC O(m+n)
SC O(1)

No comments :