public class AVLTree {
static Node root;
static class Node {
int data;
Node left;
Node right;
int height = 1;
Node(int val) {
data = val;
}
}
public static void main(String[] args) {
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
preOrder(root);
root = delete(root, 10);
System.out.println();
/*
* 30 / \ 20 40 / \ \ 10 25 50
*/
preOrder(root);
}
static int calculateHeight(Node n) {
if (n == null) {
return 0;
}
int left = n.left != null ? n.left.height : 0;
int right = n.right != null ? n.right.height : 0;
return Math.max(left, right) + 1;
}
static void preOrder(Node n) {
if (n != null) {
System.out.print(n.data + " ");
preOrder(n.left);
preOrder(n.right);
}
}
static Node insert(Node n, int val) {
if (n == null) {
n = new Node(val);
return n;
}
if (n.data < val) { n.right = insert(n.right, val); } else { n.left = insert(n.left, val); } n = balanceNode(n, val); return n; } private static Node balanceNode(Node n, int val) { n.height = calculateHeight(n); int balance = getBalanceFactor(n); // left left /* z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
* */
if (balance > 1 && getBalanceFactor(n.left) >= 0) {
n = rightRotaion(n);
}
// left right
/* z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2*/
if (balance > 1 && getBalanceFactor(n.left) < 0) { n.left = leftRotaion(n.left); n = rightRotaion(n); } // right right /* z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
*/
if (balance < -1 && getBalanceFactor(n.right) <= 0) { n = leftRotaion(n); } // right left /* z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z x / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4*/
if (balance < -1 && getBalanceFactor(n.right) > 0) {
n.right = rightRotaion(n.right);
n = leftRotaion(n);
}
return n;
}
private static int getBalanceFactor(Node n) {
if (n == null) {
return 0;
}
int left = n.left != null ? n.left.height : 0;
int right = n.right != null ? n.right.height : 0;
return left - right;
}
static Node rightRotaion(Node n) {
Node root = n.left;
n.left = root.right;
root.right = n;
n.height = calculateHeight(n);
root.height = calculateHeight(root);
return root;
}
static Node leftRotaion(Node n) {
Node root = n.right;
n.right = root.left;
root.left = n;
n.height = calculateHeight(n);
root.height = calculateHeight(root);
return root;
}
private static Node delete(Node temproot, int val) {
if (temproot != null) {
if (temproot.data > val) {
temproot.left = delete(temproot.left, val);
} else if (temproot.data < val) {
temproot.right = delete(temproot.right, val);
} else {
//no child or leaf node
if (temproot.right == null && temproot.left == null) {
temproot = null;
} else if (temproot.right != null && temproot.left != null) {
Node nextNode = getNextnode(temproot.right);
//replace with inorder nexr node.
if (nextNode != null) {
temproot.data = nextNode.data;
temproot.right = delete(temproot.right, nextNode.data);
} else {
temproot = null;
}
} else
//only one child
{
if (temproot.right != null) {
temproot = temproot.right;
} else {
temproot = temproot.left;
}
}
}
}
if (temproot != null) {
temproot = balanceNode(temproot, val);
}
return temproot;
}
private static Node getNextnode(Node temproot) {
while (temproot != null && temproot.left != null) {
temproot = temproot.right;
}
return temproot;
}
}
Majority Elements in An Array
import java.util.Scanner;
//Majority Element finding with running O(n) time with O(1) extra space.
public class MajorityElements {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int elements[] = new int[n];
for (int i = 0; i < elements.length; i++) {
elements[i] = scan.nextInt();
}
int count = 1;
int index = 0;
// iterate through the array and try to increase the count of matching
// numbers, if the element is majority it will stay till end.
for (int i = 1; i < elements.length; i++) {
if (elements[i] == elements[index]) {
count++;
} else {
count--;
}
// if not same element reset element to current number.
if (count == 0) {
index = i;
count = 1;
}
}
count = 0;
// Make sure the elements occurs more than half.
for (int i = 0; i < elements.length; i++) {
if (elements[i] == elements[index]) {
count++;
}
}
if (count == (n / 2 + 1)) {
System.out.println("Majority Element:" + elements[index]);
} else {
System.out.println("No Majority");
}
}
}
Find Next Palindrome
Find next palindrome of given number,Naive approach is to increment by one and check is it palindrome. We can find next palindrome by 3 condition.
- Its full of 9’s.[Need increment number by 2 ]
- Given number is palindrome.[Increment the half and mirror]
- Given number is not a palindrome.[Check if mirror different numbers alone is greater than given number, if yes you got result, else go to second approach.]
import java.util.Scanner;
public class NextPalindrome {
public static void main(String[] args) {
while (true) {
String result = "";
Scanner scan = new Scanner(System.in);
String inp = scan.next();
int type = checkType(inp);
if (type == 1) {
//All nine need to be added 2 with value
StringBuilder sb = new StringBuilder("1");
for (int i = 0; i < inp.length() - 1; i++) { sb.append("0"); } sb.append("1"); result = sb.toString(); } else if (type == 2) { //If palindrome means increament and mirror result = incrementAndMirror(inp); } else { //If not palindrome, mirror left part and check it is greater then given number , // if yes reaturn result, else increment and mirror int i, j, m = inp.length() / 2; if ((inp.length() % 2) == 0) { i = m - 1; j = m; } else { i = m - 1; j = m + 1; } while (i > -1 && j < inp.length()) {
if (inp.charAt(i) == inp.charAt(j)) {
i--;
j++;
} else {
break;
}
}
if (i < 0 || inp.charAt(i) < inp.charAt(j)) {
result = incrementAndMirror(inp);
} else {
// Mirror non palindrom part in given number
result = inp.substring(0, j) + new StringBuilder(inp.substring(0, i + 1)).reverse();
}
}
System.out.println(result);
}
}
private static String incrementAndMirror(String inp) {
String result;
String left = "", mid = "";
int m = inp.length() / 2;
boolean even = (inp.length() % 2) == 0;
if (even) {
left = inp.substring(0, (m));
StringBuilder sb = new StringBuilder((Integer.parseInt(left) + 1) + "");
result = sb.toString() + sb.reverse().toString();
} else {
left = inp.substring(0, (m));
mid = inp.charAt((m)) + "";
StringBuilder sb = new StringBuilder((Integer.parseInt(left + mid) + 1) + "");
result = sb.toString() + sb.deleteCharAt(sb.length() - 1).reverse().toString();
}
return result;
}
private static int checkType(String inp) {
//Full of 9's
if (inp.matches("[9]+")) {
return 1;
}
int i = 0, j = inp.length() - 1;
while (i < j) {
if (inp.charAt(i) != inp.charAt(j)) {
//Not a palindrome
return 0;
}
i++;
j--;
}
//Palindrome
return 2;
}
}
Time complexity and Space complexity : O(1)
Missing Numbers
Numeros, the Artist, had two lists AA and BB, such that BB was a permutation of AA. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers were left out of AA. Can you find the missing numbers?
Notes
If a number occurs multiple times in the lists, you must ensure that the frequency of that number in both lists is the same. If that is not the case, then it is also a missing number.
You have to print all the missing numbers in ascending order.
Print each missing number once, even if it is missing multiple times.
The difference between maximum and minimum number in BB is less than or equal to 100100.
Problem Link: HackerRank
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Map < Integer, Integer > map = new HashMap < Integer, Integer > ();
int n = scan.nextInt();
for (int i = 0; i < n; i++) {
int num = scan.nextInt();
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
List < Integer > result = new ArrayList < Integer > ();
int t = scan.nextInt();
for (int i = 0; i < t; i++) {
int num = scan.nextInt();
if (map.containsKey(num)) {
map.put(num, map.get(num) - 1);
} else {
result.add(num);
}
}
for (Integer key: map.keySet()) {
if (map.get(key) != 0) {
result.add(key);
}
}
Collections.sort(result);
for (Integer val: result) {
System.out.print(val + " ");
}
}
}
The Maximum Subarray
Problem Statement:
HackerRankLink
Given an array A={a1,a2,…,aN} of N elements, find the maximum possible sum of a
Contiguous subarray
Non-contiguous (not necessarily contiguous) subarray.
Empty subarrays/subsequences should not be considered.
Sample Input
2
4
1 2 3 4
6
2 -1 2 3 4 -5
Sample Output
10 10
10 11
/**
* Created by sidharthan on 6/2/16.
*/
import java.util.Scanner;
public class MaxSubArray {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] res1 = new int[n];
int[] res2 = new int[n];
for (int i = 0; i < n; i++) {
subArray(res1, res2, i, scan);
}
for (int i = 0; i < n; i++) {
System.out.println(res1[i] + " " + res2[i]);
}
}
static void subArray(int[] res1, int[] res2, int i, Scanner scan) {
int t = scan.nextInt();
if(t==0)
{
return;
}
int max = 0, currMax = 0, currNCMax = 0, maxNC = 0;
int vals = scan.nextInt();
//Choose first number as max
currMax = vals;
currNCMax = vals;
maxNC = vals;
max = vals;
for (int j = 1; j < t; j++) { vals = scan.nextInt(); currMax = Math.max(currMax + vals, vals); max = Math.max(currMax, max); //If the negative number in array, check its greater or not. if (currNCMax + vals > vals) {
currNCMax = Math.max(currNCMax + vals, currNCMax);
} else {
currNCMax = vals;
}
maxNC = Math.max(currNCMax, maxNC);
}
res1[i] = max;
res2[i] = maxNC;
}
}
Time Complexity : O(n)
Space Complexity : O(1)
Sudoku Solver
Problem Statement:Given a partially filled 9 x 9 sudoku board, you need to output a solution to it.
Problem Source: HackerRank
Input:
2
0 0 0 0 0 0 0 0 0
0 0 8 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 8 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0
Output:
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
Pretty Version:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static void sudoku_solve(int[][] grid) {
if (solve(grid)) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
System.out.print(grid[i][j]+" ");
}
System.out.println();
}
}
}
static boolean solve(int[][] grid) {
Integer x = -1, y = -1;
Map<String,Integer> map= new HashMap<>();
//check for completion
if (isFull(grid,map)){
return true;
}
else{
x=map.get("x");
y=map.get("y");
for (int i = 1; i <= grid.length; i++) {
//check is safe to place a digit in a place
if(isSafe(grid,x,y,i)){
grid[x][y] = i;
if (solve(grid))
return true;
//Reset values for backtracking
grid[x][y] = 0;
}
}
}
return false;
}
//used to check its done if not return values
static boolean isFull(int[][] grid,Map<String,Integer> map) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
if (grid[i][j] == 0) {
map.put("x",i);
map.put("y",j);
return false;
}
}
}
return true;
}
static boolean isSafe(int[][] grid,int x,int y,int j)
{
for(int i=0;i<grid.length;i++)
{
//check horizontal
if(grid[x][i]==j)
return false;
//vertical
if(grid[i][y]==j)
return false;
}
//Find square Block
int xq=x/3*3;
int yq=y/3*3;
for(int a=xq;a<xq+3;a++)
{
for(int b=yq;b<yq+3;b++)
{
if(grid[a][b]==j)
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n;
int board[][] = new int[9][9];
n = in .nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
board[j][k] = in .nextInt();
}
}
sudoku_solve(board);
}
}
}
Minified:
import java.util.*;public class S{static void ss(int[][]g){if(s(g)){for(int i=0;i<9;i++){String s=””;for(int j=0;j<9;j++){s+=g[i][j]+” “;}System.out.println(s);}}}static boolean s(int[][]g){int l[]=new int[2];if(iF(g,l))return true;int x=l[0];int y=l[1];for(int i=1;i<=9;i++){if(iS(g,x,y,i)){g[x][y]=i;if(s(g))return true;g[x][y]=0;}}return false;}static boolean iF(int[][]g,int[]l){for(int i=0;i<9;i++)for(int j=0;j<9;j++){if(g[i][j]==0){l[0]=i;l[1]=j;return false;}}return true;}static boolean iS(int[][]g,int x,int y,int j){int i;for(i=0;i<9;i++){if(g[x][i]==j)return false;if(g[i][y]==j)return false;}int xq=x/3*3;int yq=y/3*3;for(int a=xq;a<xq+3;a++){for(int b=yq;b<yq+3;b++){if(g[a][b]==j)return false;}}return true;}public static void main(String[]a){Scanner p=new Scanner(System.in);int b[][]=new int[9][9];int n=p.nextInt();for(int i=0;i<n;i++){for(int j=0;j<9;j++)for(int k=0;k<9;k++)b[j][k]=p.nextInt();ss(b);}}}
Time Complexity: O(n^m) i.e. 9^9 in worst case.
Find perfect square numbers with in given range.
Input :
2
3 9
17 24
output:
2 // 4 and 9 are squares.
0 // no squares in between them
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.lang.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int arr[]= new int[n];
for(int i =0;i<n;i++)
{
int s=scan.nextInt();
int e=scan.nextInt();
int a=(int)Math.ceil(Math.sqrt(s));
int b=(int)Math.floor(Math.sqrt(e));
arr[i]=b-a+1;
}
for(int ar:arr)
{
System.out.println(ar);
}
}
}
By finding starting number square root and end number square root.we can get differences.
Example:
sqrt of 3 is 2(ceil)
sqrt of 14 is 3(floor)
so difference is 1 and we need add 1 to normalize ceil and floor.
Find next square root element using ceil
Find previous square root element using floor.
Find difference and include first square root value too by adding 1 to difference.
Shuffle middle letters of words in given String
Input: “A quick brown fox jumped over the high fence”
Example Output: “A qicuk bowrn fox jmpued over the hgih fcene”
goal: output sentence != input sentence
import java.io.*;
import java.util.*;
class Solution {
public static void main(String args[]) {
Scanner scan = new Scanner(System. in );
int n=scan.nextInt();
String input = "";
String output = "";
for (int i = 0; i < n; i++) {
input += scan.next();
input += " ";
}
String stringArray[] = input.split(" ");
for (int i = 0; i < stringArray.length; i++) {
String currentWord = stringArray[i];
if (currentWord.length() < 4) {
output += currentWord;
} else {
Random random = new Random();
char[] charArray = currentWord.toCharArray();
for (int j = 1; j < currentWord.length() - 1; j++) {
int pos = random.nextInt(currentWord.length() - 3) + 1;
char temp = charArray[j];
charArray[j] = charArray[pos];
charArray[pos] = temp;
}
output += new String(charArray);
}
output += " ";
}
System.out.print(output.trim());
}
}
Time Complexity: O(n)
Corner Cases:
1)The Solution Will not work for words with less than 4 chars ex: a, BB,the
2)Will not work on Characters with repeated chars.Ex: aaaaaaaaaaaaa or BBBBB
Insertion Sorting
Split array into two arrays.Sorted array and unsorted array.Move elements from unsorted array in to sorted array at its correct position.
for (int j = 1; j < array.length; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];//Move element one place right till we reach its position
i--;
}
array[i + 1] = key;//place the key at its position
printNumbers(array);
}
Time complexity:O(n^2)
Check whether two strings are anagram of each other
import java.io.*;
import java.util.*;
public class Solution {
static boolean isAnagram(String A, String B) {
if (A.length() != B.length()) {
return false;
}
if (A.equals(B)) {
return true;
} else {
A = A.toLowerCase();
B = B.toLowerCase();
int charArrayA[] = new int[256];
int charArrayB[] = new int[256];
Arrays.fill(charArrayA, 0);
Arrays.fill(charArrayB, 0);
for (int i = 0; i < A.length(); i++) {
charArrayA[A.charAt(i)]++;
charArrayB[B.charAt(i)]++;
}
for (int i = 0; i < 256; i++) {
// check count of each char is equal in both string
if (charArrayA[i] != charArrayB[i]) return false;
}
return true;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System. in );
String A = sc.next();
String B = sc.next();
boolean ret = isAnagram(A, B);
if (ret) System.out.println("Anagrams");
else System.out.println("Not Anagrams");
}
}
Complexity: O(n)
Learn Something new 