Showing posts with label Adobe. Show all posts
Showing posts with label Adobe. Show all posts
, , , ,  

Root to leaf path sum equal to a given number

Problem:Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given below is the tree and sum = 62

Output: Yes

5 -> 25 -> 11 -> 19

Method 1: Add all node to a queue and store sum value of each node to another queue. When it is a leaf node, check the stored sum value.

For the tree above, the queue would be: 5 - 9 - 27 - 14 - 11 - 19 - 21. It will check node 14, 19 and 21. This is a typical breadth first search(BFS) problem.
import java.util.*;

/* definetinon for creation of tree */
class Node 
{
    int data;
    Node left, right;
  
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {

    Node root;

    public boolean hasPathSum(Node root, int sum) {

        /* handling base case */
        if(root == null) 
            return false;
 
        LinkedList<Node> nodes = new LinkedList<Node>();
        LinkedList<Integer> values = new LinkedList<Integer>();
 
        nodes.add(root);
        values.add(root.data);
 
        while(!nodes.isEmpty()) {
            Node curr = nodes.poll();
            int sumValue = values.poll();
 
            /* check if current node is root root and sum is 
               equal to required sum */
            if(curr.left == null && curr.right == null && sumValue==sum) {
                return true;
            }
 
            /* checking for left node */
            if(curr.left != null) {
                nodes.add(curr.left);
                values.add(sumValue + curr.left.data);
            }
 
            /* checking for right node */
            if(curr.right != null) {
                nodes.add(curr.right);
                values.add(sumValue + curr.right.data);
            }
        }
 
        return false;
    }

    /* driver method */
    public static void main(String args[]) 
    {
        int sum = 62;
         
        /* binary tree is
               5
             /   \
            9    27
           /      \
          14      11
                /   \
               19   21
        */
               
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(9);
        tree.root.right = new Node(27);
        tree.root.left.left = new Node(14);
        tree.root.right.right = new Node(11);
        tree.root.right.right.left = new Node(19);
        tree.root.right.right.right = new Node(21);
  
        if (tree.hasPathSum(tree.root, sum))
            System.out.println("There is a root to leaf path with sum " + sum);
        else
            System.out.println("There is no root to leaf path with sum " + sum);
    }
}
Output:
There is a root to leaf path with sum 62
Time Complexity: O(n)

Method 2: We can also do this problem using recursion. Below is the function program for recursion.
public boolean hasPathSum(TreeNode root, int sum) {

    /* handling base case */
    if (root == null)
        return false;

    /* if current node is leaf node */
    if (root.val == sum && (root.left == null && root.right == null))
        return true;
 
    /* recursing for left and right sub-tree */
    return hasPathSum(root.left, sum - root.val)
            || hasPathSum(root.right, sum - root.val);
}
Time Complexity: O(n)
, ,  

Reverse every K nodes of a Linked List

Problem: Given a linked list and a positive number K, reverse every K nodes in the list.

For example:
Input L1: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
      K = 3
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> NULL

Input L2: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL 
      K = 2
Output 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> NULL
Method 1: Recursive Method
  1. Reverse the first sub-list of size k. 
  2. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
  3. Now next points to (k+1)th node
  4. head->next = reverse(next, k), Recursively call for rest of the list and link the two sub-lists
  5. return prev, prev becomes the new head of the list
Node reverseKNodes(Node *head, int k)
{
    Node curr = head;
    Node next = null;
    Node prev = null;
    
    int count = 0;

    /* Reverse first k nodes of linked list */
    while (count < k && curr != null) 
    {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        count++;
    }

    /* next is now a pointer to (k+1)th node 
       Recursively call for the list starting from current.
       And make rest of the list as next of first node */
    if (next != null) 
        head.next = reverseKNodes(next, k);

    /* prev is now head of input list */
    return prev;
}   
Time Complexity: O(n)
,  

Print Right View of a Binary Tree

Problem: Given a Binary Tree, print right view of it. Right view of a Binary Tree is set of nodes visible when tree is visited from right side.

For example: Given the following tree, the right view of tree is 30, 40, 45, 12

Method 1: The naive approach is to do level order traversal of the binary tree and print the last node of all the levels.

Method 2: We can also do this problem using recursion. The idea is to keep track of maximum level and the current level. Here we traverse the tree in a manner that right sub tree is visited before left sub tree. Whenever current level is greater than the maximum level so far obtained, we print the current node because this is the last node in its level.

Below is the implementation of the idea.
#include <bits/stdc++.h>
using namespace std;
 
struct node
{
    int data;
    node *left;
    node *right;
};
 
/* utility funcion for new node in binary tree */
node* newNode(int data)
{
    node *temp = new node();
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
/* function to print the right view */
void rightView(node *root, int *max_level, int cur_level)
{
    /* base case */
    if(root == NULL)
        return;
 
    /* if the current node is last node in level */
    if(*max_level < cur_level)
    {
        cout<<root->data<<" ";
        *max_level = cur_level;
    }
 
    /* recursive call for left sub tree and right sub tree */
    rightView(root->right, max_level, cur_level + 1);
    rightView(root->left, max_level, cur_level + 1);
}
 
/* driver function */
int main()
{
    node *root              = newNode(30);
    root->left              = newNode(20);
    root->right             = newNode(40);
    root->left->left        = newNode(10);
    root->right->left       = newNode(37);
    root->right->right      = newNode(45);
    root->left->left->right = newNode(12);
 
    int max_level = 0;
    rightView(root, &max_level, 1);
    cout<<"\n";
 
    return 0;
}
Output:
30 40 45 12
Time Complexity: O(n)
, , , ,  

Sort linked list containing 0’s, 1’s and 2’s

Problem: Given a linked list containing 0’s, 1’s and 2’s, sort linked list. Can you do this in a single traversal?

For example:
Input: 0 -> 1 -> 2 -> 2 -> 1 -> 0 -> 0 -> 2 -> 0 -> 1 -> 1 -> 0 -> NULL
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> NULL

Input: 2 -> 1 -> 2 -> 1 -> 1 -> 2 -> 0 -> 1 -> 0 -> NULL
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> NULL
Method 1: Simplest method one can com across is counting the frequency of zero, one and two in first traversal and in second traversal updating the values of the nodes of linked list in required order.
void sortLinkedlist(struct Node *head)
{
    /* handling base case */
    if(head == NULL || head->next == NULL)
        return;

    /* count total number of '0', '1' and '2'
       count[0] will store total number of '0's
       count[1] will store total number of '1's
       count[2] will store total number of '2's  */
    int count[3] = {0, 0, 0};

    struct Node *temp = head;

    /* counting the frequencies */
    while (temp)
    {
        count[temp->data] += 1;
        temp = temp->next;
    }

    int i = 0;
    temp = head;

    /* updating the values in required order */
    while(temp)
    {
        if (count[i] == 0)
            ++i;
        else
        {
            temp->data = i;
            count[i]--;
            temp = temp->next;
        }
    }
}
Time Complexity: O(n) and Space Complexity: O(1)

Method 2: The above method is using two traversal. According to our problem statement, can we do it in single traversal? Yes, we can do this in single traversal. Following is the approach:

For each Node in the list:
  • If it has 0 
    • Move to the Front of list 
  • If it has 2 
    •  Move to the End of list 
  •  If it has 1 Do nothing.
void sortLinkedlist(Node* &head)
{
    /* handling base case */
    if(head == NULL || head->next == NULL)
        return;
    
    /* pointer to last node in the linked list */
    Node *lst = head;
    int totalNodes = 1;
    while(lst->next != NULL)
    {
        lst = lst->next;
        totalNodes++;
    }

    Node *tail = lst;
    Node *ptr = head;
    Node *prev = head;
    for(int i = 0; i < totalNodes; i++)
    {
        Node *curr = temp;
        temp = temp->next;

        if(curr->data == 0)
        {
            /* insert it at head */
            if(prev != curr)
            {
                curr->next = head;
                head = curr;
                prev->next = temp;
            }
        }
        else if(curr->data == 2)
        {
            /* insert it at the end */
            tail->next = curr;
            curr->next = NULL;
            tail = curr;

            /* if first Node */
            if(prev == curr)
                head = prev = temp;
            else
                prev->next = temp;
        }
        else
        {
            if(prev != curr)
                prev = prev->next;
        }
    }
}
Time Complexity: O(n) and Space Complexity: O(1)

Method 3: There is one more method to do this problem in single traversal. The idea is to maintain three pointers zeros, ones and twos. Then, we traverse the list from head to end and move each node to the corresponding list depending on its value. Finally, we combine all three lists at the end and x the head pointer.
void sortLinkedlist(Node* &head)
{
    /* handling base case */
    if (head == NULL || head->next == NULL)
        return;
 
    /* three dummy nodes one each for zeros, one and twos */
    struct Node zeros, ones, twos;

    zeros->next = NULL;
    ones->next = NULL;
    twos->next = NULL;
 
    struct Node *curr = head;
 
    /* travering the list */
    while (curr != NULL)
    {
        if (curr->data == 0)
        {
            zero->next = curr;
            zero = zero->next;
        }
        else if (curr->data == 1)
        {
            one->next = curr;
            one = one->next;
        }
        else
        {
            two->next = curr;
            two = two->next;
        }
        curr = curr->next;
    }
 
    /* combining lists containing 0's, 1's and 2's */
    zero -> next = (ones -> next) ? (ones -> next) : (twos -> next);
    one -> next = twos.next;
    two -> next = NULL;
 
    /* change head to point new head */
    head = zeros->next;
}
Time Complexity: O(n) and Space Complexity: O(1)
,  

Count set bits in an integer

Problem: Write an efficient program to count number of 1s in binary representation of an integer.

For example:
Input: n = 5
Output: 2
Binary representation of 5 is (101). We see it has 2 set bits.

Input: n = 13
Output: 3
Binary representation of 13 is (1101). We see it has 3 set bits.
Method 1: Simple Method is to loop through all bits in the integer and check if a bit is set. If it is then increment the set bit count.
#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}
Output:
2
Time Complexity: (-)(logn) (Theta of logn)

Method 2: We can count bits in O(1) time using lookup table.
#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}
Output:
2
3
Time Complexity: O(1)

Note:  In GCC, we can directly count set bits using __builtin_popcount().


References:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable