Exchange problem

Its new year time and your company has sent T-Shirts of varying sizes from HQ (read US). The problem is that the sizes in US and the sizes in India don't really match. So a guy with L size in India would like to settle for M size in US, one with XXL in India would like to go for XL and so on. Employees in India are bugged up and want to exchange it with appropriate sized T-Shirt. Now that the management didn't take care of it before sending the T-Shirts to India, you have been assigned by the Indian management to arrange an exchange between the employees. How would you go about it? Also describe your algorithm. If all this information is stored in the database, write a query that would do the job.

Random Number Generation

Given a function random(0,1) which randomly generates 0 or 1 with equal probabilities, extend its functionality to generate random numbers for an interval [a,b], i.e. implement random(a,b), for all 0 =< a < b. Prove that the strategy is uniformly random or would you like to put some conditions on a and b?


Another version: Given a random function random() which generates 0,1 but with uneven probabilities, create a random function newrandom() which generates 0,1 with even probabilities. Uneven probabilities mean if probability of getting 0 from random is p, that of 1 is (1-p) but p!=(1-p)!=1/2

array question again

Suppose you are having an array of n integer. All the elements in the array are unique
except one element. That one special element in array is repeating in array in order of power two(means even repetition)

example - 1 2 3 4 5 6 5 7 8

all element in this array are unique except 5.. and 5 is repeating 2 times (power of 2).
we need an algo to find this special element in array

Why is String immutable in Java or are they?

Ref: http://www.javaspecialists.eu/archive/Issue014.html

Team Photo Problem

Since three guys (Ghoida, Nini and Dinu Kaka) from our team have decided to move on, its time to take a team photo. Camera man proposed that for a nice photo people should arrange themselves in such a way that the height difference between two adjacent guys are minimum. Since Dinu Kaka is the senior most of all three, we decided to keep him at the center and Nini and Ghoida will be at either ends (one at left and the other at right). Nini being so enthusiastic about his analytical skills decides to write an algorithm that will ensure that average height gaps of the arrangement is minimum. Any idea how he would do it? If there are even team members, Dinu Kaka may choose any of the two mid positions as he wish (and since he is a nice guy, he would accept any of the two positions that Nini tells him to go to).

another graph problem

Find out if there is cycle in a given graph?

Knapsack Problem Variation

Given infinite supply of "n" denominations of coins and a change amount "A", give an algorithm to use minimum number of coins to do the transaction?