SDE - 1

In Ninja land, there are N cities that are connected to each other by undirected roads. The cities along with all the roads form a tree-like structure. Each city has an initial height associated with it. The heights of the cities can change also. Now Ninja got bored at home and decided to visit different cities. But Ninja only wants to visit two cities if the path between them forms an alternate series of ups and downs. Since Ninja doesn’t know whether the path between the two cities is alternating or not, he asked you to help him.

For Example:

Suppose Ninja is currently standing at X city and want to visit Y city. Let the heights of all the cities in the path from X to Y(including X and Y) are 10 20 5 30. Now these series of heights forms and alternate series. So Ninja will visit the city Y.

Some examples of alternate series are 15 4 11 8 25, 100 120 50 70 60 but the series like 3 5 4 1, 6 3 10 12 are not alternating.

Now you will be asked q queries, and there are two types of queries:

1 X Y: change the height of city X to Y.

2 X Y: Check whether the path between city X to Y is alternating or not.

You are given two strings ‘A’ and ‘B’. Your task is to return a substring ‘S’ of ‘A’ such that the following conditions hold true :

• You can make ‘B’ from ‘S’ by removing some characters and rearranging some characters zero or more times.

• Length of ‘S’ must be as minimum as possible.

Note :

Testcases are generated such that a substring always exists and is unique.

Example :

A = ninjas, B = sin

All possible substrings with which 'B' can be created are
"ninjas", "injas".

Hence the substring with minimum length is "injas".

Given two sorted arrays 'a' and 'b' of size 'n' and 'm' respectively.

Find the median of the two sorted arrays.

Median is defined as the middle value of a sorted list of numbers. In case the length of list is even, median is the average of the two middle elements.

The expected time complexity is O(min(logn, logm)), where 'n' and 'm' are the sizes of arrays 'a' and 'b', respectively, and the expected space complexity is O(1).

Example:

Input: 'a' = [2, 4, 6] and 'b' = [1, 3, 5]

Output: 3.5

Explanation: The array after merging 'a' and 'b' will be { 1, 2, 3, 4, 5, 6 }. Here two medians are 3 and 4. So the median will be the average of 3 and 4, which is 3.5.

Ninja has been given a number that is represented in the form of a linked list such that each digit corresponds to a node. He has been asked to add 1 to it and return the updated list.

For Example:

1234 is represented as (1 -> 2 -> 3 -> 4) and adding 1 to it should change it to (1 -> 2 -> 3 -> 5).

Note:

The input Linked list does not have any trailing zeros.

Some players are put inside an ‘N’ x ‘M’ matrix ‘GRID’ one by one where:

• ‘.’ represents an empty cell.
• ‘#’ represents a wall.
• ‘@’ represents the starting point.
• Lowercase letters represent keys.
• Uppercase letters represent locks.

The player to collect all the keys in minimum moves will win the game. The ninja is one of the players and needs your help to win the game. He wants you to find the minimum number of moves to get all the keys. The rules of the game are:

• You have to start from the starting point and move in one of the four cardinal directions.
• You cannot walk outside the grid or walk into a wall. You can pick a key whenever you walk over it.
• You cannot walk over a lock unless you have the corresponding key. For example, the key for the lock ‘A’ is ‘a’.
• There is exactly one key for each lock.

For Example:

You are given ‘GRID’= [[“@.aA”],[“.B#.”],[“...b”]]. Then the answer will be 5.

Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.

Distance between two nodes is defined as the minimum number of edges in the path from one node to another.

Detailed discussion on the project on which i was working on my previous organisation
Some questions on DBMS like sql or no sql difference, use of indexing.