Monday, August 21, 2017
Monday, August 14, 2017
Sunday, August 13, 2017
Saturday, August 12, 2017
Friday, August 11, 2017
Wednesday, August 9, 2017
Tuesday, August 8, 2017
Monday, August 7, 2017
Thursday, August 3, 2017
Wednesday, August 2, 2017
Tuesday, August 1, 2017
Monday, July 31, 2017
Sunday, July 30, 2017
Saturday, July 29, 2017
Friday, July 28, 2017
Thursday, July 27, 2017
Wednesday, July 26, 2017
Monday, July 24, 2017
Count number of occurrences (or frequency) in a sorted array
/*
Problem: Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]
Solution :- Find the first occurrence and last occurrence of x in the array then the count last-first+1
*/
public class CountOccurences {
public int countOccurrencesLinear(int arr[], int x) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x)
count++;
}
return count;
}
public int countOccurrences(int[] nums, int x) {
int first = first(nums, 0, nums.length - 1, x);
if (first == -1)
return 0;
int last = last(nums, 0, nums.length - 1, x);
return (last - first) + 1;
}
/*
This is binary search with difference that even when we find matching element we have to keep
going left till we find first occurrence
*/
public int first(int[] nums, int low, int high, int x) {
if (low < high) {
int mid = low + (high - low) / 2;
//This is the differentiators if the num[mid]==x but the element before current is not
//equal to mid then we found first occurance
if (nums[mid] == x && nums[mid - 1] < x) {
return mid;
} else if (nums[mid] < x) {
return first(nums, mid + 1, high, x);
} else {
return first(nums, low, mid - 1, x);
}
}
return -1;
}
public int last(int[] nums, int low, int high, int x) {
if (low < high) {
int mid = low + (high - low) / 2;
// If we found the element then check if the element after this is equal to current if not
//that means we found the last occurance
if (nums[mid] == x && nums[mid + 1] > x) {
return mid;
} else if (nums[mid] < x) {
return first(nums, mid + 1, high, x);
} else {
return first(nums, low, mid - 1, x);
}
}
return -1;
}
}
Find the largest pair sum in an unsorted array
package com.geekforgeeks.arrays;
import java.util.Arrays;
import java.util.Random;
/*
Problem: Given an unsorted of distinct integers, find the largest pair sum in it.
For example, the largest pair sum in {12, 34, 10, 6, 40} is 74.
*/
public class FindLargestPairSumInSortedArray {
public static void main(String[] argv){
Random random = new Random();
int[] nums = new int[10];
for(int i = 0; i< 10; i++) {
nums[i]= random.nextInt(100);
}
System.out.println(Arrays.toString(nums));
FindLargestPairSumInSortedArray findLargestPairSumInSortedArray = new FindLargestPairSumInSortedArray();
int largestPairSumInSortedArray = findLargestPairSumInSortedArray.largestPairSumInSortedArray(nums);
Arrays.sort(nums);
int maxSum = nums[nums.length-1]+ nums[nums.length-2];
System.out.println(Arrays.toString(nums) + " " + maxSum);
System.out.println("Result "+ largestPairSumInSortedArray);
}
/*
Initialize the largest and second largest element in sorted array at the start and then iterate
through rest of the array
1) If the current element is less than second max continue
2) If the current element is greater than max, replace second max with max and max with current element
3) If not replace second max sum with the current element
*/
public int largestPairSumInSortedArray(int[] nums){
int max = Math.max(nums[0],nums[1]);
int secondMax = Math.min(nums[0],nums[1]);
for(int i = 2 ; i < nums.length; i++ ){
if(nums[i] <= secondMax)
continue;
if(nums[i] > max){
secondMax = max;
max =nums[i];
}else{
secondMax=nums[i];
}
}
return max+secondMax;
}
}
Closest Pair of elements in sorted array
import java.util.Arrays;
import java.util.Random;
public class ClosestPair {
public static void main(String[] argv){
Random random = new Random();
int[] nums = new int[10];
for(int i = 0; i< 10; i++) {
nums[i]= random.nextInt(1000);
}
ClosestPair closestPair = new ClosestPair();
int[] pair = closestPair.closestPair(nums);
System.out.println(Arrays.toString(pair));
}
/*
Problem: Given sorted array find the closest pair of elements
Solution: First sort the array then perform a linear search with 2 elements at a time to find out
difference between n and n-1 while maintaining smallest difference
*/
public int[] closestPair(int[] nums){
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
int[] closestPair = new int[2];
for(int i = 1; i < nums.length; i++){
int diff = Math.abs(nums[i]-nums[i-1]);
if(diff <minDiff){
closestPair[0] = nums[i-1];
closestPair[1] = nums[i];
minDiff = diff;
}
}
return closestPair;
}
}
Monday, July 17, 2017
Is string rotation of other string
/**
* Problem: Assume you have a method isSubstring which checks if one word is a substring of another. Given
* two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring
* (i.e., “waterbottle” is a rotation of “erbottlewat”).
*/
public class IsSubString {
/*
Solution: Concat s1 with itself and now check if it contains s2.
*/
public boolean isRotation(String s1, String s2) {
if(s1.length() != s2.length())
return false;
String newString = s2+s2;
return newString.indexOf(s1) != -1;
}
}
LeetCode 643: Maximum Average subarray
/**
* Problem: Given an array consisting of n integers, find the contiguous subarray of given length k that has
* the maximum average value. And you need to output the maximum average value.
*/
public class MaximumAverageSubarray643 {
/*
At every character position calculate sum of next k characters and compare it with the max sum seen so far
at the end return average
*/
public double findMaxAverage(int[] nums, int k) {
if(nums == null || nums.length < k)
return 0;
int length = nums.length -1;
double maxSum = Integer.MIN_VALUE;
for(int i =0 ; i < nums.length-k+1; i++){
int localSum = 0;
for(int j = i ; j < i+k ;j++){
localSum = localSum + nums[j];
}
maxSum =Math.max(maxSum,localSum);
}
return maxSum/k;
}
}
Write a method to replace all spaces in a string with ‘%20’
/**
* Problem: Write a method to replace all spaces in a string with ‘%20’.
*/
public class ReplaceSpaceChar {
/*
First count the number of space character, each space character would be replaced by 3 characters (2 addition's)
so calculate new length by adding no of space chars * 2 to original length. Then start copying characters
from back and while copying replace each space with %20
*/
public void replaceSpaceChar(char[] str, int length) {
int noOfSpaceChars = 0;
for(int i = 0; i < length; i++){
if(Character.isSpaceChar(str[i])){
noOfSpaceChars++;
}
}
int newLength = length + (noOfSpaceChars*2);
int writeIndex = newLength;
for(int i = length-1; i >=0 ; i--){
char currentChar = str[i];
if(!Character.isSpaceChar(currentChar)){
str[writeIndex--] = currentChar;
}else{
str[writeIndex--] = '0';
str[writeIndex--] = '2';
str[writeIndex--] = '%';
}
}
}
}
Write a method to decide if two strings are anagrams or not.
/**
* Problem :- Write a method to decide if two strings are anagrams or not.
*/
public class TwoStringAnagrams {
/*
Take character arrays of both strings, sort them and check if they are same if not the character
arrays are not anagrams
*/
boolean anagram(String s, String t) {
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
Arrays.sort(sc);
Arrays.sort(tc);
return Arrays.equals(sc, tc);
}
/*
Generate character frequency count map for first string and then use the second string to reduce
frequency
*/
boolean anagram2(String s, String t) {
Map charCount = new HashMap<>();
char[] sChar = s.toCharArray();
for(int i = 0 ; i < sChar.length ;i++){
char currentChar = sChar[i];
if(charCount.containsKey(currentChar)){
charCount.put(currentChar,charCount.get(currentChar)+1);
}else{
charCount.put(currentChar,1);
}
}
char[] tChar = t.toCharArray();
for(int i = 0 ; i < tChar.length ; i++){
char currentChar = tChar[i];
if(charCount.containsKey(currentChar)){
charCount.put(currentChar,charCount.get(currentChar)-1);
if(charCount.get(currentChar) == 0)
charCount.remove(currentChar);
}else{
return false;
}
}
return charCount.size() ==0;
}
}
Remove duplicate characters from String
/**
* Problem :- Design an algorithm and write code to remove the duplicate characters in a string without using any
* additional bu er. NOTE: One or two additional variables are ne. An extra copy of the array is not.
*/
public class RemoveDuplicates {
/*
If the duplicate characters are contiguous
*/
public void removeDuplicates(char[] str) {
if (str == null || str.length < 2)
return;
int writeIndex = 1;
for (int i = 1; i < str.length; i++) {
if (str[i] != str[i - 1]) {
str[writeIndex++] = str[i];
}
}
for (int i = writeIndex; i < str.length; i++) {
str[i] = '0';
}
}
/*
If the duplicate characters are non duplicate then we should manintain a HashSet/boolean array to remember
the characters that we have seen so far and not copy them again
*/
public void removeDuplicates2(char[] str) {
if (str == null || str.length < 2)
return;
boolean[] charHit = new boolean[256];
int writeIndex = 0;
for(int i = 0 ; i < str.length; i++){
int currentChar = Character.getNumericValue(str[i]);
if(charHit[currentChar])
continue;
str[writeIndex++] = str[i];
charHit[currentChar] = true;
}
for (int i = writeIndex; i < str.length; i++) {
str[i] = '0';
}
}
}
Friday, July 14, 2017
Implement an algorithm to determine if a string has all unique characters
/**
* Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
*/
public class StringUniqueCharacters {
public void main(String[] argv){
String str = "This is sample String";
str =" uniqe ";
System.out.println(isUniqueChars2(str));
}
public boolean isUniqueChars(String str){
char[] chars = str.toCharArray();
HashSet charSet = new HashSet<>();
for(char c: chars){
if(Character.isLetterOrDigit(c)) {
if ( charSet.contains(c))
return false;
}
charSet.add(c);
}
return true;
}
// Sort all the characters in the word and if there is duplicate char they will come next to each other
// so check if two consecutive chars are same if yes then thats a problem
public static boolean isUniqueChars2(String str){
char[] chars = str.toCharArray();
Arrays.sort(chars);
for(int i = 1; i < chars.length; i++){
if(Character.isLetterOrDigit(chars[i])) {
if (chars[i] == chars[i - 1])
return false;
}
}
return true;
}
/*
This is bitmask based solution.
Basic idea is take every character's numberic value and create a mask by calculating 1 << bitValue
Then if you & bit mask with the checker it will turn all other bits to offand if the char bit is already set to 1
it will return 1 if not it will 0.
After that you or the bitMask with the checker to remember what all alphabets are seen so far
*/
public static boolean isUniqueChars3(String str){
int checker = 0;
char[] chars = str.toCharArray();
for(char c: chars){
int charValue = Character.getNumericValue(c);
int bitMask = 1 << charValue;
if((checker & bitMask) > 0)
return false;
checker = checker | bitMask;
}
return true;
}
}
Tuesday, July 11, 2017
Print matrix in spiral order
public void matrixInSpiralOrder(int[][] squareMatrix) {
spiralPrint(squareMatrix.length, squareMatrix[0].length,squareMatrix);
}
public void spiralPrint(int endRow, int endColumn, int[][] squareMatrix){
int startRow = 0;
int startColumn = 0;
int i =0;
while (startRow < endRow && startColumn < endColumn){
for( i = startColumn ; i < endColumn ; i++){
System.out.print(squareMatrix[startRow][i] +" ");
}
startRow++;
for(i = startRow ; i < endRow ; i++){
System.out.print(squareMatrix[i][endColumn-1] +" ");
}
endColumn--;
if(startRow< endRow) {
for (i = endColumn-1; i >= startColumn; i--) {
System.out.print(squareMatrix[endRow-1][i] +" ");
}
endRow--;
}
if(startColumn < endColumn){
for(i = endRow-1 ; i >= startRow; i--){
System.out.print(squareMatrix[i][startColumn]+" ");
}
startColumn++;
}
}
}
LeetCode 389: Find the difference
/*
Problem: Given 2 strings which consist of only lower case letters and letters being randomly mixed, find the odd letter
*/
public class Solution {
public char findTheDifference(String s, String t) {
char[] first = s.toCharArray();
char[] second = t.toCharArray();
Arrays.sort(first);
Arrays.sort(second);
for (int i = 0; i < second.length; i++) {
if (i > first.length - 1)
return second[i];
if (first[i] != second[i])
return second[i];
}
return '0';
}
}
LeetCode 273 Integer to English Words
/*
Problem: Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
Ex.1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Solution: Basic idea is create a generic method to convert a number less than 1000 to words. Then for all the numbers
greater than 1000, break it into 1000's Ex. how many billions or how many millions and use the same method to
convert the number into English words
*/
public class IntegerToEnglishWords273 {
HashMap map = new HashMap();
public String numberToWords(int num) {
fillMap();
StringBuilder sb = new StringBuilder();
if(num == 0)
return map.get(0);
if(num >= 1000000000){
int numberOfBillion = num /1000000000;
sb.append(convert(numberOfBillion)).append(" Billion");
num = num %1000000000;
}
if(num >= 1000000){
int numberOfMillion = num /1000000;
sb.append(convert(numberOfMillion)).append(" Million");
num = num %1000000;
}
if(num >= 1000){
int numberOfThousand = num /1000;
sb.append(convert(numberOfThousand)).append(" Thousand");
num = num %1000;
}
if(num >0)
sb.append(convert(num));
return sb.toString().trim();
}
/*
This method takes care of converting a number less than 1,000 to english
*/
public String convert(int num){
StringBuilder sb = new StringBuilder();
if(num >= 100){
int numHundred = num /100;
sb.append(" " +map.get(numHundred) +" Hundred");
num = num %100;
}
if(num >0){
if(num > 0 && num < 20){
sb.append(" " +map.get(num));
}else {
int numTen = num /10;
sb.append(" " + map.get(numTen*10));
int numOne = num %10;
if(numOne >0)
sb.append(" " + map.get(numOne));
}
}
return sb.toString();
}
public void fillMap(){
map.put(0, "Zero");
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
map.put(5, "Five");
map.put(6, "Six");
map.put(7, "Seven");
map.put(8, "Eight");
map.put(9, "Nine");
map.put(10, "Ten");
map.put(11, "Eleven");
map.put(12, "Twelve");
map.put(13, "Thirteen");
map.put(14, "Fourteen");
map.put(15, "Fifteen");
map.put(16, "Sixteen");
map.put(17, "Seventeen");
map.put(18, "Eighteen");
map.put(19, "Nineteen");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");
map.put(60, "Sixty");
map.put(70, "Seventy");
map.put(80, "Eighty");
map.put(90, "Ninety");
}
}
LeetCode 202 Happy Number
public class HappyNumber202 {
/*
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the
sum of the squares of its digits, and repeat the process until
the number equals 1 (where it will stay), or it loops endlessly
in a cycle which does not include 1. Those numbers for which this
process ends in 1 are happy numbers.
Example: 19 is a happy number
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
*/
public boolean isHappy(int n) {
HashSet set = new HashSet<>();
set.add(n);
while (n != 1) {
n = getSum(n);
if (n == 1)
return true;
// Have we seen this number already if yes that means
//we are looping so break
if (set.contains(n))
return false;
set.add(n);
}
return false;
}
private int getSum(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
n = n / 10;
sum += Math.pow(digit, 2);
}
return sum;
}
}
LeetCode 268 Missing Number
public class MissingNumber {
/*
Problem: Given an array containing n distinct numbers taken from
0, 1, 2, ..., n, find the one that is missing from
the array.
For example,
Given nums = [0, 1, 3] return 2
Solution: The basic idea is to use XOR operation. We all know
that a^b^b =a, which means two xor operations
with the same number will eliminate the number and reveal the
original number.
In this solution, I apply XOR operation to both the index and
value of the array. In a complete array with no
missing numbers, the index and value should be perfectly
corresponding( nums[index] = index), so in a missing array,
what left finally is the missing number.
*/
public int missingNumber(int[] nums) {
int result = 0;
int i = 0;
for( i = 0 ; i < nums.length ; i++){
result = result ^ i ^ nums[i];
}
return result ^i;
}
}
LeetCode 260: Single Number III
public class SingleNumberIII260 {
/*
Problem: Given an array of numbers nums, in which exactly two elements appear only once
and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Solution: Once again, we need to use XOR to solve this problem. But this time, we need to do it
in two passes:
In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need
to find. Note that since the two numbers are distinct, so there must be a set bit (that is,
the bit with value '1') in the XOR result. Find
out an arbitrary set bit (for example, the rightmost set bit).
In the second pass, we divide all numbers into two groups, one with the aforementioned bit set,
another with the aforementinoed bit unset. Two different numbers we need to find must fall into
thte two distrinct groups. XOR numbers in each group, we can find a number in either group.
*/
public int[] singleNumber(int[] nums) {
int result = 0;
for(int n: nums)
result = result^n;
System.out.println("Result " + result + " " + Integer.toBinaryString(result));
int resultLowestBit = Integer.lowestOneBit(result);
ArrayList zeroBit = new ArrayList();
ArrayList oneBit = new ArrayList();
for(int n: nums){
if((n&resultLowestBit) == 0){
System.out.println("Zero bit " + n);
zeroBit.add(n);
}else{
System.out.println("One bit " + n);
oneBit.add(n);
}
}
int firstN = 0;
for(int i : zeroBit)
firstN = firstN ^i;
System.out.println("First Number " + firstN);
int secondN = 0;
for(int i: oneBit)
secondN = secondN^i;
System.out.println("Second Number " + secondN);
return new int[]{firstN,secondN};
}
}
LeetCode 137: Single Number 2
public class SingleNumberII137 {
/*
problem: Given an array of integers, every element appears three
times except for one, which appears exactly once. Find that single one.
Solution: The usual bit manipulation code is bit hard to get and replicate.
I like to think about the number in 32 bits and just count how many 1s are there
in each bit, and sum %= 3 will clear it once it reaches 3. After running for all
the numbers for each bit, if we have a 1, then that 1 belongs to the single number,
we can simply move it back to its spot by doing ans |= sum << i;
This has complexity of O(32n), which is essentially O(n) and very easy to think and
implement. Plus, you get a general solution for any times of occurrence. Say all the
numbers have 5 times, just do sum %= 5.
*/
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int sum = 0;
for(int j = 0; j < nums.length; j++) {
if(((nums[j] >> i) & 1) == 1) {
sum++;
sum %= 3;
}
}
if(sum != 0) {
ans |= sum << i;
}
}
return ans;
}
}
Rectangle Intersection
public class RectangleIntersection {
public static class Rectangle{
int x, y, width, height;
public Rectangle(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
}
public Rectangle intersect(Rectangle R1, Rectangle R2){
if(!isIntersect(R1,R2))
return new Rectangle(0,0,-1,-1);
return new Rectangle(
Math.max(R1.x,R1.x), Math.max(R1.y,R2.y),
Math.min(R1.x + R1.width, R2.x + R2.width) - Math.max(R1.x,R2.x),
Math.min(R1.y + R1.height, R2.y + R2.height) - Math.max(R1.y,R2.y)
);
}
public boolean isIntersect(Rectangle R1, Rectangle R2){
return R1.x <= R2.x + R2.width && R1.x + R1.width >= R2.x
&& R1.y <= R2.y + R2.height && R1.y + R1.height >= R2.y;
}
}
Reverse Digits in decimal Number
public class ReverseDigits {
/*
Problem: Given a number reverse it. Ex. input 321 output should be 123
Solution:- Take % of x with 10 at a time and add it to result.
*/
public long revereseDigits(int x){
long result = 0;
int xRemaining = Math.abs(x);
while (xRemaining != 0){
result = result * 10 + xRemaining%10;
xRemaining = xRemaining/10;
}
return result;
}
}
Find only non-duplicate number in an array
public class FindNonDuplicateNumber {
/*
Problem: Given array of integer every element appears twice except one find that number
Solution: Take xor of all the numbers, the numbers that appear twice will cancel out each
other only number that would remain is the number that appears only once
*/
public int findNumber(int[] number){
int result = 0;
for(int i = 0; i < number.length ;i++){
result = result ^ number[i];
}
return result;
}
}
Palindromic Number
public class PalindromeNumber {
/*
Problem: Check if the given number is palindromic. Ex. 1001 is palindromic but 17 is not
Solution: You can find out number of digits in the of the decimal number by calculating
Math.log10(x).
Then you can use this information to calculate most significant and least significant digits
and check if they are equal if not return false
MSD of decimal = x / (Math.pow(10, Math.log10(x))
LSD of decmial = x &10
*/
public boolean isPalindromeNumber(int x){
if(x <0)
return false;
int numberOfDigits = (int)(Math.floor(Math.log10(x)))+1;
int msdMask =(int) Math.pow(10, numberOfDigits-1);
for(int i = 0; i < numberOfDigits/2 ;i++){
if( x / msdMask != x%10)
return false;
x = x %msdMask;
x = x/10;
msdMask = msdMask /100;
}
return true;
}
}
Number with same weight
public class ClosestInSameBitCount {
public static final int NUM_UNSIGN_BITS=63;
/*
Problem: Given a number return another number closest to the input which has same number of 1 bits
Solution :- Start from the end and check if last and but one last digit match if not then
build a bitMap to reverse those 2 bits
*/
public long closestInSameBitCount(long x){
for (int i = 0; i < NUM_UNSIGN_BITS ; i++){
if( ((x>>> i) & 1) != ((x>>> (i+1)) & 1)){
long bitMask =(1L << i) | (1L << (i+1));
System.out.println(Long.toBinaryString(bitMask));
x ^= bitMask;
return x;
}
}
return -1;
}
}
Reverse bits and return the number
public class ReverseBits {
long[] precomputedReverse = new long[1 << 16];
/*
Problem: Given a number reverse its bits. Ex. given
1011 you shoudl return 1101
Solution: Basic idea is simple take out the last bit from number
by executing n&1, then adding that bit to result and shifting all bits
in result by 1
*/
public int reverseBits2(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
int takeOutBit = n & 1;
result = result + takeOutBit;
n = n >>> 1;
if (i < 31)
result = result << 1;
}
return result;
}
/*
Problem: Given a number reverse its bits. Ex. given
1011 you shoudl return 1101
Solution: This is optimized version which assumes that there could be a more than
one byte that has same bit pattern compared to other.
So it breaks integer into 4 bytes then reverses one byte at a time and keeps
cache of the reversed byte. At the end it adds all the bytes together in reverse
*/
private final Map cache = new HashMap<>();
public int reverseBits(int n) {
byte[] bytes = new byte[4];
//Break integer into 4 bytes
for (int i = 0; i < 4; i++)
bytes[i] = (byte) ((n >>> 8 * i) & 0xFF);
//Now reverse one byte at a time, add it to result in reverse order
int result = 0;
for (int i = 0; i < 4; i++) {
result = result + reverseBits(bytes[i]);
if (i < 3)
result = result << 8;
}
return result;
}
private int reverseByte(byte b) {
Integer value = cache.get(b);
if (value != null)
return value;
value = 0;
// This part is same as reverseBits simple but for 8 bits at a time
for (int i = 0; i < 8; i++) {
value = value + ((b >>> 1) & 1);
if (i < 7)
value = value << 1;
}
cache.put(b, value);
return value;
}
}
Swap bits at position i and j in given number
public class SwapBits {
/*
Problem: Swap bits at position i and j in given number.
Ex. swap(85,0,3). 85 looks like this in binary 1010101 swapping will convert it to 1011100
Solution: Basic idea is simple first check the bits i and j if they are actually different
if not we dont need to swap anything
If the two bits are actually different create a bit mask with i and jth bit set to 1 and
xor it with number which takes care of flipping those 2 bits
*/
public long swapBits(long x, int i, int j){
// First the value of firstBit and secondBit
long firstBit = x >>> i & 1;
long secondBit = x >>> j & 1;
if(firstBit!=secondBit){
//If the ith and jth bit are different then create bit mask with ith and jth bit set to 1
long bitMask = (1L << i ) | (1L <<j);
//xoring it with original number will switch ith and jth bit
x = x ^ bitMask;
}
return x;
}
}
Count number of bits set to 1 in an integer
public class CountBits {
public static void main(String[] argv){
CountBits cb = new CountBits();
for(int i = 0; i < 100 ; i++){
System.out.println(cb.countBits(i) +" " + cb.countBits2(i));
}
}
/*
Problem:- Count number of bits set to 1 in an integer
Solution:- Basic idea is performing x&1 gives you value of the LSB then performing >>> on it
will push the last bit out and so on till x becomes 0. Time complexity is number of bits in the
integer
*/
public int countBits(int x){
int numberOfBits = 0;
while (x !=0){
numberOfBits = numberOfBits + ( x&1);
x = x>>>1;
}
return numberOfBits;
}
/*
Solution: This is little more efficient method in which we just remove the last bit that is
set to 1, that way the time complexity is equal to number of bits set to 1
*/
public int countBits2(int x){
int numberOfBits = 0;
while (x !=0){
x = x& (x-1);
numberOfBits ++;
}
return numberOfBits;
}
}
Thursday, July 6, 2017
Largest rectangle in histogram
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length ==0)
return 0;
Stack stack = new Stack();
int maxRectangleArea = 0;
int i = 0;
int currentArea = 0;
while(i < heights.length){
//Either stack is empty or still increasing
if(stack.isEmpty() || heights[stack.peek()] <= heights[i]){
stack.push(i++);
}else{
// Next height is smaller than before, so calculate area
int top = stack.pop();
if(stack.isEmpty())
currentArea = heights[top] * i;
else
currentArea = heights[top] * (i - stack.peek()-1);
maxRectangleArea= Math.max(maxRectangleArea, currentArea);
}
}
while (!stack.isEmpty()) {
int top = stack.pop();
if(stack.isEmpty())
currentArea = heights[top] * i;
else
currentArea = heights[top] * (i - stack.peek()-1);
maxRectangleArea = Math.max(maxRectangleArea, currentArea);
}
return maxRectangleArea;
}
Print nodes in top view of the binary tree
// Java program to print top view of Binary tree
import java.util.*;
// Class for a tree node
class TreeNode
{
// Members
int key;
TreeNode left, right;
// Constructor
public TreeNode(int key)
{
this.key = key;
left = right = null;
}
}
// A class to represent a queue item. The queue is used to do Level
// order traversal. Every Queue item contains node and horizontal
// distance of node from root
class QItem
{
TreeNode node;
int hd;
public QItem(TreeNode n, int h)
{
node = n;
hd = h;
}
}
// Class for a Binary Tree
class Tree
{
TreeNode root;
// Constructors
public Tree() { root = null; }
public Tree(TreeNode n) { root = n; }
// This method prints nodes in top view of binary tree
public void printTopView()
{
// base case
if (root == null) { return; }
// Creates an empty hashset
HashSet set = new HashSet<>();
// Create a queue and add root to it
Queue Q = new LinkedList();
Q.add(new QItem(root, 0)); // Horizontal distance of root is 0
// Standard BFS or level order traversal loop
while (!Q.isEmpty())
{
// Remove the front item and get its details
QItem qi = Q.remove();
int hd = qi.hd;
TreeNode n = qi.node;
// If this is the first node at its horizontal distance,
// then this node is in top view
if (!set.contains(hd))
{
set.add(hd);
System.out.print(n.key + " ");
}
// Enqueue left and right children of current node
if (n.left != null)
Q.add(new QItem(n.left, hd-1));
if (n.right != null)
Q.add(new QItem(n.right, hd+1));
}
}
}
// Driver class to test above methods
public class Main
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.left.right.right = new TreeNode(5);
root.left.right.right.right = new TreeNode(6);
Tree t = new Tree(root);
System.out.println("Following are nodes in top view of Binary Tree");
t.printTopView();
}
}
Bottom view of binary tree
// Java Program to print Bottom View of Binary Tree
import java.util.*;
import java.util.Map.Entry;
// Tree node class
class Node
{
int data; //data of the node
int hd; //horizontal distance of the node
Node left, right; //left and right references
// Constructor of tree node
public Node(int key)
{
data = key;
hd = Integer.MAX_VALUE;
left = right = null;
}
}
//Tree class
class Tree
{
Node root; //root node of tree
// Default constructor
public Tree() {}
// Parameterized tree constructor
public Tree(Node node)
{
root = node;
}
// Method that prints the bottom view.
public void bottomView()
{
if (root == null)
return;
// Initialize a variable 'hd' with 0 for the root element.
int hd = 0;
// TreeMap which stores key value pair sorted on key value
Map map = new TreeMap<>();
// Queue to store tree nodes in level order traversal
Queue queue = new LinkedList();
// Assign initialized horizontal distance value to root
// node and add it to the queue.
root.hd = hd;
queue.add(root);
// Loop until the queue is empty (standard level order loop)
while (!queue.isEmpty())
{
Node temp = queue.remove();
// Extract the horizontal distance value from the
// dequeued tree node.
hd = temp.hd;
// Put the dequeued tree node to TreeMap having key
// as horizontal distance. Every time we find a node
// having same horizontal distance we need to replace
// the data in the map.
map.put(hd, temp.data);
// If the dequeued node has a left child add it to the
// queue with a horizontal distance hd-1.
if (temp.left != null)
{
temp.left.hd = hd-1;
queue.add(temp.left);
}
// If the dequeued node has a left child add it to the
// queue with a horizontal distance hd+1.
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
// Extract the entries of map into a set to traverse
// an iterator over that.
Set> set = map.entrySet();
// Make an iterator
Iterator> iterator = set.iterator();
// Traverse the map elements using the iterator.
while (iterator.hasNext())
{
Map.Entry me = iterator.next();
System.out.print(me.getValue()+" ");
}
}
}
// Main driver class
public class BottomView
{
public static void main(String[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
Tree tree = new Tree(root);
System.out.println("Bottom view of the given binary tree:");
tree.bottomView();
}
}
Ceil search in sorted array
/* Function to get index of
ceiling of x in arr[low..high]*/
static int ceilSearch(int arr[], int low, int high, int x)
{
int mid;
/* If x is smaller than or equal to the
first element, then return the first element */
if(x <= arr[low])
return low;
/* If x is greater than the last
element, then return -1 */
if(x > arr[high])
return -1;
/* get the index of middle element
of arr[low..high]*/
mid = (low + high)/2; /* low + (high - low)/2 */
/* If x is same as middle element,
then return mid */
if(arr[mid] == x)
return mid;
/* If x is greater than arr[mid], then
either arr[mid + 1] is ceiling of x or
ceiling lies in arr[mid+1...high] */
else if(arr[mid] < x)
{
if(mid + 1 <= high && x <= arr[mid+1])
return mid + 1;
else
return ceilSearch(arr, mid+1, high, x);
}
/* If x is smaller than arr[mid],
then either arr[mid] is ceiling of x
or ceiling lies in arr[mid-1...high] */
else
{
if(mid - 1 >= low && x > arr[mid-1])
return mid;
else
return ceilSearch(arr, low, mid - 1, x);
}
}
Print Right view of the binary tree
private static int maxLevel = 0;
public static void printRightViewOfBT(BinaryTreeNode root){
printRightViewHelper(root,1);
}
public static void printRightViewHelper(BinaryTreeNode root, int level){
if(root == null)
return;
if(level > maxLevel){
System.out.print(root.data + " ");
maxLevel = level;
}
printRightViewHelper(root.right,level+1);
printRightViewHelper(root.left,level+1);
}
Number of leaves in Binary Tree
public static int numberOfLeavesInBT(BinaryTreeNode root){
if(root == null)
return 0;
Queue queue = new LinkedList();
queue.add(root);
int count =0;
while(!queue.isEmpty()){
BinaryTreeNode node = queue.poll();
if(node.getRight() == null&& node.getLeft() ==null)
count++;
if(node.getLeft() !=null)
queue.add(node.getLeft());
if(node.getRight() !=null)
queue.add(node.getRight());
}
return count;
}
Subscribe to:
Posts (Atom)