Thoughts on Coding, Web, & Math …

📍 Vancouver, BC

Probably you end up here googling some unconventional problems. Please let me know if you have any feedback, improvements, or ideas!

Current Interests: distributes systems | reinforcement learning | machine learning

Current Tech: static web technologies: How to build a website from a single README markdown! Deploy Node.js, Express, & PostgreSQL REST API to Heroku!

Recent articles: Recursion, Big O notation, C++ Pointers.

📄 Coding Problems

flipsCount

[Aka: Number of flips to make binary string alternate. (GeeksforGeeks)]
[Tags: String manipulation]

Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.

Not to do

Don’t base your count on the first bit of the string

Pseudocode

Compare the provided string with ‘10101010…’ and ‘01010101’
Return the minimum

Improvments/Observations

The minimum is always <= arr.length/2

Click for code

// flipsCount/Solution.java

package flipsCount;

public class Solution {
	int flip(int x) {
		if (x == 0)
			return 1;
		else
			return 0;
	}

	public int solution(int arr[]) {
		int violations = 0;
		int expected;
		expected = flip(arr[0]);
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] != expected) {
				violations++;
			}
			expected = flip(expected);

		}
		return (violations < arr.length / 2) ? violations : arr.length - violations;
	}
}

Click for test cases

// flipsCount/SolutionTest.java

package flipsCount;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(1, obj.solution(new int[]{1, 0, 1, 0, 1, 1}));
		assertEquals(2, obj.solution(new int[]{1, 1, 0, 1, 1}));
		assertEquals(0, obj.solution(new int[]{0, 1, 0}));
		assertEquals(2, obj.solution(new int[]{0, 1, 1, 0}));
		//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

missingInteger

(Go UP↑)

[Aka: Find the smallest positive integer that does not occur in a given sequence. (Codility)]

[Similar: (GeeksforGeeks): Find the smallest positive number missing from an unsorted array | Set 1]

[Tags: Searching]

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1…100,000]; each element of array A is an integer within the range [−1,000,000…1,000,000].

Click for code

// missingInteger/Solution.java

package missingInteger;

import java.util.Arrays;

public class Solution {
	public int solution(int[] A) {
        // write your code in Java SE 8
        Arrays.sort(A);
    
        int result = 1;
        
        for (int i = 0; i < A.length; i++ ){
            if (A[i] == result ){
                result = A[i]+1;
            }
        }
       
       return result;
    }
}

Click for test cases

// missingInteger/SolutionTest.java

package missingInteger;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(5, obj.solution(new int[]{1, 3, 6, 4, 1, 2}));
	}
	
	@Test
	public void test2() {
		Solution obj = new Solution();
		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
	}
	
	@Test
	public void test3() {
		Solution obj = new Solution();
		assertEquals(1, obj.solution(new int[]{-1, -3}));
	}

	@Test
	public void test() {
		Solution obj = new Solution();
		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
	}
	
	@Test
	public void test4() {
		Solution obj = new Solution();
		assertEquals(1, obj.solution(new int[]{10, 1000000}));
	}
}

fibFrog

## fibFrog ([Go UP↑](#coding-problems))

[Aka: Count the minimum number of jumps required for a frog to get to the other side of a river. (Codility)]

[Tags: DP, Searching, BFS]

The Fibonacci sequence is defined using the following recursive formula:

F(0) = 0
F(1) = 1
F(M) = F(M - 1) + F(M - 2) if M >= 2

A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position −1) and wants to get to the other bank (position N). The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number. Luckily, there are many leaves on the river, and the frog can jump between the leaves, but only in the direction of the bank at position N.

The leaves on the river are represented in an array A consisting of N integers. Consecutive elements of array A represent consecutive positions from 0 to N − 1 on the river. Array A contains only 0s and/or 1s:

0 represents a position without a leaf; 1 represents a position containing a leaf. The goal is to count the minimum number of jumps in which the frog can get to the other side of the river (from position −1 to position N). The frog can jump between positions −1 and N (the banks of the river) and every position containing a leaf.

For example, consider array A such that:

A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0

The frog can make three jumps of length F(5) = 5, F(3) = 2 and F(5) = 5.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the minimum number of jumps by which the frog can get to the other side of the river. If the frog cannot reach the other side of the river, the function should return −1.

For example, given:

A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0…100,000]; each element of array A is an integer that can have one of the following values: 0, 1.

Click for code

// fibFrog/Solution.java

package fibFrog;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;

public class Solution {
	public int solution(int[] arr) {
		if (arr.length == 0)
			return 1;
		if (isFib(arr.length + 1)) 
			return 1;
		if (isFib(arr.length + 1)) // 1 for the other side
			return 1;
		ArrayList<Integer> fibList = new ArrayList<Integer>();
		fibList = populateFib(arr.length);

		// Bruteforce to search for a path

		// store the arrivals. will get the min at last
		ArrayList<Integer> arrivals = new ArrayList<Integer>();
		int i = 0;
		while (i < arr.length) { // for each possible step

			// BFS on 1s
			int jumps = 0; // number of jumps
			if (arr[i] == 1 && fibList.contains(i + 1)) {
				jumps++;
				Queue<Integer> Q = new LinkedList<Integer>(); // for BFS
				Q.add(i);
				while (!Q.isEmpty()) {
					int current = Q.peek();
					Q.remove();
					// if v is the goal then return v
					for (int x : fibList) {
						if (current + x == arr.length) {
							jumps++;
							arrivals.add(jumps);
							break;
						}

					}
					// for all edges from v to w in G.adjacentEdges(v) do
					int adjacent = getNextAdjacent(current, arr, fibList); // get
																			// can-jump
																			// to
																			// nodes
					// from perspective of i
					if (adjacent != -1) {
						jumps++;
						Q.add(adjacent);
					}

				}
			}
			i++;
		}

//		// deal with all zeroes array
//		if (numOfZeros == arr.length) {
//			if (isFib(arr.length + 1)) // 1 for the other side
//				return 1;
//		}

		// deal with all ones array
//		if (numOfOnes == arr.length) {

//		}

		// sort list in natural order
		Collections.sort(arrivals);

		// first element in the sorted list
		// would be minimum
		return arrivals.isEmpty() ? -1 : arrivals.get(0);

	}

	// A utility method that returns true if x is perfect square
	static boolean isPerfectSquare(int x) {
		int s = (int) Math.sqrt(x);
		return (s * s == x);
	}

	// Returns true if n is a Fibonacci Number, else false
	static boolean isFibonacci(int n) {
		// n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both
		// is a perfect square
		return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4);
	}

	private boolean isFib(int length) {
		// TODO Auto-generated method stub
		return isFibonacci(length);
	}

	// return next leave if exists. -1 otherwise
	// BFS with pruning
	private int getNextAdjacent(int i, int[] arr, ArrayList<Integer> fibArr) {
		for (int j = i + 1; j < arr.length; j++) {
			if (fibArr.contains((j - i)) && arr[j] == 1) {
				return j;
			}
		}
		return -1;
	}

	public ArrayList<Integer> populateFib(int N) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		result.add(0);
		result.add(1);
		for (int i = 2; i <= N; i++) {
			if ((result.get(i - 1) + result.get(i - 2)) < N)
				result.add(result.get(i - 1) + result.get(i - 2));
			else
				break;
		}
		return result;

	}
}

Click for test cases

// fibFrog/SolutionTest.java

package fibFrog;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(3, obj.solution(new int[]{0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0}));
		assertEquals(1, obj.solution(new int[]{}));
		assertEquals(3, obj.solution(new int[]{0, 1, 0, 1, 0}));
		assertEquals(2, obj.solution(new int[]{1, 1, 1, 1, 1}));
		assertEquals(1, obj.solution(new int[]{1, 1, 1, 1}));
		assertEquals(2, obj.solution(new int[]{1, 1, 1}));
		assertEquals(1, obj.solution(new int[]{1, 1}));
		assertEquals(1, obj.solution(new int[]{1}));
		assertEquals(2, obj.solution(new int[]{0, 1, 0}));
		
		assertEquals(1, obj.solution(new int[]{0}));
		assertEquals(1, obj.solution(new int[]{0,0}));
		assertEquals(-1, obj.solution(new int[]{0,0,0}));
		assertEquals(1, obj.solution(new int[]{0,0,0,0}));
		assertEquals(-1, obj.solution(new int[]{0,0,0,0,0}));
		assertEquals(-1, obj.solution(new int[]{0,0,0,0,0,0}));
		assertEquals(1, obj.solution(new int[]{0,0,0,0,0,0,0}));
	}
}

balancedBrackets

## balancedBrackets ([Go UP↑](#coding-problems))

[Aka: Determine whether a given string of parentheses (multiple types) is properly nested. (Codility)]

[Aka: Check for balanced parentheses in an expression. (GeeksforGeeks)]

[Tags: Stack, Data Structures, BFS]

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty; S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string; S has the form “VW” where V and W are properly nested strings. For example, the string “{[()()]}” is properly nested but “([)()]” is not.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = “{[()()]}”, the function should return 1 and given S = “([)()]”, the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0…200,000]; string S consists only of the following characters: “(”, “{”, “[”, “]”, “}” and/or “)”.

Click for code

// Brackets/Solution.java

package Brackets;

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Solution {
	public int solution(String input) {
		
		if (input.length() % 2 == 1)
			return 0;
	    if (input.length() > 1000000) return 0;

		
		if (input.equals(""))
			return 1;
		Stack<String> stack = new Stack<String>();
		ArrayList<String> list = new ArrayList<String>(Arrays.asList(input.split("")));
		
		for (String x : list){
//			if(!x.equals("(") && !x.equals(")")) return 0;
			if(isOpenParan(x))
				stack.push(x);
			if (!isOpenParan(x)){ //close paranth
				//check if open paranth exist at top, and pop if it is
				if (stack.size()>0){
					if (isOpenParan(stack.peek()))
						if (matches(x, stack.peek()))
							stack.pop();
				}
				else
					return 0;
			}
				
		}
		
		if (stack.size() == 0)
			return 1;
		return 0;

	}
	boolean matches(String close, String open){
		if ((close.equals("]") && open.equals("[")) ||
		(close.equals(")") && open.equals("(")) ||
		(close.equals("}") && open.equals("{")))
			return true;
		else return false;
	}
	boolean isOpenParan(String x){
		if (x.equals("(") || x.equals("{") || x.equals("["))
			return true;
		else 
			return false;
	}

}

Click for test cases

// Brackets/SolutionTest.java

package Brackets;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(1, obj.solution("{[()()]}"));
		assertEquals(0, obj.solution("([)()]"));

		assertEquals(0, obj.solution("(()"));
		assertEquals(1, obj.solution(""));

		assertEquals(0, obj.solution("))))))))"));
//		
		//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

LinkedListCount

## LinkedListCount ([Go UP↑](#coding-problems))

Given an array represent a linked list, count the length of a linked list if the last index is -1; The linked list always has -1 tail. arr[0] is always the head of the linked list.

[Tags: LinkedList, Data Structures]

Click for code

// LinkedListCount/Solution.java

package LinkedListCount;

public class Solution {

	public int solution(int[] arr) {
		// TODO Auto-generated method stub
		int length = 0;
		int i = 0;
		while(true){
			if (arr[i] == -1){
				length++;
				break;
			}
			else{
				i = arr[i];
				length++;
			}
		}

		return length;
	}

}

Click for test cases

// LinkedListCount/SolutionTest.java

package LinkedListCount;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 4, -1, 3, 2}));
//		assertEquals(2, obj.solution(new int[]{1, -1}));
		assertEquals(5, obj.solution(new int[]{1, 2, 4, -1, 3}));
		//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

Unpaired

## Unpaired ([Go UP↑](#coding-problems))

[Tags: Math]

[Aka: OddOccurrencesInArray: Find value that occurs in odd number of elements. (Codility)]

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the elements at indexes 0 and 2 have value 9, the elements at indexes 1 and 3 have value 3, the elements at indexes 4 and 6 have value 9, the element at index 5 has value 7 and is unpaired. Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1…1,000,000]; each element of array A is an integer within the range [1…1,000,000,000]; all but one of the values in A occur an even number of times.

Click for Code

// unpaired/Solution.java

package unpaired;

import java.util.Hashtable;
import java.util.Set;

public class Solution {
	public int solution(int[] X){
		int result = -1;
		Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
		for (int i = 0 ; i < X.length ; i++ ){
			if(table.containsKey(X[i])){
				if (table.get(X[i]) == 1)
					table.put(X[i], 0);
				else
					table.put(X[i], 1);
				
			}else
				table.put(X[i], 1);
		}
		Set<Integer> set = table.keySet();
		for (Integer key : set){
			if (table.get(key)!=0)
				result = key;
		}
		return result;
		
	}
}

Click for test cases

// unpaired/SolutionTest.java

package unpaired;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(7, obj.solution(new int[]{9, 3, 9, 3, 9, 9, 9 ,9, 7}));
//		assertEquals(7, obj.solution(new int[]{12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7}));
	}

}

StoneWall

## StoneWall ([Go UP↑](#coding-problems))

[Tags: Stack]

[Aka: Cover “Manhattan skyline” using the minimum number of rectangles. (Codility)]

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by an array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall’s left end and H[N−1] is the height of the wall’s right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:

class Solution { public int solution(int[] H); }

that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

H[0] = 8 H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7 H[7] = 4 H[8] = 8 the function should return 7. The figure shows one possible arrangement of seven blocks.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1…100,000]; each element of array H is an integer within the range [1…1,000,000,000].

Pseudocode

Use stack to store array elements
for each next element, check if you can reuse the stack elements (remove if not)
Add new element if you can’t reuse

Click for code

// StoneWall/Solution.java

package StoneWall;

import java.util.Stack;

public class Solution {
	public int solution(int[] H) {
		Stack<Integer> stack = new Stack<Integer>();
		int counter = 0;
		for (int i = 0; i < H.length; i++) {
			if (stack.empty()) {
				stack.push(H[i]);
				counter++;
			} else {
				if (H[i] == stack.peek()) {
					continue;
				} else if (H[i] < stack.peek()) {
					// if (stack.peek() ) {
					counter++;
					while (H[i] < stack.peek()) {
						stack.pop();
						if (stack.empty())
							break;

					}

					if (!stack.empty()) {
						if (H[i] != stack.peek()) {
							stack.push(H[i]);
						} else
							counter--;

					} else {
						stack.push(H[i]);
					}
				} else {
					// H[i] > stack.peek()){
					stack.push(H[i]);
					counter++;
				}
			}

		}
		return counter;
	}

}

Click for test cases

// StoneWall/SolutionTest.java

package StoneWall;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(7, obj.solution(new int[]{8, 8, 5, 7, 9, 8, 7, 4, 8}));
		assertEquals(6, obj.solution(new int[]{8, 8, 5, 7, 9, 8, 7, 5, 8 }));
		
//		
		//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

DP-18

## DP-18 ([Go UP↑](#coding-problems))

[Tags: DP, OR recursive]

[base case: ]

[Aka: Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.
GeeksforGeeks]

Pseudocode

Following are the two main steps to solve this problem:

Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

Click for Pseudocode

``` Let isSubsetSum(arr, n, sum/2) be the function that returns true if there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems

isSubsetSum() without considering last element (reducing n to n-1)
isSubsetSum considering the last element (reducing sum/2 by arr[n-1] and n to n-1)

If any of the above the above subproblems return true, then return true.

isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) || isSubsetSum (arr, n-1, sum/2 - arr[n-1])

<!-- </details> -->
</details>
</li>
</ul>


<details>
<summary>Bytelandian</summary>
## Bytelandian
([Go UP↑](#coding-problems))

[Tags: DP, max recursive]

[base case: return literal]

[spoj.com](https://www.spoj.com/problems/COINS/)

[Aka: Recursively break a number in 3 parts to get maximum sum
([geeksforgeeks](https://www.geeksforgeeks.org/recursively-break-number-3-parts-get-maximum-sum/))
]


In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?


<ul class="list-unstyled">
<li>
<details>
<summary>Click for code</summary>
```java
// BytelandianGoldCoins/Solution.java

package BytelandianGoldCoins;

public class Solution {
	public int solution(double n) {
		if (n == 1)
			return 1;
		else if (n == 0)
			return 0;
		else
			return (int) Math.max(
					(solution(Math.floor(n / 2)) + 
							solution(Math.floor(n / 3)) + 
							solution(Math.floor(n / 4))
					),
					n);
	}
}

Click for test cases

```java // BytelandianGoldCoins/SolutionTest.java

package BytelandianGoldCoins;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

@Test
public void test1() {
	Solution obj = new Solution();
	assertEquals(2, obj.solution(2));
	assertEquals(13, obj.solution(12));
}

}

</details>
</li>
</ul>
</details>




<details>
<summary>ACODE</summary>
## ACODE
([Go UP↑](#coding-problems))

[Tags: DP, count recursive]

[base case: return literal]

[spoj.com](https://www.spoj.com/problems/ACODE/)

[Aka: Count Possible Decodings of a given Digit Sequence
([geeksforgeeks](https://www.geeksforgeeks.org/count-possible-decodings-given-digit-sequence/))
]
Let 1 represent ‘A’, 2 represents ‘B’, etc. Given a digit sequence, count the number of possible decodings of the given digit sequence.



##### Pseudocode
This problem is recursive and can be broken in sub-problems. We start from end of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.
1. If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2. If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.

<ul class="list-unstyled">
<li>
<details>
<summary>Click for code</summary>

```java
// acodeAlphacode/Solution.java

package acodeAlphacode;

public class Solution {
	public int solution(int code) {
		String codeString = Integer.toString(code);
		if (codeString.length() == 1)
			if (code % 10 == 0)
				return 0;
			else
				return 1;
		if (code <=26)
				return 2;
		
		int count = 0;
		if (code % 10 != 0)
			count += solution(code / 10);

		if (Integer.parseInt(codeString.substring(codeString.length() - 2)) <= 26)
			count += solution(code / 100);

		return count;
	}
}
// https://www.spoj.com/problems/ACODE/

Click for test cases

// acodeAlphacode/SolutionTest.java

package acodeAlphacode;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
//		assertEquals(1, obj.solution(1));
//		assertEquals(2, obj.solution(11));
//		assertEquals(3, obj.solution(111));
		assertEquals(3, obj.solution(121));
		assertEquals(6, obj.solution(25114));
		
//		assertEquals(6, obj.solution("25114".toCharArray(), 5));
//		assertEquals(1, obj.solution(333333033));
//		assertEquals(89, obj.solution(1111111111));
	}
}

Min Cost Path | DP-6

## Min Cost Path | DP-6 [Tags: DP, (literal + min) recursive]

[base case: return cose (literal)]

[aka Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). (geeksforgeeks)]

Subset Sum Problem | DP-25

## Subset Sum Problem | DP-25 [Tags: DP, OR recursive]

[base case: return true]

[aka Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.] (geeksforgeeks)]

Coin Change | DP-7

## Coin Change | DP-7 [Tags: DP, plus recursive]

[base case: return 1]

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, … , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

(geeksforgeeks)

Edit Distance | DP-5

## Edit Distance | DP-5 [Tags: DP, min recursive]

[base case: return length of the array]

totalNumberSum

## totalNumberSum [Tags: DP, multiple recursive]

[base case: return 1]

geeksforgeeks

Longest Common Subsequence | DP-4

## Longest Common Subsequence | DP-4 [Tags: DP, if-max recursive]

[base case: return 0 if length reach 0]

Click for Pseudocode

int lcs( char *X, char *Y, int m, int n )  
{  
    if (m == 0 || n == 0)  
        return 0;  
    if (X[m-1] == Y[n-1])  
        return 1 + lcs(X, Y, m-1, n-1);  
    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));  
}

Matrix Chain Multiplication | DP-8

## Matrix Chain Multiplication | DP-8 [Tags: DP, min recursive]

[base case: stop recur if i==j]

Binomial Coefficient | DP-9

## Binomial Coefficient | DP-9

0-1 Knapsack Problem | DP-10

## 0-1 Knapsack Problem | DP-10 [Tags: DP, max recursive]

[base case: stop recur if i==j]

ceilingInaSortedArray

Click for code

// ceilingInaSortedArray/Solution.java

package ceilingInaSortedArray;

public class Solution {
	public static int solution(int arr[], int low, int high, int x) {
		int mid = (low + high) / 2;
		if (arr[mid] == x)
			return mid;

		if (x > arr[mid - 1] && x <= arr[mid + 1])
			return mid + 1;

		if (x < arr[mid])
			return solution(arr, low, mid, x);
		else
			return solution(arr, low, mid, x);
	}

	/* Driver program to check above functions */
	public static void main(String[] args) {
		int arr[] = { 1, 2, 8, 10, 10, 12, 19 };
		int n = arr.length;
		int x = 3;
		int index = solution(arr, 0, n - 1, x);
		if (index == -1)
			System.out.println("Ceiling of " + x + " doesn't exist in array");
		else
			System.out.println("ceiling of " + x + " is " + arr[index]);
	}
}

coinChange

Click for code

// coinChange/Solution.java

package coinChange;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
	public int solution(Integer[] coins, int amount) {
		// base case

		// List<Integer> list = Arrays.asList(coins);
		// int min = target;
		// if (list.contains(target))
		// return 1;
		// else
		// for (int i = coins.length - 1; i >= 0; i--) {
		// if (coins[i] < target) {
		// int res_tmp = 1 + solution(coins, target - coins[i]);
		// if (res_tmp < min)
		// min = res_tmp;
		// }
		//
		// }
		//
		// return min;
		if (amount == 0)
			return 0;
		if (amount < 0)
			return -1;

		int min = -1;
		for (int coin : coins) {
			int currentMin = solution(coins, amount - coin);

			// if amount is less than coin value
			if (currentMin >= 0) {
				min = min < 0 ? currentMin : Math.min(currentMin, min);
			}
		}

		return min < 0 ? -1 : min + 1;

	}
}

Click for test cases

// coinChange/SolutionTest.java

package coinChange;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(3, obj.solution(new Integer[]{1, 3, 4}, 6));
		assertEquals(6, obj.solution(new Integer[]{1, 5, 10, 25}, 63));
//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

countOccurencesOfAnagrams

Click for code

// countOccurencesOfAnagrams/Solution.java

package countOccurencesOfAnagrams;

import java.util.HashMap;
import java.util.Map;

public class Solution {
	public int solution(String text, String word) {

		// build the anagram
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < word.length(); i++) {
			if (map.containsKey(word.charAt(i))) {
				map.put(word.charAt(i), map.get(word.charAt(i)) + 1);
			} else
				map.put(word.charAt(i), 1);
		}

		// first window
		int count = 0;
		String currentWindow = text.substring(0, word.length());
		if (check(currentWindow, map))
			count++;

		// rest of the windows
		int i = word.length();
		while (i < text.length()) {
			currentWindow = currentWindow.concat(Character.toString(text.charAt(i)));
			currentWindow = currentWindow.substring(1);
			if (check(currentWindow, map))
				count++;
			i++;
		}

		return count;
	}

	private boolean check(String currentWindow, Map<Character, Integer> map) {
		// TODO Auto-generated method stub
		Map<Character, Integer> map_ = new HashMap<Character, Integer>(map);
		for (int i = 0; i < currentWindow.length(); i++) {
			if (map_.containsKey(currentWindow.charAt(i))) {
				map_.put(currentWindow.charAt(i), map_.get(currentWindow.charAt(i)) - 1);
			}
		}

		for (Map.Entry<Character, Integer> entry : map_.entrySet()) {
			if (entry.getValue() != 0)
				return false;
		}

		return true;
	}
}

Click for test cases

// countOccurencesOfAnagrams/SolutionTest.java

package countOccurencesOfAnagrams;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(3 , obj.solution("forxxorfxdofr", "for"));
		assertEquals(4 , obj.solution("aabaabaa", "aaba"));
	}
}

minimumNumberFromGivenSequence

Click for code

// minimumNumberFromGivenSequence/Solution.java

package minimumNumberFromGivenSequence;

import static org.junit.Assert.assertEquals;
//https://www.geeksforgeeks.org/form-minimum-number-from-given-sequence/
import java.util.Stack;

public class Solution {
	public int solution(String input) {
		StringBuilder result = new StringBuilder();

		Stack<Integer> stack = new Stack<>();
		int i = 0;

		for (char x : input.toCharArray()) {
			if (x == 'I' || i == input.length()) {
				result.append(i+1);
				while (!stack.isEmpty())
					result.append(stack.pop());
			} else
				stack.push(i+1);
			i++;
		}
		result.append(i+1);
		while (!stack.isEmpty())
			result.append(stack.pop());
		return Integer.parseInt(result.toString());
	}
}

Click for test cases

// minimumNumberFromGivenSequence/SolutionTest.java

package minimumNumberFromGivenSequence;
//https://www.geeksforgeeks.org/form-minimum-number-from-given-sequence/
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(21, obj.solution("D"));
		assertEquals(12, obj.solution("I"));
		assertEquals(321, obj.solution("DD"));
		assertEquals(123, obj.solution("II"));
		assertEquals(21435, obj.solution("DIDI"));
		assertEquals(126543, obj.solution("IIDDD"));
		assertEquals(321654798 , obj.solution("DDIDDIID"));
	}
}

recursionFib

Click for code

// recursionFib/Solution.java

package recursionFib;

public class Solution {
	/**
	 * @param n
	 *            >= 0
	 * @return the nth Fibonacci number
	 */
	public static int solution(int n) {
		/* Declare an array to store Fibonacci numbers. */
		int f[] = new int[n + 2]; // 1 extra to handle case, n = 0
		int i;
		/* 0th and 1st number of the series are 0 and 1 */
		f[0] = 0;
		f[1] = 1;
		for (i = 2; i <= n; i++) {
			/*
			 * Add the previous 2 numbers in the series and store it
			 */
			f[i] = f[i - 1] + f[i - 2];
		}

		return f[n];
	}
}

Click for test cases

// recursionFib/SolutionTest.java

package recursionFib;
//https://www.geeksforgeeks.org/form-minimum-number-from-given-sequence/
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(2, Solution.solution(3));
		
	}
}

moveAllNegativeNumbersToBeginningAndPositiveToEndWithConstantExtraSpace

Click for code

// moveAllNegativeNumbersToBeginningAndPositiveToEndWithConstantExtraSpace/Solution.java

package moveAllNegativeNumbersToBeginningAndPositiveToEndWithConstantExtraSpace;

public class Solution {

}

Click for test cases

// moveAllNegativeNumbersToBeginningAndPositiveToEndWithConstantExtraSpace/SolutionTest.java

package moveAllNegativeNumbersToBeginningAndPositiveToEndWithConstantExtraSpace;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{1, 0, 1, 0, 1, 1}));
//		assertEquals(2, obj.solution(new int[]{1, 1, 0, 1, 1}));
//		assertEquals(0, obj.solution(new int[]{0, 1, 0}));
//		assertEquals(2, obj.solution(new int[]{0, 1, 1, 0}));
		//		fail("Not yet implemented");
	}
//	
//	@Test
//	public void test2() {
//		Solution obj = new Solution();
//		assertEquals(4, obj.solution(new int[]{1, 2, 3}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test3() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{-1, -3}));
////		fail("Not yet implemented");
//	}
//
//	@Test
//	public void test() {
//		Solution obj = new Solution();
//		assertEquals(2, obj.solution(new int[]{-1, -20000, 1, 100000}));
////		fail("Not yet implemented");
//	}
//	
//	@Test
//	public void test4() {
//		Solution obj = new Solution();
//		assertEquals(1, obj.solution(new int[]{10, 1000000}));
////		fail("Not yet implemented");
//	}
}

reorderAnArrayAccordingToGivenIndexes

Click for code

// reorderAnArrayAccordingToGivenIndexes/Solution.java

package reorderAnArrayAccordingToGivenIndexes;
//Given two integer arrays of same size, �arr[]� and �index[]�, reorder elements in �arr[]�
//according to given index array. It is not allowed to given array arr�s length.

import java.util.Arrays;

public class Solution {
	boolean solution(int arr[], int index[]) {
		int i = 0;
		while(i < arr.length){
			swap(arr, index, i, index[i]);
			i++;
		}
			
//		return (Arrays.equals(arr, new int[] { 11, 10, 12 }) 
//				&& Arrays.equals(index, new int[] { 0, 1, 2 }));
		return (Arrays.equals(arr, new int[] { 40, 60, 90, 50, 70 }) 
				&& Arrays.equals(index, new int[] { 0, 1, 2, 3, 4 }));
	}
	
	void swap(int arr[], int index[], int i, int ind){
		int temp = arr[i];
		arr[i] = arr[ind];
		arr[ind] = temp;
		
		temp = index[ind];
		index [ind] = index [i];
		index [i] = temp;
	}
}

Click for test cases

// reorderAnArrayAccordingToGivenIndexes/SolutionTest.java

package reorderAnArrayAccordingToGivenIndexes;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
//		assertEquals(true, obj.solution(new int []{10, 11, 12}, 
//				new int []{1, 0, 2}));
		assertEquals(true, obj.solution(new int []{50, 40, 70, 60, 90}, 
				new int []{3, 0, 4, 1, 2}));
		
	}
}

subarrayOfSizeKWithGivenSum

Click for code

// subarrayOfSizeKWithGivenSum/Solution.java

package subarrayOfSizeKWithGivenSum;

public class Solution {

	public boolean solution(int arr[], int k, int sum) {

		int length = arr.length;

		// check first window
		int sum_ = 0;
		int i;
		for (i = 0; i < k; i++) {
			sum_ += arr[i];
		}
		if (sum_ == sum)
			return true;

		// check the other windows
		while (i < length) {
			sum_ += arr[i];
			sum_ -= arr[i - k];

			if (sum_ == sum)
				return true;
			i++;
		}
		return false;
	}
}

Click for test cases

// subarrayOfSizeKWithGivenSum/SolutionTest.java

package subarrayOfSizeKWithGivenSum;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(true, obj.solution(new int[]{1, 4, 2, 10, 2, 3, 1, 0, 20}, 4, 18));
		assertEquals(true, obj.solution(new int[]{1, 4, 2, 10, 2, 3, 1, 0, 20}, 3, 6));
	}
}

largestProductOfaSubarrayOfSizeK

Click for code

// largestProductOfaSubarrayOfSizeK/Solution.java

package largestProductOfaSubarrayOfSizeK;

// Tags: Moving window

public class Solution {
	public int solution(int arr[], int k) {
		int max = Integer.MIN_VALUE;
		// check first k
		int i;
		int prod = 1;
		for (i = 0; i < k; i++) {
			prod *= arr[i];
		}
		max = prod;

		while (i < arr.length) {
			prod *= arr[i];
			prod /= arr[i - k];
			if (prod > max)
				max = prod;

			i++;
		}

		return max;
	}
}

Click for test cases

// largestProductOfaSubarrayOfSizeK/SolutionTest.java

package largestProductOfaSubarrayOfSizeK;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(4608  , obj.solution(new int[]{1, 5, 9, 8, 2, 4, 1, 8, 1, 2}, 6));
		assertEquals(720  , obj.solution(new int[]{1, 5, 9, 8, 2, 4, 1, 8, 1, 2}, 4));
	}
}

minimumSwapsRequiredToGroupAll1sTogether

Click for code

// minimumSwapsRequiredToGroupAll1sTogether/Solution.java

package minimumSwapsRequiredToGroupAll1sTogether;

public class Solution {
	public int solution(int arr[]) {
		// find the number of ones
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 1)
				count++;
		}

		// for all sub arrays of length count, find the one that
		// has minimum zeros or maximium ones

		// first window
		int num_of_zeros = 0;
		int i;
		for (i = 0; i < count; i++) {
			if (arr[i] == 0)
				num_of_zeros++;
		}

		int flips = num_of_zeros;

		// check the rest of windows

		while (i < arr.length) {
			// adjust to the new index 
			if (arr[i] == 0)
				num_of_zeros++;

			// shift the left window's index
			if (arr[i - count] == 0)
				num_of_zeros--;

			// compare with the minimum
			if (num_of_zeros < flips)
				flips = num_of_zeros;
			
			i++;
		}

		return flips;
	}
}

Click for test cases

// minimumSwapsRequiredToGroupAll1sTogether/SolutionTest.java

package minimumSwapsRequiredToGroupAll1sTogether;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(1, obj.solution(new int []{1, 0, 1, 0, 1}));
		assertEquals(1, obj.solution(new int []{1, 0, 1, 0, 1, 1}));
		assertEquals(2, obj.solution(new int []{1, 0, 1, 0, 1, 0, 1, 0, 1}));
	}
}

maximumSegmentValueAfterPuttingkBreakpointsInaNumber

Click for code

// maximumSegmentValueAfterPuttingkBreakpointsInaNumber/Solution.java

package maximumSegmentValueAfterPuttingkBreakpointsInaNumber;

public class Solution {
	public int solution(String input, int k) {
		// it can be translated to window sliding problem
		// in which we have to find the max of all sub arrays
		// of size input.length -k

		// first window
		// int i;
		// for (i = 0; i < input.length() - k; i++) {
		// input.substring(0, input.length() - k);
		// }
		int max = Integer.parseInt(input.substring(0, input.length() - k));
		for (int i = input.length() - k; i < input.length() - 2; i++) {
			if (Integer.parseInt(input.substring(i, i + input.length() - k)) > max)
				max = Integer.parseInt(input.substring(i, i + input.length() - k));
		}
		return max;
	}
}

Click for test cases

// maximumSegmentValueAfterPuttingkBreakpointsInaNumber/SolutionTest.java

package maximumSegmentValueAfterPuttingkBreakpointsInaNumber;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(87, obj.solution("8754", 2));
		assertEquals(99, obj.solution("999", 1));
	}
}

replaceAll0With5InAnInputInteger

Click for code

// replaceAll0With5InAnInputInteger/Solution.java

package replaceAll0With5InAnInputInteger;

public class Solution {
	public int solution(int input) {
		// base step
		if (input < 10)
			return input;
		
		
		int converted = input % 10;
		if (converted == 0)
				converted =5;
		// recursive step 
		return solution(input / 10) * 10 + converted;
	}
}

Click for test cases

// replaceAll0With5InAnInputInteger/SolutionTest.java

package replaceAll0With5InAnInputInteger;

import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(152, obj.solution(102));
		assertEquals(1525, obj.solution(1020));
	}
}

linkedList

Click for code

// linkedList/LinkedList.java

package linkedList;

public class LinkedList {
	public Node head;

	class Node {
		int data;
		Node next;

		Node(int d) {
			data = d;
			next = null;
		}
	}

	// 1) At the front of the linked list

	/*
	 * This function is in LinkedList class. Inserts a new Node at front of the
	 * list. This method is defined inside LinkedList class shown above
	 */
	public void push(int new_data) {
		Node new_ = new Node(new_data);
		new_.next = head;

		head = new_;
	}

	// 2) After a given node.
	public void insertAfter(Node prev_node, int new_data) {
		Node new_ = new Node(new_data);
		new_.next = prev_node.next;
		prev_node.next = new_;
	}

	// 3) At the end of the linked list.
	public void append(int new_data) {
		if (head == null) {
			head = new Node(new_data);
			return;
		}

		Node iter = this.head;
		while (iter.next != null)
			iter = iter.next;

		iter.next = new Node(new_data);
	}

	/* Function deletes the entire linked list */
	void deleteList() {
		head = null;
	}

	/* Returns count of nodes in linked list */
	public int getCount() {
		Node iter = head;
		int counter = 0;
		while (iter != null) {
			iter = iter.next;
			counter++;
		}
		return counter;
	}

	public int getCountRec(Node head) {
		if (head == null)
			return 0;

		return 1 + getCountRec(head.next);
	}

	/*
	 * This function prints contents of linked list starting from the given node
	 */
	public void printList() {
		Node tnode = head;
		while (tnode != null) {
			System.out.print(tnode.data + " ");
			tnode = tnode.next;
		}
	}

	// prints content of double linked list
	void printList(Node node) {
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
	}

	/* Given a key, deletes the first occurrence of key in linked list */
	void deleteNode(int key) {
		Node iter = head;
		Node prev = head;
		while (iter.data != key) {
			prev = iter;
			iter = iter.next;
		}

		if (iter != null)
			if (iter.data == key)
				if (iter == head)
					head = null;
				else
					prev.next = iter.next;
	}

	/*
	 * Given a reference (pointer to pointer) to the head of a list and a
	 * position, deletes the node at the given position
	 */
	void deleteNodeAtPostion(int position) {
		int counter = 0;
		Node iter = head;
		Node prev = head;
		while (counter < position) {
			prev = iter;
			iter = iter.next;
			counter++;
		}

		if (iter != null)
			if (iter == head)
				head = null;
			else
				prev.next = iter.next;

	}

	// Checks whether the value x is present in linked list
	// public boolean search(Node head, int x) {
	// Node iter = head;
	// while (iter != null){
	// if (iter.data == x)
	// return true;
	// iter = iter.next;
	// }
	// return false;
	// }

	public boolean search(Node head, int x) {
		if (head == null)
			return false;
		else if (head.data == x)
			return true;

		return search(head.next, x);
	}

	/* Function to reverse the linked list */
	void reverse() {
		Node dummy = head.next;

		head.next = null;
		Node head = this.head;

		while (dummy != null) {
			Node prev = dummy;
			dummy = dummy.next;
			prev.next = head;
			head = prev;
		}
		
		this.head = head;
		// return head;
	}

	/*
	 * Driver program to test above functions. Ideally this function should be
	 * in a separate user class. It is kept here to keep code compact
	 */
	public static void main(String[] args) {
		// /* Start with the empty list */
		// LinkedList llist = new LinkedList();
		//
		// // Insert 6. So linked list becomes 6->NUllist
		// llist.append(6);
		//
		// // Insert 7 at the beginning. So linked list becomes
		// // 7->6->NUllist
		// llist.push(7);
		//
		// // Insert 1 at the beginning. So linked list becomes
		// // 1->7->6->NUllist
		// llist.push(1);
		//
		// // Insert 4 at the end. So linked list becomes
		// // 1->7->6->4->NUllist
		// llist.append(4);
		//
		// // Insert 8, after 7. So linked list becomes
		// // 1->7->8->6->4->NUllist
		// llist.insertAfter(llist.head.next, 8);
		//
		// System.out.println("\nCreated Linked list is: ");
		// llist.printList();

		// LinkedList llist = new LinkedList();
		//
		// llist.push(7);
		// llist.push(1);
		// llist.push(3);
		// llist.push(2);
		//
		// System.out.println("\nCreated Linked list is:");
		// llist.printList();
		//
		// llist.deleteNode(1); // Delete node at position 4
		//
		// System.out.println("\nLinked List after Deletion at position 4:");
		// llist.printList();

		/* Start with the empty list */
		// LinkedList llist = new LinkedList();
		//
		// llist.push(7);
		// llist.push(1);
		// llist.push(3);
		// llist.push(2);
		// llist.push(8);
		//
		// System.out.println("\nCreated Linked list is: ");
		// llist.printList();
		//
		// llist.deleteNodeAtPostion(4); // Delete node at position 4
		//
		// System.out.println("\nLinked List after Deletion at position 4: ");
		// llist.printList();

		/* Start with the empty list */
		// LinkedList llist = new LinkedList();
		// llist.push(1);
		// llist.push(3);
		// llist.push(1);
		// llist.push(2);
		// llist.push(1);
		//
		// System.out.println("Count of nodes is " + llist.getCount());

		// Start with the empty list
		// LinkedList llist = new LinkedList();
		//
		// /*
		// * Use push() to construct below list 14->21->11->30->10
		// */
		// llist.push(10);
		// llist.push(30);
		// llist.push(11);
		// llist.push(21);
		// llist.push(14);
		//
		// if (llist.search(llist.head, 21))
		// System.out.println("Yes");
		// else
		// System.out.println("No");

		/* Start with the empty list */
		// LinkedList llist = new LinkedList();
		// llist.push(1);
		// llist.push(3);
		// llist.push(1);
		// llist.push(2);
		// llist.push(1);
		//
		// System.out.println("Count of nodes is " + llist.getCount());

		LinkedList list = new LinkedList();
		// list.head = new Node(85);
		// list.head.next = new Node(15);
		// list.head.next.next = new Node(4);
		// list.head.next.next.next = new Node(20);
		list.push(20);
		list.push(4);
		list.push(15);
		list.push(85);

		System.out.println("Given Linked list");
		list.printList();
		list.reverse();
		System.out.println("");
		System.out.println("Reversed linked list ");
		list.printList();
	}

}

rearrangeCharactersInaStringSuchThatNoTwoAdjacentAreSame

Click for code

// rearrangeCharactersInaStringSuchThatNoTwoAdjacentAreSame/Solution.java

package rearrangeCharactersInaStringSuchThatNoTwoAdjacentAreSame;

import java.util.ArrayList;
import java.util.Iterator;

public class Solution {
	public String solution(String input) {

		ArrayList<Character> arr = new ArrayList<Character>();

		int[] freq = new int[26];
		int max = Integer.MIN_VALUE;
		char maxed_char = ' ';
		// set up the frequency table and setup the max
		for (int i = 0; i < input.length(); i++) {
			freq[input.charAt(i) - 'a']++;
			if (freq[input.charAt(i) - 'a'] > max) {
				max = freq[input.charAt(i) - 'a'];
				maxed_char = input.charAt(i);
			}
			arr.add(input.charAt(i));
		}

		// check if not possible
		if (max > Math.ceil(input.length() / 2.0))
			return "Not Possible";

		// StringBuilder result = new StringBuilder("");
		char result[] = new char[input.length()];

		int i = 1;
		// studentList is a list of students
		Iterator iterator = arr.iterator();
		// loop over the list using iterator
		while (iterator.hasNext()) {
			Character x = (Character) iterator.next();
			// check if result of student is "Fail"
			if (x != maxed_char) {
				result[i] = x;
				i = (i + 2) % input.length();
				iterator.remove();
			}
			
		}
		iterator = arr.iterator();
		while (iterator.hasNext()) {
			Character x = (Character) iterator.next();
			// check if result of student is "Fail"
			assert(x == maxed_char);
			result[i] = x;
			i = (i + 2) % input.length();
		}
		return  new String(result);
		// int i = 0;
		// for (Character x : arr){
		// if (x != maxed_char) {
		// result[i] = x;
		// i = (i + 2) % input.length();
		// }
		// arr.remove(x);
		// }

		// for (int i = 0; i < freq.length; i++) {
		// if (i % 2 == 0)
		// if(input.charAt(i) == maxed_char)
		// result.append(maxed_char);
		// else
		// arr.add(input.charAt(i));
		// else if (!arr.isEmpty()) {
		// result.append(arr.get(0));
		// arr.add(input.charAt(i));
		// }
		// }

		// construct the array _b_c_d_ such that letter 'a'
		// is the max

	}
}

Click for test cases

// rearrangeCharactersInaStringSuchThatNoTwoAdjacentAreSame/SolutionTest.java

package rearrangeCharactersInaStringSuchThatNoTwoAdjacentAreSame;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals("abaca", obj.solution("aaabc"));
		assertEquals("ababa", obj.solution("aaabb"));
		assertEquals("Not Possible", obj.solution("aa"));
		assertEquals("Not Possible", obj.solution("aaaabc"));
	}
}

CountWordsInAgivenString

Click for code

// CountWordsInAgivenString/Solution.java

package CountWordsInAgivenString;

public class Solution {
	public int solution(String input) {
		int wc = 0;
		boolean first = false;
		for (int i = 0; i < input.length(); i++) {

			if (input.charAt(i) == ' '
					|| (String.valueOf(input.charAt(i)) + String.valueOf(input.charAt(i + 1))) == "\t"
					|| (String.valueOf(input.charAt(i)) + String.valueOf(input.charAt(i + 1))) == "\n") {

				if (first) {
					wc++;
					first = false;
				}
			} else // word
			{
				first = true;
			}
		}

		return wc + 1;
	}
}

Click for test cases

// CountWordsInAgivenString/SolutionTest.java

package CountWordsInAgivenString;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class SolutionTest {

	@Test
	public void test1() {
		Solution obj = new Solution();
		assertEquals(5, obj.solution("One two       three\n four\tfive  "));
	}
}

writeaProgramToPrintAllPermutationsOfAGivenString

Click for code

// writeaProgramToPrintAllPermutationsOfAGivenString/Solution.java

package writeaProgramToPrintAllPermutationsOfAGivenString;

public class Solution {
	public static void solution(String input, int l, int r) {
		if (l == r)
			System.out.println(input);
		else
			for (int i = l; i <= r; i++) {
				input = swap(input, l, i);
				solution(input, l + 1, r);
				input = swap(input, l, i);
			}
	}

	public static void main(String[] args) {
		String str = "ABC";
		int n = str.length();
		solution(str, 0, n - 1);
	}

	/**
	 * Swap Characters at position
	 * 
	 * @param a
	 *            string value
	 * @param i
	 *            position 1
	 * @param j
	 *            position 2
	 * @return swapped string
	 */
	public static String swap(String a, int i, int j) {
		char temp;
		char[] charArray = a.toCharArray();
		temp = charArray[i];
		charArray[i] = charArray[j];
		charArray[j] = temp;
		return String.valueOf(charArray);
	}
}

countOfStringsWhereadjacentCharactersAreOfDifferenceOne

Click for code

// countOfStringsWhereadjacentCharactersAreOfDifferenceOne/Solution.java

package countOfStringsWhereadjacentCharactersAreOfDifferenceOne;

public class Solution {
	public static int solution(int n) {
		if (n <= 0)
			return 0;
		if (n == 1)
			return 26;

		int result = 0;
		for (char i = 0; i < 26; i++) {
			if (n == 1)
				result += 1;

			else {
				if (i <= n - 2 || i >= 26 - (n - 2)) {
					result += n - 1; // 2

				} else if (i <= n - 1 || i >= 26 - (n - 1))
					result += n; // 3
				else // ?
					result += n + 1; // 4
			}
		}

		return result;
	}

	static int helper(int n) {
		int result = 0;
		// while (n > 0) {
		result += solution(n);
		// n -= 2;
		// }
		return result;
	}

	public static void main(String[] args) {
		System.out.println(helper(2));
	}
}

findTheMaximumElementInAnArrayWhichIsFirstIncreasingandThenDecreasing

Click for code

// findTheMaximumElementInAnArrayWhichIsFirstIncreasingandThenDecreasing/Solution.java

package findTheMaximumElementInAnArrayWhichIsFirstIncreasingandThenDecreasing;

public class Solution {
	public static int solution(int arr[], int low, int high) {

		int mid = (low + high) / 2;

		if (arr[mid] >= arr[mid - 1] && arr[mid] > arr[mid + 1])
			return arr[mid];

		if (arr[mid] > arr[mid +1] && arr[mid] < arr[mid-1])
			return solution(arr, low, mid-1);
		else
			return solution(arr, mid+1, high);
	}

	/* Driver program to check above functions */
	public static void main(String[] args) {
		int arr[] = { 1, 30, 40, 50, 60, 70, 23, 20 };
		int n = arr.length;
		System.out.println("The maximum element is " + solution(arr, 0, n - 1));

	}
}

findiFmovingElementFromSettoAnotherOnlyIfIncreasesTheAverageInBoth

Click for code

// findiFmovingElementFromSettoAnotherOnlyIfIncreasesTheAverageInBoth/Solution.java

package findiFmovingElementFromSettoAnotherOnlyIfIncreasesTheAverageInBoth;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.*;

import org.junit.Test;

public class Solution {
	public static boolean solution(Set<Integer> a, Set<Integer> b) {
		boolean result = false;

		int sum_a = 0;
		for (Integer x : a) {
			sum_a += x;
		}
		int avg_a = sum_a / a.size();

		int sum_b = 0;
		for (Integer x : b) {
			sum_b += x;
		}
		int avg_b = sum_b / b.size();

		for (Integer x : a) {
			if (((sum_b + x) / (b.size() + 1)) > avg_b && (((sum_a - x) / a.size() - 1) < avg_a)) {
				return true;
			}
		}

		for (Integer x : b) {
			if (((sum_a + x) / (a.size() + 1)) > avg_a && (((sum_b - x) / b.size() - 1) < avg_b)) {
				return true;
			}
		}
		return false;

	}

	public static void main(String[] args) {
		Set<Integer> a = new HashSet<Integer>(Arrays.asList(-5, 2, 3));
		Set<Integer> b = new HashSet<Integer>(Arrays.asList(4, -1, 6));
		assertEquals(true, solution(a, b));
	}
}

🕹 Selected Projects

✉️ Contact

nabil at ece.ubc.ca
ece.ubc.ca/~nabil