Friday, June 17, 2016

#coding exercise
Given array of N integers ranging from 0 to N-1. Output maximum repeating integer. Use only O(1) memory
int maxRepeating(List<int> arr, int n, int k)
{
for (int i =0; i < n; i++)
{
arr[arr[i]%k] += k;
}
int max = arr[0];
int result = 0;
for (int i =1; i < n; i++)
{
   if (arr[i] > max)
   {
     max = arr[i];
     result = i;
   }
}
for (int i =0; i <n; i++)
      arr[i] = arr[i] %k;
return result;
}

find maximum element in an array which is first increasing and then decreasing:
int getMax(List<int> arr, int start, int end)
{
if (start == end)
   return arr[start];
if ((end == start + 1) && arr[start] >= arr[end])
   return arr[start];
if ((end == start + 1) && arr[start]  < arr [end])
   return arr[end];
int mid = (start+end)/2;
if (arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1])
   return arr[mid];
if (arr[mid] > arr[mid+1] && arr[mid] < arr[mid-1])
   return getMax(arr, start, mid-1);
else
   return getMax(arr, mid+1, end);
}

Another tree question
void printLeftView(node root, int level, ref int maxlevel)
{
if (root == null) return;
if (maxlevel < level){
   console.write(root.data);
   return level;
}
printLeftView(root.left, level+1, ref maxlevel);
printLeftView(root.right, level+1, ref maxlevel);
}

No comments:

Post a Comment