[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 :

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

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

Q3. How do you find the middle item in a link list?
Q4. How would you write a function to reverse a string? Can you do it without a temporary string?

Source : Algorithms from 100 Interview Questions for Software Developers

Find the bulb for the switch

There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can't change them. Identify each switch with its bulb.

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

Find direction of rotation

Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

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

Pay for 7 days using 1 7-segment gold bar and 2 cuts

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

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

[Probability] Divide 100 marbles into two piles

How would you divide 50 black and 50 white marbles into two piles so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random?

Source : http://gurmeetsingh.wordpress.com/puzzles/

Find the poisoned wine barrel

An enemy spy has poisoned one out of 1000 barrels of wine in a king’s cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel

Source : http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-poisoned-wine-barrels/

ping.fm - better than friendfeed, just what I want

Experimenting with ping.fm's Y! bot. You can post to the huge set of social networks http://ping.fm supports - all using their integration with IMs, SMS and Web. Prety cool :)

Rope Escape

Rajeev is trapped atop a building 200m high. He has with him a rope 150m long.There is a hook at the top where he stands.

Looking down, he notices that midway between him and the ground, at a height of 100m, there is a ledge with another hook. In his pocket lies a Swiss knife.

How might he be able to come down using the rope, the two hooks and the Swiss knife?

Source : http://gurmeetsingh.wordpress.com/puzzles/

[ALGO] Six Colored Balls

We have two red, two green and two yellow balls. For each color, one ball is heavy and the other is light. All heavy balls weigh the same. All light balls weigh the same. How many weighings on a beam balance are necessary to identify the three heavy balls?

Source : http://gurmeetsingh.wordpress.com/puzzles/

svn:ignore

I have a build which produces some extra files (not to be checked in).
Every time a do a build, svn shows these files as non versioned, new files and I have to ignore them.

Enter -

svn propset svn:ignore

. Here is how it worked for me :

prompt> svn status
?       test.log
?       test.log.1
..... (other src code)

Look at those test.log entries - my test case generated them and I'm least bothered to delete them. However, it corrupts my svn status output :-)

So will create an ignore file :

prompt> cat ifile
test*

and ask svn to ignore these file patterns :

prompt> svn propset -R svn:ignore --file ifile .
prompt> svn status
M      .
M      src
M      src/test
... (other src code)

There - the test.log entries no longer show up in svn status

prompt> svn commit

Detailed reading on svn property set : http://svnbook.red-bean.com/en/1.1/ch07s02.html

Find if there is only one bit set in a number

In the bit representation of a number, find if there is exactly one bit that is set.

e.g. your approach should say true for the following numbers :
1,2,4,8,16
and false for the following numbers :
3,5,7,10

[PS] Catch the Fox

Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?

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

Q1. How do you find out if a number is a power of 2?
Q2. And how do you know if it is an odd number?

Source : Algorithms from 100 Interview Questions for Software Developers

All purpose problem solving algorithm

LOL - Only if he had put in all that logic into solving the real problem ;-)

[ALGO] Water jugs problem

Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water & vice versa.

How can you find the grouping of the jugs into pairs of red & blue jugs that hold the same amount of water, in the minimum number of comparisons.

Operations allowed

always compare between a red and a blue jar (no two reds, no two blues)
fill water in red / blue jug
pour from red jug to blue (& vice versa). This will help compare the capacity of the jugs.

Source : Introduction to Algorithms (by Cormen..., Problem 8-4)

Find if number occurs exactly n/2 times in an array

You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?

Expected time complexity : O(n)
Expected space complexity : O(1)

What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)

Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html

Dividing array into groups

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:
<8,2,4,7,1,0,3,6>

should be divided into two groups like this:
<2,4,1,0,3> <8,7,6>

Source : http://discuss.techinterview.org/default.asp?interview.11.770712.8

Sort on second key when, first key in a set is sorted

Assume that we are given as input n pairs of items, where

the first item is a number
the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Find if summation of numbers from two lists is given number

Problem: Given two lists A & B define an algo, which will identify two numbers 'a' and 'b', such that a + b = x, where 'x' is the input.

Gebo - Madhur Tanwani's blog