CareerCup

spot on!!

@eugene
building the comparator depends on the api of the dictionary, what would be the api of the dictionary? is it also the problem to be solved by us

refer to my earlier reply for the approach

public class AlphabetMatrixMoves {

	public static void main(String args[]) {
		char[][] array = { { 'a', 'b', 'c', 'd', 'e' },
				{ 'f', 'g', 'h', 'i', 'j' }, { 'k', 'l', 'm', 'n', 'o' },
				{ 'p', 'q', 'r', 's', 't' }, { 'v', 'u', 'w', 'x', 'y' },
				{ 'z' } };

		HashMap<Character, int[]> map = fillMap(array);

		String testStr = "zkl";
		
		char[] test = testStr.toCharArray();

		int[] cur = { 0, 0 };
		
		System.out.println("Starting at "+Arrays.toString(cur));

		for (int i = 0; i < test.length; i++) {
			// need to go to
			System.out.println("Need to go to " + test[i]);

			
			int[] target = map.get(test[i]);
			
			System.out.println("Target "+Arrays.toString(target));

			while (cur[0] != target[0] || cur[1] != target[1]) {

				while (cur[0] < target[0]) {
					cur[0]++;
					System.out.print(" DOWN ");
				}

				while (cur[0] > target[0]) {
					cur[0]--;
					System.out.print(" UP ");
				}

				while (cur[1] > target[1]) {
					cur[1]--;
					System.out.print(" LEFT ");
				}

				while (cur[1] < target[1]) {
					cur[1]++;
					System.out.print(" RIGHT ");
				}
			}
			System.out.println(" ! ");
			
		}

	}

	private static HashMap<Character, int[]> fillMap(char[][] array) {
		Map<Character, int[]> map = new HashMap<Character, int[]>();

		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				map.put(array[i][j], new int[] { i, j });
			}
		}
		System.out.println(map);
		return (HashMap<Character, int[]>) map;

	}

}

my approach
1. Maintain a hashtable which stores char --> address
2. As there is no diagonal moment possible, the shortest distance from the current point to the target would be moving horizontally till we reach the column containing the target and moving vertically to the row containing the target.(increase/decrease x and increase/decrease y)
3. print out the sequence while moving and print ! once you reach the target.

@Rakesh, IMO, you understood the question wrong, the input here is a word, that needs to be typed and we need to generate the sequence of 'up/down/left/right/!' key press sequence.

explanation or code comments please!!

@showell
Thanks for a such a clear explanation."min-item-in-list" problem, how can I forgot a basic thing.
I am struggling with a question though, could you please comment on it, id=15489912

@Showell nice answer.
but at the first glance of the question, I was thinking about KNOWS(A,B) as some kind of comparative function, which can be used in sorting. and once we sort the list we would get the celebrities at one end, ofcourse there is no comparitive sort which can perform in linear time.

approach 1 : read F1 and F2 line by line and perform a regex such that only alphabets can be retrieved and compare the matches from both the results,do it till we reach end of the two files
If we reach the end of one file sooner, than the other, they are not equal.

approach 2: I am not sure about this, may be some one can give some feedback
create a hash of the file 1 and file 2 ignoring spaces and special characters, and if they are equal then the files are equal.

The definition can be easily found on web, I would like to give an example from the Java Api
'Comparator'

@Chih Chiu
It makes the solution much simpler, when the characters are repeated, then we can further prune the recursion tree using the memoization.

@Ashwini

good thinking outside the box, I guess the problem description here is not complete, if it was then it would have included a simple balance and the interviewer is test the knowledge on the information theory, see below Tigran's comment.

I guess you are right, but if that is actually the case then we need to prove that it is impossible, it can be proved some concept called information theory.
5 balls
2 weighs gives us two outcomes , two bits of information
can represent 00, 01, 11, 10 (4 states)
but there are 5 balls hence, it is impossible.

and to add one more thing, we would not be calculating permuations for 26 alphabets but for only for alphabets in the set "a,e,o,g,z,k,l,j,w,n" with varying lengths ofcourse.

But I would not be generating the entire number of permutations, I will stop if the no more words are found with the current prefix, IMO that reduces the number of permutations to be calculated by very large extent

could any one review my approach

Let us assume that the dictionary is in a trie
Start by finding the permutations of the given letters, here we could be using recursion, we can prune the recursion tree, by checking the letters in the dictionary. and we maintain a variable which holds the largest string formed till now.

second it.

Working solution in java.
I am assuming the entire array is passed,and the end elements are filled with spaces
I calculate the number of pairs,and I start at the last pair and work my way to the first pair

public static void main(String[] args) {
	//	new ProgramToCompressString().displayCompressedString("ABD");
		new ProgramToCompressString().displayDecompressedString(new char[]{'a','2','b','3','d','3',' ',' '});
	}

	private void displayDecompressedString(char[] cs) {
		System.out.println("Before : "+Arrays.toString(cs));
		int f = 0 ;
		while(cs[f] != ' '){
			f = f+1;
		}
		
		int pairs = f/2;
		assert f%2==0;
		
		System.out.println("Number of pairs : "+ pairs);
		
		int rptCount = 0 ;
		
		for(int i=pairs; i> 0 ; i --){
			char temp  = cs[i*2-2];
			int rpt = Character.getNumericValue(cs[i*2-1]);
			rptCount += rpt;
			for(int j = 0 ; j < rpt ; j ++){
				System.out.println(rpt+" "+j);
				cs[cs.length-rptCount+j] = temp;
			}
		}
		
		System.out.println("After : "+Arrays.toString(cs));
	}

This method prints the first node , whose value lies between i and j

private void findNodeBetweenValues(Node node ,int i, int j) {
		if(i > j){
			throw new IllegalArgumentException();
		}
		if(node.data > i && node.data < j){
			System.out.println("value between "+i+" & "+j+" is "+this.root.data);
		}else if(node.data < i){
			findNodeBetweenValues(node.left,i,j);
		}else if(node.data > j){
			findNodeBetweenValues(node.right,i,j);
		}

}

could be related to the "game of life"
search for conways-game-of-life-in-java in technicalypto site

when i < inp.length()
and
inp.charAt( i ) == inp. charAt(i+1)
gives
ArrayIndexOutOfBoundsError

straight forward solution

public void doIt(String s,Map<Character,Character[]> m){
		List<String> results = new ArrayList<String>();
		if(results.add(s));
		for(Character c : s.toCharArray()){
			if(M.containsKey(c)){
				List<String> list = new ArrayList<String>();
				for(Character k : M.get(c)){
					for(String temp : results){
						list.add(temp.replace(c,k));
					}
				}
				results.addAll(list);
			}
		}
		System.out.println(results);

could you please explain, what is the time and space compexity of this solution??

I agree with @nitingupta180 , once you find the least common ancestor of two nodes , you need to find the distance from the first node to LCA and from LCA to second node, then add them up.

this is my approach , given the longitude and latitude of an amazon store , we need to sort
the other list using the distance as for comparision, this sort can be done in nlogn time.

first approach is to sort the string 1 and 2 and check if they are equal.

second approach is to check the no of unique characters and there cardinality to be equal.
assuming ascii character set, define a int array with 256 length with all zeros, for each character from string 1 update the array , if you encounter the same character again update the count at the position.
now when going through the second array , decrease the count at that position. at the end check whether the array is neutralized(all zeros)

do you want to retrieve all the keys that are mapped to same value in a hashmap?

get the EntrySet of the hashmap, and retrieve the <Entry>entries in the set with the given value, which are nothing but the pairs having the same value.

If you are referring to java, then your conclusion might be wrong

if you start two threads one after the other, the start in a separat thread of execution. lets assume t1 takes 2 days for execution and t2 takes an hour, in your case t2 completes before t1 completes, using join is the right way to do it.

i guess the question said that inbuilt string functions should not be used

I would like to answer the second part of the question regarding the usage of the abstract class Lets say class A contains methods a1 , a2 and a3. Now a1 is a method which should be implemented specific to the subclass and it has no relevance if implemented in the parent class, and methods a2 and a3 use a1.

The best real time example that uses Abstract class is the InputStream class, here the read method is overloaded and all the overloaded methods depend on the one abstract read method, which is implemented by the specific child classes like FileInputStream , ZipFileInputStream