spsneo
BAN USERApproach 2 (using malloc only once) (revised, ignore the previous one):
void *temp = (void *) malloc(r*sizeof(int *) + (r*c)*sizeof(int));
int **arr = (int **)temp;
arr[0] = (int *)(arr+r);
arr[1] = (int *) (arr+r+c);
arr[2] = (int *) (arr+r+2c);
.
.
arr[r-1] = (int *) (arr+r+(r-1)c);
Approach 2 (using malloc only once) (revised):
void *temp = (void *) malloc(r*sizeof(int *) + (r*c)*sizeof(int));
int **arr = (int **)temp;
arr[0] = (int *)(arr+r);
arr[1] = (int *) (arr+r+c);
arr[2] = (int *) (arr+r+2c);
.
.
arr[r-1] = (int *) (arr+r+(r-1)c);
Priority Inversion:
Its an issue with priority scheduler. Lets say there are three processes with high, medium and low priority - say H, M and L respectively. If H has to wait for L (for instance, for a lock held by L), and M is on the ready list, then H will never get the CPU because L (the low priority thread) will never get any CPU time. To solve this problem, H donates its priority to L, till L is holding the lock. And then L recall the donation once L releases (and thus H acquires) the lock.
#include <stdio.h>
#include <stdlib.h>
#define size 4
int arr[size] = {1,2,3,4};
int generate_powerset(int *temparr, int level, int start)
{
int i, j;
for(i=start; i<size; i++)
{
temparr[level] = arr[i];
printf("{ ");
for (j=0; j<=level; j++)
printf("%d ",temparr[j]);
printf("}\n");
if( i < size-1)
generate_powerset(temparr, level+1, i+1);
}
}
int main()
{
printf("{ }\n");
int temparr[size] = {0};
generate_powerset(temparr, 0, 0);
}
It can be done in O(n) time and O(1) space.
Assuming the array starts with 1 and its size is n.
low=1, mid=1, high=n
while (mid <= high)
{
if (arr[mid] < 5)
swap(arr[mid], arr[low])
mid++, low++
if (arr[mid] == 5)
mid++
if (arr[mid] > 5)
swap(arr[high], arr[mid])
high--
}
I will explain with an example.
Let n=5, k=4 and the array is: a[] = {2,3,2,1,4} (Let us consider array index starts from 1)
Now we can use the array elements as the pointer to the array itself. Like a[1] points to a[2], a[2] points to a[3] , a[3] points to a[2], a[4] points to a[1] and a[5] points to a[4]. Now consider this as a directed graph with a[1] to a[5] as nodes and the points to as directed edges. Start with a[5] and travel the directed graph. You are sure to find a loop. (Figure out why?)
So, its like tail and a cycle. Now the problem is to simply find the beginning node of cycle, which is a duplicate integer.
Pseudo code:
i = n;
j = n;
while (i != j)
{
i = a[i];
j = a[a[j]]; // This is like detecting loop in a linked list
}
j = n;
while (i != j)
{
i = a[i];
j = a[j];
} //This while loop finds the first node of the loop
return i;
Order of this algo O(n) and space requirement is O(1).
I will explain with an example.
Let n=5, k=4 and the array is: a[] = {2,3,2,1,4} (Let us consider array index starts from 1)
Now we can use the array elements as the pointer to the array itself. Like a[1] points to a[2], a[2] points to a[3] , a[3] points to a[2], a[4] points to a[1] and a[5] points to a[4]. Now consider this as a directed graph with a[1] to a[5] as nodes and the points to as directed edges. Start with a[5] and travel the directed graph. You are sure to find a loop. (Figure out why?)
So, its like tail and a cycle. Now the problem is to simply find the beginning node of cycle, which is a duplicate integer.
Pseudo code:
i = n;
j = n;
while (i != j)
{
i = a[i];
j = a[a[j]]; // This is like detecting loop in a linked list
}
j = n;
while (i != j)
{
i = a[i];
j = a[j];
} //This while loop finds the first node of the loop
return i;
This is a problem of Round Robin Tournament Scheduling Algorithm. Search for "Round Robin Tournament" in Wikipedia.
- spsneo March 02, 2010