Secret Google FooBar

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package com.vee.algorithms.problems.foobar;

import org.junit.Test;

public class GooFooCrossings {
	/*
	 * Calculate the number if times > will interact with following <
	 */
	@Test
	public void test() {
		System.out.println(numCrossings("<><--->-><-><-->-"));
	}

	public int numCrossings(String s) {
		char[] a = s.toCharArray();
		int crossings=0;
		int right=0;
		for (int i=0; i<a.length;i++) {
			if (a[i]=='>') right++;
			if (a[i]=='<') crossings+=right;
		}
		return crossings;
	}
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

package com.vee.algorithms.problems.foobar;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Optional;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import org.junit.Assert;
import org.junit.Test;

import com.vee.algorithms.datastructures.TreeNode;
import com.vee.algorithms.util.Tuple;

//FIXME

public class GooFooPostOrderRoot {

	/*
	 * Oh no! Commander Lambda's latest experiment to improve the efficiency of
	 * her LAMBCHOP doomsday device has backfired spectacularly. She had been
	 * improving the structure of the ion flux converter tree, but something
	 * went terribly wrong and the flux chains exploded. Some of the ion flux
	 * converters survived the explosion intact, but others had their position
	 * labels blasted off. She's having her henchmen rebuild the ion flux
	 * converter tree by hand, but you think you can do it much more quickly -
	 * quickly enough, perhaps, to earn a promotion!
	 * 
	 * Flux chains require perfect binary trees, so Lambda's design arranged the
	 * ion flux converters to form one. To label them, she performed a
	 * post-order traversal of the tree of converters and labeled each converter
	 * with the order of that converter in the traversal, starting at 1. For
	 * example, a tree of 7 converters would look like the following:
	 * 
	 *         7
     		 /   \
   		    3      6
  		   /  \   / \
 		  1    2 4   5
	 * 
	 * Write a function answer(h, q) - where 
	 * h is the height of the perfect tree of converters and,
	 * q is a list of positive integers representing different flux converters - 
	 * which returns a list of integers p where each element in p is the label of the converter that
	 * sits on top of the respective converter in q, or -1 if there is no such
	 * converter. 
	 * For example, answer(3, [1, 4, 7]) would return the converters above the converters
	 * at indexes 1, 4, and 7 in a perfect binary tree of height 3, which is [3, 6, -1].
	 * 
	 * The domain of the integer h is 1 <= h <= 30, where 
	 * h = 1 represents a perfect binary tree containing only the root, 
	 * h = 2 represents a perfect binary tree with the root and two leaf nodes, 
	 * h = 3 represents a perfect binary tree with the root, two internal nodes and four leaf nodes (like the example above), 
	 * and so forth. 
	 * The lists q and p contain at least one but no more than 10000 distinct integers, all of which will be between 1 and 2^h-1, inclusive. 
	 * The test cases provided are:
	 * 
	 * Inputs:
	 * (int) h = 3 (int list) q = [7, 3, 5, 1] 
	 * 
	 * Output:
	 * (int list) [-1, 7, 6, 3] 
	 * 
	 * Inputs:
	 * (int) h = 5 (int list) q = [19, 14, 28] 
	 * 
	 * Output:
	 * (int list) [21, 15, 29]
	 */
	@Test
	public void test0() {
		int h = 2;
		int[] q = new int[] {1,2,3,4,5,6,7};
		Map<Integer, Integer> map = new LinkedHashMap<>();
		for (int i=0; i< q.length; i++) {
			map.put(q[i], 0);
		}
		int max = (int) (Math.pow(2, h)-1);
		TreeNode<Integer> node = new TreeNode<>(max);
		build(node, new AtomicInteger(max), h-1, true);
		//node.postorder(node);
		search(node, map);
		System.out.println(map);
	}
	
	private void search(TreeNode<Integer> node, Map<Integer, Integer> map) {
		if(node == null)
			return;
		if (map.containsKey(node.getData()) && map.get(node.getData()) == 0) {
			int parent = node.getParent() == null ? -1 : node.getParent().getData();
			map.put(node.getData(), parent);
		}
		search(node.getLeft(), map);
		search(node.getRight(), map);
	}
	
	private void build(TreeNode<Integer> parent, AtomicInteger val, int height, boolean isRight) {
		if (val.get() == 0 || parent == null) return;
		System.out.println("1. " + val + " " + isRight + " " + height + " " + parent.getData());
		if (height == 0 || 
				parent.getLeft() != null && parent.getRight() != null) {
			return;
		}
		TreeNode<Integer> newNode = new TreeNode<>(val.decrementAndGet());
		parent.setRight(newNode);
		newNode.setParent(parent);
		//System.out.println("2. " + val + " " + "true" + " " + height + " " + parent.getData());
		build(newNode, val, height-1, true);
		//System.out.println("3. " + val + " " + "false" + " " + height + " " + parent.getData());
		newNode = new TreeNode<>(val.decrementAndGet());
		parent.setLeft(newNode);
		newNode.setParent(parent);
		build(newNode, val, height-1, false);
	}
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

package com.vee.algorithms.problems.foobar;

import org.junit.Test;

public class GooFooChecksum {

	/*
	 * You're almost ready to make your move to destroy the LAMBCHOP doomsday
	 * device, but the security checkpoints that guard the underlying systems of
	 * the LAMBCHOP are going to be a problem. You were able to take one down
	 * without tripping any alarms, which is great! Except that as Commander
	 * Lambda's assistant, you've learned that the checkpoints are about to come
	 * under automated review, which means that your sabotage will be discovered
	 * and your cover blown - unless you can trick the automated review system.
	 * 
	 * To trick the system, you'll need to write a program to return the same
	 * security checksum that the guards would have after they would have
	 * checked all the workers through. Fortunately, Commander Lambda's desire
	 * for efficiency won't allow for hours-long lines, so the checkpoint guards
	 * have found ways to quicken the pass-through rate. Instead of checking
	 * each and every worker coming through, the guards instead go over everyone
	 * in line while noting their security IDs, then allow the line to fill back
	 * up. Once they've done that they go over the line again, this time leaving
	 * off the last worker. They continue doing this, leaving off one more
	 * worker from the line each time but recording the security IDs of those
	 * they do check, until they skip the entire line, at which point they XOR
	 * the IDs of all the workers they noted into a checksum and then take off
	 * for lunch. Fortunately, the workers' orderly nature causes them to always
	 * line up in numerical order without any gaps.
	 * 
	 * For example, if the first worker in line has ID 0 and the security
	 * checkpoint line holds three workers, the process would look like this:
	 * 
	 * 	0 1 2 /
		3 4 / 5
		6 / 7 8 
		where the guards' XOR (^) checksum is 0^1^2^3^4^6 == 2.
	 * 
	 * Likewise, if the first worker has ID 17 and the checkpoint holds four
	 * workers, the process would look like:
	 * 
	 * 	17 18 19 20 /
		21 22 23 / 24
		25 26 / 27 28
		29 / 30 31 32 
	 * which produces the checksum 17^18^19^20^21^22^23^25^26^29 == 14.
	 * 
	 * All worker IDs (including the first worker) are between 0 and 2000000000
	 * inclusive, and the checkpoint line will always be at least 1 worker long.
	 * 
	 * With this information, write a function answer(start, length) that will
	 * cover for the missing security checkpoint by outputting the same checksum
	 * the guards would normally submit before lunch. You have just enough time
	 * to find out the ID of the first worker to be checked (start) and the
	 * length of the line (length) before the automatic review occurs, so your
	 * program must generate the proper checksum with just those two values.
	 * 
	 * Test cases
	 * 
	 * Inputs: (int) start = 0 (int) length = 3 Output: (int) 2
	 * 
	 * Inputs: (int) start = 17 (int) length = 4 Output: (int) 14
	 */
	@Test
	public void test() {
		System.out.println(checksum(17, 4)); //returns 14
		System.out.println(checksum(0, 3)); //returns 2
	}

	public int checksum(int start, int length) {
		int ans = 0;
		int j = length;	
		for (int i = 0; i < length; i++) {
			int end = start + --j;
			ans = ans^xor(start-1);
			ans = ans^xor(end);
			start = start+length;
		}
		return ans;
	}
	
	private int xor(int a) {
		int rem = a%4;
		switch (rem) {
			case 0: return a;
			case 1: return 1;
			case 2: return a+1;
			case 3: return 0;
		}
		return 0;
	}
	
	public void test5() {
		int length = 100000;//1651559072
		//2,147,483,647
		long stime = System.currentTimeMillis();
		int start = 17;
		int ans = 0;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length+1; j++) {
				if (i+j < length) {
					ans = ans ^ start++;
				}
				if (i+j == length) {
					start = start + length-j;
					j = length+1;
					continue;
				}
				
			}
			/*if (i%1000 == 0) System.out.println(i);*/
		}
		System.out.println(System.currentTimeMillis()-stime);
		System.out.println(ans);
	}
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

package com.vee.algorithms.problems.foobar;

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Queue;

import org.junit.Test;

import java.util.Map.Entry;

import com.vee.algorithms.datastructures.TreeNode;
import com.vee.algorithms.util.Tuple;

public class GooFooMF {
	/*
	 * You're so close to destroying the LAMBCHOP doomsday device you can taste
	 * it! But in order to do so, you need to deploy special self-replicating
	 * bombs designed for you by the brightest scientists on Bunny Planet. There
	 * are two types: Mach bombs (M) and Facula bombs (F). The bombs, once
	 * released into the LAMBCHOP's inner workings, will automatically deploy to
	 * all the strategic points you've identified and destroy them at the same
	 * time.
	 * 
	 * But there's a few catches. First, the bombs self-replicate via one of two
	 * distinct processes: Every Mach bomb retrieves a sync unit from a Facula
	 * bomb; for every Mach bomb, a Facula bomb is created; Every Facula bomb
	 * spontaneously creates a Mach bomb.
	 * 
	 * For example, if you had 3 Mach bombs and 2 Facula bombs, they could
	 * either produce 3 Mach bombs and 5 Facula bombs, or 5 Mach bombs and 2
	 * Facula bombs. The replication process can be changed each cycle.
	 * 
	 * Second, you need to ensure that you have exactly the right number of Mach
	 * and Facula bombs to destroy the LAMBCHOP device. Too few, and the device
	 * might survive. Too many, and you might overload the mass capacitors and
	 * create a singularity at the heart of the space station - not good!
	 * 
	 * And finally, you were only able to smuggle one of each type of bomb - one
	 * Mach, one Facula - aboard the ship when you arrived, so that's all you
	 * have to start with. (Thus it may be impossible to deploy the bombs to
	 * destroy the LAMBCHOP, but that's not going to stop you from trying!)
	 * 
	 * You need to know how many replication cycles (generations) it will take
	 * to generate the correct amount of bombs to destroy the LAMBCHOP. Write a
	 * function answer(M, F) where M and F are the number of Mach and Facula
	 * bombs needed. Return the fewest number of generations (as a string) that
	 * need to pass before you'll have the exact number of bombs necessary to
	 * destroy the LAMBCHOP, or the string "impossible" if this can't be done! M
	 * and F will be string representations of positive integers no larger than
	 * 10^50. For example, if M = "2" and F = "1", one generation would need to
	 * pass, so the answer would be "1". However, if M = "2" and F = "4", it
	 * would not be possible.
	 */
	@Test
	public void test() {
		String[] a = {"2","4","1", "9","33", "5", "31", "17", "19", "12497125815806718571802751027512057176753465398623"};
		String[] b = {"1","7","1", "6", "5", "21", "74", "3", "23", "1241241240998968792038592859236307678658823642327"};
		for (int i = 0; i<a.length; i++) {
			System.out.println(a[i] +"," + b[i] + "=" + mf(a[i], b[i]));
		}
	}
	
	private String mf(String a, String b) {
		BigInteger m = new BigInteger(a);
		BigInteger f = new BigInteger(b);
		BigInteger steps = BigInteger.ZERO;
		while(!m.subtract(f).abs().equals(BigInteger.ONE) && !m.min(f).equals(BigInteger.ONE)) {
			if (m.remainder(f).equals(BigInteger.ZERO) || m.remainder(f).equals(BigInteger.ZERO)) {
				return "impossible";
			}
			BigInteger step = BigInteger.ZERO;
			//System.out.print(m +"," + f + "=" );
			if (m.compareTo(f) > 0) {
				BigInteger[] sub = m.subtract(f).divideAndRemainder(f);
				step= sub[0].add(sub[1].equals(BigInteger.ZERO) ? BigInteger.ZERO : BigInteger.ONE);
				m= m.subtract(step.multiply(f));
			} else {
				BigInteger[] sub = f.subtract(m).divideAndRemainder(m);
				step= sub[0].add(sub[1].equals(BigInteger.ZERO) ? BigInteger.ZERO : BigInteger.ONE);
				f= f.subtract(step.multiply(m));
			}
			//System.out.println(step);
			steps=steps.add(step);
		}
		if (m.subtract(f).abs().equals(BigInteger.ONE)) {
			steps=steps.add(m.max(f));
		} else if (m.equals(BigInteger.ONE)) {
			steps=steps.add(f);
		} else if (f.equals(BigInteger.ONE)) {
			steps=steps.add(m);
		}
		return steps.subtract(BigInteger.ONE).toString();
	}
	
	//call this function and use the stdout responses to validate the above solution
	private void generateMFSample() {
		int MAX = 4096;
		Tuple<Integer, Integer> t = new Tuple<>(1,1);
		TreeNode<Tuple<Integer, Integer>> node = new TreeNode<>(t);
		int count = 1;
		int newCount = 0;
		Map<Tuple<Integer, Integer>, Integer> map  = new LinkedHashMap<>();
		Queue<TreeNode<Tuple<Integer, Integer>>> q = new ArrayDeque<>();
		q.offer(node);
		int level = 1;
		for (int i = 2; i<MAX; i++) {
			node = q.poll();
			count--;
			Tuple<Integer, Integer> data = node.getData();
			if (!map.containsKey(data)) {
				map.put(data, level);
			}
			TreeNode<Tuple<Integer, Integer>> l = new TreeNode<>(new Tuple<>(data.head+data.tail, data.tail));
			TreeNode<Tuple<Integer, Integer>> r = new TreeNode<>(new Tuple<>(data.head, data.head+ data.tail));
			
			node.setLeft(l);
			node.setRight(r);
			newCount+=2;
			q.offer(l);
			q.offer(r);
			if(count == 0) { //NOTE Trick is to check for zero or empty
				count = newCount;
				newCount = 0;
				level++;
			}
		}
		while(!q.isEmpty()) {
			node = q.poll();
			Tuple<Integer, Integer> data = node.getData();
			if (!map.containsKey(data)) {
				map.put(data, level);
			}
		}
		for (Entry<Tuple<Integer, Integer>, Integer>  e : map.entrySet()) {
			int f = e.getKey().head;
			int s = e.getKey().tail;
			System.out.println(String.format("%d, %d - %d", f,s, e.getValue()));
		}
	}
}