### Search if a value exists in binary search tree (BST)

Search
Algorithms
``````import java.util.*;

class Node {
int value;
Node left;
Node right;

public Node(int value) {
this.value = value;
}
}

class BST {
public static boolean search(Node root, int key) {
if(root == null) {
return false;
}

while(root != null) {
if(root.value == key) {
return true;
}

if(root.value > key) {
root = root.left;
} else if(root.value < key) {
root = root.right;
}
}

return false;
}
}``````

### Test Kumite

This is a test kumite

``````var getAge = function(today, dob) {
if(!today || !dob) {
return null;
}

var now = new Date(today);
return now.getYear() - new Date(dob).getYear();
};``````

### Return Largest Possible Number

Given a list of numbers, return the combination that is largest number.

As output can be large, return the result in `String` format.

Example:

Input:

`[5, 50, 56]`

Output:

`56550`

``````import java.util.*;

class Solution {
public static String largestNumber(Integer[] nums) {
Arrays.sort( nums, new Comparator<Integer>() {

@Override
public int compare(Integer a, Integer b) {
String aStr = a.toString();
String bStr = b.toString();

return (aStr + bStr).compareTo(bStr + aStr) * -1;
}

} );

String result = "";
for(Integer num : nums) {
result += num.toString();
}

return result;
}
}``````

### Find Peak Element

Given array of integer elements, find the index of peak element in `O(Log N)` time complexity.

A peak element is an element that is greater than its neighbors. Given an input array where `num[i] != num[i + 1]`, find a peak element and return its index. Array may contain multiple peaks, in that case return index of any peak.

Example:

Input:
`1 2 3 1`

Output:
`2`

because peak element is `3` and it is at index `2`.

``````import java.util.*;;

class Solution {
public static int peakIndex(int[] nums) {
int left = 0;
int right = nums.length - 1;
int peak = -1;

while(left <= right) {
if(left == right) {
peak = left;
break;
}

int mid = (left + right) / 2;

if(nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}

return peak;
}
}``````

### Has duplicates

Write a program to find if given array contains duplicate elements or all elements are unique.
Your function should output `true` if there are duplicates, `false` if all elements are unique.

Example:

Input:
`1 4 3 2 6 4`

Output:
`true`

Input:
`1 4 3 2 6 5`

Output:
`false`

``````import java.util.*;

class Solution {
/**
*  Checks if given array contains duplicate elements.
*  Complexity: O(N)
*  @author     Jayesh Chandrapal

*  @param nums integer array of elements
*  @return     true if duplicate elements are found, false otherwise
*/
public static boolean hasDuplicates(int[] nums) {
Set<Integer> set = new HashSet<Integer>();

for(int i = 0, len = nums.length; i < len; i++) {
if(set.contains(nums[i])) {
return true;
} else {
}
}

return false;
}
}``````

### Matching Brackets

Stacks
Arrays

Given an expression string exp, examine whether the pairs and the orders of "{", "}", "(", ")", "[", "]" are correct in exp.

For example, the program should return `true` for `[()]{}{[()()]()}` and `false` for `[(])`.

Check provided test cases to see expected behaviour for different inputs.

``````/**
*  Check if brackets are matching.
*  Time Complexity: O(N), Space Complexity: O(N)
*
*  @author Jayesh Chandrapal
*/
import java.util.*;
import java.lang.*;
import java.io.*;

class MatchingBrackets {

/**
*  Checks if given input string contains matching brackets.
*
* @params str  input string to be checked
* @returns     boolean value indicating if given string contains matching brackets
*/
public static boolean isBalanced(String str) {
boolean balanced = true;
Stack<Character> stack = new Stack<Character>();

for(Character c : str.toCharArray()) {
if(c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if(stack.isEmpty()) {
balanced = false;
break;
}

Character top = stack.peek();
if((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')) {
stack.pop();
} else {
balanced = false;
break;
}
}
}

return balanced && stack.isEmpty();
}
}``````

### Power of Two

Write a function that determines if given number is a power of two. A power of two means a number of the form `2^n` where `n` is an integer, i.e. the result of exponentiation with number two as the base and integer `n` as the exponent. i.e. 1024 is a power of two: it is `2^10`.

Example:

`power_of_two(4096) # true`

`power_of_two(333) # false`

``````def power_of_two( n ):
return n & ( n - 1 ) == 0``````

### Merge Sort

Implementation of Merge Sort.

• Time Complexity: `O(n log(n))`

• Space Complexity: `O(n)`

• Preserves the input order of equal elements in the sorted output.

• Type of Divide-and-Conquer algorithm.

• Efficient at handling slow-to-access sequential media.

• Well-suited for sorting huge amounts of data that does not fit into memory.

``````class Sort:

def merge_sort(self, nums):
if nums == None: return None

if len(nums) > 1:
mid = len(nums) // 2
lefthalf = nums[:mid]
righthalf = nums[mid:]

self.merge_sort(lefthalf)
self.merge_sort(righthalf)

i = 0
j = 0
k = 0

while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
nums[k] = lefthalf[i]
i += 1
else:
nums[k] = righthalf[j]
j += 1
k += 1

while i < len(lefthalf):
nums[k] = lefthalf[i]
i += 1
k += 1

while j < len(righthalf):
nums[k] = righthalf[j]
j += 1
k += 1

return nums``````

### Insertion Sort

Sorting
Algorithms

Implementation of Insertion Sort.

• Time Complexity: Worst case: `O(n^2)`, Best case: `O(n)`

• Space Complexity: `O(1)`

• Useful when list size is small.

• only scans as many elements as needed to determine the correct location.

• More efficient than bubble or selection sort.

• Efficient for data sets that are already substantially sorted.

• Requires more writes because the inner loop can require shifting large sections of the sorted portion of the array.

• Can sort a list as it receives it.

``````class Sort:

def insertion_sort(self, nums):
if nums is None:
return None

for i in range(1, len(nums)):
currentvalue = nums[i]
position = i

while position > 0 and nums[position - 1] > currentvalue:
nums[position] = nums[position - 1]
position -= 1

nums[position] = currentvalue
return nums``````

### Selection Sort

Sorting
Algorithms

Implementation of Selection Sort.

• Time Complexity: `O(n^2)`
• Space Complexity: `O(1)`
• Useful when list size is small
• Preferable to insertion sort in terms of number of writes (`O(n)` swaps versus `O(n2)` swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.
``````class Sort:

def selection_sort(self, nums):
if nums == None: return None

for i in range(0, len(nums) - 1):
minIndex = i

for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]:
minIndex = j

nums[i], nums[minIndex] = nums[minIndex], nums[i]
return nums``````

### Most frequently appearing number in given array

Example:

Find first most frequently occuring number in given array.

Given input `{1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2}`,
output should be `3` as it has highest frequency of occurence.

Note: This solution uses LinkedHashMap to preserve order of entry.

Code
Diff
• ``````import java.util.*;

/**
Time Complexity  : O(N)
Space Complexity : O(N)
*/
class MaxOccurence {
public static int findMax(int[] nums) {
}

private static int findMaxOccurenceLinkedHashMap(int[] nums) {
int maxKey = 0, maxNum = 0;

if(nums.length < 1) return -1;
if(nums.length == 1) return nums[0];

Map<Integer, Integer> counts = new LinkedHashMap<Integer, Integer>(nums.length);

for(int i = 0, len = nums.length; i < len; i++) {
if(!counts.containsKey(nums[i])) {
counts.put(nums[i], 1);
} else {
counts.put(nums[i], (counts.get(nums[i]) + 1));
}
}

for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (entry.getValue() > maxNum) {
maxKey = entry.getKey();
maxNum = entry.getValue();
}
}

return maxKey;
}
}``````
•  1 1 ```import java.util.*; ``` 2 2 3 3 ```/** ``` 4 4 ``` Time Complexity : O(N) ``` 5 5 ``` Space Complexity : O(N) ``` 6 6 ```*/ ``` 7 7 ```class MaxOccurence { ``` 8 8 ``` public static int findMax(int[] nums) { ``` 9 − ``` return findMaxOccurenceCountArray(nums); ``` 9 + ``` return findMaxOccurenceLinkedHashMap(nums); ``` 10 10 ``` } ``` 11 11 ``` ``` 12 − ``` private static int findMaxOccurenceCountArray(int[] nums) { ``` 13 − ``` int maxNum = 0; ``` 14 − ``` int maxCount = 0; ``` 12 + ``` private static int findMaxOccurenceLinkedHashMap(int[] nums) { ``` 13 + ``` int maxKey = 0, maxNum = 0; ``` 15 15 ``` ``` 16 16 ``` if(nums.length < 1) return -1; ``` 17 17 ``` if(nums.length == 1) return nums[0]; ``` 18 18 ``` ``` 19 − ``` int[] counts = new int[nums.length]; ``` 18 + ``` Map counts = new LinkedHashMap(nums.length); ``` 20 20 ``` ``` 21 21 ``` for(int i = 0, len = nums.length; i < len; i++) { ``` 22 − ``` counts[nums[i]]++; ``` 23 − ``` if(counts[nums[i]] > maxCount) { ``` 24 − ``` maxCount = counts[nums[i]]; ``` 25 − ``` maxNum = nums[i]; ``` 21 + ``` if(!counts.containsKey(nums[i])) { ``` 22 + ``` counts.put(nums[i], 1); ``` 23 + ``` } else { ``` 24 + ``` counts.put(nums[i], (counts.get(nums[i]) + 1)); ``` 26 26 ``` } ``` 27 27 ``` } ``` 28 28 ``` ``` 29 − ``` return maxNum; ``` 28 + ``` for (Map.Entry entry : counts.entrySet()) { ``` 29 + ``` if (entry.getValue() > maxNum) { ``` 30 + ``` maxKey = entry.getKey(); ``` 31 + ``` maxNum = entry.getValue(); ``` 32 + ``` } ``` 33 + ``` } ``` 34 + ``` ``` 35 + ``` return maxKey; ``` 30 30 ``` } ``` 31 31 ```} ```

### Most frequently appearing number in given array

Example:

Find first most frequently occuring number in given array.

Given input `{1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2}`,
output should be `3` as it has highest frequency of occurence.

``````import java.util.*;

/**
Time Complexity  : O(N)
Space Complexity : O(N)
*/
class MaxOccurence {
public static int findMax(int[] nums) {
return findMaxOccurenceCountArray(nums);
}

private static int findMaxOccurenceCountArray(int[] nums) {
int maxNum = 0;
int maxCount = 0;

if(nums.length < 1) return -1;
if(nums.length == 1) return nums[0];

int[] counts = new int[nums.length];

for(int i = 0, len = nums.length; i < len; i++) {
counts[nums[i]]++;
if(counts[nums[i]] > maxCount) {
maxCount = counts[nums[i]];
maxNum = nums[i];
}
}

return maxNum;
}
}``````

### HashMap Example

Hashes
Data Structures

Using HashMap in Java.

``````/* HashMap Example */

import java.util.*;
import java.lang.*;
import java.io.*;

class HashMapDemo
{
public static void main (String[] args) throws java.lang.Exception
{
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(1, 1);
map.put(2, 1);
map.put(3, 1);
map.put(4, 1);
map.put(5, 1);
map.put(6, 1);

for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
System.out.println(key + " " + value);
}
}
}``````

### Generate Prime Numbers

Generate prime numbers within a given minimum and maximum.
min and max values should be positive (greater than 0).

``````import java.util.*;

public class Primes {
public static List<Integer> generatePrimes(int min, int max) {
List<Integer> primes = new ArrayList<Integer>();
boolean isPrime = false;

if((min > max) || min < 0 || max <= 0) {
return null;
}

for(int i = min; i <= max; i++) {
long endLimit = (long)Math.floor(Math.sqrt(i));
isPrime = true;
for(long j = 2; j <= endLimit; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}

if(isPrime) {
}
}

return primes;
}
}``````

### Balanced Parenthesis

Given a string of open and closed parenthesis output "Balanced" if the parenthesis are balanced or "Unbalanced" otherwise.

A string is balanced if it consists entirely of pairs of opening/closing parenthesis (in that order), none of which mis-nest.

Example input:
(())())

Example output:
Unbalanced

Example input:
(()())

Example output:
Balanced

``````function balanced_parenthesis(s) {
if(s == null) return null;

var i = 0,
startCnt = 0,
n = s.length;

for(i = 0; i < n; i++) {
if(s[i] === "(") {
startCnt += 1;
} else if(s[i] === ")") {
startCnt -= 1;
if(startCnt < 0) {
break;
}
}
}

if(startCnt !== 0) {
return 'Unbalanced';
} else {
return 'Balanced';
}
}``````