SDE - 2

You are given a binary tree. Return the count of unival sub-trees in the given binary tree. In unival trees, all the nodes, below the root node, have the same value as the data of the root.

For example: for the binary tree, given in the following diagram, the number of unival trees is 5.

Ninja is learning a new but strange language known as Alien Language. Alien language possesses the same alphabets as of English language, but their order is different. The order of letters are given as ‘ORDER’ string. Ninja has ‘N’ words in the ‘WORDS’ array. Ninja’s task is to check whether the words of ‘WORDS’ are sorted lexicographically in this alien language or not.

Note: ‘ORDER’ consists of all 26 letters of English alphabet.

For Example

If ‘WORDS’ = ["word","world","row"], ‘ORDER’ = "worldabcefghijkmnpqstuvxyz",the answer will be ‘NO’ as first and second words are not lexicographically sorted as ‘l’ comes before ‘d’ in alien language.

You are given an array ‘A’ containing a permutation ‘N’ numbers (0 ≤ A[i] < N). You are also given another array ‘B’ containing a permutation ‘M’ numbers (0 ≤ B[j] < M) and it is also given that N ≤ M.

For each element in array ‘A’ you need to find the first greater element to the right of the element in array ‘B’ that has the same value as the current array A’s element. In other words, for each ‘i’ from 0 to N - 1 in array ‘A’, you need to find an index ‘j’ in array ‘B’ such that A[i] = B[j], now you need to print the element that lies on the right of the j’th index and is also greater than B[j]. Print -1 if there is no greater element.

Follow Up :

Can you solve it in O(N+M) time?

For Example :

If ‘N’ = 6, ‘A’ = {1, 2, 0, 3, 4, 5}, ‘M’ = 7 and ‘B’ = {3, 5, 0, 2, 1, 6, 4}.

Then, we will return {6, 6, 2, 5, -1, 6} because:
For i = 0, A[i] = 1 and the first element greater than 1 that lies to the right of it in array ‘B’ is 6.
For i = 1, A[i] = 2 and the first element greater than 2 that lies to the right of it in array ‘B’ is 6.
For i = 2, A[i] = 0 and the first element greater than 0 that lies to the right of it in array ‘B’ is 2.
For i = 3, A[i] = 3 and the first element greater than 3 that lies to the right of it in array ‘B’ is 5.
For i = 4, A[i] = 4 and there is no greater element to the right of 4 in array ‘B’.
For i = 5, A[i] = 5 and the first element greater than 5 that lies to the right of it in array ‘B’ is 6.

Ninjaland is a country in the shape of a 2-Dimensional grid 'GRID', with 'N' rows and 'M' columns. Each point in the grid has some cost associated with it.

Find a path from top left i.e. (0, 0) to the bottom right i.e. ('N' - 1, 'M' - 1) which minimizes the sum of the cost of all the numbers along the path. You need to tell the minimum sum of that path.

Note:

You can only move down or right at any point in time.

1) What do you mean by Virtual Memory?

2) Explain TLB Cache

1) TCP vs UDP difference
2) How to make UDP reliable?

Write a C++ code to solve a method called onReceivePacket which gets called whenever a UDP packet arrives from different multicast channels with all sending the same data

Given balance and N different weights of all same size except one. Find the odd one out in minimum number of checks. 

If 1.5 hens can lay 1.5 eggs in 1.5 days then how many eggs does 3 hens lay in 3 days.

How unordered_map works internally?

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.