algomaster, Author at Algo Tutor

0

Determine if singly linked list is a palindrome.

Posted on January 25, 2017 by algomaster

Problem statement:

Given a singly linked list, determine if it a palindrome.

Example:

Input: 1-> 2-> 3-> 2-> 1

Output: True

Description:

Palindrome is a word, number or sequence of characters which reads the same backward or forward. Words like noon, level or number like 12321, 161 are examples of palindrome.

We will check if given linked list is a palindrome using two approaches, one using stack and another by reversing half linked list.

1.Using stack:

Using stack, one way is to traverse entire linked list from head to tail and push each visited node on to stack. When entire linked list is traversed, start traversing linked list again from head and for each node check if node’s value matches to the stack pop node. If not, then return false.

Instead of pushing entire linked list on stack, lets push half linked list on stack and then as we continue to traverse linked list from middle node to tail, we will check for each node if node’s value is equal to stack pop value. If values are not equal then given linked list is not a palindrome.

private boolean isPalindrome(ListNode head)
   {
      if(head == null || head.next == null)
          return true;
      Stack<ListNode> stack = new Stack<ListNode>();
      ListNode slow = head;
      ListNode fast = head;
      ListNode prev = null;
      while(fast != null && fast.next != null)
        {
           prev = slow;
           stack.push(prev);
           slow = slow.next;
	   fast = fast.next.next;
	}
      if(fast != null)
        slow = slow.next;
      while(slow !=null)
	{
           if(slow.val != stack.pop().val)
	      return false;
	   slow = slow.next;
	}
      return true;
   }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

private boolean isPalindrome(ListNode head)

{

if(head == null || head.next == null)

return true;

Stack<ListNode> stack = new Stack<ListNode>();

ListNode slow = head;

ListNode fast = head;

ListNode prev = null;

while(fast != null && fast.next != null)

{

prev = slow;

stack.push(prev);

slow = slow.next;

fast = fast.next.next;

}

if(fast != null)

slow = slow.next;

while(slow !=null)

{

if(slow.val != stack.pop().val)

return false;

slow = slow.next;

}

return true;

}

For this approach time complexity is O(n) as entire linked list is traversed.Stack is used for maintaining previous nodes, so extra space required is n/2, by ignoring constant for large linked list, space complexity will be O(n) .

2. By reversing second half of linked list:

In this approach following steps will be followed.

Traverse linked list from head to middle of linked list.
Next step, is to divide linked list in two parts. One from head to middle and another from middle to tail of linked list.
Reverse second linked list.
Traverse and compare both linked list from head to tail.
If both lists are identical, given linked list is palindrome else not.

public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null)
       return true; 
    ListNode slow = head;
    ListNode fast = head; 
    ListNode prev = null;
    while(fast != null && fast.next != null)
      {
	 prev = slow;
         slow = slow.next;
         fast = fast.next.next;
      }
    if(fast != null)
      {
         prev = slow;
         slow = slow.next;
      }
    prev.next = null;  //Break linked list in two parts
    slow = reverse(slow);
    prev = head;
    while(slow != null)
      {
          if(prev.val != slow.val)
	      return false;
	  slow = slow.next;
	  prev = prev.next;
       }
     return true;
   }
    
public ListNode reverse(ListNode head){
     ListNode prev = null;
     while(head != null)
       {
          ListNode nextNode = head.next;
          head.next = prev;
	  prev = head;
          head = nextNode;
        }
     return prev;
 }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

public boolean isPalindrome(ListNode head) {

if(head == null || head.next == null)

return true;

ListNode slow = head;

ListNode fast = head;

ListNode prev = null;

while(fast != null && fast.next != null)

{

prev = slow;

slow = slow.next;

fast = fast.next.next;

}

if(fast != null)

{

prev = slow;

slow = slow.next;

}

prev.next = null; //Break linked list in two parts

slow = reverse(slow);

prev = head;

while(slow != null)

{

if(prev.val != slow.val)

return false;

slow = slow.next;

prev = prev.next;

}

return true;

}

public ListNode reverse(ListNode head){

ListNode prev = null;

while(head != null)

{

ListNode nextNode = head.next;

head.next = prev;

prev = head;

head = nextNode;

}

return prev;

}

In this approach linked list is traversed only once so time complexity will be O(n) and as constant space is required to store temporary ListNode values, space complexity will be constant, O(1).

0

Level Order Traversal of Binary Tree

Posted on January 19, 2017 by algomaster

Problem statement:

Level order traversal for binary tree.

Example:

Logic:

Basic idea behind level order traversal is explained in previous post on same topic. However, instead of using extra TreeNode as marker node to mark end of level, we will use ‘prevCount’ variable which will keep count for how many nodes we need to check if they have any child node in next level. For eg. for level 0, prevCount will be 1. So, we need to check for 1 node if there are any children. Number of children will be stored in ‘curCount’ variable. When prevCount is equal to 0, that means we finished checking for children of all the nodes at current level. Now prevCount will be curCount as for next level we need to check for curCount number of nodes. This idea will be more clear with below detail example for the above diagram.

At start prevCount = 1,curCount = 0, and queue contains: <50>. We will repeat below steps while queue is not empty.
Dequeue 5o, prevCount = 0, if left child of 50 present,curCount = 1 enqueue <35>, if right child of 50 present, curCount increment, curCount = 2, enqueue 57, queue <35,57>
Now, prevCount is 0 means all nodes of current levels are traversed, so prevCount = nextLevel, in this example prevCount = 2 and curCount is updated to 0.
Repeat step 2 and 3 till queue is not empty. prevCount =0, indicates that we finished traversing curCount and assigning curCount count to prevCount indicates how many nodes need to be traversed in next level.

Code:

public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> result = new LinkedList<List<Integer>>();
       List<Integer> levels = new LinkedList<Integer>();
       Queue<TreeNode> q = new LinkedList<TreeNode>();
       if(root == null)
	 return result;
       q.add(root);
       int preCount = 1;
       int curCount = 0;
       while(!q.isEmpty())
	{
	  TreeNode currentNode = q.remove();
	  preCount--;
	  levels.add(currentNode.val);
	  if(currentNode.left != null)
	   {
	     q.add(currentNode.left);
	     curCount++;
	   }
	   if(currentNode.right != null)
	    {
	      q.add(currentNode.right);
	      curCount++;
	    }
	   if(preCount == 0)
	    {
	      result.add(new LinkedList<Integer>(levels));
	      levels.clear();
	      preCount = curCount;
	      curCount = 0;
	    }
	 }
      return result;	 
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> result = new LinkedList<List<Integer>>();

List<Integer> levels = new LinkedList<Integer>();

Queue<TreeNode> q = new LinkedList<TreeNode>();

if(root == null)

return result;

q.add(root);

int preCount = 1;

int curCount = 0;

while(!q.isEmpty())

{

TreeNode currentNode = q.remove();

preCount--;

levels.add(currentNode.val);

if(currentNode.left != null)

{

q.add(currentNode.left);

curCount++;

}

if(currentNode.right != null)

{

q.add(currentNode.right);

curCount++;

}

if(preCount == 0)

{

result.add(new LinkedList<Integer>(levels));

levels.clear();

preCount = curCount;

curCount = 0;

}

return result;

}

Note:

This approach can be extended to perform level order traversal for k-ary tree. We can similarly keep track of number of nodes at parent level and number of nodes need to be traversed in next level.

0

Binary Tree Longest Consecutive Sequence

Posted on January 19, 2017 by algomaster

Problem statement:

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example:

Logic:

For each node we need to check if next node has a value equal to currentNode.value+1 because as per constraint only increasing order is allowed. If yes, increment count, else for that node number of elements in sequence will be 1. Before returning function call maxLength will store maximum number of elements in sequence till now. Recursively call this function for each child of node.

Code:

public int longestConsecutive(TreeNode root) {
        if(root == null)
          return 0;
        int count = 1;
        int maxLength = 1;
        maxLength = longestConsecutive(root,count,maxLength,root.val+1);
        return maxLength;
    }
    
    int longestConsecutive(TreeNode root, int count,int maxLength,int target)
    {
        if(root == null )
          return maxLength;
        if(root.val == target)
          count++;
        else
          count = 1;
        maxLength = Math.max(maxLength,count);
        maxLength = longestConsecutive(root.left,count,maxLength,root.val+1);
        return longestConsecutive(root.right,count,maxLength,root.val+1);
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public int longestConsecutive(TreeNode root) {

if(root == null)

return 0;

int count = 1;

int maxLength = 1;

maxLength = longestConsecutive(root,count,maxLength,root.val+1);

return maxLength;

}

int longestConsecutive(TreeNode root, int count,int maxLength,int target)

{

if(root == null )

return maxLength;

if(root.val == target)

count++;

else

count = 1;

maxLength = Math.max(maxLength,count);

maxLength = longestConsecutive(root.left,count,maxLength,root.val+1);

return longestConsecutive(root.right,count,maxLength,root.val+1);

}

0

Max Consecutive Ones

Posted on January 18, 2017 by algomaster

Problem statement: (Leetcode problem no:487)

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example:

Input: [1,0,1,1,0]

Output: 4

Description: Flip the first 0 will get maximum 4 consecutive 1s. If second 0 is flipped still we will get 4 consecutive 1s, as at the max one 0 flip is allowed.

Logic:

Maintain two pointers ‘low’ to keep track of start of 1s consecutive sequence and ‘zeroIndex’ pointer to mark index at which 0 is present. Whenever we encounter next 0 we will check if current length of consecutive 1s is more than previous if yes, we will update max length else max length remains same and we will update ‘low’ to mark start of next sequence of consecutive 1s.

Code:

public int findMaxConsecutiveOnes(int[] nums) {
       int low = 0,zeroIndex = -1,max = 0,i=0;
       for(i =0; i< nums.length;i++)
       {
           if(nums[i] == 0)
           {
               if(zeroIndex != -1)
               {
                   int len = i - low;
                   max = Math.max(max,len);
                   low = zeroIndex+1;
                   zeroIndex = i;
               }
               else
                 zeroIndex = i;
           }
       }
       return Math.max(max,i-low);
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

public int findMaxConsecutiveOnes(int[] nums) {

int low = 0,zeroIndex = -1,max = 0,i=0;

for(i =0; i< nums.length;i++)

{

if(nums[i] == 0)

{

if(zeroIndex != -1)

{

int len = i - low;

max = Math.max(max,len);

low = zeroIndex+1;

zeroIndex = i;

}

else

zeroIndex = i;

}

return Math.max(max,i-low);

}

0

LRU Cache

Posted on January 18, 2017 by algomaster

In computers, cache memory provides fast access to processor by storing frequently used computer programs, data and applications; However size of cache memory is relatively small. Because of the size constraint, it is required to invalidate data from cache and store new data frequently when it is full.So, algorithms are required to decide which data should be removed from cache.

One of the algorithm to decide what to remove from cache is Least Recently Used (LRU). In this algorithm, least recently used data is removed from cache.

Example:

Imagine cache size is 4. Initially data D1,D2 and D3 requested by some program.

– As initially cache is empty, all three data elements inserted in cache sequentially.

-Then D1 and D2 data access requested. As, it is already in cache, D1 and D2 will be accessed directly from cache.

-Now new data D4 requested by program ,as it is not in cache, D4 added in cache.

-Now new data D4 requested by program. As cache does not have D5 stored ,D5 needs to be added in cache.

However, cache is already full, so we need to replace data in cache. As per LRU algorithm, we will find least recently used data in cache. For current scenario it is D3. Though, D3 inserted in cache after D1 and D2, data D1 and D2 accessed after insertion however D3 not, so we will remove D3 from cache and insert D5 in cache.

Input : Cache capacity and <key,value> pair as data.

Problem statement:(Leetcode problem no. 146)

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

To keep track of recently used data, we will use LinkedHashSet data structure and input data will be stored in HashMap as input is in the form of key, value.

Logic:

– Whenever new data is put in cache(HashMap) using set function check if cache is completely filled, if not add that value to cache. Insert key value in LinkedHashSet. Else, extract oldest element from LinkedHashSet (which will be first element in hashSet) and remove that from HashMap and then insert new <key,value>.

– If get function called which is accessing data already present in cache, value for the key is returned from HashMap if present, else -1. Requested key removed from LinkedHashSet and inserted again. Removal of required as LinkedHashSet keep keys in order of access.

– If set function called however that key is already present in the cache (HashMap), we need to update value of that key and make it most recently used by removing key from HashSet and inserting it again.

Code:

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LRUCache {
    
     private HashMap<Integer,Integer> valueDict;
     private LinkedHashSet<Integer> list;
     private int cap;
	
    public LRUCache(int capacity) {
        cap = capacity;
		valueDict = new HashMap<Integer,Integer>();
		list = new LinkedHashSet<Integer>();
    }
    
    public int get(int key) {
      if(valueDict.containsKey(key))
	{
            list.remove(key);
            list.add(key);
	    return valueDict.get(key);
	}
       return -1;
    }
    
    public void set(int key, int value) {
        if(valueDict.containsKey(key))
     	   valueDict.put(key, value);
    	else
    	{
    	   if(valueDict.size() < cap)
    	      valueDict.put(key, value);
    	   else
    	     {
    		int first = 0;
    		for(int k : list)
    		 {
    		  first = k;
    		  break;
    		}
    		list.remove(first);
    		valueDict.remove(first);
    		valueDict.put(key, value);
    	      }
    	}
       if(list.contains(key))
          list.remove(key);
       list.add(key);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

import java.util.HashMap;

import java.util.LinkedHashSet;

public class LRUCache {

private HashMap<Integer,Integer> valueDict;

private LinkedHashSet<Integer> list;

private int cap;

public LRUCache(int capacity) {

cap = capacity;

valueDict = new HashMap<Integer,Integer>();

list = new LinkedHashSet<Integer>();

}

public int get(int key) {

if(valueDict.containsKey(key))

{

list.remove(key);

list.add(key);

return valueDict.get(key);

}

return -1;

}

public void set(int key, int value) {

if(valueDict.containsKey(key))

valueDict.put(key, value);

else

{

if(valueDict.size() < cap)

valueDict.put(key, value);

else

{

int first = 0;

for(int k : list)

{

first = k;

break;

}

list.remove(first);

valueDict.remove(first);

valueDict.put(key, value);

}

if(list.contains(key))

list.remove(key);

list.add(key);

}

0

Bitwise Operators

Posted on August 8, 2015 by algomaster

Bitwise operators are used to perform operations on bits. Most of the times programmers works on byte, int, char etc. data types and does not pay attention to bit level operations. However bit operators are used to manipulate values for comparisons and calculation.

Bits always have value either ‘1’ or ‘0’. Binary operators are used to manipulate these values. In simple words ‘1’ means bit is ‘set’ and ‘0’ means bit is ‘clear’.

Following are few operators used to perform bitwise operations:

NOT/Complement :

This is a unary operator which means it works on only one operand. Not operator flips each bit means 1 become 0 and 0 become 1.

Not 5: ~5 :: Not 0101 :: result will be 1010 (10).

AND ( & ) :

Binary And operator compares each bit of first operand to the corresponding bit of second operand in two equal length operands.

Result bit will be ‘1’ if and only if both bits in the compared positions are ‘1’.

When we multiply any number by 0, output is always 0. same rule applies to And operator, whenever we multiply 1*1 result bit will be 1.

Clear bit: & operator is used to clear a particular bit in a number.

Eg. clear 2^nd bit in 46 (0 0 1 0 1 1 1 0 ) :

Not of 1 changes only expected bit in number and keeps remaining bits as it is.

OR ( | ) :

Binary Or operator compares each bit of first operand to the corresponding bit of second operand in two equal length operands.

Result bit will be ‘o’ if and only if both bits in the compared positions are ‘0’.

Set bit : As we saw & operator is used to clear a particular bit in a number, Or operator is used to set a particular bit in number.

Eg. Set 4^thbit in 46 (0 0 1 0 1 1 1 0 ) :

.

This set bit method is used to efficiently store a number of Boolean values using little memory.

XOR ( ^ ) :

Binary Xor operator compares each bit of first operand to the corresponding bit of second operand in two equal length operands.

Result bit will be ‘1’ if and only if either of the bits in the compared positions are ‘1’. That means if both bits are 1 then result will be 0.

Any bit can be toggled when XORed with 1.

Xor is used in a tricky way to swap to integer variables without any extra space.

eg. int a = 3 , b=9. a: 0 0 1 1

b : 1 0 0 1

a= a ^ b (a will be 1 0 1 0)

b= a ^ b ( b will be 0 0 1 1) which is value of a, So now b=3

a= a ^ b (a will be 1 0 0 1) which is value of b, So now a =9

Left Shift ( << ) :

Left shift operator shifts bits in first operand to left by number of bits given in second operand and inserts 0 bits are filled in vacant bits.

Eg. 23 << 1 : 0 0 0 1 0 1 1 1 << 1 result is : 0 0 1 0 1 1 1 0

Right Shift ( >> ) :

Right shift operator shifts bits in first operand to right by number of bits given in second operand and inserts 0 in vacant bits for unsigned numbers and for unsigned numbers logically signed bit is copied as it is in most significant left bit and then 0 inserted in vacant bits. In C++, singed bit is copied in all the vacant bits.

Eg. 14 >> 2 : 0 0 0 0 1 1 1 0 >> 2 result is: 0 0 0 0 0 0 1 1

Tricks :

1. 0 1 1 1 + 0 1 1 1 (7+7) is equivalent to 0 1 1 1 * 2 (1 1 1 0 : 14), which is equivalent to shifting input number left by 1. 0 1 1 1 << 1 = 1 1 1 0 (14)

2. If a number is XOR with its own negated value, result will be sequence of 1s. Eg. 0 1 1 1 ^ (1 0 0 0 ) = 1 1 1 1 . i.e. 7 ^(~7)

3. If we multiply any number by 2ⁿ, simple way is to left shift that number by n. Eg. (3 * 4) 0 0 1 1 * 0 1 0 0 :: 4 =2²

so 0 0 1 1 << 2 : : 1 1 0 0

Author: algomaster

Determine if singly linked list is a palindrome.

Level Order Traversal of Binary Tree

Binary Tree Longest Consecutive Sequence

Max Consecutive Ones

LRU Cache

Bitwise Operators

Recent Posts

Algotutor