|
BinarySearch |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT extends ComparableT int binarySearch(T[] a, T val)> return binarySearch(a, val, 0, a.length - 1);>}>
if(end
start)
{> return -1;> }
int mid
= (start + end) / 2;
T midVal = a[mid];
if(midVal.compareTo(val) == 0)> {> return mid;> } else
if(midVal.compareTo(val) == -1)
{> start = mid + 1;> }> else
{
end = mid - 1;> }> return binarySearch(a, val, start, end);>} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()
// 0 1 2 3 4 5 6 7 8 9> Integer[] a = {1, 3, 5, 7, 9, 11, 13, 1
5,
17,
19};
> boolean check = binarySearch(a, 1) == 0;> check = binarySearch(a, 15) == 7;> if(!check)>
{
return false;
}> check = binarySearch(a, 10) == -1;> if(!check)> {> return false; > } return
true;
} |
|
FindMin |
Tests |
||
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public static int findMinInRotatedArray(int[] a) // Ret urns
the smallest number in array that has been rotated> // For example - Array {3,4,5,6,1,2}
returns
1
> // Input array was originally sorted in increasing orders> //
Must have O(log n) runtime> // Input array does not have any duplicates
if(a == null)> {> throw new IllegalArgumentException("Bad input");> }> return findMin(a, 0, a.length - 1); >} >private static int findMin(int[] a, int left, int right)> if(left == right)> {
return a[left];
}> if(left right)> {> return a[0];> } int mid
= (left + right) / 2;
if(mid right
&& a[mid] a[mid + 1])
{
return a[mid + 1];> }> if(mid left && a[mid - 1] a[mid])> {> return a[mid];> }
if(a[right] a[mid])
{> return findMin(a, left, mid - 1);> }> else
{
return findMin(a, mid + 1, right);
}>} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass() boolean
check = findMinInRotatedArray(new int[]{3,4,5,6,1,2}) == 1> &&
findMinInRotatedArray(new int[]{4,1,2,3}) == 1> &&
findMinInRotat edArray(new int[]{1,2,3,4,5,6}) == 1;> if(!check)
{
return false;> }> return true; }
|
|
CombinationOfFactors |
Tests |
||
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static Listint[] generate(int n) // Return
all possible combinations of factors of number n> // !6 has factors:> // 2, 2,
2,
2
> // 2, 2, 4> // 2, 8> // 4, 4> Listint[] result = new
ArrayList();> ListInteger current = new ArrayList();>
generate(n, 2, 1, current, result);> return result;>}>
> if(start target || currentProduct target)> {> return;> }
if(currentProduct == target)
{> result.add(current.stream().mapToInt(x -
x).toArray());
return;> }> for(int i = start; i target; ++i) > { if(i
* currentProduct target)
{
break;> }> if(target % i == 0)> {> current.add(i);> generate(target, i, i * currentProduct, current, result);> current.remove(current.size() - 1); }> }>} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Con fluence>static boolean testsPass()
Listint[] result = generate(16);
boolean check = Arrays.equals(new int[] {2, 2, 2, 2}, result.get(0)) &&
>
Arrays.equals(new int[] {2, 2, 4}, result.get(1))
&&
Arrays.equals(new int[] {2, 8}, result.get(2)) &&> Arrays.equals(new
int[]
{4,
4},
result.get(3));> if(!check)> {> return false;> }
return
true;
} |
|
EditDistance |
Tests |
||
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Conflue
nce>static int editDistance(String s1, String s2)
return
editDistance(s1, s2, s1.length(), s2.length());>}
>
>private static int editDistance(String s1,
String s2, int len1, int len2)
> if(len1 == 0)> {
return len2;
}> if(len2 == 0)> {> return len1;> }
if(s1.charAt(len1 - 1) == s2.charAt((len2 - 1)))> {
return editDistance(s1, s2, len1 - 1, len2 - 1);> }
int d1 =
editDistance(s1, s2, len1, len2 - 1);
int
d2 = editDistance(s1, s2, len1 -1, len2);
int d3 = editDistance(s1, s2, len1 -1, len2 - 1);> return 1 + min3(d1, d2, d3);>}
|
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
String s1 =
"sunday";
String s2 =
"saturday";
boolean check =
editDistance(s1, s2) == 3;
if(!check)
{> return false;> }
return
true;
} |
|
EggDrop |
Tests |
||
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static int drop(int topFloor, int eggs)
if(eggs == 1
|| topFloor == 0 || topFloor == 1)
{
return topFloor;> }> int min = Integer.MAX_VALUE;> for(int currentFloor = 1; currentFloor = topFloor; ++ currentFloor)> {> int option1 = drop(currentFloor - 1, eggs - 1);> int option2 = drop(topFloor - currentFloor, eggs);> int max = Math.max(option1, option2);> min = Math.min(min, max + 1);> }> return min; }
|
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
boolean
check = drop(28, 2) == 7;
if(!check) {> return false;> }
return
true;
} |
|
Elevator |
Tests |
||
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static int capacity(int limit, int[] weights)
// We have
an elevator with stated capacity and people with various weights who want to get on.pre
data-role="codeBlock"
data-info="js" class="language-javascript"> // The objective is to maximize capacity without exceeding it.
>
// Example:> // Capacity: 750> // Weights: [420, 200, 150,
780, 350]> // Max: 700 = 200 + 150 + 350> // NOTE:> // 1. Weights array does
not need to be
sorted
> // 2. Same as knapsack problem but easier to understand>
return capacit y(limit, weights, weights.length -
1);
}> > private
static int capacity(int limit, int[] weights, int index)
if(lim it ==
0 || index 0)
{> return 0;> }> if(weights[index] limit)> {
return capacity(limit, weights, index - 1);> }
else
{> int include = weights[index] + capacity(limit - weights[index],
weights, index - 1);
int exclude =
capacity(limit, weights, index - 1);
return Math.max(include, exclude);
} } |
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
boolean
check = capacity(750, new int[] {420, 200, 150, 780, 350}) == 700;> if(!check)
{
return false;> }> check = capacity(800, new int[] {420, 200, 150, 780, 350}) == 780;> if(!check)> {> return false;> } return
true;
} |
|
Fibonacci |
Tests |
||
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int fib(int n)
if(n 0)> {> return -1;> } else
if(n 2)
{> return n;> }> else
{
return fib(n - 1) + fib(n - 2); }>}
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static int fibWithMemoization(int n)
int[] dp =
new int[n + 1];
dp[0] = 0; dp[1] = 1;
return fibWithMemoization(n, dp); }>private static int fibWithMemoization(int n, int[] dp) > if(n 0)> {
return -1;
}> else if(n 2)> {> return n;> } if(dp[n]
== 0)
{> dp[n] = fibWithMemoization(n - 1, dp) + fibWithMemoization(n - 2,
dp);
}> return dp[n];>} |
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
boolean
check = fib(14) == 377;
if(!check) {> return false;> }
check =
fibWithMemoization(14) == 377;
if(!check)
{> return false;> }
return
true;
} |
|
IslandCount |
Tests |
||
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static int countIslands(int[][] grid)
int count =
0;
for(int i = 0; i grid.length; ++i)
{> for(int j = 0; j grid[0].length; ++j)> {
> i f(grid[i][j] == 1)
> {>
count++;> merge(grid, i, j);> }>
}
}
return count;>}>
{> return;> }> grid[x][y] = 0;> merge(grid, x + 1, y);>
merge(grid, x - 1, y);> merge(grid, x, y + 1);> merge(grid, x, y - 1);>}
|
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
int[][] data
= new int[][]{
{1, 1, 0, 1},
{0, 1, 0, 0},> {0, 1, 0, 0},> {1, 0, 1, 1},> {1,
0,
1, 0}> };> boolean check = countIslands(data) == 4;>
if(!check)
{
return false;> }> return true; }
|
|
FloodFill |
Tests |
||
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static void floodFill(int[][] grid, int[] pos, int value)
>/*
Filling
[3,3] with 2 will result in
{0, 0, 0, 1,
0, 0, 0}, {0, 0, 0, 1, 2, 2, 2},
{0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 2, 2, 2},> {0, 0, 1, 0, 0, 0, 0}, {0,
0,
1,
2,
2,
2,
2},> {1, 1, 0, 0, 0, 1, 1}, {1, 1, 2, 2, 2, 1, 1},> {0, 0,
0, 0, 1, 0, 0}, {2, 2, 2, 2, 1, 0,
0},
{0, 0, 0, 1, 0, 0, 0}, {2, 2,
2, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0,
0}, {2, 2, 2, 1, 0, 0, 0},
*/ int originalVal = grid[pos[0]][pos[1]]; floodFill(grid, pos[0], pos[1], originalVal,
value);
}>static private void floodFill(int[][] grid, int x, int y, int fromVal, int toVal) > if(x 0 || x = grid.length || y 0 || y = grid[0].length || grid[x][y] != fromVal) {> return;> }> grid[x][y] = toVal;> floodFill(grid, x + 1, y,
fromVal, toVal);> floodFill(grid, x - 1, y, fromVal, toVal);> floodFill(grid, x, y + 1, fromVal,
toVal);> floodFill(grid, x, y - 1, fromVal, toVal);>}
|
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
int[][] data
= {
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},> {0, 0, 1, 0, 0, 0, 0},> {1, 1, 0, 0, 0, 1,
1},> {0, 0, 0, 0, 1, 0, 0},> {0, 0, 0, 1, 0, 0, 0},> {0, 0, 0, 1,
0,
0, 0},> };> floodFill(data, new int[] {3, 3}, 2);
> int[][] expected = {> {0, 0, 0, 1, 2, 2, 2},> {0, 0, 0, 1, 2, 2, 2},
> {0, 0, 1, 2, 2, 2, 2},> {1, 1, 2, 2, 2, 1, 1},> {2, 2, 2, 2, 1, 0, 0},
> {2, 2, 2, 1, 0, 0, 0},> {2, 2, 2, 1, 0, 0, 0},> };
for(int
i = 0; i expected.length; ++i)
{
int[] a1 = expected[i];> int[] a2 = data[i];> if(!Arrays.equals(a1, a2)) > {> return false;> } }
return true;>} |
|
Game Strategy |
Tests |
||
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>Consider a row of n coins of values v1 . . . vn, where n is even.>We play a game against an opponent by alternating turns.>In each turn, a player selects either the first or last coin from the row, removes it from the row permanently,>and receives the value of the coin.>Determine the maximum possible amount of money we can definitely win if we move first. Examples:>5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)>8, 15, 3, 7 : The user collects maximum value as 22(7 + 15) Two strategies:>1. User chooses left coin, opponent chooses left or right User collects: Vi + min(F(i+2,j),
F(i+1, j-1))
2. User chooses right coin,
opponent chooses left or right
User
collects: Vj + min(F(i+1, j-1), F(i, j-2))>Why:
If I take
Vi, the opponent can choose either Vi+1 or Vj leaving me the choice of:> If the opponent
takes
Vi+1,
I
have a choice of: Vi+2 or Vj> If the opponent takes Vj, I have a choice of: Vi+1
or Vj-1
If I take Vj, the opponent can
choose wither Vi or Vj-1
If the opponent
takes Vi, I have a choice of: Vi+1 or Vj-1
If the opponent takes Vj-1, I have a choice of Vi ot Vj-2
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static int optimalStrategy(int[] coins)
return
optimalStrategy(coins, 0, coins.length - 1);
}
>static private int optimalStrategy(int[] coins, int left, int right)> if(left == right)> {
return coins[left];
}> if(left + 1 == right)> {> return Math.max(coins[left], coins[right]);> }> int leftMin = Math.min(optimalStrategy(coins, left + 2, right), > optimalStrategy(coins, left + 1, right - 1)); int rightMin =
Math.min(optimalStrategy(coins, left + 1, right - 1), > optimalStrategy(coins, left,
right
-
2));
> return Math.max(coins[left] + leftMin, coins[right] + rightMin);>}
|
data-syntaxhig hlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
boolean
check =
optimalStrategy(new int[]
{5, 3, 7, 10}) == 15 &&
optimalStrategy(new int[] {8, 15, 3, 7}) == 22;> if(!check)
{
return false;> }> return true; }
|
|
HanoiTower |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>public class HanoiTower
private
StackInteger disks = new Stack();> static HanoiTower[] init()> {
HanoiTower[] towers = new HanoiTower[3];> for(int i = 0; i 3; ++i)> {
> towers[i] = new HanoiTower();> }
for(int i = 2; i = 0; --i)
{
towers[0].disks.push(i);> }> return towers;> } private
void moveTo(HanoiTower dest)
{> dest.disks.push(disks.pop());> }> private void moveDisks(int n,
HanoiTower dest, HanoiTower buffer)> {> if(n 0)> {
> moveDisks(n - 1, buffer, dest);> moveTo(dest);> buffer.moveDisks(n -
1,
dest, this);> }> }
static HanoiTower[] play() {> HanoiTower[] towers = init();> towers[0].moveDisks(3, towers[1], towers[2]);
return towers;> }>} |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
data-theme=Confluence>static boolean testsPass()
HanoiTower[]
towers = play();
boolean check =
towers[0].disks.size() == 0 && > towers[1].disks.size() == 3 &&
towers[2].disks.size() == 0;> if(!check)> {> return false;> }
return
true;
} |
Josephus
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>There are n people standing in a circle waiting to be executed.>The counting begins at some point in the circle and proceeds around the circle in a fixed direction.In each step, a certain number of people are skipped and the next person is executed.>The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed),until only the last person remains, who is given freedom.>Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed.The task is to choose the place in the initial circle so that you are the last one remaining and so survive.data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int josephus(int n, int k)if(n == 1){> return 1;> }else{> return (josephus(n - 1, k) + k - 1) % n + 1;> }>}boolean check = josephus(5, 2) == 3;if(!check){> return false;> }return true;}
KnightTour
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class KnightTour// backtrackingprivate static int SIZE = 8;private static int[][] solution = new int[SIZE][SIZE];private static int[] X_MOVES = {2, 1, -1, -2, -2, -1, 1, 2};private static int[] Y_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};> static{for(int i = 0; i SIZE; ++i){> Arrays.fill(solution[i], -1);> }> }> }private static boolean isSafe(int x, int y){> return x =0 && x solution.length && y = 0 && y solution[0].length && solution[x][y] == -1;> solution[7][7] = 0;> return solve(7, 7, 1);> }static boolean solve()> {> {private static boolean solve(int x, int y, int move){> if(move == SIZE * SIZE)return true;}> > for(int i = 0; i SIZE; ++i) > {> int nextX = x + X_MOVES[i];> int nextY = y + Y_MOVES[i]; >if(isSafe(nextX, nextY)){solution[nextX][nextY] = move;if(solve(nextX, nextY, move + 1)){> return true;> }> solution[nextX][nextY] = -1;> }> }return false;}> > private static void printSolution() > {for(int x = 0; x solution.length; ++x)> {> for(int y = 0; y solution[0].length; ++y)> {> System.out.print(String.format( " %2d ", solution[x][y]));}> System.out.println("\n");> }> }}boolean check = solve();if(!check)> {> return false;> }else{> printSolution();> }return true;}
LinkedList
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT extends ComparableT List.NodeT reverse(List.NodeT head)> if(head == null || head.next == null)> {> return head;> }List.NodeT second = head.next;List.NodeT result = reverse(second);> head.next = null;> second.next = head; > returnresult;>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public staticT extends ComparableT List.NodeT nthToLast(List.NodeT head, int k)> return nthToLast(head, k, new IntWrapper());>}>private static class IntWrapper {int value = 0;}> >private staticT extends ComparableT List.NodeT nthToLast(List.NodeT head, int k, IntWrapper i)if(head == null){> return null;> }List.NodeT priorListNode = nthToLast(head.next, k, i);> i.value++;if(i.value == k){> return head;> }> return priorListNode;>}ListInteger list = new List();> list.add(1, 2, 3, 4, 5);> List.NodeInteger reversed = reverse(list.head);> List.NodeInteger[] arr = toArray(reversed); > int[] a = Arrays.stream(arr).mapToInt(x - x.data).toArray();boolean check = Arrays.equals(new int[] {5, 4, 3, 2, 1}, a);> if(!check){return false;> }> list = new List();> list.add(1, 2, 3, 4, 5, 6, 7);> List.NodeInteger n = nthToLast(list.head, 2);pre data-role="codeBlock" data-info="js" class="language-javascript"> check = n.data == 6;> if(!check){return false;> }> return true;}
MakeChange
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int makeChangeWithLeastNumberOfCoins(int initialAmount, int[] denoms)> return makeChangeWithLeastNumberOfCoins(initialAmount, denoms, 0);>}>private static int makeChangeWithLeastNumberOfCoins(int amountRemaining, int[] denoms, int coins)if(amountRemaining == 0){> return coins;> }> for(int i = denoms.length - 1; i = 0; --i)pre data-role="codeBlock" data-info="js" class="language-javascript"> {> if(amountRemaining denoms[i])> { > coins += amountRemaining / denoms[i];> amountRemaining %= denoms[i];> break;> }}return makeChangeWithLeastNumberOfCoins(amountRemaining, denoms, coins);>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int numberOfWaysToMakeChange(int amount, int denom)> // Note: assuming 25, 10, 5, 1 denominationspre data-role="codeBlock" data-info="js" class="language-javascript"> int nextDenom = 0;> switch(denom)> {case 25:nextDenom = 10;> break;> case 10:> nextDenom = 5; > break; > case 5:> nextDenom = 1;> break;> case 1: > return 1;> }int ways = 0;for(int i = 0; i * denom = amount; ++i){> ways += numberOfWaysToMakeChange(amount - i * denom, nextDenom);}> return ways;>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int numberOfWaysToMakeChangeAnyDenom(int amount, int[] denoms)> return numberOfWaysToMakeChangeAnyDenom(amount, denoms, denoms.length - 1);>}>private static int numberOfWaysToMakeChangeAnyDenom(int amount, int[] denoms, int index)if(amount 0 || index 0){> return 0;> }> if(amount == 0)> {return 1;}> return numberOfWaysToMakeChangeAnyDenom(amount, denoms, index - 1) +numberOfWaysToMakeChangeAnyDenom(amount - denoms[index], denoms, index);pre data-role="codeBlock" data-info="js" class="language-javascript">}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static Listint[] numberOfWaysToMakeChangeAndPrint(int amount, int[] denoms)> Listint[] result = new ArrayList();> String s = "";> numberOfWaysToMakeChangeAndPrint(amount, denoms, denoms.length - 1, result, s);> return result;pre data-role="codeBlock" data-info="js" class="language-javascript">}>private static void numberOfWaysToMakeChangeAndPrint(int amount, int[] denoms, int index, Listint[] result, String s)> // Note: order of recursive calls is important> if(amount 0 || index 0)> {> return;> }if(amount == 0){> String[] parts = s.split(",");int[] vals = Arrays.stream(parts).mapToInt(Integer::valueOf).toArray();> result.add(vals); > return; > }numberOfWaysToMakeChangeAndPrint(amount, denoms, index - 1, result, s);> s += denoms[index] + ",";> numberOfWaysToMakeChangeAndPrint(amount - denoms[index], denoms, index, result, s);}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()boolean check = makeChangeWithLeastNumberOfCoins(99, new int[] {1, 5, 10}) == 14;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){return false;> }> check = numberOfWaysToMakeChange(100, 25) == 242;> if(!check)> {return false;}> check = numberOfWaysToMakeChangeAnyDenom(5, new int[] {1, 2, 3}) == 5;if(!check)> {> return false;> }Listint[] result = numberOfWaysToMakeChangeAndPrint(5, new int[] {1, 2, 3});pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new int[] {1, 1, 1, 1, 1}, result.get(0)) &&Arrays.equals(new int[] {2, 1, 1, 1}, result.get(1)) &&> Arrays.equals(new int[] {2, 2, 1}, result.get(2)) &&> Arrays.equals(new int[] {3, 1, 1}, result.get(3)) &&Arrays.equals(new int[] {3, 2}, result.get(4));> if(!check){return false;> }> return true;}
Maze
Tests
private static boolean solve(int x, int y, int[][] maze, int[][] solution){> if(x == maze.length - 1 && y == maze[0].length - 1){> solution[x][y] = 1;> return true;> }>if(isValid(maze, x, y)){> solution[x][y] = 1;> if(solve(x + 1, y, maze, solution)){> return true;> }> if(solve(x, y + 1, maze, solution))> {> return true;> } > solution[x][y] = 0;> }return false;}> > private static boolean isValid(int[][] maze, int x, int y)> {> return x = 0 && x maze.length && y = 0 && y maze[0].length && maze[x][y] == 1;> }> for(int x = 0; x solution.length; ++x)> {> for(int y = 0; y solution[0].length; ++y) > {> System.out.print(String.format( " %2d ", solution[x][y]));> private static void printSolution(int[][] solution)> {}> System.out.println("\n");> }> }}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()int[][] data = new int [][] {{1, 1, 0, 1},{0, 1, 0, 0},> {0, 1, 1, 0},> {0, 0, 1, 1},> {0, 0, 0, 1}> };> int[][] solution = solve(data);> boolean check = solution[solution.length - 1][solution[0].length - 1] == 1;> if(!check)> {> return false; > }check = Arrays.equals(new int[] {1, 1, 0, 0}, solution[0]) &&> Arrays.equals(new int[] {0, 1, 0, 0}, solution[1]) &&> Arrays.equals(new int[] {0, 1, 1, 0}, solution[2]) &&Arrays.equals(new int[] {0, 0, 1, 1}, solution[3]) &&> Arrays.equals(new int[] {0, 0, 0, 1}, solution[4]);> if(!check)> {> return false;> }printSolution(solution);return true;}
NSum
Tests
private static Listint[] generate(int target, int[] sortedVals,> int index, int sumOnStack, StackInteger stack, > Listint[] result) > if(sumOnStack == target)> {result.add(stack.stream().mapToInt(x - x).toArray());> }for(int i = index; i sortedVals.length; ++i){if(sumOnStack + sortedVals[i] = target){> stack.push(sortedVals[i]);> sumOnStack += sortedVals[i]; > generate(target, sortedVals, i + 1, sumOnStack, stack, result);sumOnStack -= stack.pop();}> }> return result;>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()Listint[] result = generate(15, new int[] {6, 1, 8, 5, 3, 15, 4});pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = result.size() == 5;> if(!check){return false;> }> check = Arrays.equals(new int[] {1, 3, 5, 6}, result.get(0)) &&> Arrays.equals(new int[] {1, 6, 8}, result.get(1)) &&Arrays.equals(new int[] {3, 4, 8}, result.get(2)) &&> Arrays.equals(new int[] {4, 5, 6}, result.get(3)) &&> Arrays.equals(new int[] {15}, result.get(4));if(!check)> {> return false;> }return true;}
NumericOperations
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public static int gcd(int a, int b)if(b == 0){> return a;> }return gcd(b, a % b);}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int add(int a, int b)if(b == 0){> return a;> }int sum = a ^ b;int carry = (a & b) 1;return add(sum, carry);>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int multiply(int a, int b)if(b == 0) return 0;if(b % 2 == 0)> {> return multiply(a + a, b / 2); > }else{> return multiply(a + a, b / 2) + a;> }>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int exponent(int a, int b)if(b == 0){> return 1;> }if(b % 2 == 0){> return exponent(a * a, b / 2);> }> else{return exponent(a * a, b / 2) * a;}>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static String toBinary(int n, StringBuilder sb)if(n == 0){> return "";> }toBinary(n / 2, sb);sb.append(n % 2);return sb.toString();>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()boolean check = gcd(8, 36) == 4;if(!check){> return false;> }check = add(159, 37) == 196;if(!check)> {> return false;> }check = multiply(12, 19) == 228;if(!check){> return false;> }check = exponent(2, 10) == 1024;if(!check){> return false;> }check = toBinary(55, new StringBuilder()).equals("110111");> if(!check){return false;> }> return true;}
Palindrome
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean stringPalindrome(String s)if(s.length() 2){> return true;> }> if(s.charAt(0) != s.charAt(s.length() - 1))pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }return stringPalindrome(s.substring(1, s.length() - 1));>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()String s1 = "abcddcba", s2 = "abcdcba", s3 = "abcdba";pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = stringPalindrome(s1) && stringPalindrome(s2) && !stringPalindrome(s3);if(!check)> {> return false;> }return true;}
PhoneNumbers
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class PhoneNumbersstatic int[][] MOVES = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};> > static int countPhoneNumbersWithKnight(int numDigits, int currentNum, int move)> {> if(move == numDigits)> {> return 1;> }> for(int i = 0; i num; ++i)> {> sum += countPhoneNumbersWithKnight(numDigits, MOVES[currentNum][i], move + 1);static ListString keepPhoneNumbersWithKnight(int numDigits, int currentNum, int move)> {ListString result = new ArrayList();> StringBuilder sb = new StringBuilder(); pre data-role="codeBlock" data-info="js" class="language-javascript"> keepPhoneNumbersWithKnight(numDigits, currentNum, move, result, sb);return result;> }>private static void keepPhoneNumbersWithKnight(int numDigits, int currentNum,> int move, ListString result, StringBuilder sb){> if(move == numDigits)> {> result.add(sb.toString()); > return;> }> sb.append(MOVES[currentNum][i]); > keepPhoneNumbersWithKnight(numDigits, MOVES[currentNum][i], move + 1, result, sb);int num = MOVES[currentNum].length;for(int i = 0; i num; ++i){> sb.delete(move, sb.length());}> }>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()boolean check = countPhoneNumbersWithKnight(10,0, 0) == 4608;> if(!check){return false;> }> check = countPhoneNumbersWithKnight(2,0, 0) == 6;> if(!check)> {return false;}> ListString result = keepPhoneNumbersWithKnight(2, 0, 0);check = result.size() == 6;if(!check)> {> return false;> }check = result.get(0).equals("40") && result.get(1).equals("43") && result.get(2).equals("49")> && result.get(3).equals("61") && result.get(4).equals("67") && result.get(5).equals("60");> if(!check)> {return false;}> return true;>}
PlaceQueens
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class PlaceQueens// backtrackingprivate static int SIZE = 8;private static int[][] solution = new int[SIZE][SIZE];> static boolean solve()> {> return solve(0);> }> if(col = SIZE)> { > return true;> }static private boolean solve(int col)> {> {> solution[row][col] = 1; > if(solve(col + 1))> {> return true; > }> solution[row][col] = 0;> }> }for(int row = 0; row SIZE; ++row){> if(isSafe(row, col))return false;}> > private static boolean isSafe(int x, int y)> {> if(x 0 || x = SIZE || y 0 || y = SIZE) > {> return false;> }> {> return false; > } > if(solution[i][y] == 1)> {> return false;> } > for(int j = 0; j SIZE; ++j)> {> if(solution[i][j] == 1 && Math.abs(i - x) == Math.abs(j - y))for(int i = 0; i SIZE; ++i){> if(solution[x][i] == 1){> return false;> }> } > }return true;}> > private static void printSolution() > {for(int x = 0; x SIZE; ++x){for(int y = 0; y SIZE; ++y){> System.out.print(String.format( " %2d ", solution[x][y]));}> System.out.println("\n");}> }>}if(solve()){> printSolution();> }else{> System.out.println("Solution does not exist");> } >}
PowerSet
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static ListListCharacter generate(String s)> ListCharacter chars = s.chars().mapToObj(c - (char)c).collect(Collectors.toList());return generate(chars);}> >private static ListListCharacter generate(ListCharacter input) > ListListCharacter result = new ArrayList();> if(input.isEmpty()) > {> result.add(new ArrayList());> return result;> }Character first = input.get(0);ListCharacter rem = input.subList(1, input.size());> for(ListCharacter sub : generate(rem))> {> ListCharacter list = new ArrayList(); > list.add(first);> list.addAll(sub);> > result.add(list);> result.add(sub);> }return result;}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()ListListCharacter result = generate("ABC");> boolean check = result.size() == 8; > if(!check){return false;> }> char[] a = result.get(0).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();> check = Arrays.equals(new char[] {'A', 'B', 'C'}, a);> if(!check)> {> return false;> }a = result.get(1).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'B', 'C'}, a);> if(!check) > {> return false;> }a = result.get(2).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'A', 'C'}, a);> if(!check) > {> return false;> }a = result.get(3).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'C'}, a);> if(!check) pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }a = result.get(4).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'A', 'B'}, a);> if(!check) > {> return false;> }a = result.get(5).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'B'}, a);> if(!check) pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }a = result.get(6).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[] {'A'}, a);> if(!check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {> return false;> }a = result.get(7).stream().map(Object::toString).collect(Collectors.joining()).toCharArray();pre data-role="codeBlock" data-info="js" class="language-javascript"> check = Arrays.equals(new char[0], a);> if(!check)> {return false;}> return true;>}
RemoveAdjacentDups
Tests
if(s.length() == 1){> return s;> }> if(s.charAt(0) == s.charAt(1))> {return removeAdjacentDups(s.substring(1));}else> {> return s.charAt(0) + removeAdjacentDups(s.substring(1)); > }>}boolean check = removeAdjacentDups("aaabbbbcccb").equals("abcb");> if(!check) > {return false;}> return true;>}
ReverseStack
Tests
if(!s.isEmpty()){> T t = s.pop();> reverse(s);> insertAtBottom(s, t);> }}> >private staticT void insertAtBottom(StackT s, T val)if(s.isEmpty()){> s.push(val);> }> else{T temp = s.pop();> insertAtBottom(s, val);> s.push(temp);pre data-role="codeBlock" data-info="js" class="language-javascript"> }>}return true;}
RodCutting
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>Consider a rod which can be cut into multiple pieces and corresponding price for each piece.For example:> Rod is 4 ft long with following prices> Length: 1 2 3 4> Price: 2 4 8 9> Compute max amount that could be made from cutting/or not curring this rod> Lengths Pricepre data-role="codeBlock" data-info="js" class="language-javascript"> -----------------> 4 9> 1,1,1,1 8> 2,2 8> 1,3 10Try passing prices.length - 1
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int maxValue(int[] prices)return maxValue(prices, prices.length);}> >private static int maxValue(int[] prices, int n)int max = Integer.MIN_VALUE;for(int i = 0; i n; ++i){> max = Math.max(max, prices[i] + maxValue(prices, n - i - 1));}> return max;}boolean check = maxValue(new int[] {2, 4, 8, 9}) == 10;> if(!check){return false;> }> check = maxValue(new int[] {2, 4, 8, 11}) == 11;> if(!check)> {return false;}> return true;>}
StairWalk
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int countWays(int stairs)if(stairs 0) return 0;if(stairs == 0) return 1;return countWays(stairs - 1) +countWays(stairs - 2) +> countWays(stairs - 3);>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int countWaysWithMemoization(int stairs)if(stairs 0){> return 0;> }if(stairs == 1){> return 1;> }> int [] dp = new int[stairs + 1];> dp[0] = 1;dp[1] = 1;dp[2] = 2;> return countWaysWithMemoization(stairs, dp);}>> dp[n] = countWaysWithMemoization(n - 1, dp) + > countWaysWithMemoization(n - 2, dp) + > countWaysWithMemoization(n - 3, dp);private static int countWaysWithMemoization(int n, int[] dp)data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()boolean check = countWays(0) == 1;if(!check){> return false;> }check = countWays(1) == 1;if(!check)> {> return false;> }check = countWays(2) == 2;if(!check)> {> return false;> }check = countWays(3) == 4;if(!check)> {> return false;> }check = countWays(10) == 274;if(!check)> {> return false;> }check = countWaysWithMemoization(10) == 274;if(!check){> return false;> }> return true;}
StringPermutations
Tests
char firstChar = s.charAt(0);String rem = s.substring(1);for(String word : stringPermutations(rem)){> for(int i = 0; i = word.length(); ++i){> String p = insertAtChar(word, firstChar, i); > result.add(p);> }> }> }else{> result.add(s);> }return result;}> >private static String insertAtChar(String s, char c, int i)String start = s.substring(0, i);String end = s.substring(i);return start + c + end;}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()String test = "ABC";ListString perms = stringPermutations(test);boolean check = perms.size() == 6;if(!check){> return false;> }check = perms.contains("ABC") && perms.contains("ACB") && perms.contains("BAC") &&perms.contains("BCA") && perms.contains("CAB") && perms.contains("CBA");if(!check)> {> return false;> }return true;}
StringWildMatch
Tests
while(pattern.length() 0){> if(pattern.charAt(0) == '?')> {> if(s.length() == 0) > {> return false;> }> s = s.substring(1); > pattern = pattern.substring(1);> }else if(pattern.charAt(0) == '*'){if(wildMatch(s, pattern.substring(1))){> return true;> }> if(s.length() 0 && wildMatch(s.substring(1), pattern)){> return true;> }> return false;> }else{> if(s.length() == 0 || s.charAt(0) != pattern.charAt(0)) > {> return false;> }> s = s.substring(1);> pattern = pattern.substring(1);> }}return s.length() == pattern.length();}boolean check = wildMatch("Good Morning", "*d*");> if(!check){return false;> }> check = wildMatch("Good Morning", "*ing");> if(!check)> {> return false;> }check = wildMatch("Good Morning", "Goo*ing");> if(!check){return false;> }> check = !wildMatch("Good Morning", "Good *x");> if(!check)> {> return false;> }return true;}
Subsequence
Tests
static private String longestSubsequence(char[] a1, char[] a2, int len1, int len2)> if(len1 == 0 || len2 == 0)> {return "";}> if(a1[len1 - 1] == a2[len2 - 1])> {> return longestSubsequence(a1, a2, len1 - 1, len2 - 1) + a1[len1 - 1];> }> else{String s1 = longestSubsequence(a1, a2, len1 - 1, len2);String s2 = longestSubsequence(a1, a2, len1, len2 - 1);return s1.length() s2.length() ? s1 : s2;> }}String s1 = "abcdefg", s2 = "acefxyz";> boolean check = longestSubsequence(s1, s2).equals("acef");> if(!check)> {> return false;> }return true;}
Sudoku
Tests
return true;}> > boolean isValid(int row, int col, Integer val)> {> for(int i = 0; i 9; ++i)> { > if(board[i][col] != null && board[i][col] == val)> {pre data-role="codeBlock" data-info="js" class="language-javascript"> return false;> }> if(board[row][i] != null && board[row][i] == val)> {> return false; > }>int boxRowIdx = 3 * (row / 3) + i / 3;> int boxColIdx = 3 * (col / 3) + i % 3; pre data-role="codeBlock" data-info="js" class="language-javascript"> if(board[boxRowIdx][boxColIdx] != null && board[boxRowIdx][boxColIdx] == val)> {> return false;> } > }return true;}> > private static void printSolution() > {for(int i = 0; i board.length; ++i)> {> for(int j = 0; j board[0].length; ++j)> {> System.out.print(String.format(" %2d ", board[i][j]));> }> System.out.println("\n");> } > }}Integer[][] board = new Integer[][] {{ 5, 3, null, null, 7, null, null, null, null},> { 6, null, null, 1, 9, 5, null, null, null},> {null, 9, 8, null, null, null, null, 6, null},{ 8, null, null, null, 6, null, null, null, 3},> { 4, null, null, 8, null, 3, null, null, 1},> { 7, null, null, null, 2, null, null, null, 6},{null, 6, null, null, null, null, 2, 8, null},> {null, null, null, 4, 1, 9, null, null, 5}, > {null, null, null, null, 8, null, null, 7, 9}};> Sudoku sudoku = new Sudoku(board);> if(sudoku.solve())> {> printSolution();> }else{> System.out.println("Solution does not exist.");> } >}
TravellingSalesman
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class TravellingSalesman/*> Let's consider 4 points: A, B, C, D> Distances between these points may be represented by a 2-D array:A B C DA: {0, 20, 42, 25}> B: {20, 0, 30, 34}> C: {42, 30, 0, 10}> D: {25, 34, 10, 0}> Thus:> A - B = 20, A - C = 42, A - D = 25> B - A = 20, B - C = 30, B - D = 34> C - A = 42, C - B = 30, C - D = 10D - A = 25, D - B = 34, D - C = 10*/> > static int VISITED_ALL;> static int[][] MATRIX;>static int tsp(int[][] martix){> VISITED_ALL = (1 martix.length) - 1;MATRIX = martix;> return tsp(1, 0);> }>private static int tsp(int mask, int pos){if(mask == VISITED_ALL)> {> return MATRIX[pos][0]; > }{> if((mask & (1 city)) == 0) // city not yet visited{> int ans = MATRIX[pos][city] + tsp(mask | (1 city), city);min = Math.min(min, ans);}}> return min;> }}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()int[][] data1 = {{0, 20, 42, 25},{20, 0, 30, 34},> {42, 30, 0, 10},> {25, 34, 10, 0}> }; > boolean check = tsp(data1) == 85; > if(!check){return false;> }> int[][] data2 = {> {0, 12, 10, 19, 8},> {12, 0, 3, 7, 2},> {10, 3, 0, 6, 20},> {19, 7, 6, 0, 4},> { 8, 2, 20, 4, 0},> };check = tsp(data2) == 32;if(!check)> {> return false;> }int[][] data3 = {{0, 29, 82, 46, 68, 52, 72, 42},{29, 0, 55, 46, 42, 43, 43, 23},{82, 55, 0, 68, 46, 55, 23, 43},{46, 46, 68, 0, 82, 15, 72, 31},{68, 42, 46, 82, 0, 74, 23, 52},{52, 43, 55, 15, 74, 0, 61, 23},{72, 43, 23, 72, 23, 61, 0, 42},{42, 23, 43, 31, 52, 23, 42, 0}};> check = tsp(data3) == 244;> if(!check){return false;> }> int[][] data4 = {> {0, 29, 82, 46, 68, 52, 72, 42, 51, 55, 29, 74, 23, 72, 46},> {29, 0, 55, 46, 42, 43, 43, 23, 23, 31, 41, 51, 11, 52, 21},{82, 55, 0, 68, 46, 55, 23, 43, 41, 29, 79, 21, 64, 31, 51},> {46, 46, 68, 0, 82, 15, 72, 31, 62, 42, 21, 51, 51, 43, 64},> {68, 42, 46, 82, 0, 74, 23, 52, 21, 46, 82, 58, 46, 65, 23},{52, 43, 55, 15, 74, 0, 61, 23, 55, 31, 33, 37, 51, 29, 59},> {72, 43, 23, 72, 23, 61, 0, 42, 23, 31, 77, 37, 51, 46, 33},> {42, 23, 43, 31, 52, 23, 42, 0, 33, 15, 37, 33, 33, 31, 37},{51, 23, 41, 62, 21, 55, 23, 33, 0, 29, 62, 46, 29, 51, 11},> {55, 31, 29, 42, 46, 31, 31, 15, 29, 0, 51, 21, 41, 23, 37},> {29, 41, 79, 21, 82, 33, 77, 37, 62, 51, 0, 65, 42, 59, 61},{74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65, 0, 61, 11, 55},> {23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61, 0, 62, 23},> {72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62, 0, 59},{46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59, 0},> };// check = tsp(data4) == 244;return true;}
ValidParens
Tests
if(leftRem == 0 && rightRem == 0){result.add(new String(buffer));return;> }> if(leftRem 0)> {buffer[idx] = '(';generateValidParens(result, leftRem -1, rightRem, idx + 1, buffer);> }if(rightRem 0){> buffer[idx] = ')';> generateValidParens(result, leftRem, rightRem - 1, idx + 1, buffer);}>}ListString result = generateValidParens(3);> boolean check => result.get(0).equals("((()))") &&> result.get(1).equals("(()())") &&result.get(2).equals("(())()") &&> result.get(3).equals("()(())") &&> result.get(4).equals("()()()");if(!check)> {> return false;> }return true;}