Re: [algogeeks] Amazom interview question
this is the general task scheduling problem apply greedy algorithms On Sat, Dec 4, 2010 at 10:13 AM, Prims topcode...@gmail.com wrote: You are given 'n' appointments. Each appointment contains startime and endtime. You have to retun all conflicting appointments efficiently starttime and endtime can range from a few min to few years. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
[algogeeks] Amazon Interview Question
find out all the elements in a sorted integer array whose value is equal to index of the array. O(logn) solution is expected. Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Amazom interview question
sort the jobs according to their starting time and check wheather a job starting time is less than its previous job ending time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Amazon Question
an array contain positive and negative element, find subarray whose sum =0; Regrads Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Microsoft interview question
Given the size of the input array,
construct array1 = {0, 1, 0, 1} till n elements
traverse through input array checking sum of 1's n 0's.
at the end if both sums are equal return array1 else return input array.
On Sat, Dec 4, 2010 at 12:06 AM, siva viknesh sivavikne...@gmail.comwrote:
Modified 2 color sort problem i.e. you are given an array of integers
containing only 0s and 1s.You have to place all the 0s in even
position and 1s in odd position. And if suppose, no. of 0s exceed no.
of 1s or vice versa then keep them untouched. Do that in ONE PASS and
without taking extra memory (modify the array in-place).
For Example :
Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
,1,1}
Write a solid secure code for it.
My solution:
.i thought of a solution ..but it takes 2 passes !!
in first pass count all no. of zeros nd ones
and in 2nd pass check whether no. of zeros no. of 1 s and vice
versa and accordingly assign values to the same input array
can anybody give the solution in single pass??
--
Regards,
$iva
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Microsoft interview question
My bad, did not see the in-place memory requirement
On Sat, Dec 4, 2010 at 8:49 PM, coolfrog$
dixit.coolfrog.div...@gmail.comwrote:
@shreyas VA
you are using O(n) extra space...
On Sat, Dec 4, 2010 at 8:46 PM, Shreyas VA v.a.shre...@gmail.com wrote:
Given the size of the input array,
construct array1 = {0, 1, 0, 1} till n elements
traverse through input array checking sum of 1's n 0's.
at the end if both sums are equal return array1 else return input array.
On Sat, Dec 4, 2010 at 12:06 AM, siva viknesh sivavikne...@gmail.comwrote:
Modified 2 color sort problem i.e. you are given an array of integers
containing only 0s and 1s.You have to place all the 0s in even
position and 1s in odd position. And if suppose, no. of 0s exceed no.
of 1s or vice versa then keep them untouched. Do that in ONE PASS and
without taking extra memory (modify the array in-place).
For Example :
Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
,1,1}
Write a solid secure code for it.
My solution:
.i thought of a solution ..but it takes 2 passes !!
in first pass count all no. of zeros nd ones
and in 2nd pass check whether no. of zeros no. of 1 s and vice
versa and accordingly assign values to the same input array
can anybody give the solution in single pass??
--
Regards,
$iva
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
[algogeeks] Longest interval with maximum sum
We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0... we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal... i.e. a[p]+a[p+1]+a[q]= b[p]+b[p+1]+b[[q]q -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Please check it out
#includestdio.h
void main()
{
int a[]={0,1,1,1,1,1,0,0,0,0,0,1},i=0;
static int o=0,e=0;//e for no. of 1's in array and o means no. of 0 in array
int l=sizeof(a)/4;
while(il)
{
if(a[i]==0)
{o++;i++;}
else
{e++,i++;}
}
if(eo) //if n0. of 1's greater than no. of 0's then e=o
e=o;
for(i=0;i(e*2);i++)
{
a[i]=i%2;
}
for(i=e*2;il;i++)
{
if(oe)
a[i]=0;
else if(eo)
a[i]=1;
}
for(i=0;il;i++)
{
printf(%d,a[i]);
}
}
i think that this code will work.if any problem in this code u can ask
freely on pathak@gmail.com.
--
~Pathak~
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Microsoft interview question
Hello,
2010/12/4 siva viknesh sivavikne...@gmail.com:
Modified 2 color sort problem i.e. you are given an array of integers
containing only 0s and 1s.You have to place all the 0s in even
position and 1s in odd position. And if suppose, no. of 0s exceed no.
of 1s or vice versa then keep them untouched. Do that in ONE PASS and
without taking extra memory (modify the array in-place).
For Example :
Input Array: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output Array: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1
,1,1}
the problem makes me to recall the quick-sort provided by Knuth in
Introduction to Algorithms, 2ed, here I use some skill like he shows.
eidx = 0 // even index
oidx = 1 // odd index
while (eidx len oidx len):
while (eidx len array[eidx] == 1) eidx += 2;
while (oidx len array[oidx] == 0) oidx += 2;
if (eidx len oidx len) swap(eidx, oidx);
}
if (eidx len)
{
p = eidx;
q = (len 1) 1;
while (p q)
{
while (p q array[p] == 1) p += 2;
while (p q array[q] == 0) q -= 2;
if (p q) swap(p, q);
}
}
else if (oidx len)
// similar to above
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] k nearest points
Given set of n points (Xi, Yi), write a function to find k nearest points from origin. -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon Interview Question
2010/12/5 juver++ avpostni...@gmail.com: Wrong. Counterexample: 1 2 2 2 2 6 suppose you mean 1 3 3 3 3 6? 1) divide-conquer 2) search binary, in each sub array [s, t], mid = (s+t)/2 if t array[mid]: // no need to check the part after mid, all will fail else if s array[mid]: // no need to check the part before mid, all will fail // if we have the elements unique if mid array[mid]: // no need to check the part after mid, all will fail else if mid array[mid]: // no need to check the part before mid, all will fail 3) when the elements are unique, in [s, t], if (array[s] = s array[t] = t) // all in [s, t] is ok but I think its complexity will be O(n) in the worse case if elements could be equal. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Amazom interview question
If you expect a lot of conflicting appointments:
Sort the appointments into ascending order by starttime.
Establish an empty min heap of {starttime,endtime} ordered by endtime.
Process the given appointments one by one:
While the heap is not empty and the endtime of the root does not
exceed the the starttime of the appointment
Delete the root of the heap.
If the heap is not empty, then
The given appointment conflicts with every appointment in the
heap.
Insert the given appointment into the heap.
Dave
On Dec 3, 10:43 pm, Prims topcode...@gmail.com wrote:
You are given 'n' appointments. Each appointment contains startime and
endtime. You have to retun all conflicting appointments efficiently
starttime and endtime can range from a few min to few years.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Amazom interview question
This is good. Another way is to build an interval tree and then query
it for every appointment's start time.
On Dec 4, 2:56 pm, Dave dave_and_da...@juno.com wrote:
If you expect a lot of conflicting appointments:
Sort the appointments into ascending order by starttime.
Establish an empty min heap of {starttime,endtime} ordered by endtime.
Process the given appointments one by one:
While the heap is not empty and the endtime of the root does not
exceed the the starttime of the appointment
Delete the root of the heap.
If the heap is not empty, then
The given appointment conflicts with every appointment in the
heap.
Insert the given appointment into the heap.
Dave
On Dec 3, 10:43 pm, Prims topcode...@gmail.com wrote:
You are given 'n' appointments. Each appointment contains startime and
endtime. You have to retun all conflicting appointments efficiently
starttime and endtime can range from a few min to few years.- Hide quoted
text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Amazom interview question
Use sweep line approach. Store start and finish points of the intervals and deal with is as events - starting point introduces new interval (place it into a set or an appropriate DS, call it active set), second point - removes previously inserted interval from the active set. Sort events in increasing order. When you reach starting point, all intervals from active set are conflicted with the current. On Dec 4, 7:43 am, Prims topcode...@gmail.com wrote: You are given 'n' appointments. Each appointment contains startime and endtime. You have to retun all conflicting appointments efficiently starttime and endtime can range from a few min to few years. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] convert binary matrix to zero matrix
How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps (a step is defined as toggling a whole row or whole column -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] k nearest points
will O(n) work or u wish something lesser dependent on k or log(n) ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
