kr.neerav
BAN USERI will explain xlshi's solution.
Let the arrays be M and H for mice and hole respectively. Sort the arrays in ascending order
M : -4 2 4
H : 0 4 5
For any mice at position i all holes with position <i (in the array) will be further away when compared to hole at i (because the array is sorted in ascending order). Thus applying this logic recursively from the bottom of the array you will be able to get the final hole for each mouse and max time taken.
Was to partition data in threads/pipelines
1) Round robin (fastest and uniformly distributed)
2) Randomly assign to each thread (uniformly distributed but relatively slow as we have to generate random numbers)
3) Hashing (good to group duplicates together but slow because of hashing)
I guess the question is to output a matrix where both rows and column are sorted. To do that
1) Sort the n^2 elements O(n^2 logn)
2) Make the first n elements as first row, next n elements as 2nd row.....
Other matrix combinations can be formed by using the below logic
1) Choose a value of increment d <n
2) Pick up the elements of a row in increments of d e.g.
row 1: 1, 1+d, 1+2d....
row 2: 2, 2+d, 2+2d....
for(i=1;i<=n;i++)
{ for(j=i;j<=n^2;j+=d)
print A[j]
print "\n"
}
If the array is very large (e.g. stream) then binary search is not efficient. Use the following:
1) Check the value at the following points 1,2,4,8,16,32,64..... till you encounter 1
2) Now the first 1 would be in the last block e.g if A[64] is 1 then the first 1 will lie between 32 and 64
3) Perform binary search in the block (or repeat the same procedure till block size is 1)
Here is an implementation. I am using static arrays but this can easily be changed to use dynamic arrays. Have used both insertion sort and heap sort to verify if the implementation of heap is correct.
#include<stdio.h>
#include<stdlib.h>
typedef struct heap_t
{
int arr[1000];
int count;
} heap;
float insertion(heap*ins_obj, int val);
int htop(heap*hp);
void heap_ins(heap*heap_obj, int val, int minmax);
int heap_del(heap*heap_obj, int minmax);
float minmaxheap(heap*hmax, heap*hmin, int val);
void printarr(int arr[], int l);
main()
{
heap hmax, hmin, ins;
int val, i;
float base, hp;
hmax.count = 1;
hmin.count = 1;
ins.count = 1;
for(i=0;i<50;i++)
{
val = rand()%1000;
base = insertion(&ins, val);
hp = minmaxheap(&hmax, &hmin, val);
printf("Insertion Sort: %.1f \t Heap: %.1f\n", base, hp);
}
return 0;
}
float insertion(heap*ins_obj, int val)
{
int i, j;
for(i=1;i<(*ins_obj).count;i++)
if(val>=(*ins_obj).arr[i])
break;
for(j=(*ins_obj).count;j>=i;j--)
(*ins_obj).arr[j+1] = (*ins_obj).arr[j];
(*ins_obj).arr[i] = val;
(*ins_obj).count++;
if((*ins_obj).count%2==0)
return (*ins_obj).arr[(*ins_obj).count/2];
else
return ((*ins_obj).arr[(*ins_obj).count/2]+(*ins_obj).arr[(*ins_obj).count/2+1])/2.0;
}
void heap_ins(heap*heap_obj, int val, int minmax)
{
int parent, child, temp;
(*heap_obj).arr[(*heap_obj).count]= val;
child = (*heap_obj).count++;
parent = child/2;
while((((*heap_obj).arr[parent]>(*heap_obj).arr[child])&&!minmax)||(((*heap_obj).arr[parent]<(*heap_obj).arr[child])&&minmax)&&(child!=1))
{
//swap parent and child
temp = (*heap_obj).arr[parent];
(*heap_obj).arr[parent] = (*heap_obj).arr[child];
(*heap_obj).arr[child] = temp;
child = parent;
parent = child/2;
}
}
int heap_del(heap*heap_obj, int minmax)
{
int temp, temp1, parent, child, child1;
temp = (*heap_obj).arr[1];
(*heap_obj).arr[1] = (*heap_obj).arr[--(*heap_obj).count];
parent = 1;
child = 2;
child1 = 3;
while((child<=(*heap_obj).count)&&(child1<=(*heap_obj).count))
{
if((((*heap_obj).arr[child]<(*heap_obj).arr[child1])&&!minmax)||(((*heap_obj).arr[child]>(*heap_obj).arr[child1])&&minmax))
{
temp1 = (*heap_obj).arr[parent];
(*heap_obj).arr[parent] = (*heap_obj).arr[child];
(*heap_obj).arr[child] = temp1;
parent = child;
}
else //if(((*heap_obj).min[child1]<(*heap_obj).min[child])&&!minmax)
{
temp1 = (*heap_obj).arr[parent];
(*heap_obj).arr[parent] = (*heap_obj).arr[child1];
(*heap_obj).arr[child1] = temp1;
parent = child1;
}
child = 2*parent;
child1 = 2*parent + 1;
}
if(child <=(*heap_obj).count)
(*heap_obj).arr[parent] = (*heap_obj).arr[child];
return temp;
}
float minmaxheap(heap*hmax, heap*hmin, int val)
{
int hmaxtop, hmintop, temp;
hmaxtop = htop(hmax);
hmintop = htop(hmin);
if(val<hmaxtop)
heap_ins(hmax, val,1);
else
heap_ins(hmin, val,0);
if(abs((*hmax).count - (*hmin).count)==2)
{
if((*hmax).count>(*hmin).count)
{
temp = heap_del(hmax, 1);
heap_ins(hmin, temp, 0);
}
else
{
temp = heap_del(hmin, 0);
heap_ins(hmax, temp, 1);
}
}
int total;
total = (*hmax).count + (*hmin).count;
if(total%2!=0)
{
if((*hmax).count>(*hmin).count)
return htop(hmax);
else
return htop(hmin);
}
else
return (htop(hmax)+htop(hmin))/2.0;
}
int htop(heap*hp)
{
return (*hp).arr[1];
}
void printarr(int arr[], int l)
{
int i;
for(i=1;i<l;i++)
printf("%d ",arr[i]);
printf("\n");
}
Here is an implementation which uses only one recursion parameter. Also this does not include checking for duplicates before printing. That needs to be accounted for.
#include<stdio.h>
#include<string.h>
char in[100], s[100];
int N;
void combRec(int i);
void remSpacePrint();
void main()
{
scanf("%s",in);
N=strlen(in);
char s[100]={'\0'};
combRec(0);
}
void combRec(int i)
{
if(i==N)
{
remSpacePrint();
return;
}
s[i] = ' ';
s[i+1] = '\0';
combRec(i+1);
s[i]=in[i];
combRec(i+1);
}
void remSpacePrint()
{
char new[100];
int i=0,j=0;
while(i<=N)
{
if(s[i]==' ')
{
i++;
continue;
}
new[j++]=s[i++];
}
printf("%s\n", new);
}
Sure ryaan
The brute force solution O(n^2) does not structure the data in any way. So to optimize it lets try to bring a structure in the data. The operation to optimize is the linear search of the next greater element to the right, currently O(n). If all the elements on the right were in the form of a BST the search would take O(logn) time (if the BST was threaded. please lookup on internet for more information about binary threaded tree). So we start by building the tree from the right of the array (step 1) Each time we insert a new element in the BST we find out its successor which is the output we desire.
I have mentioned it as amortized performance as its not a balanced BST that we are using. Am not sure if we can build a balanced threaded BST.
Hope it helps
Here is an O(nlogn) [amortized] approach using a threaded BST where each node points to the next in order successor.
1) read the array from right to left
2) Insert each element into a threaded BST.
3) Output the inorder successor after each insertion.
Perhaps we could reshape the threaded tree in between to make it balanced and increase performance but am not sure if we can modify a threaded tree.
I guess the O(n^2) constraint is on reading the binary tree i.e. don't read it n times. For filling up the array we do need O(n^2) time. Here is one approach
The predecessors of a node are the predecessors of its parent + its parent.
Using this logic we need to read the binary tree only once.
Tree traversal will be done as preorder.
It looks similar to a database scenario where we store the data in a table and build indexes to optimize search.
Lets store the data in the form of an array of objects sorted by phone numbers. So to search via a phone number it takes O(logN), for binary search.
For efficient search via names we can create a balanced BST with names as key and a list of Ids, of the array containing phone number and name, as nodes. Better use a trei for efficient storage. This takes care of efficient searching from names. O(logN) in case of balanced BST and O(L) in case of trie where L is the length of the name.
The strategy for spending minimum money is to arrange the students in such a way that if the immediate neighbor has more score then he gets 2 laddu else he gets 1. So the students should be arranged in such a way that each student with a high score is followed by a student with a score <= to him. This arrangement can be made by sorting the students by score and then swapping the adjacent element e.g. if the scores are 1,6,3,5,4,2 then the arrangement will be 2,1,4,3,6,5.
Once the arrangement is finalized use the following to calculate the number of laddus
if(score[prev]>=score[curr]
laddus[curr]=1
else
laddus[curr]=2
Now just sum the elements of laddus array.
- kr.neerav June 15, 2014* -- * -- *
| | |
B--C -- *
| | |
A-- D-- *
Lets take an example. In the grid shown above
min no of steps to reach C = MIN OF {min no of steps to reach B + 1,
min no of steps to reach D + 1,
if A is a special point then min no of steps to reach A + 1
}
Use this formula and start calculating min no of steps to reach each point on the right and top of the source point, skipping those points whose X and Y coordinate exceed the X and Y coordinate of destination.
RepProcess Technicians are responsible for monitoring and improving manufacturing and engineering processes. They are employed by a wide variety of ...
Repchristinetcollazoc, Software Analyst
I am a pediatric nurse.I administer directly procedures and medicines to children according to prescribed I also continually assess ...
If there are unlimited magic potions then the complexity will be of Dijkstra’s algorithm. In case the number is fixed then it will need to be analyzed.
- kr.neerav September 18, 2014