Well,I am trying hard to get an internship preferably from Microsoft and that too in US..
Now a days, i am trying to build an Impressive portfolio..But these end semester exams have really made my pace a little slow towards doing some creative things.
Anyways,I was reading up some Interview experiences of Interns at Microsoft..In that i got a question,:
Ques:
"Finding the kth smallest element in a given unsorted sequence of nos."?
The intern answered that we can sort and then find that kth no.
Well this might be right but has flaw, when all the nos in the array are not distinct.
But the Interviewer emphasized on doing
without sorting.
Well,I thought to give it a shot.This question was already asked by my prof of DAA (Data Analysis And Algo)in Internal viva to someone but he was expecting a conventional answer of some steps of Randomised sort etc.
No one knew the steps ,neither they tried to think for some method.
I thought to give this question a shot and within few minutes i invented a nice algo.
A nice algo becoz it works for every sequence,a recursive procedure and it was invented by me in few minutes.Maybe ,someone had already knew this but atleast i didn't knew anything before(my ignorance)..
Here is the code :
class KthSmallestElement
{
static int highest; //Maximum Element Among all the numbers in the sequence
static int smallest; //Smallest number among all the numbers in sequence
static int i = 1; //Index which stores the Last position in sorted array
/// <summary>
/// The algo is :
/// At each call to method,we find the smallest no which is not in the sorted array.
/// Since,The sorted array is initialized with smallest number in the sequence,
/// the method goes on finding next smaller numbers until the length of array reaches k.
/// Finally,we have a sorted array which contains all the elements of sequence sorted upto kth position.
/// but sorted array have all distinct numbers.
/// </summary>
/// <param name="sequence">unsorted "sequence" of numbers</param>
/// <param name="sortArray">A temporary array "sortarray"</param>
/// <param name="k">the kth position</param>
static void KthElement(int[] sequence, int[] sortArray, int k)
{
int minimum=highest ;
foreach (int number in sequence)
{
if (minimum > number && !sortArray.Contains(number))
{
minimum = number;
}
}
sortArray[i] = minimum;
i++;
if ((i) != k)
KthElement(sequence, sortArray, k); //Recursive call to find kth lement until sortarray contains k sorted elements
}
static void Main(string[] args)
{
int[] sequence = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,19,110 };
int[] sortArray=new int[sequence.Length];
highest = 110;
smallest = 1;
sortArray[0] = smallest;
KthSmallestElement.KthElement(sequence, sortArray, 20);
foreach(int no in sortArray)
Console.WriteLine(no);
Console.WriteLine("The 20th smallest No is : " + sortArray[i-1]);
}
}