CareerCup

Classic 3-SUM problem.

Also your input is invalid in the 2nd example. N=4 and then you provide only 3 more lines, one of which is supposed to be the result. If N=4 then I would expect 5 more lines.

It becomes an O(n) time loop through the array seeing how many of the powers of 2 we have and then returning how many we need minus that count.

No, his solution doesn't tell you what the list will contain afterwards. His solution says that you can make any number, n in [8,15], using 3+1=4 elements in the array. This is the same size as your given optimal solution. The program would then return 2 because the difference between 4 and size({3,6}) is 2.

For the people asking for code, here is working java code.

public class RobotDitchProblem {
	public static void main(String args[]){
		
		//How long does it take the robot to go from 0 to 10
		//when moving 5 forward and 3 backward every time
		//at 1 time unit per meter
		System.out.println(walkRobot(0,5,3,1,-10,10));
		
		//returns 28 which is correct
	}
	
	
	//returns the time it took to reach a ditch, -1 if it never reaches a ditch.
	//returns 0 if started inside a ditch.
	//Assumes; F and B > 0
	public static int walkRobot(int position, int F, int B, int timePerMeter, int ditchBehind, int ditchFront){
		//Assume everything outside boundary is ditch
		if (position <= ditchBehind) return 0;
		if (position >= ditchFront) return 0;
		
		if (position + F < ditchFront && F == B) return -1; //never reaches a ditch condition
		
		int tempPosition = 0;
		int totalTime = 0;
		
		//one of the two final conditions will be hit inside this loop.
		while ( position > ditchBehind && position < ditchFront){
			//move forward
			tempPosition = position + F;
			if (tempPosition >= ditchFront){  //final condition
				totalTime += ((ditchFront - position) * timePerMeter);
				return totalTime;
			}
			else{
				totalTime += (F * timePerMeter);
				position += F;
			}
			
			//move backward
			tempPosition -= B;
			if (tempPosition <= ditchBehind){  //final condition
				totalTime += ((position - ditchBehind) * timePerMeter);
				return totalTime;
			}
			else{
				totalTime += (B * timePerMeter);
				position -= B;
			}
		}
		return -1;
	}
}

Good catch! This man is correct, everyone. I should have not just been comparing locally, but comparing locally + what has already been calculated. Silly bug on my part. Thanks.

@Aman Mittal: A HashSet is essentially a HashMap without values that are mapped from the key set. HashSet has all of those same access functions and their worst case behavior since it's based on a constant time hash of the object.

Since we're talking about HashSet though which is part of java's util package, I should also note that HashSet is NOT synchronized. So we would need some sort of external locking mechanism in place if this data structure were to be used by multiple processes simultaneously.

Sure, so think about what this algorithm is doing. We are constantly splitting the input in half. The time here is a question of how many times does it take us splitting the input in half to have 1 number remaining (aka 2^0 numbers remaining).

We start with an array of size size = n = 2^k.
Then we split the array in half, size = 2^(k-1)
Then again, size = 2^(k-2)
continue..
until size = 2^0 = 2^(k-k) = 1

It took us K steps to go from 2^K to 2^0. What is K in terms of N?

2^K = N, therefore, K = lg2(N)

What's the point of a linked list here? Why not just use a HashSet and be done with it:

1. Create/Insert -> O(1)
2. Retrieve -> O(1)
3. Update -> O(1)
4. Delete -> O(1)

This is a recursive problem:

Base condition: From the current starting point see if moving F goes into the ditch. Now see if moving F + B goes into the ditch behind us. If none of these end in the ditch then also check the "net movement". ie) if F +B == 0 then you know you will never be in a ditch.

Otherwise, move F + B and then add F + B time to the total time and recurse using your new starting position. Continue until you are in a ditch.

Now, in order to save space on the stack avoid recursion and use a while loop in your code.

Divide the initial array into 4 pieces. One side will have 2 equal parts and the other side will have 2 non-equal parts. Use the equal side to tell the weight of the normal marble. Now binary search the unequal side of the array by splitting the current portion in half and moving to the half that's weight doesn't logically make sense given the normal marble weight. Once you have a single marble selected, that should be the odd one out.

This is an O(lgn) time algorithm and O(1) space.

Here's a solution where the staircase is a 4xN array as follows:

Cost to move up left | cost to move right | cost to move left | cost to move up right
level 1
level 2
..
..

Now, starting from the bottom of the array we hold a size-2 array that denotes the minimum path thus far. This gives us a solution with O(n) time and O(1) space.

public class StairClimber {
	public static void main(String args[]){
		int stairs[][] = {
				{3,5,7,9,10,12,4,6},    //cost of moving up the left side
				{1,1,12,13,14,14,5,6},  //cost of moving to the right
				{4,6,10,10,1,10,9,8},   //cost of moving to the left
				{1,5,7,9,3,12,8,2}      //cost of moving up the right side
		};
		
		System.out.println(minCostPath(stairs));
	}
	
	public static int minCostPath(int stairs[][]){
		int curLevel = 0;
		int costOption = 0;
		int minCostThusFar[] = new int[2];
		
		while (curLevel < stairs[0].length-1){
			
			//Is it better to move up the left side, or move up the right side and go across?
			costOption = stairs[3][curLevel] + stairs[2][curLevel+1];
			if (stairs[0][curLevel] <= costOption){
				minCostThusFar[0] += stairs[0][curLevel];
			}
			else{
				minCostThusFar[0] += costOption;
			}
			
			//Is it better to move up right right side, or move up the left side and go across?
			costOption = stairs[0][curLevel] + stairs[1][curLevel+1];
			if (stairs[3][curLevel] <= costOption ){
				minCostThusFar[1] += stairs[3][curLevel];
			}
			else{
				minCostThusFar[1] += costOption;
			}
			
			curLevel++;
		}
		
		//Of the 2 final solutions, which is the smaller?
		if (minCostThusFar[0] <= minCostThusFar[1]) return minCostThusFar[0];
		else return minCostThusFar[1];
	}
}

The good ole slow O(n*n) time solution.

public static boolean abcSum(int a[], int b[], int c[], int k){
		HashSet<Integer> bcCombos = new HashSet<Integer>();
		for (int i = 0; i < b.length; i++){
			for (int j = 0; j < c.length; j++){
				bcCombos.add(b[i]+c[j]);
			}
		}
		for (int i = 0; i < a.length; i++){
			if (bcCombos.contains(k-a[i])) return true;
		}
		return false;
	}

Why this doesn't work:

A = {10,15,20,25}
B = {3,6}
C = {1,5}
K = 27

Based on your algorithm, we would start at i1=0, i2=0, i3=0. So the current sum is 10 + 3 + 1 = 14
Next lowest element is 5 so i3++. Now our sum is 18.
Next lowest element is 6 so i2++. Now our sum is 21.
Next lowest element is 15 so i1++. Now our sum is 26.
Next lowest element is 20 so i1++. Now our sum is 31.
..

We skipped our value and will not return to it using your algorithm. We will return false when the actual return value should be true. We can get 27 by adding 20 + 6 + 1.

Working java code for anyone who wants it.

Note: this is open to integer overflow as n grows.

public class Pascals {
	public static void main(String args[]){
		int p[] = GetPascals(34);
		for (int i = 0; i < p.length; i++){
			System.out.print(p[i] + " ");
		}
	}
	
	public static int[] GetPascals(int level){
		if (level < 1) return null;
		
		int curRow[] = new int[level];
		int lastRow[] = new int[level];
		
		return recursePascals(level, 1, curRow, lastRow);
	}
	
	private static int[] recursePascals(int level, int curLevel, int curRow[], int lastRow[]){
		int tmp[];
		int sum;
		
		tmp = lastRow;
		lastRow = curRow;
		curRow = tmp;
		
		if (curLevel == 1){
			curRow[0] = 1;
		}
		else if (curLevel == 2){
			curRow[0] = 1;
			curRow[1] = 1;
		}
		else{
			for (int i = 0; i < curLevel/2+1; i++){
				if (i == 0){
					curRow[0] = 1;
					curRow[curLevel-1] = 1;
				}
				else{
					sum = lastRow[i-1] + lastRow[i];
					curRow[i] = sum;
					curRow[curLevel-(i+1)] = sum;
				}
			}
		}
		
		if (level == curLevel) return curRow;
		else return recursePascals(level, curLevel+1, curRow, lastRow);
	}
}