Software Analyst

You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

For example:

If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.

Note:

The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

You are given an array/list 'ARR' of ‘N’ integers, and ‘Q’ queries. Each query can be of two types:

Given 2 integers ‘L’,’R’ ( L>=0 and R<N ) find the sum of all the elements of the array with the index in the range 'L' and 'R' (inclusive). This is a query of type range sum.

Given an index ‘i’ update the value of ARR[i] to a given integer ‘X’. This is a query of type point update.

Your task is to perform the queries on the given array and return the desired output for each query.

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along the edge of the triangle. What is the probability that any two ants collide?

Given a binary search tree and an integer ‘K’. Your task is to find the ‘K-th’ smallest element in the given BST( binary search tree).

BST ( binary search tree) -

If all the smallest nodes on the left side and all the greater nodes on the right side of the node current node.

Example -

Order of elements in increasing order in the given BST is - { 2, 3, 4, 5, 6, 7, 8, 10 }

Suppose given ‘K = 3’ then 3rd smallest element is ‘4’.

Suppose given ‘K = 8’ then 8th smallest element is ‘10’.

Note:

1. You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the ‘K-th’ smallest element of BST.
2. You don’t need to return ‘K-th’ smallest node, return just value of that node. 
3. If ‘K-th’ smallest element is not present in BST then return -1.

He asked me to do a system design for a website like Instagram which can be used by travellers.

What are Semaphores? Explain in detail

Implementing the LRU Cache and its uses

a person has 3000 bananas and a camel. He wants to transport the maximum number of bananas to a destination which is 1000 KMs away Camel eats 1 banana for every km. What is the maximum number of bananas that can be transferred to the destination using the only camel?