# Random Problem Set

1. Check if two rectangles overlap – instead of checking if they overlap we check if a rectangle lies outside. So we check if a rectangle lies on the right,left, top or bottom of the first rectangle. If it lies outside then don’t overlap. Else they overlap.  SO
2. Amazon: Count Negative Integers in Matrix – Numbers are sorted row and column wise. Youtube
two lines will intersect of there slope is not same. So check if two lines are same – if yes then will intersect. If two lines slope are different then will intersect somewhere. GeeksforGeeks
4. Given an integer n, write a function to compute the nth Fibonacci number.
GeeksforGeeks
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
5. Data Structure for Dictionary and Spell Checker?
6. https://github.com/mission-peace/interview/wiki/Randomization
7. https://github.com/mission-peace/interview/wiki/Misc
8. Shuffle an array or shuffle a deck of card.
This problem is based on Fisher–Yates shuffle algo. Wiki. Youtube. GeeksforGeeks. Code.
9. If you’re given a list of countries and its corresponding population, write a function that will return a random country but the higher the population of the country, the more likely it is to be picked at random.\$sumOfWeights = array_sum(\$array);\$result = [
‘india’ => 989892,
‘us’      => 98123,
‘uk’      => 3467,
‘mex’   => 9793,
‘chi’     => 8342
];\$random = rand(1, \$sumOfWeights);
foreach (\$array as \$name => \$weight) {
\$random -= \$weight;
if (\$random <= 0) {
return \$name;
}
}
This method will return the country with a high population with a higher probability.
10. Select element from array with probability proportional to its value. Same as above.
One of the solution is posted by yourself. Check that.
Implement the other suggested solution.
11. Write a function fib() that a takes an integer n, and returns the nth fibonacci number. Code .  GeeksForGeeks
12.  Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
13. Given two integers, write a function that swaps them without using any temporary variables. Youtube
x = x + y;
y = x – y;
x = x – y;x = x ^ y;
y = x ^ y;
x = x ^ y;
14. Given two integers, an hour and a minute, write a function to calculate the angle between the two hands on a clock representing that time.
The hour hand moves at the rate of 0.5 degrees per minute.(using simple unitary method. 12 hours 360 degree,  1/60 hour(=1 minute) = how many degree  )
The minute hand moves at the rate of of 6 degrees per minute
15. Given two numbers represented as strings, return multiplication of the numbers as a string.
16. Given a natural number n, print all distinct divisors of it. GFG.
1. A Naive Solution would be to iterate all the numbers from 1 to n, checking if that number divides n and printing it.  Time Complexity : O(n) Auxiliary Space : O(1)
2.If we look carefully, all the divisors are present in pairs.
For example if n = 100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10) . So we can loop only till sqrt(n) and print the other number of the pair.
Time Complexity : O(sqrt(n)) Auxiliary Space : O(1)
17. Given an array of stock prices, find the maximum profit that can be earned by doing a single transaction of buy and sell in the given period of time. video
This type of problem has 4 standard variation. This is quite simple.
18. ****** Stock Buy Sell to Maximize Profit – The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days. Here we are allowed to buy and sell multiple times. Code
Following is algorithm for this problem –
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
3. Update the solution (Increment count of buy sell pairs)
4. Repeat the above steps if end is not reached.
19. First of all, MD5 is broken – you can generate a collision, so MD5 should not be used for any security applications. SHA1 is not known to be broken and is believed to be secure. Other than that – yes, MD5 is faster but has 128-bit output, while SHA1 has 160-bit output. SO