[ALGO] Is Binary Search Tree

Given a binary tree, verify if it is Binary Search Tree

[ALGO] Find the string in 2 dimensional matrix

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
|  A  |  B  |  C  |
|-----|-----|-----|
|  H  |  X  |  D  |
|-----|-----|-----|
|  G  |  F  |  E  |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    |  y  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  a  |  o  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  o  |  o  |
    |-----|-----|-----|-----|
    |  h  |  a  |  a  |  o  |
    |-----|-----|-----|-----|
    |  y  |  a  |  h  |  o  |
    |-----|-----|-----|-----|
                            (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

[ALGO] Random number generator, with equal probability

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)


Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here  http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

Things To Do...

I recently attended a Spring training by SpringSource. While learning the framework and admiring its features, it prick me that there is a LOT that I don't know and have to gather.

So, after a long time I'm starting this post, that I anticipate to update regularly with things I want to do, things I want to learn and things I want to talk about.

Expect one blog title for each entry in this list. So, here I go :

1. P1: Spring - an E2E tutorial - put to use all the learning from the training into a live example.
2. P2: OSGi - post an article listing resources I read to understand OSGi. Maybe with a few self comments
3. P?: Groovy - I really loved the way Groovy scripts helped code Java applications quickly. I'm going to try them out
   
4. P?: Grails - Another quick build of a web application. I'm going to try this out too.
5. P?: Castor - Data binding framework : http://www.castor.org/
6. P?: JBoss Seam
7. P?: Spring Roo : http://en.wikipedia.org/wiki/Spring_Roo
8. P2: Why should one refrain from using Stubs and prefer using XPath for Web service implementation (server side)
9. P2: Code-first VS contract-first approach for webservices
10. P?: The JSF standard
11. P2: Distributed transactions - an interesting concepts / field. How about starting here : Distributed transactions in Spring, with and without XA
12. P2: Java Persistence API : https://glassfish.dev.java.net/downloads/persistence/JavaPersistence.html
13. P?: JDO : http://java.sun.com/jdo/
14. P2: JSR-250 Common Annotation
15. P1: Introduction to Algorithms @ MIT Open Courseware - http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm
16. P?: A course / reading on OOAD, Systems Analysis, Design
17. P?: Machine Learning Modeling Algo : Linear CRF - What? How?
    

.... (To be continued...)

Walk the bridge, in pairs as fast a possible

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Find jar with the contaminated pills

You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Algorithms from "100 Interview Questions for Software Developers" : Part 3

Find repeating element in array

I felt this  question deserves a post of its own. So here it is :

 Q5. In an array from 1 to n, one number is present twice. How to do you determine which one?

There are multiple answers - all correct. We would, obviously, aim for the optimized one - benchmark parameters being time & space complexity

Source : Algorithms from 100 Interview Questions for Software Developers