Tree is the most widely used data structure for representing hierarchical data.

Tree Terminology

Root – The top node in a tree.
Child – A node directly connected to another node when moving away from the Root.
Parent – The converse notion of a child.
Siblings – Nodes with the same parent.
Descendant – A node reachable by repeated proceeding from parent to child.
Ancestor – A node reachable by repeated proceeding from child to parent.
Leaf – A node with no children.
Internal node – A node with at least one child
External node – A node with no children.
Degree – Number of sub trees of a node.
Edge – Connection between one node to another.
Path – A sequence of nodes and edges connecting a node with a descendant.
Level – The level of a node is defined by 1 + (the number of connections between the node and the root).
Height of node – The height of a node is the number of edges on the longest path between that node and a leaf.
Height of tree – The height of a tree is the height of its root node.
Depth – The depth of a node is the number of edges from the node to the tree’s root node.
Forest – A forest is a set of n ≥ 0 disjoint trees.

Applications

Represent Hierarchical data e.g File System, ancestory etc
Router algorithm
Easy Searching (Traversal)

Tree representation

//Have left and right node
//Have a value to store the value of the current node
class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val){
        this.val = val;
    }
}
public static void main(String args[]){
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
}

Tree Traversal

Level Order (Breadth first) (Visit each level at a time)
- All the nodes of the current level will be visited first before going to the next level
- In the above tree, the level order will display the node values in this order
  - 1234567

To find the levels we need to get the height of the tree

//if root is null then return 0
//find the left and right node height by recursing
//find the max of left and right node 
public static int height(TreeNode root){
        if(root == null)
            return 0;
        int lheight = height(root.left) + 1;
        int rheight = height(root.right) + 1;
        int height = Math.max(lheight,rheight);
        return height;
    }

//get the level order
//decrease the level and recurse, return if the level is 1    
public static void bfs(TreeNode root, int level){
        if(root == null)
            return;
        if(level == 1)
            System.out.println(root.val);
        else{    
                bfs(root.left,level-1);
                bfs(root.right,level-1);
            }
    }

InOrder Traversal (left-root-right)
- left node will be visited first and then the root node and then the right node
  - the above tree will return 4251637

    //left root right
    //4251637
    public static void inOrder(TreeNode root){
        if(root == null)
            return;
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }

PreOrder Traversal (root-left-right)
- root node will be visited first and then the left node and then the right node
  - the above tree will return 1245367

//root left right
    //1245367
    public static void preOrder(TreeNode root){
        if(root == null)
            return;
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

PostOrder Traversal (left-right-root)
- left node will be visited first and then the right node and then the root node
  - the above tree will return 4526731

//left right root
    //4526731
    public static void postOrder(TreeNode root){
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

Stack – Implementation

April 4, 2016

Arrays, Data Structures, Linked List, Stack

Leave a comment

Introduction

Stack is a very common data structures which will return in the element stored in a Last In First Out fashion.

Applications

Expression Evaluation
- Post fix /In fix
Backtracking
- Finding Paths
- Game Playing
Exhaustive search
Memory Management
Depth First Search traversal

Here we will see how to implement a stack using Array and Linked List

Array Implementation

We can implement array with fixed capacity(bounded) or with dynamically allocating the memory for storing the elements(unbounded). If the size reaches the maximum element the size is doubled and the elements are copied to a new array

class ArrayStack{
    
    int size; // size of the array
    int[] array;
    int head; // head pointer
    int max; //max capacity
 
//initialize size, max and the internal array
  public ArrayStack(int max){
      this.array = new int[max];
      this.head = 0;
      this.size = 0;
      this.max = max;
  }
  
//return the current size
  public int getSize(){
      return size;
  }

//return true if the size == 0
  public boolean isEmpty(){
      return size == 0;
  }

//return the head of the stack
    public int peek(){
      return head;
  }  

//check for empty
//if not then update the head with the last array element that was inserted
//set the array element to 0 (reset)
//return the head
  public int pop(){
      if(!isEmpty()){
          head = array[--size];
          array[size] = 0;
          return head;
      }
          System.out.println("No Element");
          return -1;

  }

//set the array to the value inserted if the size is not equal to max
/set the head to last inserted element
//increment the size
  public void push(int val){
      if(size != max){
          array[size] = val;
          head = array[size];
          size++;
      }
      else
          System.out.println("Reached max element");
          //------------------Dynamic Allocation Code - START----------------
          //max = (max * 2) + 1; //simply doubling the size (dynamic allocation)
          //int[] tempArray = new int[max];
          //for(int i=0;i<size;i++){
          //  tempArray[i] = array[i];
          //}
          //array = tempArray;
          //array[size] = val;
          //head = array[size];
          //size++;
          //------------------Dynamic Allocation Code - END----------------
  }
}

public class ArrayStackLimitedImpl {
    public static void main(String[] args) {
       ArrayStack s = new ArrayStack(3);
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(4);
       s.push(4);
       s.push(4);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
    }
}

Linked List Implementation

class ListNode{
  ListNode next;
  int val;
  
  ListNode(int val){
    this.val = val;  
  }
  
}

class LinkedListStack{
    ListNode tail;
    int size;
   
//get the current size of the stack 
    public int getSize(){
      return size;
    }

//return true if size == 0
  public boolean isEmpty(){
    return size == 0;
  }

//return the top element  
  public int peek(){
    return tail.val;
  }

//pop the last inserted element if not empty
//store the top element by peek
//top will be pointing to the next element
//decrement the size
//return the top value  
  public int pop(){
    if(!isEmpty()){
      int val = peek();
      tail = tail.next;
      size--;
      return val;
    }
      System.out.println("No Element");
      return -1;

  }

//push the new element
//set the new node's next element as the previous top element
//set current top element as the new node
//increment the size
  public void push(int val){
    ListNode newNode = new  ListNode(val);
    newNode.next = tail;
    tail = newNode;
    size++;
  }
}

public class YourClassNameHere {
    public static void main(String[] args) {
       LinkedListStack s = new LinkedListStack();
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(7);
       s.push(8);
       s.push(9);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
      
    }
}

Test cases

Cannot pop if the stack is empty
In bounded stack if the size of the stack reaches max then it will not allow pushing further elements to the stack
peek should not pop the element

Bit Manipulation

March 21, 2016

Bit

Leave a comment

Bitwise Operation

You have to be comfortable with Bitwise operations (<<, >>, &, | , ~, ^). Please have a look at the basics here.

These are the operations to summarize

& - bitwise and
| - bitwise or
~ - bitwise nor
^ - bitwise xor
<< - bitwise left shift
>> - bitwise right shift

In this section I will get to more detailed explanation of the operations that we have seen in the previous post and also techniques for some new operations.

Masking

Masking is very basic in bit manipulation and make sure you get that right before starting any bit level operations.

use left shift (<<) to increase the shift from LSB to MSB
use right shift (>>) to increase the shift from LSB to MSB

How to mask?

Take a number lets say x = 8; The binary representation for this for 8 bit register will be 0000 1000
Lets consider that we are masking this number with a mask which is at the 0th position, that will be 0000 0001 = 1

x(8)       0000 1000
mask(1)    0000 0001
------------------------------------
x & mask will give us 0000 0000 - 0
x | mask will give us 000 1001 - 9
x ^ mask will give us 000 1001 - 9

What if we want to mask the bit at the position 4

Left shift the mask 1 with 4. this will move the bit to the 4th position. from
mask = 1 << 4 = (0000 0001 << 4)= 0000 1000

Now

x(8)            0000 1000
mask(1 << 4)    0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 000 1000 - 8
x ^ mask will give us 000 0000 - 0

This is enough to start with our first bit trick.

#1 . How to check if the Integer is even or odd

We know that

for even number we will have LSB set to 0 always
for odd number we will have LSB set to 1 always

x(3)    0000 0011
1       0000 0001
------------------------------------
x & 1 will give us 0000 0011 - 3

So with this trick we can come up with the code like

if((x & 1) == 0)
   //even
else
   //odd

#2 . Check if the n’th bit is set or not

we take the number, lets say x = 8 => 0000 1000
prepare a mask for the nth position at which you want to check the bit
do the bit wise (x & mask)
bit wise & will be 1 if both the bits are set to 1. If the output is 1 for that bit then the bit is set

case 1 – position – 4

x(8)          0000 1000
mask(1 << 4)  0000 1000
------------------------------------
x & mask will give us 0000 1000 - 8
x | mask will give us 0000 1000 - 8

case 2 – position – 3

x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x & mask will give us 0000 1000 - 0
x | mask will give us 0000 1100 - 12 (we cannot use |)

We can write code for this like

if(x & (1 << position))
   // bit is set
else
  // bit is not set

#3 . Set the n’th bit

we take the number, lets say x = 8 => 0000 1000
prepare a mask for the nth position at which you want to check the bit
do the bit wise (x | mask)
for the position where the bit is 0 doing a bit wise | will set the bit to 1

x(8)          0000 1000
mask(1 << 3)  0000 0100
------------------------------------
x | mask will give us 0000 1100 - 12
y = x | (1 << position)

#4 . Unset the n’th bit

we take the number, lets say x = 12 => 0000 1100
prepare a mask for the nth position at which you want to check the bit
do the bit wise (x & ~mask)
for the position where the bit is 0 doing a bit wise | will set the bit to 1.

x(12)                     0000 1100
mask(1 << 3)   0000 0100 
~mask(1 << 3)             1111 1011
---------------------------------------------------
x & ~mask will give us 0000 1000 - 8
y = x & ~(1 << position)

#5 . Toggle the n’th bit

we take the number, lets say x = 12 => 0000 1100
prepare a mask for the nth position at which you want to check the bit
do the bit wise (x ^ mask)
for the position where the bit is 0 doing a bit wise | will set the bit to 1.

x(8)           0000 1000
mask(1 << 3)   0000 0100 
---------------------------------------------------
x ^ mask will give us 0000 1100 - 12
y = x  ^ (1 << position)

#6 Turn off the right most 1 bit

we take the number, lets say x =8 => 0000 1000
subtract 1 from x (x – 1)
Bitwise & x and (x – 1)

x(8)         0000 1000 
x-1 (7)      0000 0111 
---------------------------------------------------
x & (x- 1) will give us 0000 0000 - 0 (4th position 1 is changed)

x(7)         0000 0111 
x-1 (6)      0000 0110
---------------------------------------------------
x & (x- 1) will give us 0000 0110 - 6 (0th position 1 is changed)
y = x & (x - 1)

#7 Turn on the rightmost 0 bit

we take the number, lets say x =8 => 0000 1000
Add 1 to x (x + 1)
Bitwise | x and (x – 1)

x(8)         0000 1000 
x+1 (9)      0000 1001 
---------------------------------------------------
x | (x + 1) will give us 0000 1001 - 9

x(7)         0000 0111 
x+1 (8)      0000 1000
---------------------------------------------------
x | (x- 1) will give us 0000 1000
y = x | (x + 1)

#8 Isolate the rightmost 1 bit

we take the number, lets say x =8 => 0000 1000
take -x (-x)
Bitwise & x and (-x)

x(11)         0000 1011 
-x (-11)      1111 0101         (~x + 1)
---------------------------------------------------
x & (-x) will give us 0000 0001 - 1
y = x & (-x)

#9 Isolate the rightmost 0 bit

we take the number, lets say x =8 => 0000 1000
do the ~ of x
Bitwise & ~x and (x + 1)

~x(11)         1111 0101 
(x + 1)        0000 0110
---------------------------------------------------
~x & (x + 1) will give us 0000 0100
y = ~x & (x + 1)

Reference:
https://graphics.stanford.edu/~seander/bithacks.html
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

Bit Basics

March 20, 2016

Bit

1 Comment

Bits are basically represented in either 1 or 0 so the each bit contains either of the 2 values

For integer which can hold 32 bits = 4 bytes

Integer max value

Decimal: 2147483648 – (2 power 31)

Binary: 10000000 00000000 00000000 00000000

Integer min value

Decimal: 2147483647 – (2 power 31) – 1

Binary: 11111111 11111111 11111111 11111111

Following table will help to visualize bits in detail

This code will give compile error

byte ch = 129; // byte will hold upto 127

No need to cast explicitly to change byte to int

int x = ch;
x = 2000; // now x can hold upto 2147483648

you need explicit casting to change integer to byte and you will loose data

int x = 2000;
byte ch = (byte) x; // will reduce the value 2000 to 127;

Left Shift (<<)

It is a bit wise operation which will let you shift the bit position.
We use this << operator for moving the bit to the position.
Left shift is equivalent to the number multiplied by 2

In the below table we move the ‘1’ from the least significant bit(LSB) to the position specified

Right Shift (>>)

This is opposite the left shift where we move the bit to right
It is equivalent to dividing the number by 2

Bitwise AND (&)

This will do the AND operation at the bit level. The following code will check number of bits set for the given number

    int x = 65;
    int count= 0;
    while(x>0){
         x = x & (x - 1);
         count ++;
    }

Bitwise OR (|)

This will do the OR operation at the bit level. The following code will check if a bit is set at the given position

    int x = 8;
    int position = 3;
    int mask = 1 << position;
    System.out.println(x | mask);

Bitwise NOT (~)

This operator will help to clear a bit.

    int x = 8;
    int position = 3;
    int mask = 1 << position;
    System.out.println(x & ~mask);

Bitwise XOR (^)

We can use the XOR operator to toggle a bit.

   int x = 8;
   int position = 3;
   int mask = 1 << position;
   System.out.println(x ^ mask);

Primitive Data Structures – Overview

March 16, 2016

Bit, Character, Data Structures, Integer

Leave a comment

Memory Representation

Representation of boolean, char, Integer in memory

Boolean

(1/0) or (true/false) or (+/-) or (Yes/No)
used for checking if the given condition passes
used in logic checking (AND OR NOT)
represented as a binary digit or 1 bit (Java and size not precisely defined)

Array: boolean array – boolean[]

Byte

8 bit signed two’s complement integer
-128 to 127
used to save memory for arrays
and in some time use in place of int also
Array: byte array – byte[]

Character

characters are letters, digits, special characters, control characters
in java these are 16 bits Unicode characters from ‘\u0000’ to ‘\uffff’
represented in ASCII(256 or 2 power 8) or UTF-8 encodings (65535 or 2 power 16)
characters together forms a String
Array: char array – char[]

Note: when you type a character in a notepad and store it will be stored as 1 byte

ASCII character -> 1 byte – 8 bit
enter /return -> 2 bytes – 16 bit

Floating Point

stored in memory as exponents (8 bit) and mantissa (23 bit) and sign bit (1 bit)
float – 32 bit
double – 64 bit
Array: float array – float[]

Integer

short – 16 bit
int – 32 bit
long – 64 bit
Array: char array – int[]

Enumerated Types

These are fixed length strings

Common Test Cases for Integer Array and Strings

March 13, 2016

Arrays, Character, Strings

Leave a comment

Integer Array

Check for null input array
- passing null to the function call

findMid(null); // expecting valid array elements

check : if(array != null)

Check for validity of data type
- passing improper data type to the function call

char[] ch = new char[10];

findMid(ch); //expecting an integer array

check: if(array instanceof int[])

Check for no valid elements
- passing a valid integer array with no proper values for the function
- This can be considered as one of the input and this check is debatable

int[] val = new int[10];

findMid(val); //expecting a valid input array of length 3

check: if(array.length > 3)

Check for single elements
- passing an array with single element in it

int[] val = {1};

findMid(val); // expecting at least 3 elements

check: if(array.length > 3)

Check for all positive numbers
- This is a positive testing with proper values for the array elements

int[] val = {1,2,3,4,5}

check: if(array[index] > 0)

Check for all negative numbers
- pass negative numbers for the array inputs
- your function should consider negative values also

int[] val = {-11,-12,-13,-4,-5}

check: if(array[index] < 0)

Check for duplicate elements
- pass duplicates and see how the function responds
- you function should handle duplicates

int[] val = {-11,-11,0,0,1,1}

check: if(array[index] != array[index+1]) // in sorted adjacent duplicates

Check for positive and negative number combinations
- pass combinations of negative and positive values

int[] val = {-11,7,5,-13,0,1,21,-31}

Check for Minimum and Maximum overflow
- pass value that is over the integer max or min value
- your function should handle overflows

int[] val = {2147483647,65535 ,–2147483648,4294967295};

check: if(array[index] > Integer.MAX_VALUE)

if(array[index] < Integer.MIN_VALUE)

Check for Array Index Overflow
- sometimes array index overflow arises if you are checking for a value that is referring to an invalid index in an array
- your function should not result in array index overflow and you should handle it

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

if(array[i] == array[i+1]) //array index overflow for array[i+1]

}

Check for ordering / non ordering
- some times you might want to check if the array is sorted or not before processing further. in case of Binary Search in an array

Strings

Check for null input
- passing null to the function call

check: if(str != null)

Check for “” for string as input
- passing no value to the string

check: if(!str.equals(“”))

Check for single character
- passing single character to the string

check: if(str.length > 3) //expecting minimum of 3 character in the input string

Check for case sensitivity
- you will have to check for case sensitive for the function involving character manipulations

check: if(str.charAt(index) >= 65 && str.charAt(index) <= 90 ) // upper case

if(str.charAt(index) >= 97 && str.charAt(index) <= 122 ) // lower case

Check for digits
- you will have to limit the characters to digits for integer calculations considering only 0 to 9

check: if(str.charAt(index) >= 48 && str.charAt(index) <= 57)

Check for special characters
- you will have to consider only special characters at times in a function
- some common special characters are space (32), comma (44), colon (58), semicolon (59) etc. for others you can look up the ASCII table and get the corresponding values

check: if(str.charAt(index) == 32 || str.charAt(index) == 44 || str.charAt(index) == 58 || str.charAt(index) == 59)

Check for duplicate characters
- consider duplicate character presence consecutively.

check: if(str.charAt(index) == str.charAt(index + 1))

Check for ASCII or Unicode characters
process for ASCII or Unicode according to the need

check: if(str.getBytes( “UTF-8” ))

Check for index out of bound access
- look for index out of bound when using charAt() function

Function

Check if the function returns a value
- sometimes we tend to have a return statement which is inside an if clause but forget to add a default return statement
Check for base case of the problem first
- some of the base case for the problem is to be added at the top of the function to by pass additional checks

These are some of the basic test cases to be considered for most of the functions that you write in java or any other languages

Leetcode – 16 – 3Sum Closest

March 12, 2016

Arrays, Leetcode

Leave a comment

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Description:

This problem is same as that of Leetcode – 15 – 3Sum but the change is that we have return the closest sum instead of the elements adding up to zero.

Solution (three pointers)

The approach that we are talking about is to sort the array first and then have one pointer running along the length of the array. We will have another two pointer to point to the start and end of the array elements

We will check for the sum store in a variable and if its equal to the target then we return the result. Otherwise we will get the difference and see if the value is closest enough to the target and return the closest after checking for all the elements in the array.

Code:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int leastDiff = Integer.MAX_VALUE;
        int closest = 0;
        if(nums != null && n >= 3){
            Arrays.sort(nums);
            for(int i=0;i < n-2;i++){
                for(int j = i+1, k = n-1;j<k;){
                    int result = nums[i] + nums[j] + nums[k];
                    if(result == target){
                        return result;  
                    }
                    else{
                        int diff = Math.abs(target - result);
                        if(diff < leastDiff){
                            leastDiff = diff;
                            closest = result;
                        }
                        if(result > target){
                          k--;  
                        }
                        else{
                         j++;   
                        }
                    }
                }
                }
            }
            return closest;
        }    
    }

Time Complexity: O(n2)

Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

We will adding 3 elements to the list and can have n number of combinations – O(n)

Available Test Cases: 120

Check for empty array
Check for duplicate elements

Github:

Leetcode_16_3_Sum_Closest

Leetcode – 15 – 3Sum

March 11, 2016

Arrays, Leetcode

1 Comment

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Description:

In this problem we have to find all the number combinations in the array which will add upto 0. We have to consider that the output should be sorted.

Solution (three pointers)

We will check for the sum and if the sum is 0 then we we will add it to the list and move forward with increment the second and decrement third pointer

We will ignore any duplicates along the way.

Code:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for(int i = 0; i < nums.length-2; i++) {
        if(i > 0 && (nums[i] == nums[i-1])) continue; // avoid duplicates
        for(int j = i+1, k = nums.length-1; j<k;) {
            if(nums[i] + nums[j] + nums[k] == 0) {
                list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                j++;k--;
                while((j < k) && (nums[j] == nums[j-1]))j++;// avoid duplicates
                while((j < k) && (nums[k] == nums[k+1]))k--;// avoid duplicates
            }else if(nums[i] + nums[j] + nums[k] > 0) k--;
            else j++;
        }
    }
    return list;
}
}

Time Complexity: O(n2)

Go through the length of array elements and check for elements adjacent to the current element – O(n2)

Space Complexity: O(1)

We will adding 3 elements to the list and can have n number of combinations – O(n)

Available Test Cases: 311

Check for empty array
Check for duplicates

Github:

Leetcode_15_3_sum

Java – 2- Checking character properties

March 10, 2016

Character, Java, Leetcode

Leave a comment

Normally we tend to check the character by comparing with ‘a’ or ‘z’ or ‘X’ or ‘1’ or ‘:’ but this is considered wrong and we should avoid comparing characters like this

Why is this not efficient?

Consider the following code

if(ch == 'a' || ch  >= '0'){
//some code

The above code will work only for English and few other languages. For the sake of working with internationalization we should modify the code to

if(Character.isDigit(ch) || Character.isUpperCase(ch))

Some of the properties of Characters which is useful are

isDigit
isLetter
isLetterOrDigit
isLowerCase
isUpperCase
isSpaceChar
isDefined

Complete list of properties of Characters are here

Note: We can also compare the character with their corresponding ASCII values

Java – 1 – Character.valueOf()

March 10, 2016

Character, Java

Leave a comment

Character.valueOf(char c)

Algorithm

Check if the character is less than 127
Return the cache value from the private CharacterCache class
Otherwise return the new Character

public static Character valueOf(char c) {
    if(c <= 127) { // must cache
        return CharacterCache.cache[(int)c];
    }
        return new Character(c);
  }

CharacterCache class

This class has a cache array of size 127 + 1
Keep adding the characters from 0 to 127 (‘\u0000‘ to ‘\u007F‘)
Next time when the valueOf method is called on Character then we will be returning from the cache

private static class CharacterCache {
    private CharacterCache(){}

static final Character cache[] = new Character[127 + 1];

 static {
        for(int i = 0; i < cache.length; i++)
                 cache[i] = new Character((char)i);
         }
    }

—{Problem Sets} —

Tree – Implementation

Stack – Implementation

Bit Manipulation

Bit Basics

Primitive Data Structures – Overview

Common Test Cases for Integer Array and Strings

Integer Array

Strings

Function

Leetcode – 16 – 3Sum Closest

Java – 2- Checking character properties

Java – 1 – Character.valueOf()