SDE - Intern

You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .

Return true if the given string 'S' is balanced, else return false.

For example:

'S' = "{}()".

There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Given a list of cities numbered from 0 to N-1 and a matrix 'DISTANCE' consisting of 'N' rows and 'N' columns denoting the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city?

Design a search engine for global retail application, write a) a) Assumptions b) System considerations c)Design Components

Ninja requests a PS5 from Santa on Christmas. Santa decides to give Ninja a brand new PS5, but he locks it in a safe and gives Ninja a string SECRETCODE. The password to open the safe is the length of the longest palindromic subsequence present in SECRETCODE.

A palindromic subsequence is a subsequence (generated by deleting some character of a given string without changing its order) which is a palindrome. For example: ‘ABBA’ is the longest palindromic subsequence for ‘CACBDBA’.

As Ninja is busy sending Christmas presents to his friends, he asks you for help. Can you help Ninja open the safe and retrieve his PS5?

Note:

‘SECRETCODE’ consists of only English uppercases.

You have been given a root node of the binary search tree and a positive integer value. You need to perform an insertion operation i.e. inserting a new node with the given value in the given binary search tree such that the resultant tree is also a binary search tree.

If there can be more than one possible tree, then you can return any.

Note :

A binary search tree is a binary tree data structure, with the following properties :

    a. The left subtree of any node contains nodes with a value less than the node’s value.

    b. The right subtree of any node contains nodes with a value equal to or greater than the node’s value.

    c. Right, and left subtrees are also binary search trees.
It is guaranteed that,

    d. All nodes in the given tree are distinct positive integers.

    e. The given BST does not contain any node with a given integer value.

Example, below the tree, is a binary search tree.

Below the tree is not a BST as node ‘2’ is less than node ‘3’ but ‘2’ is the right child of ‘3’, and node ‘6’ is greater than node ‘5’ but it is in the left subtree of node ‘5’.

He asked me some questions based on Google maps, how it works and how it can be further optimized. He asked some questions about the scalability of websites and my opinions on the System design questions asked in the group fly round

You are given a stack ‘S’. Your task is to sort the sack recursively.

Note:

Looping through the stack is not allowed.
You need to return a stack that is sorted in descending order.

For example:

Given stack S = 1 3 2 
The output will be 3 2 1 since it is the sorted order.

Where do you see yourself in 5 years?

Why Microsoft?