Software Engineer

Ninja has to implement a new data structure, ‘PRE_SUF_SEARCH’. This data structure allows searching the word by prefix and suffix that is present in ‘PRE_SUF_SEARCH’.

Ninja has to implement two functions:

1) wordFilter(‘WORDS’): Add this ‘WORDS’ array/list into ‘PRE_SUF_SEARCH’.
2) find(‘PREFIX’, ‘SUFFIX’): Return the index of the word that is present in ‘PRE_SUF_SEARCH’ having prefix as ‘PREFIX’ and the suffix as ‘SUFFIX’.

Note:

1) If there is more than one valid index in ‘PRE_SUF_SEARCH’ for the word, then return the largest possible index.
2) If there is no such word present in the ‘PRE_SUF_SEARCH’, then return -1.
3) ‘WORDS’ array/list contains only lowercase English alphabets.

For example:

‘PRE_SUF_SEARCH’ = [“apple”, “mango”, “banana”].
Query_1: find(‘a’, ‘e’).

We have to find the index of the largest possible word that starts with ‘a’ and ends with ‘e’.

Here we have only one word ‘apple’ present in ‘PRE_SUF_SEARCH’ and satisfy this condition. So we return 0.

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.

Ninja has a binary tree. He wants to find the sum of multiplication of each node of the binary tree with its mirror node. Help Ninja to find the sum.

The mirror of a node is a node that is present at the mirror position in the opposite subtree at the root. The mirror of the root node is the node itself.

The answer can be very large, so print answer modulo 1000000007.

For Example :

In this example, The mirror of 2 will be 4, the mirror of 3 will be 9 and the mirror of 7 will be 6 so the final answer is (5 * 5) + (2 * 4) + (3 * 9) + (7 * 6) = 102. 

Note :

Every Node has a mirror node in the given tree.

You are given a binary search tree of integers with N nodes. You are also given references to two nodes 'P' and 'Q' from this BST.

Your task is to find the lowest common ancestor(LCA) of these two given nodes.

The lowest common ancestor for two nodes P and Q is defined as the lowest node that has both P and Q as descendants (where we allow a node to be a descendant of itself)

A binary search tree (BST) is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

For example:

'P' = 1, 'Q' = 3
tree = 2 1 4 -1 -1 3 -1 -1 -1,

The BST corresponding will be- 

Here, we can clearly see that LCA of node 1 and node 3 is 2.

What are ACID properties?

What is normalization?

What is 2NF, 3NF?

What are ER Diagrams?

Explain process and memory management?

What are paging and segmentation?

What is CPU scheduling?

Synchronization mechanisms such as semaphores (including types of semaphores).

You are given an array ‘arr’ consisting only of 0s , 1s, and 2s.

Sort the given array.

For Example:

For ‘arr’ = {1, 0, 0, 2, 1}.
‘Answer’ = {0, 0, 1, 1, 2}.
‘Answer’ should contain all 0s first, then all 1s and all 2s in the end.

You are given a Singly Linked List of integers and an integer array 'B' of size 'N'. Each element in the array 'B' represents a block size. Modify the linked list by reversing the nodes in each block whose sizes are given by the array 'B'.

Note:

1. If you encounter a situation when 'B[i]' is greater than the number of remaining nodes in the list, then simply reverse the remaining nodes as a block and ignore all the block sizes from 'B[i]'. 

2. All block sizes are contiguous i.e. suppose that block 'B[i]' ends at a node cur, then the block 'B[i+1]' starts from the node just after the node cur.

Example

Linked list: 1->2->3->4->5
Array B: 3 3 5

Output: 3->2->1->5->4

We reverse the first block of size 3 and then move to block 2. Now, since the number of nodes remaining in the list (2) is less than the block size (3), we reverse the remaining nodes (4 and 5) as a block and ignore all the block sizes that follow.