Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public class KRankService
{
public static void kRank(int[] arr, int k)throws NullPointerException, IllegalArgumentException
{
if(arr==null)
{
throw new NullPointerException(“input array cannot be null”);
}
if(k<0||k>arr.length)
{
throw new IllegalArgumentException(“k cannot be less than zero or greater than array length”);
}
MinHeap mh=new MinHeap(k);
HashMap<Integer,Boolean> inHeap=new HashMap<Integer,Boolean>(k);
for(int i=0; i< arr.length;i++)
{
if(!inHeap.contains(arr[i]))
{
if(mh.isFull())
{
if(arr[i]>mh.getMin())
{
mh.extractMin();
}
}
mh.insert(arr[i]);
inHeap.put(arr[i],true);
}
}
System.out.println(“kth rank: “ + mh.getMin());
System.out.println(“k highest values: “ );
while(!mh.isEmpty())
{
System.out.print(mh.extractMin() + “ “);
}
}
private static int[] getInputArray(int n)
{
if(n==0)
{
return null;
}
int[] arr=new int[n];
Random rnd=new Random();
for(int i=0; i<arr.length;i++)
{
arr[i]=rnd.nextInt(n);
}
return arr;
}
public static void main(String[] args)
{
Random rnd=new Random();
int n=rnd.nextInt(1001);
int k=rnd.nextInt(51);
int[] input=KRankService.getInputArray(n);
KRankService.kRank(input,k);
}
}
#include <iostream>
#include <map>
using namespace std;
void arr_rank(int a[], int n)
{
map <int, int> count;
map <int, int> rank;
int rankCount = 1;
// construct map
for(int i=0;i<10;i++)
{
count[i] = 0;
rank[i] = 0;
}
for(int i=0;i<n;i++)
{
count[a[i]] += 1;
}
for (int i=0;i<10;i++)
{
if (count[i] > 0)
{
rank[i] = rankCount;
rankCount++;
}
}
for (int i=0;i<n;i++)
cout << rank[a[i]] << endl;
}
int main(void)
{
int a[] = {3, 1, 3, 4, 9, 8, 5};
arr_rank(a, 7);
}
what is rank k number of an array...
- Anonymous July 16, 2015