Q1. Devise an algorithm to find all four digit numbers which are perfect squares such that the first two digits are equal and the last two digits are equal. eg. 7799, 2233 etc. (No need to write the code, just the logic)
A: The question asks to find numbers which follow the pattern aabb and are perfect squares i.e sqrt(aabb) = an integer.
If we look at the number aabb, we can see:
Aabb = aa00 + bb
i.e aa*100 + bb = a*11*100 + b*11 = 11* (100a + b)
As 11 is not a perfect square, (100a+b) must have the factor 11 in them. So,
Sqrt(aabb) = 11*sqrt((100a+b)/11)
Because 11 is not a perfect square, then (100a + b) must have the factor 11 in them
11* (100a+b) = 11* 11 * ( 100a+b)/11
In order for aabb to be a perfect square, (100a+b)/11 must also be a perfect square i.e it must be an integer.
Therefore, (100a + b)/11 = 9*a + (a+b)/11 is an integer , then a+b must be divisible to 11
Putting it all together, let’s check out all cases:
a=1 b =10, eliminate
a=2 b=9, then 9*a +(a+b)/11 = 2*9 + 1 = 19, not a perfect square, eliminate. Call 9*a + (a+b)/11 a name f(a,b) for short.
a=3 b=8, f(a,b) = 3*9 +1 = 28, eliminate for the same reason above.
a=4,b=7, f(a,b) = 37
a=5,b=6, f(a,b) = 46
a=6, f(a,b) = 55
a=7, f(a,b) = 64, that’s it, 64 = 8^2, a perfect square.
a=8, f = 73
a=9, f= 82
Thus there is only one four digit number that matches the requirement i.e 7744.
Q2: How many times a day do a clock’s hands overlap?
A: The clock hands don’t overlap at 1:05, 2:10, 3:15 etc. Because, by the time the minutes hand reaches where the hours hand was, the hours hand has moved on, as it doesn’t remain fixed through the entire hour. The answer can be worked out in this way:
In every hour, as the hour hand moves across 5 minute spaces, the minute hand moves across 60. That means the minute hand gains 55 min space over hour hand in 60 min. Thus, between the nth and (n+1)st hr, to overlap the minute hand must gain the 5n min space that exists between them when the clock strikes n hrs. Apply unitary method and you get the time in which it does so i.e. 60n/11 min. So, the clock hands overlap at n hrs 60n/11 min. Obtain the values by putting m = 0 to 11, and you will find that from 00:00:00 to 23:59:59 (please note that 23:59:60 is equivalent to 24:00:00 or 00:00:00), the hands overlap 22 times.
Q3: A double-square number is an integer X which can be expressed as the sum of two perfect squares, e.g. 10 is a double square of 3 & 1, 10 = sq(3) + sq(1).
Your task is to ask user for 5 integers and calculate how many possible double squares exist for each number
eg 10 can be only be written as sq(3) + sq(1) (sq(1) + sq(3) is not considered different) and 25 can be written as sq(5) + sq(0) & sq(4) + sq(3). Note: sq = Square
A: The general way of solving this problem is to use brute force and check all the possible combinations that would exist for a number. But bellow is a smarter method of getting around this.
A point to note here is that the two numbers of a double square solution for any number would never be greater than the square root of the number itself. So instead of running the loop for “n” number of times (supposing n is the number), we can run the loop for floor(sqrt(n)) number of times.
Now, what we usually would do is run two for loops one inside other and check for every possible combination, if it is a double square or not. We can do the same with just one for loop.
Let the number be N.
- first take the square root of N (M = sqrt(N))
- run a for loop from 0 to M (let the incrementing variable be X)
- square X (X2), then subtract X2 from N (Y = N – X2)
- check if Y is a perfect square i.e sqrt(Y) = an integer
- if so, then X and sqrt(Y) is a double square solution of N.
Take 25, run a loop from 0 to 5.
First number would be 0, 02 = 0; subtract this from 25, i.e. 25-0 = 25. Sqrt(25) = 5 i.e. an integer.
So 0 + sqrt(25) i.e. 0 & 5 are one double square solution for 25.
When X=3, 32 = 9, Y = 25 – 9 = 16. Sqrt(16) = 4 i.e. an integer again (implying 16 is a perfect square). And do, 32 + 42 = 25, second double square solution for 25.
We can simply put one if condition to check if a combination has already been considered or not.
Concluding, this whole problem can be solved with just two loops (one for asking user the 5 values, and other to find the number of double square solutions for the numbers) instead of three.
Q4: There are 3 baskets. One of them has apples, one has oranges only and the other has a mixture of apples and oranges. The labels on their baskets always lie. (I.e. if the label says oranges, you are sure that it doesn’t have oranges only, it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets.
A: The answer is pretty simple. Take a fruit from the basket named mixture. As the labels lie, it is certain that it won’t have both. So in-case it has apples, the basket labeled apple is sure to not have apples and the one labeled oranges is again sure to not have oranges. As a consequence, the basket labeled apples must have oranges and the one labeled oranges must have the mixture.
Q5: You’re given an array containing both positive and negative integers and required to find the sub-array with the largest sum. Give an algorithm/logic for the above.
A: One can simply take out all positive numbers from the array and store them into a new array. The sum of all positive numbers will always be the largest sum. A special case might be one all the numbers in the array are negative. In that case, one can just check for the minimum number. That’d be the answer.
The two interview questions that were probably asked to everyone are “How many cars are there in India?” and “Why is a manhole cover round?”
First of all, they are Microsoft interview questions. First one was just to check if you are willing to answer and can apply logics to come up with something or not. The answer to the second is that, the diameter of a Round shape is same all over, unlike a square or a hexagon. And so, it will never fall into the hole. After all it’s not easy to pull a 50kg weight up a manhole!