CareerCup

import java.util.*;

public class Main {
    public static void main(String[] args) {
        printLongestWord("abpcplea",new HashSet(Arrays.asList("ale", "apple", "monkey", "plea")));
    }

    public static void printLongestWord(String input, Set<String> dictonary){
        Set<String> sortedBySizeDictonary = orderSetBySize(dictonary);

        for (String dictonaryEntire : sortedBySizeDictonary) {
            if (isStringContained(dictonaryEntire, input)) {
                System.out.println(dictonaryEntire);
                return;
            }
        }

    }

    public static boolean isStringContained(String src, String dest){
        int i=0,j=0;

        while (j<dest.length() && i<src.length()){
            char x=src.charAt(i);
            char y=dest.charAt(j);
            if (x==y) {
                i++;
            }
            j++;
            if (!(j<dest.length())){
                return false;
            }
        }

        return true;
    }

    private static Set<String> orderSetBySize(Set<String> set) {
        TreeSet<String> treeSet= new TreeSet(new comparator());
        for (String entire : set){
            treeSet.add(entire);
        }
        return treeSet;
    }

    static class comparator implements Comparator<String>{
        @Override
        public int compare(String s, String t1) {
            if (s.length()>t1.length()) return -1;
            return 1;
        }
    }

that is great exept I have no idea what is n (n equals to..?). all I have is the tree root.

Good thinking.
But in fact, you turn the problem above into this problem:
"Given an a equation of the form of x1+x2+...+xn=sum, while x1!=x2!=..!=xn, find a soultion from the group {1,2...2n} (i.e. 1<=x1,x2...xn<=2n))
How you can solve this problem by **not using** backtracking?
The answer is that you can't. This is a NP-complete problem and if you solve it in a polynomail time that means that you prove that P=NP and you can get your turing prize this year! :)

I believe that the problem above cannot be solve without backtracking since it can be reducted into an NP complete one...

my 2 cents.
lets model the problem as a adjacency matrix one.
lets define int arr[][] and for each arr[i][j] is 1 <=> i knows j.

so we acutally need to find 2 thing:
1. all of the k rows that follow this rule: (arr[k][i]==0 iff k!=i) for (0<=i<=arr.length)
2. all of the m colums that follow this rule: (arr[i][m]==1) for (0<=i<=arr.length)

the 1's rule checks if the person k doesn't know no one else but himself.
the 2's rule checks if all the other person know who person m is.

we need to find k such as (k==m), meaning both of the conditions are followed.

for i.e. this is a matrix that has person with index 3 (starting from 0) as a celebrity:

1 0 0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0 1 0
0 0 0 1 1

note that there can be no more than one k and no more the one m.

we can travel in a manhattan distance path from the first line until we encouter the last line or column of the matrix fo find the celebrity (we are actully finding k which is unique and can only be equal to m).

1-0-0 1 1
1 1 1 1 1
0 0 1 1 0
0 0 0-1-0
0 0 0 1 1

and the code:

package findCelebs;

import java.util.HashSet;
import java.util.Set;

public class FindCelebrity {
	static int knows[][];

	public static void main(String[] args) {
		knows = new int[][] { 
				{ 1, 0, 1, 1, 1 }, 
				{ 1, 1, 1, 1, 1 },
				{ 0, 0, 1, 1, 0 }, 
				{ 0, 0, 0, 1, 0 }, 
				{ 0, 0, 0, 0, 1 } };
		
		Set<Integer> people = new HashSet<Integer>();

		for (int i = 0; i < 5; i++) {
			people.add(i);
		}

		System.out.println(findCelebrity(people));
	}

	public static int findCelebrity(Set<Integer> group) {
		return isCelebrity(group, 0);
	}

	public static int isCelebrity(Set<Integer> group, int personInKRow) {
		if (personInKRow >= group.size()) {
			return -1;
		}

		// a celebrity must knows himself
		if (!knows(personInKRow, personInKRow)) {
			// so check the next person in line
			return isCelebrity(group, personInKRow + 1);

		}
		for (int j = personInKRow + 1; j < group.size(); j++) {

			if (knows(personInKRow, j)) {
				// personInKRow is not the celebrity - knows some one else but
				// himslef
				// so check the person in line j
				return isCelebrity(group, j);
			} else {
				// personInKRow does not know j -j is not the celebrity
			}
		}
		return personInKRow;
	}

	private static boolean knows(int i, int j) {
		return (knows[i][j] == 1);
	}
}

public static void printSeq(char[] word) {
		int xPos = 0;
		int yPos = 0;
		char c;
		for (int i = 0; i < word.length; i++) {
			c = word[i];
			for (int j = xPos; j < (c - 'a') / 5; j++) {
				System.out.println("Down");
			}
			for (int j =  (c - 'a') / 5; j < xPos; j++) {
				System.out.println("Up");
			}
			for (int j = yPos; j < (c - 'a') % 5; j++) {
				System.out.println("Right");
			}
			for (int j =  (c - 'a') % 5; j < yPos; j++) {
				System.out.println("Left");
			}
			System.out.println("Ok");
			xPos = (c - 'a') / 5;
			yPos = (c - 'a') % 5;
 
		}
	}

lets take the worths case where there are m elements and each one of the m number is seprated between two numbers
i.e (1,3,5,7) and not (1,6).
then we will do binary search (O(log(n)) for each missing number (m) which will give us: m*log(n) which in case m is constat will give O(log(n))

right... so lets make it:

public static void findMissingNumbersBetweenToIndexes(int[] arr,
			Set<Integer> set, int start, int finish) {
		if (arr.length == 1) {
			return;
		}
		if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
			return;
		}
		if (start + 1 == finish) {
			for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
			}
			return;
		}
		int middle = (start + finish) / 2;
		// right
		findMissingNumbersBetweenToIndexes(arr, set, start, middle);

		// left
		findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
	}

I know, just added it to try to make it more readable to others...

can't edit but I reposted the code with the correct modification.

In Java:

public static Set<Integer> findMissingNumbers(int arr[], int m) {
	
		Set<Integer> set = new HashSet<Integer>();
		// dealing with array that does not start with 1
		for (int i = 1; i < arr[0]; i++) {
			set.add(i);
		}
		// dealing with the middle elements
		findMissingNumbersBetweenToIndexes(arr, set, 0, arr.length - 1);
		// recalculate m for any extra tail's numbers
		m = m - (((arr[arr.length - 1] - arr[0] + 1) - arr.length))
				- (arr[0] - 1);
		// dealing with the any extra tail's numbers
		for (int i = 1; i <= m; i++) {
			set.add(arr[arr.length - 1] + i);
		}

		return set;
	}

	public static void findMissingNumbersBetweenToIndexes(int[] arr,
			Set<Integer> set, int start, int finish) {
		if (arr.length == 1) {
			return;
		}
		if ((arr[finish] - arr[start] + 1) - (finish - start) == 0) {
			return;
		}
		if (start + 1 == finish) {
			for (int i = arr[start] + 1; i < arr[finish]; i++) {
				set.add(i);
			}
			return;
		}
		int middle = (start + finish) / 2;
		// right
		findMissingNumbersBetweenToIndexes(arr, set, start, middle);

		// left
		findMissingNumbersBetweenToIndexes(arr, set, middle, finish);
	}

T(n) is a function that is used in combination? because it is pretty obvious from the question that it is recursive (it is calling himself -1 and -2...) so I am not sure that I understood what you mean.

but you only check triplets of the form <i,i+1,k> - what about this triplet: <arr[2],arr[7],arr[15]>? When will you check it?