SDE - 1

Given a square binary matrix ‘mat[n][n]’, find ‘K’ such that all elements in the Kth row are ‘0’ and all elements in the Kth column are ‘1’. The value of mat[k][k] can be anything (either ‘0’ or ‘1’). If no such k exists, return ‘-1’.

For example

Consider the following matrix :
0 1 1 
0 1 0 
1 1 0 

You can see that row 1 (0-based) contains all 0’s except mat[1][1] and column 1 contains all 1’s. Hence the answer for the above case is 1.

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

Random pointers are shown in red and next pointers in black.

You are given a list, ‘DICTIONARY[]’ containing a list of words and a stream of characters (queries). Your task is to choose a suitable data structure to implement ‘CharacterStreamChecker’ class described as follows:

1) ‘CharacterStreamChecker(dictionary)’: Constructor to initialize the data structure with given words present in ‘DICTIONARY[]’.

2) ‘solveQuery(character)’: Function to check whether the string formed by last ‘C’ (C >= 1) queried characters (in order from oldest to newest, including the character just queried) is present in the ‘DICTIONARY[]’. If yes, return true. Otherwise, return false.

Note :

The ‘DICTIONARY[]’ contains only distinct strings.

The second question was a mixture of OOP and Problem Solving. You are provided with a function that has two parameters Object of a class LIST and an integer 'k.' The LIST class has an endpoint valAtIndex() that can be used to access the value at the index provided and it returns IndexOutOfBoundException if the index is greater than the size of the length of the LIST. LIST class uses some DS to store integers internally. You do not know the size of the LIST. So we have to check whether the integer k is present in the LIST or not (Return 1 or 0.) The LIST stores the elements in sorted order.

You are given a Doubly Linked List of integers and a positive integer 'K' representing the group size. Modify the linked list by reversing every group of 'K' nodes in the linked list.

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward. 

Note:

If the number of nodes in the list or in the last group is less than K, just reverse the remaining nodes. 

Example:

Linked list: 8 9 10 11 12
K: 3 

Output: 10 9 8 12 11

We reverse the first K (3) nodes. Now, since the number of nodes remaining in the list (2) is less than K, we just reverse the remaining nodes (11 and 12).  

You are given an arbitrary binary tree consisting of N nodes. Your task is to find the largest subtree sum.

Note :

1. The value of any node will not be equal to zero.
2. Subtree of a node X is all the nodes that are below X and X itself.
3. For example in the tree given below, nodes 1, 2 and 3 are in subtree of 1.

4. Subtree sum of X is the sum value of all the nodes in subtree of X.  
5. Binary tree is a tree wherein each node has at most two children.  
6. Any two nodes may have the same value associated with it.