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

iPhone application tutorial - Body Mass Index Calculator : Part 7

The first posting's output and this may vary since that was developed with XCode 3 and this one with XCode 4. There are slight differences between both of them, but that we don't want to know. You can download XCode 4 for $5 from Apple's website.

I wanted to keep this final section very light. Hence going to show only the output here. :)

Click here to download the entire source code for this project. It is free to develop and distribute. Hope you guys learnt something.

Cheers!!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 6

This is our last part of the tutorial. We have done whatever that needs to be done with respect to the UI. All that is left is the coding part. In the last post, you would have seen that we had a couple of methods defined called as updateResult() and range(). These are supposed to be private methods. But then, I don't want to overload the readers with that concept yet, hence I have not set the access modifier for them. They will come in handy in our implementation part.

The implementation part involves responding to the actions that are sent from the UI. Lets take a look at the implementation of the height slider and go line by line.

The first line is nothing but a copy of the method declaration. The return type of the this method is an IBAction. The argument that it takes is the sender's object. If you had known Java, 'id' is a data type similar to Object. It is the sender's object. Since we have attached this method with the Slider, this would be the Slider itself.

On the fist line inside the method, we are typecasting the sender to the UISlider since we know for sure that the sender is an instance of UISlider. We then get its value, asssign it to a NSString variable followed by assigning it to the height text. Since we have allocated the NSString we should release it. You could notice there is a tiny little call to updateResults. It is nothing but updating the BMI and the Result at the bottom. Its implemenation is,

The above code is self explanatory and straightforward to read. We also need to add a similar slider method for weight as we did for height.

Whoof thats a lotta coding. Lets see the final output in the final part of this tutorial!

Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 5

In the past section we saw how to design the view and set the basic things up. Now, its time to do some coding. Before that, to check whether everything are Ok, press the ⌘ + B button to build your project. It may prompt you to save the project. If it does, click the Save button. The build should succeed at this point. If it fails, then go and check the logs or tell me the error in the comments section, I would surely help you out!

Now, back to business. We need to dynamically update the values in the UI. To attach this with the code, we have a binding object defined called as IBOutlet. Using this object, we would be able to set stuff in the code and see it change in the UI. Looks magic. To start binding the UI components and the code. Click on the Editor icon the right top side to see both the Interface Builder and the Interface file side by side.

Select your component on the UI - the height label. Hold down the control key and draw a line from the component to the Interface definition, you should be seeing a line coming up automatically for it to be inserted as shown below.

Lets name that IBOutlet variable to be height. Do the same for weight, bmi and the result labels. So, we are done with defining our binding variables namely the IBOutlet. Now whatever change you do for these outlets will now be reflected in the UI. We have one more thing left from the hooking up perspective - the Sliders. We need to assign an action when we slide the height and weight sliders. It is pretty simple. Select the height slider, choose the properties from the side and click on the Value changed option and drag it to the interface code. All you should be naming here is the method name which would be height slider. Note, you do not need to press Control key as we did for the Outlets.

You would need to add a couple of more methods in your interface file. The final code would look something like the following


Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 4

Welcome to the part4 of the BMI Calculator iPhone application tutorial. We saw in the last section on how to set components on the UI. I had said that there was a small thing mentioned about the slider.

Before I tell more about it. Lets strategize how our application should behave. You slide two things in your application namely the heights and weights, the user will be seeing his body mass index calculated and will be given the result on whether he is normal or underweight or obese etc. We will be needing to determine the upper and lower bounds of the heights and weights. I have taken the height range as 120-210 cm and the weight range as 30-130 kg.

Whenever you click on any component, it corresponding property should be appearing at the right hand panel. Go ahead and click on the height slider. Set the minimum and maximum values of the slider as we discussed before.

You would also need to set the initial value. Since it needs to be in the center, set the height as 165 (average of 120 and 210). Same you would need to do by selecting the weight slider. 30-130 as lower upper bounds with 80 as the current value.

Thats it we are done designing our wonderful UI for the iPhone Application. We have some UI-Code hookup and some coding left before we declare our application is complete which we will be doing in the coming posts.

Cheers!
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 3

Welcome to the part 3 of the tutorial. You could be thinking, "what the hell did I learn in Part 2?" Well. Lets take one baby step at a time. The second part of the tutorial's project name read "Body Mass Index Calculator". But then I had to change it to helloworldXcode, the name would not mind much, but whatever you choose, choose it wiser.

On the left hand top side of the you should be able to see your project. Expand it and you should be seeing your interface file (.h), Implementation file (.m) and the UI file (.xib). Clicking on any of these will bring up the corresponding code or UI on the main panel.

Go ahead and select the .xib ViewController file. You should now see an empty Canvas appearing on the center of the editor where you can drag and drop stuff. For our body mass index we need few UILabels that are going to be static and few UILabels that are going to change dynamically on the user action.
For dragging and dropping components on to the View you should select the Object from the drop down on the right hand side bottom corner as shown below.

We also will need a couple of slider for selecting the height and weight. Already sounds cool eh? Here is a screenshot on what stuff you should be dragging and dropping on the center of the editor.

After dropping the elements which includes totally 9 labels and two sliders you should be aligning them like shown in the following screenshot. The placement of the labels depends totally on your imagination and creativity, but lets make it professional looking so that our application should sell at least a million times in the App store. That was a joke :)

You could notice that changing the names of the labels are very simple. Just double click on it and start typing as shown in the above screenshot. With this your basic set up of the view is complete, we just have a few more things left regarding the slider functionality, but we will cover it in the next section.

Cheers,
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 2

Welcome to the second part of the BMI Calculator Application for iPhone tutorial. I assume that you have XCode installed in your mac or Mac under VMWare. Launch XCode and select a new View based project.

Click on Next. Fill up the basic details and move on.

Once you have selected where to save your project, you should see something like this. Note: We are using Xcode 4 to develop this application, the view may vary from the previous version of Xcodes.

Thats it in this part of the tutorial. Lets start using the Interface builder and do some coding in the coming posts.

Cheers,
Braga

iPhone application tutorial - Body Mass Index Calculator : Part 1

After an extensive learning on Objective C and covering the basics of iPhone development, I wanted to get my hands dirty with a working application. Following the concept of Minimal Marketable Subset, I thought I would develop a very primitive Body Mass Index calculator. Ok, into business

Our Final BMI Calculator Application is going to look like this.

Prerequisities

Since this is a very narrow development environment (yes you cannot develop this with windows), I would want to give a brief on what you will need, both hardware and software. First of all, you would need a Macbook or a Macbook Pro. A basic Macbook would do. Its based on how far you go. If you are very serious into iPhone development, then I would recommend you get a Macbook Pro. On the software side, you would need the XCode development suite. You can get it from Apple's website, it is free to download. It asks you to create an Apple Id. Go to youtube or google, you should find tons of resources there.

If you want to create clean iPhone Applications, you should have a very strong C Programming Background. And it would be nice if you are familiar with Object Oriented Concepts. You would need to learn Objective C basics and then the basics of iPhone development. Believe me, those links are simply too good. You can learn them both in just a day if you are freak like me.

Armed up with these basics, we can dive into the tutorial right away from the next post.

Cheers,
Braga

Minimal Markatable Subset

It has been a long time since my last technical post. Yes, 6 months!! I wanted to write something on iPhone Application development. But before doing that, I want to tell you guys on something that I learnt during my two day training on clearing the Certified Scrum Master.
During this training, I heard this term called "Minimal Marketable Subset". After hearing to what it meant, my view as a developer changed drastically. Basically, I want my code to be perfect. Whenever I develop something, I want it to be highly user interactive, highly easier and the highly optimized. But know what, that is one of the huge mistakes I have done so far. Because of this attitude, I can never be satisfied and declare my product/project as completed. I felt that was the right way to think till I heard of "Minimal Marketable Subset". It is the minimum thing that is needed to get something up and running. You can develop in increments as the application develops. That is the basis of any Agile practice and I have started to adopt it to my programming practice.
To put in simple terms, "do what you can with what you have and do it quick"