What is XOR Linked list and its benefit ?

XOR Linked list is the memory efficient version of Doubly Linked list.

An ordinary Doubly Linked list needs 2 pointers - for next and previous elements.
XOR Linked list uses bitwise XOR operation to save the space (Keeps single pointer with XOR of both the pointers instead of 2 pointers)

EXAMPLE
Node1 : npx = 0 XOR pointer(Node1)
Node2 : npx = pointer(Node1) XOR pointer(Node2)
Node3 : npx = pointer(Node2) XOR pointer(Node3)
Node4 : npx = pointer(Node3) XOR 0

What are the types of Linked list ?

Each element of Linked list have 2 items : Data and Pointer to next element

SINGLY L.L.
Every node have pointer of next node. Last node has pointer = NULL
1->2->3->4->NULL

DOUBLY L.L.
Every node have 2 pointers : for next and previous node
NULL<-1<->2<->3->NULL

CIRCULAR L.L.
It can be singly or doubly L.L. where all elements are connected to form a circle.
The next pointer of last node points to first node
1->2->3->1
 

Arrays vs. Linked list

ARRAYS VS. LINKED LIST

1. Arrays are of fixed size, Not for Linked list
2. Random access is not allowed in Linked list
3. Extra memory needed in Linked list to store pointer to next element
4. Insertion and deletion elements in arrays are expensive than Linked list

Where we can use stacks ?

STACK
A linear DS uses LIFO or FILO for accessing elements and allows PUSH, POP and PEAK operations.

Applications of stack

• Infix to Postfix conversion
• Evaluation of Postfix operation
• Reverse a string
• Check of balanced parentheses in an expression

Linear vs. Non-Linear data structures

LINEAR
Elements forms a sequence or a linear list.
E.g. : Arrays, Linked list, Stack, Queue

NON LINEAR
Traversal of nodes is non linear in nature.
E.g. : Tree, Graph

How to evaluate a postfix expression ?

Postfix notation represents a algebraic expression.
These are evaluated faster than infix notation, as ( ) are not required.

Algorithm - using Stack

• For each element in postfix string
• if element is an operand
• push element into Stack => Operand
• else  // Operator
• Pop from Stack => Operand 1
• Pop from Stack => Operand 2
• Evaluate value using both operands and element (Operator) => value
• Push the value to Stack
• Pop the element of Stack => Final result

Example

String postfix = "2 3 1 * + 9 -"

element	oprnd1	oprnd2	value	stack
2				2
3				2,3
1				2,3,1
*	3	1	3*1	2,3
+	3	2	3+2	5
9				5,9
-	5	9	5-9	-4

Java code
public static int evaluatePostfix(String postfixStr) {
  String[] postfixArr = postfixStr.split("");
  Stack<Integer> stack = new Stack<Integer>();

  for(String element : postfixArr) {
      boolean isOperator = isOperator(element);
      if(isOperator) {
         int value1 = stack.pop();

         int value2 = stack.pop();
         int value = calculate(value2, value1, element);
         stack.push(value);
      else {
         stack.push(Integer.valueOf(element));
      }

  }

  return stack.pop();
}

private static int calculate(int a, int b, String operator){
  int result = 0;
  if("+".equals(operator)) {
    result = (a+b);
  else if("-".equals(operator)) {
    result = (a-b);

  else if("*".equals(operator)) {
    result = (a*b);

  else if("/".equals(operator)) {
    result = (a/b);

  
  return result;

}

private static boolean isOperator(String element) {
  if("+".equals(element) || "-".equals(element) 
         || "/".equals(element) || "*".equals(element)) {
     return true;
  }
  return false;
}

How to implement Integer.parseInt() method ?

The method must produce :

• 12345 for "12345"
• -12345 for "-12345"
• Error for Alphanumeric input string

Algorithm

int i = 0, number = 0;

char[] value = inputStr.toCharArray();

// Check for -ve number, and set the flag

boolean isNegative = false;

if (value[0] == '-') {

    isNegative = true;

    i = 1;

}

// iterate each character 

while(i < value.length) {

    // Pick each character

    char ch = value[i++];

    int place_value = ch - '0';

    // Check for digit and form the number

    if (place_value>=0 && place_value<=9) {

       number *= 10;

       number += (ch - '0');

    } else {

       System.out.println("Wrong input format!!");

         throw new ParseException("String to int parse",-1);

     }

}

// For -ve number, Negate the number

if(isNegative) {

     number = -number;

}

return number;

What is Naïve String Matching Algorithm ?

• A Brute force algorithm
• identifies the presence of a pattern in the given text
• Complexity of checking : O( (n-m)m )

Algorithm

char[] textArr = text.toCharArray();

char[] patternArr = pattern.toCharArray();

int textLen = textArr.length;

int paternLen = patternArr.length;

for (int i = 0; i < textLen - patternLen; i++) {

     int charMatchCount = 0;

     for (int j = 0; j < patternLen; j++) {

         /**

          * If pattern mismatch, break next searching point.

          **/

          if (patternArr[j] != textArr[i + j]) {

               break;

          }

          charMatchCount++;

     }

     // If all characters of pattern matched

     if (charMatchCount == patternLen) {

         System.out.println("String found at "+(i+1)+" position!!");

         break;

     }

}

How to implement Bucket (Bin) sort ?

• Distribute the elements into a number of buckets
• Each bucket is then sorted individually (using any type of sorting algo)

• Elements are distributed among bins

       

• Elements are sorted within each bin

        


Implementation

/**

 * Initialize the Bucket array to store elements

 **/

int maxVal = 5;

int [] bucket = new int[maxVal+1];

for (int i=0; i<bucket.length; i++) {

    bucket[i]=0;

}

/**

 * Element as index and

 * value stored at array index is occurrence

 **/

for (int i=0; i<array.length; i++) {

    bucket[array[i]]++;

}

/**

 * Restore all the elements in sorted order

 **/

int outPos = 0;

for (int i=0; i<bucket.length; i++) {  // iterate through buckets

   for (int j=0; j<bucket[i]; j++) {

       array[outPos++]=i;

   }

}

Linear search vs. Binary search

Linear search

• Complexity : O(n)
• Suited for unordered array
• Loop starts from first element till the item found or end of the array.
• In Worst case, it will take 2^20 comparisons for 2^20 records.
• Easy to implement
• Takes longer time (in average) to find an item than Binary search

for (int i=0; i<array.length(); i++) {
  if (array[i] == value) {
       return i;  // item found, return the index
  }
}

return -1;  // Not found


Binary search

• Complexity : O(log n)
• Very efficient than Linear search
• Only applied on ordered array ; cannot be applied on unordered array
• Little complex algorithm than Linear search
• In Worst case, it will take only 20 comparisons for 2^20 records.

int low = 0;

int high = len - 1;

while (low <= high) {

   mid = (low+high) / 2;   // Find the mid index

   
   if (array[mid] == value)
        return mid;       // Found, return mid index

   else if (array[mid] > value)  // If value is lesser than mid element

        high = mid - 1;   // Search before mid - Adjust 'high'

   else if (array[mid] < value)  // If value is greater than mid element

        low = mid + 1;    // Search after mid - Adjust 'low'

}

return -1;  // Not found

How to check if a number is the perfect square ?

Note : A Perfect square is the Sum of all consecutive add numbers
Example of perfect squares : 1+3+5....

Algorithm

boolean isPerfectSquare = false;

int sum = 0;

// iterate from 1 to n incremented by 2

for(int i=1; sum<num; i+=2) {

    // Calculate the sum and check for perfect square

    sum += i;

    if (sum == num)

        isPerfectSquare = true;

        break;

    }

}

How to check if a number is power of 2 ?

Solution #1. Divide num by 2 recursively
Time complexity : O(log2n)


Solution #2. Using Bitwise & operator with num and num-1
boolean isPowerOf2 = (num & (num-1))==0;

Time complexity : O(1)

Example : 
num = 8
n    = 8 = 1000
n-1 = 7 = 0111
-------------------
               0000 => Power of 2, Yes.

Check if the number is odd ?

Solution #1. Check if num % 2 == 0
boolean isOdd = (num % 2 == 1);

Problem. It will not return correct result for -ve number


Solution #2. Same approach but use absolute value of num
if(num<0) {
   num = -(num);
}
boolean isOdd = (num % 2 == 1);

Solution #3. Check using bitwise & with 1 (Binary = 000000...1)

boolean isOdd = (num & 1) != 0;

Example

21 = 10101

  1 = 00001

----------------

        00001  => Odd, Yes.

Fastest and most optimized solution.

How to swap 2 numbers without using 3rd variable ?

Solution #1. Addition and Subtraction method
a = a+b;
b = a-b;
a = a-b;

Problem. Incorrect result when sum of numbers will exceed the integer range


Solution #2. Multiplication and Division method
a = a*b;
b = a/b;
a = a/b;

Problem. Same problem with multiplication result
                Additionally, Incorrect result when a or b is 0


Solution #3. XOR method
a = a^b;
b = a^b;

a = a^b;

Best approach without any problem

How to increment a number by 1 without using + operator ?

Use Bitwise operator to add 1 to binary representation
Check the each bit and flip it using bitwise operator


Here, number is input and output both

int one = 1;

/* Flip all the set bits until we find a 0 */

while((number & one)!=0 ) {

   number = number^one;

   one <<= 1;

}

/* flip the rightmost 0 bit */

number = number^one;

How to implement Merge sort ?

Merge sort - O(n log n)

• Divide and Conquer
• Divide into 2 parts
• Divide each part into 2 sub-parts recursively
• Merge parts in reverse order
• 
  
• Example
• Divide array of 8 numbers to 2 sub arrays
• Divide each subarray again into 2 (4 sub arrays)
• Divide each subarray again into 2 (8 sub arrays)
• Merge into 4 subarrays
• Merge into 2 subarrays
• Merge into 1 array

27 10 12 25 34 16 15 31

27  10  12   25   | 34   16  15  31

27  10 | 12   25   | 34   16  | 15  31

-------------------------------------------------------
27 | 10 | 12 | 25 | 34 | 16 | 15 | 31
-------------------------------------------------------
10 27 | 12 25 | 16 34 | 15 31
10 12 27 25 | 15 16 31 34
10 12 15 16 25 27 31 34