[algogeeks] Google Telephonic interview
*You have given a structure which has two member, One which stores the
time and other stores the function pointer Your function has to call the *
*function stored in the fuction poitner after the time given in the
structure elapses.
Design that function? *
Approach: To design this function I would use a min Heap data structure.
Each node of a heap has
two parameters one is the running time and other one is the
function pointer.
// Initialise a function pointer
typedef void (*functionToBeCalled)(int arg1, int arg2);
// Timer structure
typedef struct timer
{
float runingTime; // in terms of seconds
functionToBeCalled funcToBeCall; // function pointer
}TIMER;
void initTimer()
{
Initialise few nodes with running time and its corresponding function
Initialise a MIN heap data structure
}
void addTimer(uint32 runingTime, functionToBeCalled func)
{
TIMER *temp;
temp = (TIMER *)malloc(sizeof(TIMER));
temp-runingTime = runningTime
temp-funcToBeCall = func;
HeapAdd(temp);
Heapify();
}
void scheduler()
{
uint32 currentTime = ObtainCurrentTime();
// Obtain the runing time of top most element of the min Heap
uint32 runingTime = PeakHeap();
// if the runningTime is equal to current time then extract the
top most
// element of the heap and execute the function associate with
it
// Heapify the MIN heap data structure
// Obtain the runing time of top most element of the min heap
// scheduler sleep for that much amount of time.
if(runingTime == currentTime)
{
TIMER * node = ExtractMinHeap();
CreateThread(node-func, Thread);
Heapify();
runingTime = PeakHeap();
sleep(runningTime);
}
else
{
// scheduler updates its sleep time
// if runing time is not equal to current time
sleep(runningTime);
}
}
Let me know your comments
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Telephonic interview
You mean to say linked to maintain all time task with its corresponding
running time and associate function. In that case how will find the task
which has the closed running time.
If you use min heap it would be easy to find the task that has closest
runing time in O(1) complexity.
On Thu, Aug 4, 2011 at 10:57 AM, mohit verma mohit89m...@gmail.com wrote:
why are u maintaining heap? can't we use link list here?
On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri
anand.shastr...@gmail.com wrote:
*You have given a structure which has two member, One which stores the
time and other stores the function pointer Your function has to call the
*
*function stored in the fuction poitner after the time given in the
structure elapses.
Design that function? *
Approach: To design this function I would use a min Heap data structure.
Each node of a heap has
two parameters one is the running time and other one is
the function pointer.
// Initialise a function pointer
typedef void (*functionToBeCalled)(int arg1, int arg2);
// Timer structure
typedef struct timer
{
float runingTime; // in terms of seconds
functionToBeCalled funcToBeCall; // function pointer
}TIMER;
void initTimer()
{
Initialise few nodes with running time and its corresponding function
Initialise a MIN heap data structure
}
void addTimer(uint32 runingTime, functionToBeCalled func)
{
TIMER *temp;
temp = (TIMER *)malloc(sizeof(TIMER));
temp-runingTime = runningTime
temp-funcToBeCall = func;
HeapAdd(temp);
Heapify();
}
void scheduler()
{
uint32 currentTime = ObtainCurrentTime();
// Obtain the runing time of top most element of the min Heap
uint32 runingTime = PeakHeap();
// if the runningTime is equal to current time then extract
the top most
// element of the heap and execute the function associate with
it
// Heapify the MIN heap data structure
// Obtain the runing time of top most element of the min heap
// scheduler sleep for that much amount of time.
if(runingTime == currentTime)
{
TIMER * node = ExtractMinHeap();
CreateThread(node-func, Thread);
Heapify();
runingTime = PeakHeap();
sleep(runningTime);
}
else
{
// scheduler updates its sleep time
// if runing time is not equal to current time
sleep(runningTime);
}
}
Let me know your comments
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*MOHIT VERMA*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Telephonic interview
Obviously you need to run the task that a closet running time.
For Example
Task 1 : running time = 2 secs
Task 2: running time = 4 secs
This means I want to run the task 1 after 2 secs and task 2 after 4 second.
How I hope the question is clear to you know
On Thu, Aug 4, 2011 at 11:37 AM, mohit verma mohit89m...@gmail.com wrote:
there is nothing like search min or max time and then call function given
. It can be the case: call the functions in order of nodes or times saved
in objects. M i wrong?
On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri
anand.shastr...@gmail.comwrote:
You mean to say linked to maintain all time task with its corresponding
running time and associate function. In that case how will find the task
which has the closed running time.
If you use min heap it would be easy to find the task that has closest
runing time in O(1) complexity.
On Thu, Aug 4, 2011 at 10:57 AM, mohit verma mohit89m...@gmail.comwrote:
why are u maintaining heap? can't we use link list here?
On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri
anand.shastr...@gmail.com wrote:
*You have given a structure which has two member, One which stores
the
time and other stores the function pointer Your function has to call the
*
*function stored in the fuction poitner after the time given in the
structure elapses.
Design that function? *
Approach: To design this function I would use a min Heap data structure.
Each node of a heap has
two parameters one is the running time and other one is
the function pointer.
// Initialise a function pointer
typedef void (*functionToBeCalled)(int arg1, int arg2);
// Timer structure
typedef struct timer
{
float runingTime; // in terms of seconds
functionToBeCalled funcToBeCall; // function pointer
}TIMER;
void initTimer()
{
Initialise few nodes with running time and its corresponding function
Initialise a MIN heap data structure
}
void addTimer(uint32 runingTime, functionToBeCalled func)
{
TIMER *temp;
temp = (TIMER *)malloc(sizeof(TIMER));
temp-runingTime = runningTime
temp-funcToBeCall = func;
HeapAdd(temp);
Heapify();
}
void scheduler()
{
uint32 currentTime = ObtainCurrentTime();
// Obtain the runing time of top most element of the min
Heap
uint32 runingTime = PeakHeap();
// if the runningTime is equal to current time then extract
the top most
// element of the heap and execute the function associate
with it
// Heapify the MIN heap data structure
// Obtain the runing time of top most element of the min
heap
// scheduler sleep for that much amount of time.
if(runingTime == currentTime)
{
TIMER * node = ExtractMinHeap();
CreateThread(node-func, Thread);
Heapify();
runingTime = PeakHeap();
sleep(runningTime);
}
else
{
// scheduler updates its sleep time
// if runing time is not equal to current time
sleep(runningTime);
}
}
Let me know your comments
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*MOHIT VERMA*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*MOHIT VERMA*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr
Re: [algogeeks] Google Telephonic interview
/* Create a Timer Task that takes in the running time and it's associated
function to be called after its running time is elapsed */
#include time.h
#define NUM 5
typedef void (*funcToBeCalled)(void);
typedef struct timer TIMER;
struct timer
{
int runningTime;
funcToBeCalled func;
};
static TIMER timerArray[NUM];
static time_t reference;
static int count;
int LEFT(int index)
{
if(index NUM)
return (index * 2 + 1);
}
int RIGHT(int index)
{
if(index NUM)
return (index * 2 + 2);
}
static void print(void)
{
printf(Timer task has been called\n);
}
// Initialise the timer data structure
void Init()
{
int index;
count = NUM;
// Note down the reference time
reference = time(0);
printf(reference : %ld\n, reference);
// Initialise the data structure such that associate function gets
// called after 3, 6, 9, 12, 15 seconds respectively.
for(index = 0; index count; index++)
{
timerArray[index].runningTime = (index + 1) * 3;
timerArray[index].func = print;
}
}
// This function check the min heap property and arrange
// the element such that at every node, root node should be
// less than its right and left child element.
Heapify(int index)
{
int left, right, minIndex;
TIMER temp;
left = LEFT(index);
right = RIGHT(index);
if(left (count)
(timerArray[left].runningTime timerArray[index].runningTime))
{
minIndex = left;
}
else
{
minIndex = index;
}
if(right (count)
(timerArray[right].runningTime timerArray[minIndex].runningTime))
{
minIndex = right;
}
if(minIndex != index)
{
temp.runningTime = timerArray[index].runningTime;
temp.func = timerArray[index].func;
timerArray[index].runningTime = timerArray[minIndex].runningTime;
timerArray[index].func = timerArray[minIndex].func;
timerArray[minIndex].runningTime = temp.runningTime;
timerArray[minIndex].func = temp.func;
Heapify(minIndex);
}
}
// This function builds the MIN heap data structure
void BuildHeap()
{
int len, i;
len = sizeof(timerArray)/sizeof(timerArray[0]);
i = (len - 1)/2;
while(i = 0)
{
Heapify(i);
i--;
}
Heapify(0);
}
// This function extract the top element of the heap
// Min heap has the min element at the top always.
int HeapExtract()
{
TIMER temp;
// Swap the 0 the element with last element of the array
temp.runningTime = timerArray[0].runningTime;
temp.func = timerArray[0].func;
timerArray[0].runningTime = timerArray[count-1].runningTime;
timerArray[0].func = timerArray[count-1].func;
timerArray[count-1].runningTime = temp.runningTime;
timerArray[count-1].func = temp.func;
count--;
// Check the heap property heapify if it got violated
Heapify(0);
// return the minimum element of the heap
return (count);
}
void scheduler()
{
time_t now;
int diff_time, minIndex;
while(count = 0)
{
now = time(0);
printf(Current Time: %ld\n, time(0));
diff_time = now- reference;
printf(diff_time : %ld\n, diff_time);
if(diff_time = timerArray[0].runningTime)
{
minIndex = HeapExtract();
timerArray[minIndex].func();
}
else
{
sleep(timerArray[0].runningTime - diff_time);
}
}
}
main()
{
int index, minIndex;
TIMER temp;
// Initialise the data structure
Init();
// Build MIn heap data structure
BuildHeap(timerArray);
// Run the scheduler
scheduler();
return;
}
The ouput of above code is
Timer Task is about to run
reference : 1312510772
Current Time: 1312510775
diff_time : 3
Timer task has been called
Current Time: 1312510778
diff_time : 6
Timer task has been called
Current Time: 1312510781
diff_time : 9
Timer task has been called
Current Time: 1312510784
diff_time : 12
Timer task has been called
Current Time: 1312510787
diff_time : 15
Timer task has been called
Please share your comments
On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri anand.shastr...@gmail.comwrote:
Obviously you need to run the task that a closet running time.
For Example
Task 1 : running time = 2 secs
Task 2: running time = 4 secs
This means I want to run the task 1 after 2 secs and task 2 after 4 second.
How I hope the question is clear to you know
On Thu, Aug 4, 2011 at 11:37 AM, mohit verma mohit89m...@gmail.comwrote:
there is nothing like search min or max time and then call function
given . It can be the case: call the functions in order of nodes or times
saved in objects. M i wrong?
On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri anand.shastr...@gmail.com
wrote:
You mean to say linked to maintain all time task with its corresponding
running time and associate function. In that case how will find the task
which has the closed running time.
If you use min heap it would be easy to find the task that has closest
runing time in O(1) complexity.
On Thu, Aug 4, 2011 at 10:57 AM, mohit verma mohit89m...@gmail.comwrote:
why are u maintaining heap
Re: [algogeeks] Google Telephonic interview
what if new task gets added every time.
On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
Instead of a heap, sort the array once. Pick the first element every
time, and remove it from the array, or just move the 'head pointer'
ahead.
On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri anand.shastr...@gmail.com
wrote:
/* Create a Timer Task that takes in the running time and it's associated
function to be called after its running time is elapsed */
#include time.h
#define NUM 5
typedef void (*funcToBeCalled)(void);
typedef struct timer TIMER;
struct timer
{
int runningTime;
funcToBeCalled func;
};
static TIMER timerArray[NUM];
static time_t reference;
static int count;
int LEFT(int index)
{
if(index NUM)
return (index * 2 + 1);
}
int RIGHT(int index)
{
if(index NUM)
return (index * 2 + 2);
}
static void print(void)
{
printf(Timer task has been called\n);
}
// Initialise the timer data structure
void Init()
{
int index;
count = NUM;
// Note down the reference time
reference = time(0);
printf(reference : %ld\n, reference);
// Initialise the data structure such that associate function gets
// called after 3, 6, 9, 12, 15 seconds respectively.
for(index = 0; index count; index++)
{
timerArray[index].runningTime = (index + 1) * 3;
timerArray[index].func = print;
}
}
// This function check the min heap property and arrange
// the element such that at every node, root node should be
// less than its right and left child element.
Heapify(int index)
{
int left, right, minIndex;
TIMER temp;
left = LEFT(index);
right = RIGHT(index);
if(left (count)
(timerArray[left].runningTime timerArray[index].runningTime))
{
minIndex = left;
}
else
{
minIndex = index;
}
if(right (count)
(timerArray[right].runningTime timerArray[minIndex].runningTime))
{
minIndex = right;
}
if(minIndex != index)
{
temp.runningTime = timerArray[index].runningTime;
temp.func = timerArray[index].func;
timerArray[index].runningTime = timerArray[minIndex].runningTime;
timerArray[index].func = timerArray[minIndex].func;
timerArray[minIndex].runningTime = temp.runningTime;
timerArray[minIndex].func = temp.func;
Heapify(minIndex);
}
}
// This function builds the MIN heap data structure
void BuildHeap()
{
int len, i;
len = sizeof(timerArray)/sizeof(timerArray[0]);
i = (len - 1)/2;
while(i = 0)
{
Heapify(i);
i--;
}
Heapify(0);
}
// This function extract the top element of the heap
// Min heap has the min element at the top always.
int HeapExtract()
{
TIMER temp;
// Swap the 0 the element with last element of the array
temp.runningTime = timerArray[0].runningTime;
temp.func = timerArray[0].func;
timerArray[0].runningTime = timerArray[count-1].runningTime;
timerArray[0].func = timerArray[count-1].func;
timerArray[count-1].runningTime = temp.runningTime;
timerArray[count-1].func = temp.func;
count--;
// Check the heap property heapify if it got violated
Heapify(0);
// return the minimum element of the heap
return (count);
}
void scheduler()
{
time_t now;
int diff_time, minIndex;
while(count = 0)
{
now = time(0);
printf(Current Time: %ld\n, time(0));
diff_time = now- reference;
printf(diff_time : %ld\n, diff_time);
if(diff_time = timerArray[0].runningTime)
{
minIndex = HeapExtract();
timerArray[minIndex].func();
}
else
{
sleep(timerArray[0].runningTime - diff_time);
}
}
}
main()
{
int index, minIndex;
TIMER temp;
// Initialise the data structure
Init();
// Build MIn heap data structure
BuildHeap(timerArray);
// Run the scheduler
scheduler();
return;
}
The ouput of above code is
Timer Task is about to run
reference : 1312510772
Current Time: 1312510775
diff_time : 3
Timer task has been called
Current Time: 1312510778
diff_time : 6
Timer task has been called
Current Time: 1312510781
diff_time : 9
Timer task has been called
Current Time: 1312510784
diff_time : 12
Timer task has been called
Current Time: 1312510787
diff_time : 15
Timer task has been called
Please share your comments
On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri
anand.shastr...@gmail.com
wrote:
Obviously you need to run the task that a closet running time.
For Example
Task 1 : running time = 2 secs
Task 2: running time = 4 secs
This means I want to run the task 1 after 2 secs and task 2 after 4
second.
How I hope the question is clear to you know
On Thu, Aug
[algogeeks] Google interview question
Given a file containing 4,300,000,000 integers, how can you *find **one* that *appears* at *least **twice* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google interview question
file any way contains integers why do we need hash those integers? why not use the same integers to index an array. On Fri, Jul 15, 2011 at 6:36 PM, radha krishnan radhakrishnance...@gmail.com wrote: just hash it On Fri, Jul 15, 2011 at 6:28 PM, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you find one that appears at least twice -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google interview question
File has 4,300,000,000 integers if you hash it will create a distinct hash for 4,300,000,000 integers. On Fri, Jul 15, 2011 at 7:09 PM, radha krishnan radhakrishnance...@gmail.com wrote: if number is (131) -1 u declare a 2GB array ? On Fri, Jul 15, 2011 at 6:59 PM, Anand Shastri anand.shastr...@gmail.com wrote: file any way contains integers why do we need hash those integers? why not use the same integers to index an array. On Fri, Jul 15, 2011 at 6:36 PM, radha krishnan radhakrishnance...@gmail.com wrote: just hash it On Fri, Jul 15, 2011 at 6:28 PM, Anand Shastri anand.shastr...@gmail.com wrote: Given a file containing 4,300,000,000 integers, how can you find one that appears at least twice -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
