Novel finder Program

This was one of the problems that I had faced during one of my interviews. The problem sounded interesting and I was given 1 hour to solve it which I did quite comfortably.

Problem:

The K-doublets of a string of characters are the ordered pairs of characters that are K distance from each other. A string is K-singular if all its K- doublets are different. A string is Novel String if it is K-singular for all possible K distances.

For e.g. take the string FLBL, its 0-doublets are FL, LB and BL. Since all these are different, FLBL is 0-singular. Similarly, its 1-doublets are FB and LL, since they are different FLBL is 1-singular as well. Lastly, the only 2-doublet of FLBL is FL, so FLBL is 2-singular. Hence, FLBL is a Novel String.

Note that the fact that FL is both a 0-doublet and 2-doublet is insignificant as zero and two are different distances.

Input:

The input is one or more non-empty strings of at most 100 capital letters, each string on a line by itself, followed by a line containing only two dollars ($$) signaling the end of the input.

Output:

For each input line, output whether or not it is a Novel string using the exact output format shown below.

Sample Input: (Input File: novel.in)

FLBL

FFLL

ORDINARY

R

QYQRQYY

$$

Sample Output: (Output File: novel.out)

FLBL is a Novel string

FFLL is not a Novel string

ORDINARY is a Novel string

R is a Novel string

QYQRQYY is not a Novel string

Solution:

To attack this problem, you first have to find all the doublets for each distance starting from 0 to the maximum distance which would string's length minus one. Then keep pushing them into a hash set. Whenever the add() method of the Set returns false, it means we are adding a duplicate hence, its not a Novel text. Here is the Java source code.


Cheers!
Braga

Windows Phone 7.5 - Home button Navigation and Exit Confirmation

While developing a windows phone application, the one which involves navigation to various pages starting from something called as a homepage would quickly become annoying. You will find yourself in deeper pages and as a means on coming back to the home page, you will keep pressing the back button so many times it will exit you out of the application.

There are couple of problems associated with this. The user is forced to keep in mind how deep he has in the navigation page. The other main problem is he will not have patience to wait to go to the home page and pressing the back button on the first page will obviously throw you. This is because the navigation details are stored in a stack.

It is always nice to provide a home button to the end user on all the pages so that on click of them will take it to the home. Also, you can always have a confirmation dialogue fired while exiting the application. First problem first.

This code armed with a Home button will do the job cleanly for you.

private void Home_Click(object sender, System.Windows.RoutedEventArgs e)
{
    int depth = NavigationService.BackStack.Count();
    for (int i = 0; i < depth - 1; i++) { NavigationService.RemoveBackEntry(); }
    NavigationService.GoBack();
}

The funda here is it will empty all the stack and will call the back action of the navigation service just once making sure that the next back() will empty the stack and will make you quit.

As I told before adding this code to the MainPage.xaml.cs will show a confirmation popup while quitting the application so that user only deliberately quits but not accidentally.

protected override void OnBackKeyPress(System.ComponentModel.CancelEventArgs e)
{
    if (MessageBox.Show("Are you sure you want to exit?", "Exit?", MessageBoxButton.OKCancel) != MessageBoxResult.OK)
    {
        e.Cancel = true;
    }
}

These techniques are very simple and subtle but will improve the usability of your application by leaps and bounds.

Cheers!
Braga

Windows Phone 7.5 WebBrowserTask - Simple Yet Powerful

WebBrowserTask is one of the most simple yet powerful tasks I found in Windows Mobile development. It is amazingly simple, just two or three lines of code and super tempting to include it in your project. Lets quickly see how to use it and places where you can utilize its capability at the presentation level.

Enough intro, here is the code

WebBrowserTask pptTask = new WebBrowserTask();
pptTask.Uri = new Uri("http://www.iasted.org/conferences/formatting/presentations-tips.ppt");
pptTask.Show();

Damn simple isnt it? You could use this in places where you need to launch or open an URL in the inbuilt Internet Explorer. And the best thing about this is it will automatically detect the attachment file types (most of them) and opens them cleanly. For example, it could read ppt, pdf, xls even videos and open them cleanly. You can make the integration look rich by providing a button in the Application bar. Following is a screenshot.

Besides opening simple URLs consider using this Task to open regular attachments and make your end application look extremely rich with just one or two lines of code.

Cheers!

Braga

Windows Phone 7.5 - ShareStatusTask's Limitations

The Microsoft.Phone.Tasks namespace in Windows phone 7 is a neat way to access the default phone specific tasks. One such task is the ShareStatusTask. If you want to say share your status on facebook or twitter or to windows live account, you can do it in one shot.

The code looks very simple,

Very cool isnt it. But the usage of this kind of limited. You will have to have all the accounts configured already in your phone settings. I was looking for a direct solution to just provide a way to tweet. But it was not possible to tell the ShareStatusTask to open it only if it has Twitter. I had asked this question in Stackoverflow only to double confirm the above said point. This feature is not available in Emulator, hence posting a screenshot from a real device.

Anyways, this is one of the cool tasks available and just two to three lines will add social feature to your App, so do add it whatever be the case.

Cheers!
Braga

Windows Phone 7.5 - Rating/Review control Packages

There was a simple specification in my application that needs to have a Review feature. I started off with Google, but the irony here is the keyword "ratings" or "review" accompanied with Windows Phone 7 did not return results that I've been looking for. Instead it was returning the features and real reviews written for Windows Phone 7. The catch here was to convert my keyword to star rating control. I found some decent resources which are implementable, let me summarize them.

1) Silverlight Star Rating Control - This had most of the meat I was looking for. It was actually designed for silverlight and not really tested in Mobile or I can put it like I was not able to find snippets for Mobile implementation. However, it worked alright. The problem was that this package was not having a mechanism to NOT have the Half-Star Mechanism. Going through the source code confirmed that and I do not want to build a new dll out of it and include it in my project. So gave this up. But I would highly recommend this for web client.

2) The next one I stumbled upon was from a guy Jani Nevalainen. He has blogged it in his website and it had what I needed. But since it was not on a codeplex site/github, and due to its lack of documentation or support I had to push it down the priority list. I have not tried this, but my gut says it will surely work.

3) Another one which really looked promising was from a blogger named Matthieu. I thought it had everything and even the source on Github and the demo project worked flawlessly. I was expecting for a library file so that I could include it in my project and breathe easily. Unfortunately, that was not something already available. Yes, I can go through the code and compile a source out of it. But I was really lazy to do so. Hence dropped it. But I have to say this was a really good and careful implementation. Kudos to the Author.

4) And the winner was Coding4Fun! The most sexy and the most famous library for the Windows phone 7.5. It has everything and the forums are really great! Every week you can see builds coming and they are very much responsive to the features that you are suggesting. I could not say that this is the Open source folks' answer to Telerik, but this library is really good. I used their super slider to design my review page. I know it is not like the star mechanism, but still this did the job and it did really great for me!

Cheers!
Braga

Exception Handling in Windows Phone 7 - When all else fails

I was recently testing something with Toast Notifications with Windows Phone 7.1. Visual Studio that I use has amazing debugging features like any other IDE available IDE out there. Here was scenario. I need to send two types of Notifications Raw and Toast Notifications to my mobile and need to assert scenarios. Debugging the Raw Notification was very simple. However, I was not able to debug/step into when I launch the application after clicking the toast Notifcation.

It was really painful not to be able see any exception message. It was very annoying. Then I found a way to at least know what is happening. To do that, you can just go the App.xaml.cs file which has all the main entry and exit points to the application. To read more about this, just google life cycle of a windows phone app.

All I had to do was add a message box to the method Application_UnhandledException in the App.xaml.cs.

private void Application_UnhandledException(object sender, ApplicationUnhandledExceptionEventArgs e)
{
    MessageBox.Show(e.ExceptionObject.Message + "\n" + e.ExceptionObject.StackTrace);
    if (System.Diagnostics.Debugger.IsAttached)
    {
        // An unhandled exception has occurred; break into the debugger
        System.Diagnostics.Debugger.Break();
    }
}

Problem Solved. Now I could see the error messages/exception stack trace in a neat Message box!

Cheers!
Braga

Rails script/generate model with an association

I know this blog has been dormant for quite some days now for no apparent reason. But I would like to share what I learnt today. This is going to be in Rails (2.3.x) and hardly interest anyone who already knows it. But it still was a learning to me. I use to hate working in command prompt and was an IDE freak, a real good one too. But I was cornered to learn more on the command line front as well. Why waste an extra feather in the cap?
Bulling the shit, here is what I learnt today.

Rails has a script/generate ready for many usual stuff that we do. One of them is the model generator. It is not that much, but I was wondering whether it is possible to create associations using it. And I found it is not.

I tried a stupid model generation something like (in fact exactly like this)

rails -d mysql playground
cd playground
script/generate model project name:string has_many:tasks

It reeked,

exists  app/models/
exists  test/unit/
exists  test/fixtures/
create  app/models/project.rb
create  test/unit/project_test.rb
create  test/fixtures/projects.yml
create  db/migrate
create  db/migrate/20120227204200_create_projects.rb

My stupid assumption was that it would actually create a couple of models called projects and tasks. But to my wonder, it did not. The highlight was this command did not even raise any error. Inspecting the database migration, I found

class CreateProjects < ActiveRecord::Migration
  def self.up
    create_table :projects do |t|
      t.string :name
      t.tasks :has_many

      t.timestamps
    end
  end

  def self.down
    drop_table :projects
  end
end

And I did a migration and it did migrate without any errors. It silently ignored the line t.tasks :has_many. Not usual right?! But this is rails, you got to adapt and adapt very well. One more learning probably I could share are the commands that come with the script/generate model is the --pretend. This is like a dry run, does not actually creates a physical file but tells what its going to do. Thats it for today.

Cheers!
Braga

Reconstruct a binary tree given its Inorder and Preorder traversals in Java

This is one of the interesting problems that I encountered recently. Given two sequences one being an in-order traversed sequence and other being a pre-ordered traversed sequence, a binary tree has to be reconstructed out of it.

This is theoretically possible. This problem can be cracked if we form a common pattern between these two traversed values. In a pre-order traversal, the root element will always be the first element. This element when searched in an in-order traversal will have all elements to the left on the left side of the array and all elements to the right on the right side of the array.

Applying this solution recursively will give the binary tree for us. I have included a Swing UI so as to visualize the output easily.

Example,
Pre Order Sequence = A B D E C F G H I
In Order Sequence = D B E A F C H G I

I tweaked a bit from this source for UI.

The Node structure

The code for UI

Hope you learnt something today along with me.

Cheers!
Braga

Given a sorted array, find k in least possible time in Java

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

Leave some comments if you have anything to say.

Cheers!
Braga

Find middle element in a circularly sorted array

Given a circularly sorted array, find its middle element in best possible time.

A circularly sorted array is an array that is obtained by shifting an array k times. For example, the following is a circularly sorted array,

[5, 6, 7, 8, 9, 1, 2, 3, 4]

If you sort this array and find the middle element it will be 5. But then, sorting is a painful operation which will take O(nlogn) timing. So it is out of the equation right away. If you closely observe this problem, it is enough to find the shifting index, the place where the sorting varies. For example, the shifting index in the above example is 5.  Once that is found, then it is a matter of applying the bias over the length.

This program can be attacked in a recursive manner. Take the first and last elements in the array and compare them. If they are sorted, then the last element is greater than the first element. If this condition is not met, we will have to divide this array into two halves and try applying the same logic. If you do this, at some point you will arrive at a situation where you are left with only two elements or lesser. The end value is the shift index. Once the shift index is found, it is easy to find the middle element(s) for odd and even cases. Java code is below.

Leave comments if something is unclear.

Cheers!
Braga

Queue using Stack in Java

A Queue can constructed with its underlying data structure being a stack. Typically, we will need two Stacks one for enqueue and the other for dequeue.

During every enqueue() operation over a queue, we will keep pushing value to a first stack, lets say stack1.

During every dequeue() operation, we will have to simply pop an element from stack2 if stack2 is not empty. If stack2 is empty, we will need to pop all elements from stack1 one by one and push it to stack2. And then pop an element from stack2.

Take for example, I am inserting elements from 1 to 6 to a queue. This is how the following queue and the corresponding stack will look like,

Then trying a dequeue() operation will try to immediately pop values from stack 2.

So, it will pop all values from stack1 and push them to stack2 as follows,

Now the dequeue() operation shall be performed with ease since stack2 is not empty.

Finally, more enqueue will add or keep pushing values to the stack.

Following is the Java code. Note, I have not comprehensively covered the entire methods in a Queue, but this should be well more than enough.



And a test class for this with output


Cheers!
Braga

Program to check whether a tree is a BST

Write a program to check whether a given tree is a binary search tree.

We all know that a binary search tree follows the rule : for any given node with value N, all the values in the left of that node is lesser than N and all the values in the right of that node will be greater than or equal to N. For example,

This is a tricky question. We may try to immediately run through all the nodes checking only the immediate left and right nodes and coming to a conclusion that it is a binary search tree. But this program may not work for this scenario.

The simplest solution to this problem is to do an inorder traversal through the entire tree and find whether it is sorted or not. Typically we can do that by pushing into any array. Even better is to calculate the minimum value at each step. Program is as follows. Please leave some comments if something is confusing. I will get back immediately.

Cheers!
Braga

Windows, Linux and OSX

Windows is the most used Operating System from an end user point of view. Next is Mac and the last ofcourse is linux. But this is not the case for a developer. Most of the development forums I've found online for the past so many years have given me results that has dealt fairly equal with these three major operating systems.

So, I would suggest to get your hands dirty with all these, if you have not already. If you have a Windows machine at work, buy a Macbook at home, install Linux (best is Ubuntu) on your desktop. Yes, this involves some cost, but trust me, its definitely worth it and you can see yourself well ahead of the curve as a developer.

For me, I use Linux at work and Mac at home. I hardly use windows these days but I have used it for a good 10+ years!!

Cheers,
Braga

Blocks in Ruby

Blocks are one of the coolest things to have when you are coming from a language like C++ or Java. Say you are writing a function and you want to have some functionality within it which should be handled totally by the caller. Well, blocks come for the rescue.

Say I have a method like this.

There is a sweet keyword in Ruby to replace the second line of the test_method called yield.


And you can now make a call like,


Would output,
start
From block
end

Nothing great if you already are a ruby nerd. But for Java blokes, blocks are something to think for.

Cheers!
Braga

Conway's Game of Life in Java!!

I recently met with Conway's Game of Life problem given as a programming assignment by one of the famous MNCs to clear level 1 in interview process. It was so mouth watering that I want to develop an UI for it and publish it in my blog. Spent 3 hours and came up with this.

Quick gist about the game from wikipedia

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

Following is the screenshot and an applet for the same. The Code is free to share and distribute. Visit my github link for this game for the bleeding edge copy.

 

Cheers!!
Braga