SDE - Intern

Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.

OR

Push the first element to stack.
Pick rest of the elements one by one and follow the following steps in loop. 
Mark the current element as next.
If stack is not empty, compare top element of stack with next.
If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
Finally, push the next in the stack.
After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

A simple solution that comes to our mind is to sort all numbers in descending order, but simply sorting doesn’t work. For example, 548 is greater than 60, but in output 60 comes before 548. As a second example, 98 is greater than 9, but 9 comes before 98 in output.

So how do we go about it? The idea is to use any comparison based sorting algorithm. 
In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers.

For Python, the procedure is explained in largestNumber() function.

Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

Time Complexity: O(n logn) , sorting is considered to have a running time complexity of O(n logn), and the for loop runs in O(n) time.
Auxiliary Space: O(1)

The above problem represents a graph.
Variables in the equations are nodes and the value of equations is the weight of edges.
An edge from vertex x to vertex y has a weight equals to x / y.

Build the graph as mentioned above.
Each query is of the form of source and destination, we have to start from the source and reach the destination.
For every query, start from the source, if the source does not exists, return -1.
If the source has a direct edge to the required destination, return the value of the edge.
Else mark source as visited and recur for all the neighbors of source that are not visited yet, neighbor becomes the source and destination remains the same, if the answer of any of the neighbor is not -1, return edge weight from source to the neighbor plus answer of neighbor.

If we are allowed to buy and sell only once, then we can use the following algorithm. Maximum difference between two elements. Here we are allowed to buy and sell multiple times. 
Following is the algorithm for this problem. 

Find the local minima and store it as starting index. If not exists, return.
Find the local maxima. And store it as an ending index. If we reach the end, set the end as the ending index.
Update the solution (Increment count of buy-sell pairs)
Repeat the above steps if the end is not reached.

Time Complexity: The outer loop runs till I become n-1. The inner two loops increment the value of I in every iteration. So overall time complexity is O(n)