SDE - Intern

You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.

You have been given a circular path. There are N petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:
1)The amount of petrol that is available at this particular petrol pump.
2)The distance to reach the next petrol pump.
You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.
You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

Tip 1 : Read basics of system design
Tip 2 : Get your requirements before you dwell into designing
Tip 3 : Talk with the interviewer

Tip 1 : Keep calm and hear the question thoroughly
Tip 2 : Don't rush to answer, even if you get it in few seconds, take your time.

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.

Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure used to efficiently query and update prefix sums of an array. It is particularly useful when there is a need for frequent updates and prefix sum queries on a large array.

The Fenwick Tree works by maintaining a binary tree where each node represents the sum of a range of indices. The tree is constructed in such a way that each node's index is the sum of the indices of its child nodes. This property makes it possible to compute the prefix sum of an array element by following a path from the element's index to the root of the tree.

To update an element in the array, the tree is traversed from the node corresponding to the element's index to the root, and each node's value is incremented by the update amount. Similarly, to compute the prefix sum of a range of indices, the tree is traversed from the node corresponding to the starting index to the node corresponding to the ending index, and the sum of the values along the path is returned.