Minimum (Maximum) Path to Reach a Target
Distinct Ways
Merging Intervals
DP on Strings
Decision Making
Tuesday, May 26, 2020
Sunday, May 24, 2020
Step by Step Guide for Data Structures & Algorithms
Step 1 :
Start with https://www.byte-by-byte.com/tag/easy/
Friday, May 22, 2020
Sort Characters by Frequency Using JAVA 8
class SortCharactersByFrequency {
/**
* Java Streams Approach
* Time complexity : O(N)
* Space complexity : O(N)
*/
static String frequencySort(String s) {
return s.chars()
.mapToObj(Character::toString) //map to string character
.collect(Collectors.groupingBy(Function.identity())) //collect to Map<String, List<String>>
.values() //drop keys, we care only about values
.stream()
.sorted(Comparator.<List<String>>comparingInt(List::size).reversed()) //sort by list size in descending order
.flatMap(strings -> strings.stream()) //flat map to stream of character strings
.collect(Collectors.joining()); //build a string from the stream
}
}
Finding middle element in the array
int mid = firstIndex + (lastIndex-firstIndex)/2;
int mid = (low + high) >>> 1;
Both of them are preferred ways, but don't use mid=(low+high)/2; , to find out why read my article : https://siddharthnawani.blogspot.com/2020/05/why-start-end-start2-is-preferable.html
int mid = (low + high) >>> 1;
Both of them are preferred ways, but don't use mid=(low+high)/2; , to find out why read my article : https://siddharthnawani.blogspot.com/2020/05/why-start-end-start2-is-preferable.html
Why start + (end – start)/2 is preferable method for calculating middle of an array over (start + end)/2 ?
We can take a simple example to demonstrate this fact. Suppose in a certain large array, we are trying to find the midpoint of the range [1000, INT_MAX]. Now, INT_MAX is the largest value the int data type can store. Even if 1 is added to this, the final value will become negative.
Also, start = 1000 and end = INT_MAX.
Using the formula: (start + end)/2,
the mid-point will be
(1000 + INT_MAX)/2 = -(INT_MAX+999)/2, which is negative and may give segmentation fault if we try to index using this value.
But, using the formula, (start + (end-start)/2), we get:
(1000 + (INT_MAX-1000)/2) = (1000 + INT_MAX/2 - 500) = (INT_MAX/2 + 500) which will not overflow.
Note : (end – start) may overflow if end < 0 or start < 0
Also, start = 1000 and end = INT_MAX.
Using the formula: (start + end)/2,
the mid-point will be
(1000 + INT_MAX)/2 = -(INT_MAX+999)/2, which is negative and may give segmentation fault if we try to index using this value.
But, using the formula, (start + (end-start)/2), we get:
(1000 + (INT_MAX-1000)/2) = (1000 + INT_MAX/2 - 500) = (INT_MAX/2 + 500) which will not overflow.
Note : (end – start) may overflow if end < 0 or start < 0
Bitwise Operators
Basics :
1) Binary format has just two bit, 0 and 1 and that's why is called binary.
2) In binary arithmetic :
0 + 0 = 0
0 + 1 = 1
1 + 1 = 10
3) Negation bitwise operation will change 0 to 1 and 1 to 0 and it’s denoted by ~.
4) OR bitwise operation will return 1 if any of operand is 1 and zero only if both operands are zeros.
5) AND bitwise operation will return 1 only if both operands are 1, otherwise zero.
6) XOR bitwise operation will return 1 if both operands are different e.g. one of them is 1 and other is zero and returns zero if both operands are same e.g. 1,1 or 0,0
7) Integral types in Java (int, long, short and byte) are signed numbers in Java where most significant bit (MSB) represent sign of number. 1 will denote a negative number and 0 as MSB will denote a positive numbers
8) Negative numbers in Java are represented as 2's complement of number. 2's complement of a number is 1's complement + 1 and 1's complement means all zero will turn to 1 and all 1 turned to zero in a binary number e.g. 1's complement of 10 would be 01. and 2's complement of 10 would be 10+1 = 11 (all in binary).
Bitwise operators in Java :
Bitwise unary complement operator (~) Example
Bitwise unary complement operator changes bits from 0 to 1, or vice versa and can only be applied on integral types. It’s not applicable on boolean types.For example int variable contains 32 bits; Applying this operator to a value whose bit pattern is 0000 would change its pattern to 11111. Here is an example of bitwise unary complement operator in Java :
int number = 2; //0010
//example of bitwise unary complement operator (~)
System.out.println(" value of number before: " + number);
System.out.println(" value of number after negation: " + ~number);
Output:
value of number before: 2
value of number after negation: -3
Bitwise AND operator (&) Example
Bitwise AND operator works similar to logical AND operator (&&) and returns 1 if both operands are 1. Difference with bitwise AND and logical AND also known as short-circuit AND operator is that, logical AND operator applies only to boolean type. Also bitwise AND operator is denoted by singe & while short circuit AND operator is denoted by &&. If A represent 0010 and B represent 1010 then result of A&B would be 0010. Here is another example of bitwise AND operator in Java
int a = 2; //0010
int b = 4; //0100
//example of bitwise AND operator &
System.out.println("Result of a&b is " + (a&b)); //should be zero
Output:
Result of a&b is 0
Bitwise OR operator (|) Example
Bitwise OR operator is also similar to bitwise AND operator and applies to individual bits. It’s different than short-circuit OR operator, which is denoted by (||) and operates on boolean variable. Bitwise OR operator produce result of OR operation on two bits as shown in below example. Like other bitwise operator in Java, bitwise OR is only applicable to integral types.
int a = 2; //0010
int b = 4; //0100
System.out.println(" value of A bitwise OR B in Java : " + (a|b) );
Output:
value of A bitwise OR B in Java : 6
Bitwise XOR operator (^) Example
Bitwise XOR operator is denoted by ^ and also work on individual bits. There is no short-circuit XOR operator in Java and result of bitwise XOR operator is XOR operation of individual bits. see the truth table of XOR operation for predicting result. in short bitwise XOR operators will return 1 if both bits are different and return 0 if both bits are same. Bitwise XOR operator also offers a nice trick to swap two numbers without using temp variables. Here is a code example of using bitwise XOR operator in Java:
int a = 2; //0010
int b = 4; //0100
System.out.println(" value of a XOR B in Java : " + (a^b) );
Output:
value of a XOR B in Java : 6
Bit Shift operator in Java- Example
Apart from bitwise operators, Java also provides bit shift operators, which can be used to shift bit from one position to another on both left and right side in a number. Java provides three bit shift operator signed left shift operator "<<", signed right shift operator ">>" and unsigned right shift operator ">>>". Left shift operator with sign, shifts bit into left side and fill the empty place with zero, while right shift operator with sign, shifts the bit on right side and fills the empty place with value of sign bit. For positive number it fills with zero and for negative numbers it fills with 1. On the other hand ">>>" right shift without sign operator will only shift the bit towards right without preserving sign of number. As per syntax of bitshift operator, left hand side of operand is the number whose bit needs to be shift and right hand side of operator is how many bits needs to shift. This will be much clear with following example of signed left shift, signed right shift and right shift without sign operators:
public class BitShiftTest {
public static void main(String args[]) {
int number = 8; //0000 1000
System.out.println("Original number : " + number);
//left shifting bytes with 1 position
number = number<<1; //should be 16 i.e. 0001 0000
//equivalent of multiplication of 2
System.out.println("value of number after left shift: " + number);
number = -8;
//right shifting bytes with sign 1 position
number = number>>1; //should be 16 i.e. 0001 0000
//equivalent of division of 2
System.out.println("value of number after right shift with sign: " + number);
number = -8;
//right shifting bytes without sign 1 position
number = number>>>1; //should be 16 i.e. 0001 0000
//equivalent of division of 2
System.out.println("value of number after right shift with sign: " + number);
}
}
Output:
Original number : 8
value of number after left shift: 16
value of number after right shift with sign: -4
value of number after right shift with sign: 2147483644
From above example of bit shift operators in Java, you can imply that signed left shift operators are equivalent of multiplying by 2 and signed right shift operator with sign are dividing by two. I won’t suggest to do that in production quality code, because it reduces readability.
Important points to remember while using bit shift operators in Java
1. Smaller types like byte, short are promoted to int before applying bit shift operator in Java. This requires explicit casting on lower type of result.
2. If number of shift positions exceeds with number of bits in a variable, then remainder operator is used to calculate effective bit movement. For example int variables contains 32 bit, and if you shift bits to 33 times, then its equivalent of shifting bits 33%32 or just 1 time. e.g. 8 >> 33 is equal to 8 >> 1 and this is true for all bit shift operators.
3. Since bit shift operators can simulate divide by 2 and multiplied by 2 operation they can be used to implement fast multiplication and division but on the cost of readability as its difficult to comprehend code written using bit shift operators in Java.
Ref: https://javarevisited.blogspot.com/2013/03/bitwise-and-bitshift-operators-in-java-and-or-xor-left-right-shift-example-tutorial.html
1) Binary format has just two bit, 0 and 1 and that's why is called binary.
2) In binary arithmetic :
0 + 0 = 0
0 + 1 = 1
1 + 1 = 10
3) Negation bitwise operation will change 0 to 1 and 1 to 0 and it’s denoted by ~.
4) OR bitwise operation will return 1 if any of operand is 1 and zero only if both operands are zeros.
5) AND bitwise operation will return 1 only if both operands are 1, otherwise zero.
6) XOR bitwise operation will return 1 if both operands are different e.g. one of them is 1 and other is zero and returns zero if both operands are same e.g. 1,1 or 0,0
7) Integral types in Java (int, long, short and byte) are signed numbers in Java where most significant bit (MSB) represent sign of number. 1 will denote a negative number and 0 as MSB will denote a positive numbers
8) Negative numbers in Java are represented as 2's complement of number. 2's complement of a number is 1's complement + 1 and 1's complement means all zero will turn to 1 and all 1 turned to zero in a binary number e.g. 1's complement of 10 would be 01. and 2's complement of 10 would be 10+1 = 11 (all in binary).
Bitwise operators in Java :
Bitwise unary complement operator (~) Example
Bitwise unary complement operator changes bits from 0 to 1, or vice versa and can only be applied on integral types. It’s not applicable on boolean types.For example int variable contains 32 bits; Applying this operator to a value whose bit pattern is 0000 would change its pattern to 11111. Here is an example of bitwise unary complement operator in Java :
int number = 2; //0010
//example of bitwise unary complement operator (~)
System.out.println(" value of number before: " + number);
System.out.println(" value of number after negation: " + ~number);
Output:
value of number before: 2
value of number after negation: -3
Bitwise AND operator (&) Example
Bitwise AND operator works similar to logical AND operator (&&) and returns 1 if both operands are 1. Difference with bitwise AND and logical AND also known as short-circuit AND operator is that, logical AND operator applies only to boolean type. Also bitwise AND operator is denoted by singe & while short circuit AND operator is denoted by &&. If A represent 0010 and B represent 1010 then result of A&B would be 0010. Here is another example of bitwise AND operator in Java
int a = 2; //0010
int b = 4; //0100
//example of bitwise AND operator &
System.out.println("Result of a&b is " + (a&b)); //should be zero
Output:
Result of a&b is 0
Bitwise OR operator (|) Example
Bitwise OR operator is also similar to bitwise AND operator and applies to individual bits. It’s different than short-circuit OR operator, which is denoted by (||) and operates on boolean variable. Bitwise OR operator produce result of OR operation on two bits as shown in below example. Like other bitwise operator in Java, bitwise OR is only applicable to integral types.
int a = 2; //0010
int b = 4; //0100
System.out.println(" value of A bitwise OR B in Java : " + (a|b) );
Output:
value of A bitwise OR B in Java : 6
Bitwise XOR operator (^) Example
Bitwise XOR operator is denoted by ^ and also work on individual bits. There is no short-circuit XOR operator in Java and result of bitwise XOR operator is XOR operation of individual bits. see the truth table of XOR operation for predicting result. in short bitwise XOR operators will return 1 if both bits are different and return 0 if both bits are same. Bitwise XOR operator also offers a nice trick to swap two numbers without using temp variables. Here is a code example of using bitwise XOR operator in Java:
int a = 2; //0010
int b = 4; //0100
System.out.println(" value of a XOR B in Java : " + (a^b) );
Output:
value of a XOR B in Java : 6
Bit Shift operator in Java- Example
Apart from bitwise operators, Java also provides bit shift operators, which can be used to shift bit from one position to another on both left and right side in a number. Java provides three bit shift operator signed left shift operator "<<", signed right shift operator ">>" and unsigned right shift operator ">>>". Left shift operator with sign, shifts bit into left side and fill the empty place with zero, while right shift operator with sign, shifts the bit on right side and fills the empty place with value of sign bit. For positive number it fills with zero and for negative numbers it fills with 1. On the other hand ">>>" right shift without sign operator will only shift the bit towards right without preserving sign of number. As per syntax of bitshift operator, left hand side of operand is the number whose bit needs to be shift and right hand side of operator is how many bits needs to shift. This will be much clear with following example of signed left shift, signed right shift and right shift without sign operators:
public class BitShiftTest {
public static void main(String args[]) {
int number = 8; //0000 1000
System.out.println("Original number : " + number);
//left shifting bytes with 1 position
number = number<<1; //should be 16 i.e. 0001 0000
//equivalent of multiplication of 2
System.out.println("value of number after left shift: " + number);
number = -8;
//right shifting bytes with sign 1 position
number = number>>1; //should be 16 i.e. 0001 0000
//equivalent of division of 2
System.out.println("value of number after right shift with sign: " + number);
number = -8;
//right shifting bytes without sign 1 position
number = number>>>1; //should be 16 i.e. 0001 0000
//equivalent of division of 2
System.out.println("value of number after right shift with sign: " + number);
}
}
Output:
Original number : 8
value of number after left shift: 16
value of number after right shift with sign: -4
value of number after right shift with sign: 2147483644
From above example of bit shift operators in Java, you can imply that signed left shift operators are equivalent of multiplying by 2 and signed right shift operator with sign are dividing by two. I won’t suggest to do that in production quality code, because it reduces readability.
Important points to remember while using bit shift operators in Java
1. Smaller types like byte, short are promoted to int before applying bit shift operator in Java. This requires explicit casting on lower type of result.
2. If number of shift positions exceeds with number of bits in a variable, then remainder operator is used to calculate effective bit movement. For example int variables contains 32 bit, and if you shift bits to 33 times, then its equivalent of shifting bits 33%32 or just 1 time. e.g. 8 >> 33 is equal to 8 >> 1 and this is true for all bit shift operators.
3. Since bit shift operators can simulate divide by 2 and multiplied by 2 operation they can be used to implement fast multiplication and division but on the cost of readability as its difficult to comprehend code written using bit shift operators in Java.
Ref: https://javarevisited.blogspot.com/2013/03/bitwise-and-bitshift-operators-in-java-and-or-xor-left-right-shift-example-tutorial.html
Sunday, May 3, 2020
System Design Basics | Post -1
These days System Design questions have become an important part of any interview process. Not just for interviews but to for the overall improvement of oneself, one must have the knowledge of System design so that good foundation can be laid from the very beginning.
In coming posts i will touch this topic.
Flow
A. Understand the problem and scope
Define the use cases, with interviewer's help.
Suggest additional features.
Remove items that interviewer deems out of scope.
Assume high availability is required, add as a use case.
B. Think about constraints
Ask how many requests per month.
Ask how many requests per second (they may volunteer it or make you do the math).
Estimate reads vs. writes percentage.
Keep 80/20 rule in mind when estimating.
How much data written per second.
Total storage required over 5 years.
How much data reads per second.
C. Abstract design
Layers (service, data, caching).
Infrastructure: load balancing, messaging.
Rough overview of any key algorithm that drives the service.
Consider bottlenecks and determine solutions.
Source: https://github.com/jwasham/coding-interview-university#system-design-scalability-data-handling
In coming posts i will touch this topic.
Flow
A. Understand the problem and scope
Define the use cases, with interviewer's help.
Suggest additional features.
Remove items that interviewer deems out of scope.
Assume high availability is required, add as a use case.
B. Think about constraints
Ask how many requests per month.
Ask how many requests per second (they may volunteer it or make you do the math).
Estimate reads vs. writes percentage.
Keep 80/20 rule in mind when estimating.
How much data written per second.
Total storage required over 5 years.
How much data reads per second.
C. Abstract design
Layers (service, data, caching).
Infrastructure: load balancing, messaging.
Rough overview of any key algorithm that drives the service.
Consider bottlenecks and determine solutions.
Source: https://github.com/jwasham/coding-interview-university#system-design-scalability-data-handling
Subscribe to:
Posts (Atom)