Shuffle a deck of cards perfectly

Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

My initial thoughts:
We first select a card randomly from the 52 cards. That is probability of 1/52. We then select another card from the rest 51 cards. That is probability of 1/51. So on and so forth. Finally we have a particular permutation with probability of 1/52!, which is expected.

My initial codes:

	public static List<Integer> shuffle() {
		Set<Integer> deck = new HashSet<Integer>();
		// build a deck of cards
		for (int i = 0; i < 52; ++i) {
			deck.add(i + 1);
		}
		List<Integer> shuffledDeck = new ArrayList<Integer>();

		for (int i = 0; i < 52; ++i) {
			int card;
			do {
				card = new Random().nextInt(52) + 1;
			} while (!deck.contains(card));
			deck.remove(card);
			shuffledDeck.add(card);
		}
		return shuffledDeck;
	}

Solution:
Let’s start with a brute force approach: we could randomly selecting items and put them into a new array. We must make sure that we don’t pick the same item twice though by somehow marking the node as dead.

Array:					[1] [2] [3] [4] [5] 
Randomly select 4:		[4] [?] [?] [?] [?] 
Mark element as dead: 	[1] [2] [3] [X] [5]

The tricky part is, how do we mark [4] as dead such that we prevent that element from being picked again? One way to do it is to swap the now-dead [4] with the first element in the array:

Array: 					[1] [2] [3] [4] [5]
Randomly select 4: 		[4] [?] [?] [?] [?]
Swap dead element: 		[X] [2] [3] [1] [5]

Array: 					[X] [2] [3] [1] [5]
Randomly select 3: 		[4] [3] [?] [?] [?]
Swap dead element: 		[X] [X] [2] [1] [5]

By doing it this way, it’s much easier for the algorithm to “know”” that the first k elements are dead than that the third, fourth, nineth, etc elements are dead. We can also optimize this by merging the shuffled array and the original array:

Randomly select 4: 		[4] [2] [3] [1] [5] 
Randomly select 3: 		[4] [3] [2] [1] [5]

This is an easy algorithm to implement iteratively:

	public static void shuffleArray(int[] cards) {
		int temp, index;
		for (int i = 0; i < cards.length; i++) {
			index = (int) (Math.random() * (cards.length - i)) + i;
			temp = cards[i];
			cards[i] = cards[index];
			cards[index] = temp;
		}
	}
Advertisements

Add two numbers without using of arithmetic operators

Write a function that adds two numbers You should not use + or any arithmetic operators.

My initial thoughts:
We should take care of two things: adding and carry. Addition can be done using XOR(^). Carry can be done using AND(&). The only tricky part is that when we have two bits like 1 and 0 but then we have carry from previous position, then 1 & 0 = 0 suggests no carry but actually 1 + 0 + 1 will produce a carry. So we branch into two case: 1 + 1 will definitely produce a carry no matter what; 1 + 0 + 1 will produce new carry.

My initial codes:

	public static int add(int a, int b) {
		int result = 0;
		int carry = 0;
		for (int i = 0; i < Integer.SIZE; ++i) {
			int bitIAtA = a & (1 << i);
			int bitIAtB = b & (1 << i);
			carry &= (1 << i);
			result |= bitIAtA ^ bitIAtB ^ carry;
			carry |= ((bitIAtA & bitIAtB) << 1 | ((bitIAtA ^ bitIAtB) & carry) << 1);
		}
		return result;
	}

Solution:
To investigate this problem, let’s start off by gaining a deeper understanding of how we add numbers. We’ll work in Base 10 so that it’s easier to see. To add 759 + 674, we would usually add digit[0] from each number, carry the one, add digit[1] from each number, carry the one, etc. You could take the same approach in binary: add each digit, and carry the one as necessary.
Can we make this a little easier? Yes! Imagine we decided to split apart the “addition” and “carry” steps. That is, we do the following:

  1. Add 759 + 674, but “forget” to carry we then get 323
  2. Add 759 + 674 but only do the carrying, rather than the addition of each digit. We then get 1110
  3. Add the result of the first two operations (recursively, using the same process de- scribed in step 1 and 2): 1110 + 323 = 1433

Now, how would we do this in binary?

  1. If we add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and b are both 0 or both 1. This is an XOR
  2. If we add two numbers together but only carry, we will have a 1 in bit[i] if bit[i-1] in a and b are both 1’s. This is an AND, shifted
  3. Now, recurse until there’s nothing to carry
	public static int add_no_arithm(int a, int b) {
		if (b == 0)
			return a;
		int sum = a ^ b; // add without carrying
		int carry = (a & b) << 1; // carry, but don't add
		return add_no_arithm(sum, carry); // recursion
	}

Find pairs of integers in an array that sum to a value

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

My initial thoughts:
For each element a in the array, we can find its complement s-a in the array and output this pair. To speed up the search, we can use binary search. Therefore we need to sort the array first, O(n\log n). Then for each element, we search for its complement, that’s another O(n\log n). Together it’s still O(n\log n).

My initial codes:

	public static boolean binarySeach(int[] array, int element) {
		int low = 0;
		int high = array.length;
		while (low <= high) {
			int mid = low + (high - low) / 2;
			if (element < array[mid])
				high = mid;
			else if (element > array[mid])
				low = mid + 1;
			else
				return true;
		}
		return false;
	}

	public static List<Pair<Integer>> findSum(int[] array, int sum) {
		Arrays.sort(array);
		List<Pair<Integer>> result = new LinkedList<Pair<Integer>>();
		Set<Integer> visited = new HashSet<Integer>();
		for (int i = 0; i < array.length; ++i) {
			int a = array[i];
			if (!visited.contains(a)) {
				visited.add(a);
				int b = sum - a;
				if (binarySeach(array, b)) {
					visited.add(b);
					result.add(new Pair<Integer>(a, b));
				}
			}
		}
		return result;
	}

Solution:

	public static void printPairSums(int[] array, int sum) {
		Arrays.sort(array);
		int first = 0;
		int last = array.length - 1;
		while (first < last) {
			int s = array[first] + array[last];
			if (s == sum) {
				System.out.println(array[first] + "" + array[last]);
				++first;
				--last;
			} else {
				if (s < sum)
					++first;
				else
					--last;
			}
		}
	}

Comments: the solution utilizes the state of sorted array and does a two-way search. Therefore after sorting, we only need one scan of the array. Altogether it ‘reduces’ the time complexity to O(n\log n + n).

Implement rand7() using rand5()

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()).

Solution:
First, observe that we cannot do this in a guaranteed finite amount of time. Why? Let’s see by a parallel example: How would you use rand2() to create rand3()?
Observe that each call of rand2() and the corresponding decision you make can be represented by a decision tree. On each node, you have two branches. You take the left one when rand2() equals 0 (which happens with 1/2 probability). You take the right one when rand2() equals 1 (which happens with 1/2 probability). You continue branching left and right as you continue to call rand2(). When you reach a leaf, you return a result of 1, 2 or 3 (your rand3() results).

  • What’s the probability of taking each branch? 1/2
  • What’s the probability to reach a particular leaf node? 1/2^j (for some j).
  • What the probability of returning 3 (for example)? We could compute this by summing up the probabilities of reaching each leaf node with value 3. Each of these paths has probability 1/2^j, so we know that the total probability of returning 3 must be a series of terms of reciprocal powers of 2 (e g , 1/2^x + 1/2^y + 1/2^z + …).

We also know, however, that the probability of returning 3 must be 1/3 (because rand3() should be perfectly random). Can you find a series of reciprocal powers of 2 that sum to 1/3? No, because 3 and 2 are relatively prime.
We can similarly conclude that to solve this problem, we will need to accept a small (infinitesimally small) chance that this process will repeat forever. That’s ok.
So, how do we solve this?
In order to generate a random number between 1 and 7, we just need to uniformly generate a larger range than we are looking for and then repeatedly sample until we get a number that is good for us. We will generate a base 5 number with two places with two calls to the rand5().

	public static int rand7() {
		while (true) {
			int num = 5 * (rand5() - 1) + (rand5() - 1);
			if (num < 21)
				return (num % 7 + 1);
		}
	}

I personally like this post better: here

	public static int rand7() {
	    int vals[][] = {
	        { 1, 2, 3, 4, 5 },
	        { 6, 7, 1, 2, 3 },
	        { 4, 5, 6, 7, 1 },
	        { 2, 3, 4, 5, 6 },
	        { 7, 0, 0, 0, 0 }
	    };

	    int result = 0;
	    while (result == 0)
	    {
	        int i = rand5();
	        int j = rand5();
	        result = vals[i-1][j-1];
	    }
	    return result;
	}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it’s a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That’s what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don’t get a good result, we keep throwing darts.

Encode XML

Since XML is very verbose, you are given a way of encoding it where each tag gets mapped to a pre-defined integer value The language/grammar is as follows:
Element –> Element Attr* END Element END [aka, encode the element tag, then its attributes, then tack on an END character, then encode its children, then another end tag]
Attr –> Tag Value [assume all values are strings] END –> 01
Tag –> some predefined mapping to int
Value –> string value END
Write code to print the encoded version of an xml element (passed in as string).
FOLLOW UP
Is there anything else you could do to (in many cases) compress this even further?

Solution:

	private Map<String, Byte> tagMap;
	private static final Byte[] END = { 0, 1 };
	private List<String> tokens;
	private int currentTokenIndex;

	byte[] encode(char[] input) throws IOException {
		tokenize(input);
		currentTokenIndex = 0;
		ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
		encodeTokens(outputStream);
		return outputStream.toByteArray();
	}

	void encodeTokens(ByteArrayOutputStream output) throws IOException {
		nextToken("<");
		// read tag name
		String tagName = nextToken();
		output.write(getTagCode(tagName));
		// read attributes
		while (!hasNextToken(">") && !hasNextTokens("/", ">")) { // read next attribute
			String key = nextToken();
			nextToken("=");
			String value = nextToken();
			output.write(getTagCode(key));
			for (char c : value.toCharArray()) {
				output.write(c);
			}
			output.write(END[0]);
			output.write(END[1]);
		}
		// end of attributes
		output.write(END[0]);
		output.write(END[1]);
		// finish this element
		if (hasNextTokens("/", ">")) {
			nextToken("/");
			nextToken(">");
		} else {
			nextToken(">");
			// while not the end tag
			while (!hasNextTokens("<", "/")) {
				encodeTokens(output); // encode child
			}
			// ending tag
			nextToken("<");
			nextToken("/");
			nextToken(tagName);
			nextToken(">");
		}
		output.write(END[0]);
		output.write(END[1]);
	}

Find the frequency of a word in a book

Design a method to find the frequency of occurrences of any given word in a book.

My initial thoughts:
Assume this query would be asked for multiple times. Otherwise, if it’s a one-time thing, we can do no better than scanning through the book. We then need to build a Trie with nodes as character along with its count. When asked for particular word, we search through the tree.

My initial codes:

	public class Node {
		private char c;
		private int count = 1;
		private List<Node> children = new LinkedList<Node>();

		public Node() {

		}

		public Node(char c) {
			this.c = c;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getCount() {
			return count;
		}

		public void setCount(int count) {
			this.count = count;
		}

		public void increaseCount() {
			this.count++;
		}

		public List<Node> getChildren() {
			return children;
		}

		public Node addChild(char c) {
			for (Node node : children) {
				if (node.getC() == c) {
					node.increaseCount();
					return node;
				}
			}
			Node child = new Node(c);
			this.children.add(child);
			return child;
		}

		public Node getChild(char c) {
			for (Node node : children) {
				if (node.getC() == c) {
					return node;
				}
			}
			return null;
		}

		@Override
		public String toString() {
			return "(" + c + ", " + count + ")";
		}
	}

	private Node root = new Node();

	public void buildTree(String[] book) {
		for (String word : book) {
			Node current = root;
			for (int i = 0; i < word.length(); ++i) {
				char c = word.charAt(i);
				current = current.addChild(c);
			}
		}
	}

	public int getFrequency(String word) {
		Node current = root;
		for (int i = 0; i < word.length(); ++i) {
			char c = word.charAt(i);
			current = current.getChild(c);
			if (current == null)
				return 0;
		}
		return current.getCount();
	}

Solution:

	Hashtable<String, Integer> setupDictionary(String[] book) {
		Hashtable<String, Integer> table = new Hashtable<String, Integer>();
		for (String word : book) {
			word = word.toLowerCase();
			if (word.trim() != "") {
				if (!table.containsKey(word))
					table.put(word, 0);
				table.put(word, table.get(word) + 1);
			}
		}
		return table;
	}

	int getFrequency(Hashtable<String, Integer> table, String word) {
		if (table == null || word == null)
			return -1;
		word = word.toLowerCase();
		if (table.containsKey(word)) {
			return table.get(word);
		}
		return 0;
	}

Comments: Error conditions:

  1. Trim and toUpperCase the word before inserting into hashtable.
  2. Error condition for table==null and/or query==null.
  3. toUpperCase the query before searching through hashtable.

Maximum continuous sum problem

You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4})

My initial thoughts:
We need to track two variables: max sum ending at position i and max sum so far. We update maxSumEndHere to zero if adding the current element will make the sum be negative, otherwise we keep track of the maximum sum. We update maxSumSoFar according to maxSumEndHere. We then return maxSumSoFar.
My initial code:

	public static int maxContinousSum(int[] array) {
		int maxSumEndHere = 0;
		int maxSumSoFar = Integer.MIN_VALUE;
		for (int number : array) {
			if (maxSumEndHere + number > 0)
				maxSumEndHere = maxSumEndHere + number;
			else
				maxSumEndHere = 0;
			if (maxSumEndHere > maxSumSoFar)
				maxSumSoFar = maxSumEndHere;
		}
		return maxSumSoFar;
	}

Solution:

	public static int getMaxSum(int[] a) {
		int maxsum = 0;
		int sum = 0;
		for (int i = 0; i < a.length; ++i) {
			sum += a[i];
			if (maxsum < sum) {
				maxsum = sum;
			} else if (sum < 0) {
				sum = 0;
			}
		}
		return maxsum;
	}

The cleanest one:

	public static int maxContinousSum2(int[] A) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int x : A) {
			maxEndingHere = Math.max(x, maxEndingHere + x);
			maxSoFar = Math.max(maxSoFar, maxEndingHere);
		}
		return maxSoFar;
	}

Comments:
All of the above methods assume that if we have an array of all negative numbers, we return sum of zero.

Previous Older Entries