CareerCup

create an int array A, of size 26 and initialize to 0
for each letter S[i], in given string, if it is alphabet, then A[lower(S[i])-'a']++
iterate over A and return false if you find any A[i] equal to 0

This can be solved in O(N), where N is the length of the word.

Lets assume,
- that the length of the word, N is given
- the machine returns 1 for each letter in test string matching the letter in dictionary word in the same index

private void findWord(int n) {
        Character[] result = new Character[n];
        char[] sample = new char[n];
        int prevCount = 0;
        for (int c = 'a'; c <= 'z'; c++) {
            fillAll(sample, result, (char)c);
            int count1 = checkWord(sample);
            if (prevCount == count1) {
                // the alphabet c never appeared in result; so skip and go to the next alphabet
                continue;
            }
            c++; // go to next char
            for (int i = 0; i < n; i++) {
                char old = sample[i];
                if (result[i] != null) {
                    // this index already has a valid char
                    continue;
                } else {
                    sample[i] = (char) c;
                }
                int count2 = checkWord(sample);
                if (count2 > count1) {
                    // c belongs to index i
                    count1++;
                    result[i] = (char)c;
                } else if(count2<count1 ) {
                    // old char belongs to this index;
                    result[i] = old;
                    sample[i] = old;
                }
            }
            prevCount = count1;
        }
    }

    private void fillAll(char[] sample, Character[] result, char c) {
        // file the index i of sample with char c where result[c] is null;
    }

    private int checkWord(char[] sample) {
        // return the count of chars in sample, matching the corresponding index in the dictionary word
    }

Here for each iteration of outer loop we complete two alphabets, hence it runs 13 time max.
The inner loop runs N times in worst case.
Hence the word can be guess in 13*N trials

There are two clues in the question.

1. its a 10 digit number
2. they are numbers

With these we can design a list of 10 bitsets where
- 'i'th bit of 0th bitset will be 1 if the 'i'th row contains zero
- 'i'th bit of 1st bitset will be 1 if the 'i'th row contains one
and so on.
when you get a number to search get the corresponding bitset for each digit and do an AND of collected sets. Now wherever you have one, that rows are the results.

Space: 10*n bits where n is the number of rows
Time for building: O(1) for finding the right bitset for each digit and O(1) for marking the row in the set. hence 10*n (~n)
Time for searching: O(1) for finding the right bitset for each digit and iterate over the bitset to find the final rows (i.e O(n))

A[i]                      newsets                                       sets
-----------------------------------------------------------------------------
1                         {1}                                           {1}
2                         {2}, {1,2}                                    {2}, {1,2}
3                         {3}, {2,3}, {1,2,3}                           {3}, {2,3}, {1,2,3}
4                         {4}, {3,4}, {2,3,4}, {1,2,3,4}                {4}, {3,4}, {2,3,4}, {1,2,3,4}
5                         {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}   {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

Time: O(n(n+1)/2)=n*n
Space: n(n+1)/2 // to store the limited number of subsets

n=length(A)
sets=[ ]
for (i=0 to n-1)
    newsets = [ ]
    newsets.add( setof(A[i])
    if(M == 1 && setof(A[i]) == SUM) print and break
    foreach set in sets
        s1 = sets[j].add(A[i])
        if(s1.size == M && sum(s1)==SUM) print and break
        newsets.add(s1); // we can also skip adding s1 if s1.size>M
     sets.clear()   // we dont need the old sets as we cant add next item to them
     sets.addAll(newsets)

Lets say A= {1,2,3,4,5}
M=3
SUM=12


A[i] newsets sets
-----------------------------------------------------------------------------
1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

in last iteration we have {3,4,5} whose sum is 12 and size is 3.

Now we went through A only once, but for each elements we iterated over sets which is i times hence n(n+1)/2.
In the last iteration we stored n(n+1)/2 items which is the max

<pre lang="" line="1" title="CodeMonkey97168" class="run-this">import java.util.ArrayList;
import java.util.List;

/**
*
* @author Pragalathan
*/
class CoinDenomination {

static class Coin {

int value;
int count;

public Coin(int value, int count) {
this.value = value;
this.count = count;
}

@Override
public String toString() {
return "(" + value + "x" + count + ")";
}
}
Coin[] coins;

public CoinDenomination(Coin[] coins) {
this.coins = coins;
}

List<Coin> getChange(int amount) {
List<Coin> change = new ArrayList<Coin>();
getChange(amount, 0, change);
return change;
}

private boolean getChange(int balance, int coinIndex, List<Coin> change) {
if (coinIndex >= coins.length) {
return false;
}
Coin coin = coins[coinIndex];
int count = Math.min(coin.count, balance / coin.value);

for (int i = count; i >= 0; i--) {
int newBalance = balance - i * coin.value;
if (newBalance == 0) {
change.add(new Coin(coin.value, i));
return true;
}
if (getChange(newBalance, coinIndex + 1, change)) {
if (i > 0) {
change.add(new Coin(coin.value, i));
}
return true;
}
}
return false;
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] values = {1, 5, 10, 25, 50, 100};
int[] counts = {3, 4, 2, 4, 1, 2};

Coin[] coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
CoinDenomination cd = new CoinDenomination(coins);
int amount = 33;
System.out.println(amount + ": " + cd.getChange(amount));

values = new int[]{1, 10, 25, 50, 100};
counts = new int[]{3, 3, 4, 1, 2};

coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
cd = new CoinDenomination(coins);
amount = 205;
System.out.println(amount + ": " + cd.getChange(amount));
}
}
</pre><pre title="CodeMonkey97168" input="yes">
</pre>