Check if a Binary Tree is a Mirror Image or Symmetric..
Check if a given binary tree is a symmetric or you can also say check whether tree is a mirror of itself (ie, symmetric around its center)
Lets see sample input and output:
Check if a Binary Tree is a Mirror Image or Symmetric in Java.
Check if a given binary tree is a symmetric or you can also say check whether tree is a mirror of itself (ie, symmetric around its center)
Lets see sample input and output:
Find Container with Most Water in Java
Find Container with Most Water.
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You cannot slant the container.
Lets understand what is the input and the expected output.
Find Power of a Number using Recursion in Java
Find Power of a Number using Recursion in Java.
Given two integers base and number, write a function to compute base^number.
Assume that base and number are small and will not cause integer overflow.
Lets understand what is the input and the expected output.
Find length of longest substring without repeating characters in Java
Length of the longest substring without repeating characters in Java.
Given a string, find the length of the longest unique substring.
Lets understand what is the input and the expected output.
Maximum consecutive one’s in a binary array
Find the maximum consecutive 1's in an array of 0's and 1's. And Find length of the longest consecutive One's in binary representation.
Given a binary array, find the maximum number of consecutive 1s in this array or find the maximum consecutive 1's in an array of 0's and 1's.
Lets understand what is the input and the expected output.
Find sum of digits of a number until sum becomes single digit
Find sum of digits of a number until sum becomes single digit.
Given a non-negative integer, repeatedly add all its digits until the result has only one digit.
Lets understand what is the input and the expected output.
Hamming distance between two Integers in Java.
Hamming distance between two Integers in Java.
Given two integers, find the hamming distance between them.
Hamming Distance: hamming distance is the count of bits that are different at same position in a binary representation of two numbers.
Lets understand what is the input and the expected output.
Check if a binary tree is subtree of another binary tree
Check if a binary tree is subtree of another binary tree.
Given two binary trees, check if the first tree is subtree of the second one.
A tree is called subtree if all the nodes and its child of the subtree(S) is present in Tree(T) in the same structure.
Lets understand what is the input and the expected output.
Find element in a sorted array whose frequency is greater than or equal to n/2.
Find Majority Element in a Sorted Array in Java? OR Find element in a sorted array whose frequency is greater than or equal to n/2.
Given a sorted array, find the number in array that appears more than or equal to n/2 times.
Condition: there will always be element which is repeated more than n/2 times.
Lets understand with the help of example below,
Algorithm
If the element is sorted and such element is always present which is repeated more than n/2 times in that case the repeated element must be the middle element of the array.If the most repeated element is starting from 0th index, in that case it has to stretch till middle index then only it will be repeated n/2 times,
If the most repeated element is present at last index, if that is the case than middle index should also contain the same element than only it would have be repeated n/2 times,
If the most repeated starts some where in the middle in this case it is sure it would be passing from the middle index for having its count greater than or equal to n/2 times.
package com.javabypatel.arrays;
public class MajorityOfElementInSortedArray {
public static void main(String args[]) {
int arr[] = { 1, 2, 3, 3 };
int n = arr.length;
System.out.println(findMajorityElement(arr, n));
}
public static int findMajorityElement(int arr[], int n) {
return arr[n / 2];
}
}
You may also like to see
Advanced Java Multithreading Interview Questions & Answers
Type Casting Interview Questions and Answers In Java?
Exception Handling Interview Question-Answer
Method Overloading - Method Hiding Interview Question-Answer
How is ambiguous overloaded method call resolved in java?
Method Overriding rules in Java
Interface interview questions and answers in Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Check Majority Element in a Sorted Array in Java.
Majority Element in a Sorted Array in Java?
Given a sorted array, we need to find if a given x is a majority element.
What is Majority element: Number occurring more than half the size of the array is called Majority element.
Lets understand with the help of example below,
Algorithm
We will see two solutions one having time complexity O(N) and one using Binary Search approach having time complexity O(log N).
As the array is sorted we can use binary search to find the index of first occurrence of element to search and once that is found, we can directly add n/2 in that index to see if that index also contains the same element as element to search and if yes, then we have majority element else not.
package com.javabypatel.arrays;
public class MajorityOfElementInSortedArray {
public static void main(String[] args) {
int arr[];
//arr = new int[] {1, 2, 2, 2, 3, 3, 3};
//arr = new int[] {1, 1, 1, 2, 2, 3};
//arr = new int[] {1, 1, 1, 2, 2, 2, 2};
//arr = new int[] {2, 2};
arr = new int[] {2};
int x = 3;
boolean result = isMajority(x, arr, arr.length);
System.out.println(result);
result = isMajorityUsingBinarySearch(x, arr, arr.length);
System.out.println(result);
}
//Time complexity O(N)
private static boolean isMajority(int elementToSearch, int[] arr, int length) {
//Here we are calculating till what index we need to search for element.
//we need to only search till length/2 index for even length array and length/2+1 for odd length array after that index if element is present/absent
//doesn't matter as count of the element would not be greater than length/2+1 after crossing middle element.
int searchUptil = length % 2 == 0 ? length / 2 : length / 2 + 1;
for (int i = 0; i < searchUptil; i++) {
//If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
//if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
if(arr[i] == elementToSearch && arr[i + arr.length/2] == elementToSearch) {
return true;
}
}
return false;
}
private static boolean isMajorityUsingBinarySearch(int elementToSearch, int[] arr, int length) {
return isMajorityHelper(elementToSearch, arr, 0, length-1);
}
/*
In this approach we will find the first instance of the elementToSearch using BinarySearch after that
we will directly check the index n/2 from that point and if it is same as elementToSearch then we have
n/2 count of elementToSearch else not.
*/
static boolean isMajorityHelper(int elementToSearch, int[] arr, int start, int end) {
if (start > end) {
return false;
}
int mid = start + (end - start) / 2;
if (arr[mid] == elementToSearch && (mid == 0 || arr[mid-1] < elementToSearch)) {
//If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
//if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
if((mid + arr.length/2 < arr.length) && arr[mid + arr.length/2] == elementToSearch) {
return true;
}
return false;
} else if (arr[mid] < elementToSearch) {
//Search on right side of mid.
return isMajorityHelper(elementToSearch, arr, mid + 1, end);
} else {
//if the elementToSearch is found and is not the first instance or
//if elementToSearch is greater than mid, continue searching on left side of mid.
return isMajorityHelper(elementToSearch, arr, start, mid - 1);
}
}
}
You may also like to see
Advanced Java Multithreading Interview Questions & Answers
Type Casting Interview Questions and Answers In Java?
Exception Handling Interview Question-Answer
Method Overloading - Method Hiding Interview Question-Answer
How is ambiguous overloaded method call resolved in java?
Method Overriding rules in Java
Interface interview questions and answers in Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
