Q1.
Given an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n.
Ans:
The number appearing two times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n). For floating numbers multiply it with 100 and proceed.
Q2.
How will you find the first k smallest elements in a given unsorted array in O(n) at the worst case?
Ans:
This can be solved in O(n) time. You can find out the position of kth element in an array using the "median of medians" algorithm.
Median of Medians Algorithm
Once we have the kth element, we can just iterate through the array and print elements that are smaller than the kth element to get the k smallest elements.
No comments:
Post a Comment