Search in a matrix

 

Problem:

Given a matrix mat[][] of size N x M, where every row and column is sorted in increasing order, and a number X is given. The task is to find whether element X is present in the matrix or not.

Example 1:

Input:
N = 3, M = 3
mat[][] = 3 30 38 
         44 52 54 
         57 60 69
X = 62
Output:
0
Explanation:
62 is not present in the
matrix, so output is 0

My Answer:

    public static int matSearch(int mat[][], int N, int M, int X)
    {
        for ( int n = 0 ; n < N ; n++ ) {
            for ( int m = 0 ; m < M ; m++ ) {
                if ( mat[n][m] == X ) {
                    return 1;
                }
            }
        }
        
        return 0;
    }

Word Break

Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.

Note: From the dictionary B each word can be taken any number of times and in any order.
Example 1:

Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream",
"man", "go", "mango" }
A = "ilike"
Output:
1
Explanation:
The string can be segmented as "i like".

Example 2:

Input:
n = 12
B = { "i", "like", "sam",
"sung", "samsung", "mobile",
"ice","cream", "icecream", 
"man", "go", "mango" }
A = "ilikesamsung"
Output:
1
Explanation:
The string can be segmented as 
"i like samsung" or "i like sam sung".

 

Your Task:
Complete wordBreak() function which takes a string and list of strings as a parameter and returns 1 if it is possible to break words, else return 0. You don't need to read any input or print any output, it is done by driver code.

(https://practice.geeksforgeeks.org/problems/word-break1352/1)

My Answer:

class Sol
{
    public static int wordBreak(String A, ArrayList<String> B )
    {
        //code here
        int startIdx = 0;
        int len = 0;
        String word = null;
        Collections.sort(B, Comparator.comparing(String::length).reversed());

        for (int i = 0 ; i < B.size() ; i++) {
            word = B.get(i);
            if (A.contains(word)) {
                startIdx = A.indexOf(word);
                len = word.length();
                A = A.substring(0,startIdx) + A.substring(startIdx+len);
                i--;
            }
        }
        
        if (A.length() == 0) {
            return 1;
        }
        
        return 0;
    }
}

Count BST nodes that lie in a given range

 Given a Binary Search Tree (BST) and a range l-h(inclusive), count the number of nodes in the BST that lie in the given range.

• The values smaller than root go to the left side
• The values greater and equal to the root go to the right side

Example 1:

Input:
      10
     /  \
    5    50
   /    /  \
  1    40  100
l = 5, h = 45
Output: 3
Explanation: 5 10 40 are the node in the
range

Example 2:

Input:
     5
    /  \
   4    6
  /      \
 3        7
l = 2, h = 8
Output: 5
Explanation: All the nodes are in the
given range.

Your Task:
This is a function problem. You don't have to take input. You are required to complete the function getCountOfNode() that takes root, l ,h as parameters and returns the count.

My Answer:

    int getCount(Node root, int l, int h)
    {
        int count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list = getNodeData(root, list);
        Collections.sort(list);
        for( Integer number : list) {
            if ( number >= l && number <= h ) count = count + 1;
        }
        
        return count;
    }
    
    public ArrayList<Integer> getNodeData(Node node, ArrayList<Integer> list) {
        if( node == null ) return list;
        else {
            list.add(node.data);
            list = getNodeData(node.left, list);
            list = getNodeData(node.right, list);
            return list;
        }
    }

Determine if Two Trees are Identical

 Given two binary trees, the task is to find if both of them are identical or not. 

Example 2:

Input:
     1          1
   /   \      /   \
  2     3    2     3
Output: Yes
Explanation: There are two trees both
having 3 nodes and 2 edges, both trees
are identical having the root as 1,
left child of 1 is 2 and right child
of 1 is 3.

Example 2:

Input:
    1       1
  /  \     /  \
 2    3   3    2
Output: No
Explanation: There are two trees both
having 3 nodes and 2 edges, but both
trees are not identical.

Your task:
Since this is a functional problem you don't have to worry about input, you just have to complete the function isIdentical() that takes two roots as parameters and returns true or false. The printing is done by the driver code.

My Answer:

	boolean isIdentical(Node root1, Node root2)
	{
	    // Code Here
	    boolean result1 = true;
	    boolean result2 = true;

	    if( root1 == null && root2 != null) return false;
	    if( root1 != null && root2 == null) return false;
	    if( root1 == null && root2 == null) return true;
	    
	    if (root1.data == root2.data) {
	            result1 = isIdentical(root1.left, root2.left);
	            result2 = isIdentical(root1.right, root2.right);
	    } else {
	        return false;
	    }
	    
	    return result1 && result2;
	}

Mirror Tree

 Given a Binary Tree, convert it into its mirror.

            

Example 1:

Input:
      1
    /  \
   2    3
Output: 3 1 2
Explanation: The tree is
   1    (mirror)  1
 /  \    =>      /  \
2    3          3    2
The inorder of mirror is 3 1 2

Example 2:

Input:
      10
     /  \
    20   30
   /  \
  40  60
Output: 30 10 60 20 40
Explanation: The tree is
      10               10
    /    \  (mirror) /    \
   20    30    =>   30    20
  /  \                   /   \
 40  60                 60   40
The inroder traversal of mirror is
30 10 60 20 40.

Your Task:
Just complete the function mirror() that takes node as paramter  and convert it into its mirror. The printing is done by the driver code only.

My Answer:

    void mirror(Node node) {
        // Your code here
        if (node == null) return;
        mirror(node.left);
        mirror(node.right);
        Node temp = node.left;
        node.left = node.right;
        node.right = temp;
    }

Subarray with zero sum

Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.

Example 1:

Input:
5
4 2 -3 1 6

Output: 
Yes

Explanation: 
2, -3, 1 is the subarray 
with sum 0.

Example 2:

Input:
5
4 2 0 1 6

Output: 
Yes

Explanation: 
0 is one of the element 
in the array so there exist a 
subarray with sum 0.

Your Task:
You only need to complete the function subArrayExists() that takes array and n as parameters and returns true or false depending upon whether there is a subarray present with 0-sum or not. Printing will be taken care by the drivers code.

(https://practice.geeksforgeeks.org/problems/merge-2-sorted-linked-list-in-reverse-order/1)

My Answer:

    static boolean findsum(int arr[],int n)
    {
        int sum = 0;
        HashSet<Integer> set = new HashSet<>();
        for ( int num : arr ) {
            sum = sum + num;
           
            if (sum == 0) return true;
            if( set.contains(sum) ) return true;
           
            set.add(sum);
            
        }
        
        return false;
    }

Merge 2 sorted linked list in reverse order

Given two linked lists of size N and M, which are sorted in non-decreasing order. The task is to merge them in such a way that the resulting list is in decreasing order.

Input:
First line of input contains number of testcases T. For each testcase, first line of input contains length of both linked lists N and M respectively. Next two lines contains N and M elements of two linked lists.

Output:
For each testcase, print the merged linked list which is in non-increasing order.

User Task:
The task is to complete the function mergeResult() which takes reference to the heads of both linked list and returns the pointer to the merged linked list.

Constraints:
1 <=T<= 50
1 <= N, M <= 1000

Example:
Input:
2
4 3
5 10 15 40 
2 3 20
2 2
1 1
2 4

Output:
40 20 15 10 5 3 2
4 2 1 1 

Explanation:
Testcase 1: After merging the two lists in decreasing order, we have new lists as 40->20->15->10->5->3->2.

(https://practice.geeksforgeeks.org/problems/merge-2-sorted-linked-list-in-reverse-order/1)

My Answer:

    Node mergeResult(Node node1, Node node2)
    {
	    ArrayList<Integer> arrayList = new ArrayList<>();
	    while( node1 != null || node2 != null) {
                if( node1 == null ) {
                    arrayList.add(node2.data);
                    node2 = node2.next;
                } else if( node2 == null ) {
                    arrayList.add(node1.data);
                    node1 = node1.next;
                } else if ( node1.data <= node2.data ) {
	                arrayList.add(node1.data);
	                node1 = node1.next;
	        } else {
	            arrayList.add(node2.data);
	            node2 = node2.next;
	        }
	    }
	    
	    Node node = new Node(arrayList.get(arrayList.size()-1));
	    Node prevNode = node;
	    for (int i = arrayList.size()-2; i >= 0 ; i-- ) {
	        Node nextNode = new Node(arrayList.get(i));
	        prevNode.next = nextNode;
	        prevNode = nextNode;
	    }
	    
	    return node;
    }