Array of products of all other numbers

Given an array of size , return another resulting array of the same size , where is the products of all numbers in except for .
EXAMPLE:
INPUT: = [1,2,3,4]
OUTPUT: = [24, 12, 8, 6]

My initial thoughts:
We can first compute the products of everything, in the example, this is 1*2*3*4 = 24. Then for each element in the resulting array, we divide the total products by that element in the original array, that is: 24 = 24/1; 12 = 24/2; 8 = 24/3; 6 = 24/4. We need to be careful with the edge cases: where there are zero(s). We cannot divide by zero. Hence, we modify the algorithm. We first compute the products of non-zeros and count the number of zeros in . Then for position in , if , we check if there are at least 2 zeros, if yes, . If not, should be equal to the products of non-zeros. If , we check if there is at least 1 zero, if yes, . Otherwise, is the product of non-zeros divided by $A[i]$.

Codes:

public static long[] getArrayOfProducts(int[] original) {
        int zeroCounts = 0;
        long products = 1;
        for(int number : original) {
            if(number == 0)
                zeroCounts++;
            else
                products *= number;
        }
        
        long[] result = new long[original.length];
        for(int i = 0; i < result.length; ++i) {
            if(original[i] == 0) {
                if(zeroCounts > 1)
                    result[i] = 0;
                else
                    result[i] = products;
            } else if(zeroCounts > 0) {
            	result[i] = 0;
            } else {
                result[i] = products / original[i];
            }
        }
        
        return result;
    }

Better Solution:

According to the post here:
public static long[] getArrayOfProducts2(int[] original) {
    	long[] results = new long[original.length];
    	results[0] = 1;
    	for(int i = 1; i < original.length; ++i) {
    		results[i] = results[i-1]*original[i-1];
    	}
    	
    	long temp = 1;
    	for(int i = results.length - 1; i >= 0; --i) {
    		results[i] *= temp;
    		temp *= original[i];
    	}
    	return results;
    }

Notice:

If the product is too large so that we hit integer/long overflow, we need to handle that, probably by introducing additional variables to store temporary products.
	

Find the kth number with prime factors 3, 5 and 7

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

My initial thoughts:
The -th number can not be larger than . Therefore we can enumerate all the satisfying numbers by iterating the exponent of 3, 5 and 7 from 0 to k. We then sort those numbers and retrieve the kth. Altogether it’s a algorithm.

My initial codes:

	public static int findKthNumber(int k) {
		int top = k;
		List<Integer> data = new ArrayList<Integer>();
		for (int i = 0; i <= top; ++i) {
			for (int j = 0; j <= top; ++j) {
				for (int l = 0; l <= (top + 2 - i - j); ++l) {
					if (l >= 0) {
						int number = (int) (Math.pow(3, i) * Math.pow(5, j) * Math
								.pow(7, l));
						data.add(number);
					}
				}
			}
		}
		Collections.sort(data);
		return data.get(k - 1);
	}

Solution:

Here is the algorithm:

Initialize array magic and queues Q3, Q5 and Q7
Insert 1 into magic.
Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
If x was found in:

Q3 -> append x*3, x*5 and x*7 to Q3, Q5 and Q7. Remove x from Q3.
Q5 -> append x*5 and x*7 to Q5 and Q7. Remove x from Q5.
Q7 -> only append x*7 to Q7. Remove x from Q7.
Note: we do not need to append x*3 and x*5 to all lists because they will already be found in another list.


Repeat steps 4 – 6 until we’ve found k elements.

	public static int getKthMagicNumber(int k) {
		if (k <= 0)
			return 0;
		int val = 1;
		Queue<Integer> Q3 = new LinkedList<Integer>();
		Queue<Integer> Q5 = new LinkedList<Integer>();
		Queue<Integer> Q7 = new LinkedList<Integer>();
		Q3.add(3);
		Q5.add(5);
		Q7.add(7);
		for (--k; k > 0; --k) { // We’ve done one iteration already.
			val = Math.min(Q3.peek().intValue(),
					Math.min(Q5.peek().intValue(), Q7.peek().intValue()));
			if (val == Q7.peek()) {
				Q7.remove();
			} else {
				if (val == Q5.peek()) {
					Q5.remove();
				} else { // must be from Q3
					Q3.remove();
					Q3.add(val * 3);
				}
				Q5.add(val * 5);
			}
			Q7.add(val * 7);
		}
		return val;
	}

	

Find a line which passes the most number of points

Given a two dimensional graph with points on it, find a line which passes the most number of points.

My initial thoughts:
A pair of points forms a line. We can iterate through all pairs and count for how many points are on each line. That is in total a algorithm. Naive algorithm.

My initial codes:

	public class Line {
		private double slope;
		private double intercept;

		private final double THRESHOLD = Math.pow(10, -8);

		public Line(double slope, double intercept) {
			super();
			this.slope = slope;
			this.intercept = intercept;
		}

		public Line(Pair<Double> p1, Pair<Double> p2) {
			this.slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
			this.intercept = (p2.getX() * p1.getY() - p1.getX() * p2.getY())
					/ (p2.getX() - p1.getX());
		}

		public boolean contains(Pair<Double> p) {
			double x = p.getX();
			double y = p.getY();
			return Math.abs(y - (slope * x + intercept)) < THRESHOLD;
		}
	}

	public static Line findLine(Set<Pair<Double>> points) {
		int maxNumber = -Integer.MAX_VALUE;
		int number = 0;
		Line result = null;
		for (Pair<Double> p1 : points) {
			for (Pair<Double> p2 : points) {
				if (!p1.equals(p2)) {
					number = 0;
					Line line = new Line(p1, p2);
					for (Pair<Double> p : points) {
						if (line.contains(p))
							number++;
					}
					if (number > maxNumber) {
						maxNumber = number;
						result = line;
					}

				}
			}
		}
		return result;
	}

Solution:

We have a bunch of line segments, represented as a slope and y-intercept, and we want to find the most common slope and y-intercept. How can we find the most common one? This is really no different than the old “find the most common number in a list of numbers” problem. We just iterate through the lines segments and use a hash table to count the number of times we’ve seen each line.
	public static Line findBestLine(GraphPoint[] points) {
		Line bestLine = null;
		HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();
		for (int i = 0; i < points.length; i++) {
			for (int j = i + 1; j < points.length; j++) {
				Line line = new Line(points[i], points[j]);
				if (!line_count.containsKey(line)) {
					line_count.put(line, 0);
				}
				line_count.put(line, line_count.get(line) + 1);
				if (bestLine == null
						|| line_count.get(line) > line_count.get(bestLine)) {
					bestLine = line;
				}
			}
		}
		return bestLine;
	}

	public class Line {
		private static double epsilon = .0001;
		public double slope;
		public double intercept;
		private boolean infinite_slope = false;

		public Line(GraphPoint p, GraphPoint q) {
			if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
				slope = (p.y - q.y) / (p.x - q.x); // compute slope
				intercept = p.y - slope * p.x; // y intercept from y=mx+b
			} else {
				infinite_slope = true;
				intercept = p.x; // x-intercept, since slope is infinite
			}
		}

		public boolean isEqual(double a, double b) {
			return (Math.abs(a - b) < epsilon);
		}

		@Override
		public int hashCode() {
			int sl = (int) (slope * 1000);
			int in = (int) (intercept * 1000);
			return sl | in;
		}

		@Override
		public boolean equals(Object o) {
			Line l = (Line) o;
			if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
					&& (infinite_slope == l.infinite_slope)) {
				return true;
			}
			return false;
		}
	}


Be careful about the calculation of the slope of a line. The line might be completely vertical. We can keep track of this in a separate flag (infinite_slope). We need to check this condition in the equals method.
Remember that when we perform division to calculate the slope, division is not exact. Therefore, rather than checking to see if two slopes are exactly equal, we need to check if they’re different by greater than epsilon.

	

Find a line to cut two squares in half

Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

My initial thoughts:
The straight line that connects the two centers of the two squares will cut both of them into half.

My initial codes:

	public class Square {
		private double topLeftX;
		private double topLeftY;
		private double edge;

		public Square(double topLeftX, double topLeftY, double edge) {
			super();
			this.topLeftX = topLeftX;
			this.topLeftY = topLeftY;
			this.edge = edge;
		}

		Pair<Double> getCenter() {
			return new Pair<Double>(topLeftX + edge / 2, topLeftY - edge / 2);
		}
	}

	public class Line {
		private double slope;
		private double intercept;

		public Line(double slope, double intercept) {
			super();
			this.slope = slope;
			this.intercept = intercept;
		}
	}

	public static Line getLine(Square a, Square b) {
		Pair<Double> centerA = a.getCenter();
		Pair<Double> centerB = b.getCenter();

		if (centerA.equals(centerB)) {
			return new Line(centerA.getY() / centerA.getX(), 0);
		} else {
			double slope = (centerB.getY() - centerA.getY())
					/ (centerB.getX() - centerA.getX());
			double intercept = (centerB.getX() * centerA.getY() - centerA
					.getX() * centerB.getY())
					/ (centerB.getX() - centerA.getX());
			return new Line(slope, intercept);
		}
	}

Solution:
	public class Square {
		public double left;
		public double top;
		public double bottom;
		public double right;

		public Square(double left, double top, double size) {
			this.left = left;
			this.top = top;
			this.bottom = top + size;
			this.right = left + size;
		}

		public Point middle() {
			return new Point((this.left + this.right) / 2,

			(this.top + this.bottom) / 2);
		}

		public Line cut(Square other) {
			Point middle_s = this.middle();
			Point middle_t = other.middle();
			if (middle_s == middle_t) {
				return new Line(new Point(left, top), new Point(right, bottom));
			} else {
				return new Line(middle_s, middle_t);
			}
		}
	}

			

			
				

Implement *, -, and / operators using only +

Write a method to implement *, – , / operations You should use only the + operator.

My initial thoughts:
a * b can be implemented as adding a for b times.
a – b can be implemented as addition of a and -b.
a / b can be implemented as finding how many times you need to add b, until getting a.

My initial codes:

	public static int multiply(int a, int b) {
		int multiplier = (a < b ? a : b);
		int multiplicant = (multiplier == a ? b : a);
		int result = 0;
		for (int i = 0; i < multiplier; i = i + 1) {
			result = result + multiplicant;
		}
		return result;
	}

	public static int substract(int a, int b) {
		return a + (~b + 1);
	}

	public static int divide(int a, int b) {
		if (a == b)
			return 1;
		int result = 1;
		int mul = b;
		while (mul < a) {
			mul = mul + b;
			result = result + 1;
		}
		return result;
	}

Comments after running:

Two many errors.

Multiplication and division can’t handle negative numbers!
Division can only handle who quotient. For example, 8/3 will yield 3, which is wrong.
Error condition of division: can’t divide by 0.

Revision (Solution):
	public static int negate(int number) {
		return ~number + 1;
	}

	public static int abs(int number) {
		return number < 0 ? negate(number) : number;
	}

	public static int multiply(int a, int b) {
		int multiplier = Math.min(abs(a), abs(b));
		int multiplicant = (multiplier == abs(a) ? abs(b) : abs(a));
		int result = 0;
		for (int i = 0; i < multiplier; i = i + 1) {
			result = result + multiplicant;
		}
		if (abs(a) == a) { // a >= 0
			if (abs(b) == b) // b >= 0
				return result;
			else
				// b < 0;
				return negate(result);
		} else { // a < 0
			if (abs(b) == b) // b >= 0
				return negate(result);
			else
				// b < 0;
				return result;
		}
	}

	public static int substract(int a, int b) {
		return a + negate(b);
	}

	public static int divide(int a, int b) {
		if (b == 0) {
			throw new java.lang.ArithmeticException("Divide by 0.");
		}

		int divident = abs(a);
		int divisor = abs(b);
		int quotient = 0;

		while (divident >= divisor) {
			divident = substract(divident, divisor);
			quotient = quotient + 1;
		}

		if (abs(a) == a) { // a >= 0
			if (abs(b) == b) // b >= 0
				return quotient;
			else
				// b < 0;
				return negate(quotient);
		} else { // a < 0
			if (abs(b) == b) // b >= 0
				return negate(quotient);
			else
				// b < 0;
				return quotient;
		}
	}

	

Determine whether two lines would intersect on a Cartesian plane

Given two lines on a Cartesian plane, determine whether the two lines would intersect.

My initial thoughts:
On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as on a Cartesian plane and the slope is given by . Therefore if for two lines, they will intersect.

Solution:

	public class Line {
		static final double epsilon = 0.000001;
		public double slope;
		public double yintercept;

		public Line(double s, double y) {
			slope = s;
			yintercept = y;
		}

		public boolean intersect(Line line2) {
			return Math.abs(slope - line2.slope) > epsilon
					|| Math.abs(yintercept - line2.yintercept) < epsilon;
		}
	}

Comments:

Two lines can be the same. In that case, we assume they intersects (overlap).
We need to consider the floating system in a computer. Never use == to compare two floating numbers.

	

Probability of collision among ants walking on the sides of a triangle

There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle?
Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.

My initial thoughts:
For each single ant, it can move towards two directions. Denote them as 0 or 1. If two ants are moving towards two different directions (clockwise and counter-clockwise), they will eventually meet. Therefore the only case for not having a collision is 0, 0, 0 for the three ants. There are possible combination of directions. Hence probability to have a collision.
For general case, it’s .

Solution:
I forgot the case 1, 1, 1, which can also avoid collision. Therefore, for three ants, it’s and in general, it’s .

One shot or at least two shorts in three games?

You have a basketball hoop and someone says that you can play 1 of 2 games.
Game #1: You get one shot to make the hoop.
Game #2: You get three shots and you have to make 2 of 3 shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?

My initial thoughts (Solution):
For game #1, you have probability l of winning. For game #2, you can either make 2 shots of 3, with probability , or make all of the three shots, with probability . Therefore, to choose game #1, you need to have: , which gives us .

How many lockers are open after 100 passes of toggles

There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

My initial thoughts (Solutions):
Before the 1st pass, all the lockers are closed. To remain open in the end, the locker must be toggled odd number of times. Let us then think about it: when will closer i be toggled? It depends on the factors of i. For example, if i = 6, since the factors of 6 are 1, 2, 3 and 6. It will be toggled at the 1st, 2nd, 3rd and 6th passes. As a result, it will be closed after 100 passes. Therefore, all the lockers with odd number of factors will be open in the end. What are the numbers with odd number of factors? From cant-remember-name theorem, the number of factors of number is given by . To make this number odd, you must have for any . That is, is even for all . What does that mean? That means n is a perfect number! So, how many perfect numbers are there from 1 to 100? 10 of them. Therefore, after the 100th pass, we will have 10 lockers open.

Drop egg to find the threshold for breaking

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

My initial thoughts:
This is similar as binary search. If we have unlimited number of eggs, we only need 7 () to find N. But we only have 2 eggs. We can then still do binary search until the egg breaks, then do a linear search. Let us assume N = 78. We then do as follows:

1. Drop a egg from level 50. The egg does not break. We then know N is between 51 to 100.
2. Drop the egg from level 75. The egg does not break. We then know N is between 76 to 100.
3. Drop the egg from level 88. The egg breaks. We then know N is between 76 to 87.
4. Drop the egg from level 76. The egg does not break. We then know N is between 77 to 87.
5. Drop the egg from level 77. The egg does not break. We then know N is between 78 to 87.
6. Drop the egg from level 78. The egg break. We then know N is exactly 78.

This works fine for some number. But assume N = 49. The first drop will break the egg. So we know N is between 1 to 49. We then need to drop the second egg for 49 times until we find N = 49.

Solutions:
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.

1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100 X(X+1)/2 = 100 -> X = 14.

Hence, We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.