confused_banda
BAN USERMy first question - are such questions asked to college freshers or even to experienced candidates with professional background?
I am not sure what do you mean by 'induction hypothesis' and how can you use induction.
How we detect loop is
Let's say that there're two pointers r (for rabbit) and t (for tortoise).
while(1)
{
r = r+2;
t = t+1
if( r == t )
loop found
}
In other words if rabbit and tortoise are running in a straight line, tortoise would never be able to catch rabbit before it reaches the end of race unless rabbit sleeps. But since rabbit ran and found that tortoise is at same point as himself, rabbit must have run in circle.
Now rabbit is always running in a step of 2, so its values will always be like
0 - 2 - 4 - 6 - 8.......
Tortoise is crawling with step of 1, so its value will always be like
0 - 1 - 2 - 3 - 4....
For rabbit to meet tortoise, rabbit should be one step behind tortoise (because when tortoise will crawl by one, rabbit will hop by two steps jumping over tortoise's previous position and meet it).
For that to happen tortoise should be at some position in cycle so that (tortoise's position + 1) and (rabbit's position + 2) meets at the same 'even position'.
x+1 = y+2
1. if both x and y are even then x+1 will be odd, and y+2 will be even, equality won't hold
2. if both x and y are odd then x+1 will be even and y+2 will be odd, equality wont hold
3. if x is even and y is odd then x+1 will odd and y + 2 will also be odd
4. if x is odd and y is even, then x+1 will be even and y+2 will also be even.
x can be both even and odd.
y can be even if loop is of even size (because it will just keep hopping on all nodes numbered divisible by 2 and x will take each odd position so condition 3 can be true for an odd number x but even y such that
x+1 = y+2
y can be take both even or odd for loop of odd size , since x will take value every odd node and y will take value every odd node as well, both will meet when x+1 = y+2
i wrote a program based on your idea but it doesn't work for median or surrounding elements.
#include<stdio.h>
void swap(int *x, int *y)
{
if( *x == *y )
return;
*x^=*y;
*y^=*x;
*x^=*y;
}
int findkth(int a[], int start, int end, int k)
{
int pivote = (start + end) >> 1;
int begin = start;
int smaller= start;
swap(&a[pivote], &a[end]);
while( begin < end )
{
if( a[begin] < a[end] )
{
swap(&a[smaller],&a[begin]);
smaller++;
}
begin++;
}
swap(&a[end], &a[smaller]);
if( smaller == k )
return a[smaller];
else
if( smaller < k )
start = smaller + 1;
else
end = smaller - 1;
return findkth(a, start, end, k);
}
int a[] = {9, 6, 3, 2, 7, 1, 8, 5,4};
#define ASIZE(A,x) (sizeof(A)/sizeof(int))
int main()
{
int median = findkth(a,0, ASIZE(a,int)-1, (0+ASIZE(a,int))>>1);
printf("\nMedian is %d\n", median);
int i=0,j;
int k = (0+ASIZE(a,int))>>1;
for(i=0;i<ASIZE(a,int); i++)
printf("%d ",a[i]);
printf("\n");
for( i = 1, j = ASIZE(a,int)-2; i < j ; i+=2, j-=2)
{
swap(&a[i],&a[j]);
}
for(i=0;i<ASIZE(a,int); i++)
printf("%d ",a[i]);
return 0;
}
is your hash function valid for Rabin-Karp algorithm?
By the way problem is different, you are given Alphabet A={a,b,c}, generate a sequence of strings in which characters a, b and c are not adjacent to each other
instead of 'max-heap', a 'max-treap' can be employed. key will be URL for tree operation (search), and key for heap operation (insert, update) will be access time
- confused_banda November 21, 2013priority queue, implemented as a 'max-heap' on access-time. most recently visited page will be available on the top of team (its time will be greater than all others).
if heap is full, replace the end element and move up the heap readjusting it.
excellent way, per word we'll however need uint64_t which should be fine i guess but what about point 2 of the question?
- confused_banda November 19, 2013Whats the logic?
- confused_banda November 19, 2013Can you clarify on second point? "2. the multiple of the two word's length is maximum. "
- confused_banda November 19, 2013Implement two-level of hashing, two hash functions
h1( typename ) returns a key k1 in table T1 which contains links to a separate table T2(one T2 per entry of T1)
h2(k1, object) returns a key k2 (links to entry within T2)
To hash h2( object.class, object ), first hash gives a key to location of object in an entire arrangement of two hash tables.
What do you mean who coded it? I coded it based on my understanding of mutex and cond variables
- confused_banda November 17, 2013Another piece of code that works with just one mutex and one condition variable, it works without needing sleep, basically broadcast instead of signal and checking for a 'turn' of a thread did the trick. it doesnt need sleep but since it prints too fast i have added it to catch up with its speed.
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
char l1[]={'a','b','c','d','e'};
char l2[]={'l','m','n','o','p'};
char l3[]={'u','v','w','x','y'};
#define NTHREADS 3
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
int turn = 0;
typedef struct{
int tid;
int printed;
int size;
char *buffer;
}thread_data;
void* thread(void *arg)
{
thread_data *data = (thread_data*)arg;
int tid = data->tid;
int printed = 0;
int size = data->size;
while(1)
{
pthread_mutex_lock(&m);
while(turn != tid )
pthread_cond_wait(&c,&m);
sleep(1);//sleep to print slowly, program works without sleep too!
fprintf(stderr,"thread: %d item: %c\n",tid,
data->buffer[printed%size]);
data->printed = printed++;
turn = (tid+1)%NTHREADS;
pthread_cond_broadcast(&c);
pthread_mutex_unlock(&m);
}
}
void init_thread_data(thread_data *data, int tid, int size, char *buffer)
{
data->tid = tid;
data->size = size;
data->buffer = buffer;
data->printed = 0;
}
int main(int argc, char *argv[])
{
thread_data data1, data2, data3;
init_thread_data(&data1, 0, sizeof(l1), l1);
init_thread_data(&data2, 1, sizeof(l2), l2);
init_thread_data(&data3, 2, sizeof(l3), l3);
pthread_t t1, t2, t3;
pthread_create(&t1, 0, thread, &data1);
pthread_create(&t2, 0, thread, &data2);
pthread_create(&t3, 0, thread, &data3);
sleep(2);
pthread_mutex_lock(&m);
turn=0;
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);
pthread_join(t1,0);
pthread_join(t2,0);
pthread_join(t3,0);
return 0;
}
Following program works but any idea why 'sleep' is really needed? I think program though prints expected output as it needs 'sleep', its not correct. Please help me understand why it doesnt work without sleep?
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
char l1[]={'a','b','c','d','e'};
char l2[]={'l','m','n','o','p'};
char l3[]={'u','v','w','x','y'};
int count1, count2, count3;
#define NTHREADS 3
pthread_mutex_t mutexes[NTHREADS] = {PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER,PTHREAD_MUTEX_INITIALIZER};
pthread_cond_t conditions[NTHREADS] = {PTHREAD_COND_INITIALIZER,PTHREAD_COND_INITIALIZER,PTHREAD_COND_INITIALIZER};
typedef struct{
int tid;
int printed;
int size;
char *buffer;
}thread_data;
void* thread(void *arg)
{
thread_data *data = (thread_data*)arg;
int tid = data->tid;
int printed = 0;
int size = data->size;
while(1)
{
pthread_mutex_lock(&mutexes[tid]);
pthread_cond_wait(&conditions[tid],&mutexes[tid]);
fprintf(stderr,"thread: %d item: %c\n",tid,
data->buffer[printed%size]);
printed++;
data->printed=printed;
pthread_mutex_unlock(&mutexes[tid]);
sleep(1); // why is it needed?
pthread_mutex_lock(&mutexes[(tid+1)%NTHREADS]);
pthread_cond_signal(&conditions[ (tid+1)%NTHREADS ]);
pthread_mutex_unlock(&mutexes[(tid+1)%NTHREADS]);
}
}
void init_thread_data(thread_data *data, int tid, int size, char *buffer)
{
data->tid = tid;
data->size = size;
data->buffer = buffer;
data->printed = 0;
}
int main(int argc, char *argv[])
{
thread_data data1, data2, data3;
init_thread_data(&data1, 0, sizeof(l1), l1);
init_thread_data(&data2, 1, sizeof(l2), l2);
init_thread_data(&data3, 2, sizeof(l3), l3);
pthread_t t1, t2, t3;
pthread_create(&t1, 0, thread, &data1);
pthread_create(&t2, 0, thread, &data2);
pthread_create(&t3, 0, thread, &data3);
sleep(2);
pthread_mutex_lock(&mutexes[0]);
pthread_cond_signal(&conditions[0]);
pthread_mutex_unlock(&mutexes[0]);
pthread_join(t1,0);
pthread_join(t2,0);
pthread_join(t3,0);
return 0;
}
I would do this way, though i feel this might not be correct. semaphores are used to signal conditions
class ClassThatNeedsFixing
{
Mutex m;
Semaphore s;
int count;
public:
ClassThatNeedsFixing(int count): m(), s(count), count(count)
{}
void AllowMany(void)
{
m.acquire();
s.acquire();
m.release();
// whatever you wanna do
s.release();
}
void AllowOne(void)
{
m.acquire();
int n = count;
while(n > 0 )
{
s.acquire();
n--;
}
// i am gonna block all
n = count;
while(n>0)
{
s.release();
n--;
}
m.release();
}
}
1. singleton class would need a createInstance method, a static method of a class
2. overloading new and delete operators
3. a method needed to operate on static members (member shared by all objects of a class)
Really is this Google's question? Its a job of caller to allocate sufficient memory before calling this function. Function silently truncates additional characters.
char* strncopy(char *dest, const char *src, int n)
{
int i = 0;
for(i = 0; i < n-1 && src[i]!='\0'; i++)
dest[i] = src[i];
dest[i] = '\0';
return dest;
}
char increment(char *number, int len)
{
int c = 1; /* possible carry return */
if( len <= 0 )
return '\0'; /* huh? */
while( c && len > 0 ) /* got something to add to a valid string */
{
sum = number[len-1] - '0' + c;
if( sum > 10 )
{
sum = sum%10;
c = sum/10;
}
else
{
c = 0;
}
number[len-1] = sum + '0';
len --;
}
return c + '0';
}
Write a program to open a socket and calls "accept", it terminates whenever a client connects to it..
- confused_banda November 16, 2013How will you represent 'this very very long integer'? is it going to be a bit string of size needed to represent a number?
32 bit represent a maximum of 10 digit number, so for a number of with 1 million digit what representation would be best?
One way could be to go for BCD representation, each byte representing a decimal from 0 - 9 or group of 4 bits representing a decimal from 0-9 (10,11,12,13,14,15 ignored).
In either case we need to know size of a byte stream representing a number. Now if we know number of bytes and way of representation we can compute size of a string needed beforehand. In first case, it will be same but for second it will be twice.
The way of conversion is now trivial. Just run through a byte array, interpreting entire byte or half-byte depending on a representation of long long type and then fill character array with it as usual ('0'+number)?
Perhaps a stupid answer - but I have used dictionary (English) and it also contains 'one letter word' representing a character in an alphabet.
while nread < nalphabets then
read word from dictionary
if word.length == 1 && word[1] is in alphabet then
answer[nread++] = word
fi
end while
Must be thread safe
- confused_banda September 11, 2013A recursive procedure is possible.
A leaf closest to a node is that leaf which is closest to its left child and closer than closest leaf of its right child; or is closest to its right child and closer than closest leaf of its left child.
Assume we have a procedure which returns closest child of a root
int find_closest_leaf(node *root, node **closest_leaf)
{
node **left_closest_leaf,**right_closest_leaf;
if( root == 0 )
{
closest_leaf = 0;
return 0;
}
int left = find_closest_leaf( root->left, left_closest_leaf)
int right = find_closest_right( root->right, right_closest_leaf)
if( left <= right )
closest_leaf = left_closest_leaf;
else
closest_leaf = right_closest_leaf;
}
More improvement is possible, however idea is to find leaf closest to left child, leaf closest to right child and chose one of the leaves which is closer;
- confused_banda September 09, 2013#include <stdio.h>
#define MSB(n) ( sizeof(unsigned int)*8 - __builtin_clz(n) - 1 )
int main(void) {
// your code goes here
unsigned int decimal = 8;
unsigned int mask = 1 << (MSB(decimal));
while(mask)
{
if(mask & decimal)
printf("1");
else
printf("0");
mask >>= 1;
}
return 0;
}
Which part of "not using inbuilt function or library" you did not understand?
- confused_banda September 05, 2013
Why not explain an algorithm rather than giving a program?
- confused_banda November 28, 2013