CareerCup

Super cool, you can make this space efficient by using start/end pointers instead of straight up using substrings but this is good!!!!

Sorry, im slow and I don't see how your solution works, can you type out the real code for a better picture? Thanks.

The numbers are stored from most sig digit to least from right to left in the array, as you'd probably naturally imagine.

int[] arr = {1, 2, 3}; // 123

The type of array is int[]. (This was originally in Java when asked).

Am I crazy but can't we do a BFS search on the 2D plane with a K count. Once K has hit its value we just return a list of found points? Here is the code:

static boolean inbounds(int[][] plane, int x, int y) {
        if (x >= 0 && y >= 0 && 
            x < plane[0].length && y < plane.length) {
            return true;
        }
        return false;
    }
    
    static int[][] closestk(int[][] plane, int k) {
        Queue<int[]> q = new ArrayDeque<int[]>();
        int[][] found = new int[k][2];
        int n=0;
        int x=0;
        int y=0;
        q.add(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] tup = q.remove();
            int tmpx = tup[0];
            int tmpy = tup[1];
            int e = plane[tmpy][tmpx];
            if (e == 1) {
                found[n++] = tup;
            } if (n == k) {
                return found;
            }
            // NOTE: The order of the following 3
            // if statements are crutial. The diagnol
            // square is the "farthest" from our current point
            if (inbounds(plane, x+1, y)) {
                q.add(new int[]{x+1, y});
            }
            if (inbounds(plane, x, y+1)) {
                q.add(new int[]{x, y+1});
            }
            if (inbounds(plane, x+1, y+1)) {
                q.add(new int[]{x+1, y+1});
            }
            x++;
            y++;
        }
        return found;
    }

usually when i'm in interviews they want the candidate to implement any type of sorting by hand

First, note that we need to hit each character in order.

If the "graph" is just a 2D matrix the shortest path to any character is just trivially moving to the row the character is on, and then the column. Think about it for a second.

So everyone in this thread is in fact finding the shortest path on the graph, it's just not with a "shortest path algorithm" as you'd expect.

Here is the full java implementation:
It takes advantage of hashing and sorting. Sort each string alphabetically via quicksort.
Hash each string to avoid multiple comparisons, we can compare numbers easily.
Then print out buckets which are just hashtable values.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramBucket {
	/*
	 *  Input - List<String> ["star", "rats", "ice", "cie", "arts"] 
	 *	print all anagrams in buckets: 
	 *  ["star", "rats", "arts"] 
	 *  ["ice", "cie"] 
	 * 
	 *  Our implementation will take advantage of hashing and string sorting.
	 *  This is O(n*mlog(m)) where m is the length of average string, n=# strings.
	 *  We first sort each string using quicksort on the characters.
	 *  Then, hash the sorted strings into numbers which takes O(n*m). 
	 *  Then we make one more pass and dump them into buckets.
	 *  
	 */
	static String sortstr(String str) {
		/* encapsulating original sortstr method */
		char[] chararr = str.toCharArray();
		sortstr(chararr, 0, str.length()-1);
		return new String(chararr);
	}
	
	static void sortstr(char[] arrchar, int start, int end) {
		/* inplace quicksort, car=>acr */
		if (start > end)
			return;
		
		int piv = arrchar[end];
		int lo = start;
		int hi = end;
		while (lo <= hi) {
			while (arrchar[lo] < piv)
				lo += 1;
			while (arrchar[hi] > piv)
				hi -= 1;
			if (lo <= hi) {
				char tmp = arrchar[lo];
				arrchar[lo] = arrchar[hi];
				arrchar[hi] = tmp;
				lo += 1;
				hi -= 1;
			}
		}
		sortstr(arrchar, start, hi);
		sortstr(arrchar, lo, end);
	}
	
	static void anagrambuckets(List<String> input) {
		HashMap<Integer, List<String>> map = 
				new HashMap<Integer, List<String>>();
		
		for (int i=0; i<input.size(); i++) {
			String srtedstr = sortstr(input.get(i));
			int code = srtedstr.hashCode();
			if (map.containsKey(code)) {
				map.get(code).add(input.get(i));
			}
			else {
				List<String> z = new ArrayList<String>();
				z.add(input.get(i));
				map.put(code, z);
			}
		}
		
		for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
			System.out.println("Key " + entry.getKey() + 
				" bucket: " + entry.getValue().toString());
		}
	}
	
	public static void main(String[] args) {
		List<String> input = new ArrayList<String>();
		input.add("star");
		input.add("rats");
		input.add("ics");
		input.add("cie");
		input.add("arts");
		anagrambuckets(input);
	}
}

Nice breaking the problem down. But one line confused me, what do you mean "We can use dynamic programming to find the best path"? At the current point of your solution, you already have the optimal path from BFS's on every single pair of islands + permutations of the pairs to find the shortest path. Maybe it was a mis-type or something?

Lol sorry for making my test title name "sex", was bored. Please don't flag me. Mods can remove if its offensive.

Here is a full Java implementation. It's a bit long because I added utility methods for clarity.

public class DVR {
	/*
	 * 
	 * I need a function that takes the name of the movie to look up and 
	 * the width of the letter grid, and computes the key presses that 
	 * will enter that string on the DVR grid. The output should be a 
	 * string, with "u", "d", "l", "r", and "!" corresponding to up, 
	 * down, left, right, and select. 
	 *
	 * For example, with a grid of width 5, 
	 * a b c d e 
	 * f g h i j 
	 * k l m n o 
	 * p q r s t 
	 * u v w x y 
	 * z 
	 * the movie "up" would be "dddd!u!".
	 * 
	 * 
	 */
	
	static char[] alphabet = get_alphabet();
	static String UP = "u";
	static String DOWN = "d";
	static String LEFT = "l";
	static String RIGHT = "r";
	static String SELECT = "!";
	
	static char[] get_alphabet() {
		/* Generates the english alphabet in a char array. */
		char cur = 'a';
		char[] alphabet = new char[26];
		for (int i=0; i<26; i++) {
			alphabet[i] = cur;
			cur++;
		}
		return alphabet;
	}
	
	static int[] getcoords(char letter, int width) {
		/* Given a character, return it's position
		 * in the alphabet matrix */
		int pos = -1;
		for (int i=0; i<alphabet.length; i++) {
			if (letter==alphabet[i]) {
				pos = i;
				break;
			}
		}
		int rownum = (int) Math.floor(pos / width);
		int colnum = pos % width;
		int[] ret = { rownum, colnum };
		// System.out.println(rownum + " " + colnum);
		return ret;
	}
	
	static String getsequence(String name, int width) {
		
		/* 
		 * We must take ceiling because sometimes it's not
		 * a perfect square, we need the extra row. 
		 *
		 * I thought the two below vars would be needed, was wrong!
		 * int height = (int) Math.ceil(alphabet.length / width);
		 * char[][] matrix = new char[width][height]; 
		 *
		 */
		
		StringBuilder seq = new StringBuilder();
		int[] curcoord = {0, 0}; // y, x
		
		for (int i=0; i<name.length(); i++) {
			char curnchar = name.charAt(i);
			int[] nextcoord = getcoords(curnchar, width);
			int deltay = nextcoord[0] - curcoord[0];
			int deltax = nextcoord[1] - curcoord[1];
			
			boolean goup = true;
			boolean goright = true;
			if (deltax < 0) 
				goright = false;
			if (deltay > 0) // tricky, this one is flipped
				goup = false;
			
			deltax = Math.abs(deltax);
			deltay = Math.abs(deltay);
			
			for (int j=0; j<deltay; j++) {
				if (goup) seq.append(UP);
				else seq.append(DOWN);
			}
			for (int k=0; k<deltax; k++) {
				if (goright) seq.append(RIGHT);
				else seq.append(LEFT);
			}
			seq.append(SELECT);
			curcoord[0] = nextcoord[0];
			curcoord[1] = nextcoord[1];
		}
		return seq.toString();
	}
	
	public static void main(String[] args) {
		// for (char c : alphabet)	
		//     System.out.println("char " + c);
		System.out.println(getsequence("sex", 5));
	}
}

#1 This is an IO task, so we can implement multithreading. This is important to note.
#2 Don't send a GET request, send a HEAD request, that's enough to see if the link is broken.

I'm not sure how else we can make this more efficient, other than that just download all the responses and see which ones are broken! Broken error codes start with 4--.

Instead of a Radix sort, I opted for a quicksort with a custom comparison method for less space complexity. Here is some working java code.

public class LargestPerm {
	
	static int[] arr = {21, 9, 23};
	
	public static void main(String[] args) {
		qsort(arr, 0, arr.length-1);
		StringBuffer sb = new StringBuffer();
		
		for (int a : arr) 
			sb.append(Integer.toString(a));
		
		System.out.println(sb.toString());
	}
	
	public static void qsort(int[] arr, int a, int b) {
		if (arr.length <= 1) 
			return;
		if (a > b) return;
		int piv = arr[(a + b)/2];
		int start = a; 
		int end = b;
		while (start <= end) {
			while (compare(arr[start], piv)) // start > piv
				start++;
			while (compare(piv, arr[end])) // end < piv
				end--;
			if (start <= end) {
				int tmp = arr[start];
				arr[start] = arr[end];
				arr[end] = tmp;
				start++;
				end--;
			}
		}
		qsort(arr, a, end);
		qsort(arr, start, b);
	}
	
	public static boolean compare(int a, int b) {
		if (a == b) 
			return false;
		char[] aa = Integer.toString(a).toCharArray();
		char[] bb = Integer.toString(b).toCharArray();
		int i = 0;
		while (i < aa.length && i < bb.length) {
			if (aa[i] > bb[i]) return true;
			else if (bb[i] > aa[i]) return false;
			else i++;
		}
		return true;
	}
}

Impressive, your solution is THE optimal one I believe!

Is if (set.contains(current.next)) --blocks; needed? That's the only part that seems iffy to me, everything else looks great, blows all the other answers away. Also, what if the references array was ordered, how would this be more effecient?

Thanks.

This is Analogous to Java's LinkedHashMap. Just create a LinkedList structure and attach new nodes (elements) as they are added, it's going to be in added order.

What if you are going in one direction but a word has multiple words within it.

For example: "automobile" has "auto" in it, which is also a valid word. Auto is just a prefix of automobile though, so it will just return automobile right? Do tries handle that?? I'm not sure

Anon is right, might wanna edit the code Rami

looks correct, the values of the HashMap dont matter right? It can be whatever, we are only testing for keys?

I may have figured it out just now with help from "anonymous", not sure though.

1. Put all the node refs into a hashtable.
2. Iterate through the linkedlist:

int blocks = 0;
while ( cur != null ) {
       if ( cur.inHashTable() ) {
           while ( cur != null && cur.inHashTable() ) {
                  cur = cur.next;
           blocks++;
       }
       cur = cur.next;
}

return blocks;

O(n) runtime with n being the number of nodes.

It works, I think we can do better though, the guy hinted that the good soln was "like a few lines of code" and "used a HashMap"

1. No it can not
2. 2 blocks:
[0, 1, 2] 3 [4]

0, 1, 2 are adjacent, counts as one block.

I had no idea that this was a famous problem, thank you.