Find Largest Binary Search Tree in a Tree: Java Solution

The question is simple and fair common:

Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree. (From: GeeksForGeeks)

Additionally, I'll be returning the root node for the BST. In this case the BST would have to include all its children (i.e.: it must be a BST from a specific node to the leaves).

Algorithm

To find the largest BST in a tree there are different options to traverse the tree: we could take an top-down approach or a bottom-up.

Top-Down

The top-down approach require us to check at each node from the root if the tree starting at that node is a BST. This makes us traverse multiple times the tree to find the bst. Although it stops as soon as it find a BST because it will be the largest. This solution has a time complexity of O(n^2) in worst-case (degenerated tree into list) or O(nLogn) (balanced tree)

 where n is the number of nodes in the tree.

Bottom-Up

A better approach will be bottom-up where we check from the bottom of the tree the nodes to check if the trees created are BST. This makes the evaluation of a BST in O(1) for each node, although we still have to traverse the tree completely, so this approach has a time complexity of O(n) (in fact we have to traverse the tree twice because to get to the bottom nodes we must traverse from the root and then again from the bottom to the top).

Given the implementation is recursive, this has a space complexity of O(n). 

Implementation

Below is my Java proposed solution. For a complete solution (including testing, full comments and printing) check this.

If you are preparing for a tech interview, don't forget to check the Interview Study Guides.

Big-Oh English Java Programming

Tips and Solutions for Dell XPS 13 Developer Edition

The Dell XPS 13 Developer Edition comes with Ubuntu 12.04, and even though most of its hardware works perfectly with Ubuntu there are some things that doesn't quite work from the beginning (what a shame).

In this post I present some of the issues that I experienced with this powerful ultrabook and how I solved them.

Bluetooth

At the beginning I couldn't enable the bluetooth but after the first Ubuntu update it worked perfectly.

Additional Tip: if you want to send files from your phone to your computer you should do search and find "Personal File Sharing" in the dash and activate both the checkboxes under "Recieve Files over Bluetooth, as commented by Reza Ghayem in AskUbuntu.

WiFi

By default there are some issues with the stability of WiFi connections. If your WiFi connection is not stable (ie: disconnects and reconnects a lot) you should run the following in a Terminal:

sudo apt-get install linux-generic-lts-quantal

and reboot your computer after that as suggested by Dan Wood in this AskUbuntu post.

Hibernate

Warning: Some people have reported some problems (ruins installation) using this hibernate tip when the Home directory is encrypted. I haven't confirmed this, though.

Although in my case Suspend worked from the beginning, Hibernate didn't so just installing uswusp solves the issue:

sudo apt-get install uswsusp

There are additional instructions suggested here but they weren't necessary. After installing uswsusp you can try hibernating your computing executing in a terminal:

sudo s2disk

If it works then you just have to restart the computer (after waking it up) and check hibernate through the standard options in Ubuntu (right top button-->Hibernate).

And that's it! Just let me know if you have additional hacks needed for Dell XPS 13 Developer Edition or if you had any problem with any of these solutions!

Dell English Linux Tips Troubleshooting Ubuntu

How synchronized methods can be ignored

Here is a question:

If an object has a synchronized method A and a not synchronized method B, can both method be called by different threads?

And the answer is:

Only one thread can access synchronized method A at a time (unless there are two different objects and each thread calls method A on different objects). B can be accesed by many threads at any given time, even when A is executing.

At the beginning I was a bit confused about the second part, if that is so, then a class might not be protected against multithreading update if it has at least one non-synchronized method that modifies an instance variable used by a synchronized method. I was right!

Here's is the code to prove it:

If you run this code it will sometimes show final value as 0 and other times value as 1. So when designing a class that should be synchronized take under consideration which methods are you leaving free that can modify instance (or static) attributes.

English Java Multithreading

Volunteering at Chuck Pezoldt Park

Not all is sitting behind a computer programming and publishing blog posts! ;) Sometimes is good to take fresh air and do something helpful for the community.

Last weekend as well as in the Global Youth Service Day I went with my wife to a park to plant trees (after all as José Martí once said: before die you should "Plant a tree, write a book, have a son"). It was exhausting but a fulfilling activity and it was great to see that the trees we planted months ago were healthy and still there. 

The Miami-Dade county parks workers are very nice and organized people and they had it all under control so the job was very fruitful. Specifically with this park (Chuck Pezoldt) they are improving its services and we helped them saving some money to more costly activities like installing lights or improving the sport courts in the park, while doing something good for the environment and the the community.

To learn more about this or other activities, please refer to the Parks Foundation of Miami-Dade County.

And, because not everything is hard work, I leave you with the Harlem Shake we did back in April. This video is also posted on the Parks Foundation Facebook site.

Ecology English Miami Volunteering

How to send emails in Wordpress with Contact Form 7

Recently I was working with a client's Wordpress-based site where they had configured a contact form using Contact Form 7 to send emails to clients. I'm not going to enter in details on how to use Contact Form 7 since there are good guides in the plugin's site.

The thing is that after configuring Contact Form 7, I found issues sending emails. The Contact Form 7 owner posted a link to a blog that explained how to solve this for specific configurations using WP-Mail-SMTP plugin. This gave some guidance but I had to tweak it a lot (for example, changing from WP-Mail-SMTP to WP-SMTP) to make it work for me, and I hope with the following instructions you will be able to solve it in your site too.

First of all, my configurations:

• Wordpress, version 3.5.2
• Contact Form 7, version 3.4.2
• WP-SMTP, version 1.1.5
• The site is hosted in GoDaddy.

Notice that I use WP-SMTP instead of WP-Mail-SMTP.

First, you have to change the WP-SMTP configuration. You can do it through Settings -> WP-SMTP. Set the following:
                From: my email (ex: "asdf@gmail.com")
                From Name: "Whatever you like"
                Host: localhost
                SMTP Secure: None
                Port: 25
                SMTP Authentication: No
                All the other fields empty. 

WP-SMTP Configuration

You should be able to send a test email using the fields at the bottom of the form. If this works, you're almost done!

Finally,  another problem that I found is that you cannot send empty message body in the Contact Form (notice the [your-message] value in the picture below). Based on the Contact Form Docs, I configured the contact form as shown. The field [email-88] is the name of the field email that the user introduced in the form.

The reply-to header was a nice touch that I took from Mario Varga's post.

Contact Form 7 Configuration

Hope it works for you!

English Troubleshooting Web Wordpress

How to map Postgres capital names to Hibernate

When I was developing the Simulation Model System (SimModSys), I faced this issue.

I'm from the school that believes that the database should be developed first and independently from the system, to serve the purpose of maintaining the data integrity, and the application should integrate to the existing database to apply logic on the data, but not to force how the data should be represented. So I designed the database first ignoring that there were issues between Hibernate and Postgres capital letters.

Instead of changing the database I decided to fight for it, after all it was a learning personal project. 

I received a partial answer that I completed later at StackOverflow. In short, what you have to do is the following:

• Escape every table that has capital letters (using \"):

• Escape every field that has capital letters (using \"):

• Escape joins that include columns that have capital letters (strangely, using `):

It is a tedious work. This worked for me with PostgreSQL 9.1.9, Hibernate 4.1.3 and Java 7. 

For a complete example you can review the code at BitBucket of any of the classes of the SimModSys project's persistence package.

English Hibernate Java PostgreSQL Simulation Model System Troubleshooting