SDE - Intern

You are given an arbitrary linked list consisting of 'N' nodes having integer values. You need to perform insertion sort on the linked list and print the final list in sorted order.
In other words, you are given a singly linked list, you need to perform insertion sort on it.

Let P(R) be the probability of picking a red marble.

P(R) = P(B1) * P(B1 | J1) + P(B2) * P(B2 | J2)

Here, P(B1) and P(B2) refers to selecting B1 and B2 and the probability of selecting each box is \frac{1}{2} J1 and J2 refers to number of total balls in B1 and B2 respectively.

P (R) = ((1 / 2) * (1 / 1)) + ((1 / 2) * (49 / 99)) = 0.747474

For a given array/list of integers of size N, print the Next Greater Element(NGE) for every element. The Next Greater Element for an element X is the first element on the right side of X in the array, which is greater than X. If no greater elements exist to the right of X, consider the next greater element as -1.

A door is toggled in an ith walk if i divide door number. For example, door number 45 is toggled in the 1st, 3rd, 5th, 9th,15th, and 45th walks.
The door is switched back to an initial stage for every pair of divisors. For example, 45 is toggled 6 times for 3 pairs (5, 9), (15, 3), and (1, 45). 

It looks like all doors would become closed at the end. But there are door numbers that would open, for example, in 16, the divisors are (1,2,4,8,16) and as the pair(4,4) contributes only one divisor making the number of divisors odd, it would become open at the end. Similarly, all other perfect squares like 4, 9,…, and 100 would become open. Now, for prime numbers like 2,3,5,7… the divisors are (1, that number) and it is a pair, so they will remain closed at the end. And for all other numbers divisors are always in pairs, e.g. 15 = (1,15),(3,5), they will also remain closed.

So the answer is 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.