Re: [algogeeks] Microsoft Interview Question
@rahul: I got my fault. I didn't thought about that test case. I am thinking about applying DFS traversal algorithm for graph here. It may work here. On Wed, Oct 17, 2012 at 9:01 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: still i am not getting your solution.. can you make more clear it pls.. here is my doubt.. take input matrix and one temp visited matrix which stores the visited path. eg: 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 Suppose i want to find the number of paths between M[4][2] - M[0][0] First i explore path M[4][2]-M[4][3]-M[3][3] and so on... your program set 1 on visited matrix... on corresponding V[i][j] entries next time i explore the path M[4][2]-M[3][2]-M[3][3]... but here we found that V[3][3]=1 so we can't take this in put path... but actually both are different paths.. how you will ensure this. because we are maintaining only one visited matrix. On Wed, Oct 17, 2012 at 7:54 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Rahul: Loop won't occur because when you are visiting any matrix element then you are marking 1 in visited matrix. So second time it will be seen as a already visited element and it will choose another element (or path if exist) or will blocked. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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
Re: [algogeeks] Microsoft Interview Question
@atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are ch ances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.com wrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
@Rahul: Loop won't occur because when you are visiting any matrix element then you are marking 1 in visited matrix. So second time it will be seen as a already visited element and it will choose another element (or path if exist) or will blocked. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex:1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
@Rahul : yes i know and actually i posted this query on geeksforgeeks. you can find my solution in comments , search for atul007 in the provided link.It will work for all cases. now to find all path you need to do small modification on the same code. On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in your solution object only can move down or right direction. but in my problem object is free to move in any direction and hence there are chances of cycle.. how to memoize cycle. if there is cycle then your approach will give infinite solution. consider this maze 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 you can see that object can take path M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][] OR M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][] But simple approach will also take path M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1] -- CYCLE how you will avoid these cycles... On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex:1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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.
[algogeeks] Microsoft Interview Question
Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
http://www.geeksforgeeks.org/archives/13376 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.com wrote: can be done simply by backtracking . On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: Pls help to solve this que.. does any one have DP solution for following que. http://www.geeksforgeeks.org/archives/24488 section 5/question 2 Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array). ex: 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 If there is a block it’s represented by 0. If there is a path it’s represented by 1. -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com [image: Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro [image: Twitter] https://twitter.com/rahulkumarpatle https://www.facebook.com/rkpatle -- 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] Microsoft Interview Question
find the element nearest to zero.make it pivot element.then apply one pass
of quicksort over the array.this is O(n)
On Thu, Jun 21, 2012 at 12:27 AM, Akshat Sapra sapraaks...@gmail.comwrote:
void make_group( int a[], int size) {
int j = 0;
for ( int i = 0; i size; i++ ) {
if ( a[i] 0 ) {
swap(a[i],a[j]);
j++;
}
}
}
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
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.
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
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] Microsoft Interview Question
@Abhi: if you apply quick sort then again the order will will not be intact -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ic2CXJXSGuoJ. 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] Microsoft Interview Question
void make_group( int a[], int size) {
int j = 0;
for ( int i = 0; i size; i++ ) {
if ( a[i] 0 ) {
swap(a[i],a[j]);
j++;
}
}
}
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
*--*
sapraaks...@gmail.com
akshatsapr...@gmail.com
rit20009008@ rit20009...@gmail.comiiita.ac.in
--
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] Microsoft Interview Question
void change(int a[],int n)
{
int i,j;
i=0;
j=1;
while(injn)
{
if(ji)
j=i+1;
else if(a[j]0a[i]0)
{
swap(a,j,i);
}
else
{
if(a[j]0)
j++;
else
i++;
}
}
}
--
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] Microsoft Interview Question
@guneesh your code fails to keep order b/w 3 and 4 in the above example
On Fri, Jun 15, 2012 at 2:40 PM, Guneesh Paul Singh gunees...@gmail.comwrote:
void change(int a[],int n)
{
int i,j;
i=0;
j=1;
while(injn)
{
if(ji)
j=i+1;
else if(a[j]0a[i]0)
{
swap(a,j,i);
}
else
{
if(a[j]0)
j++;
else
i++;
}
}
}
--
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] Microsoft Interview Question
As nothing is written about space complexity, I am assuming that we can take extra space. Take a temporary array of length n. 1. Maintain a counter for the length of temporary array filled till now. 2. Traverse the given array. If value contained is negative insert it in new array and update counter. After complete traversal all negative values will be in the temporary array. 3. Traverse again the given array. Repeat step 2 but this time for positive numbers. Finally temporary array contains the required answer. If required copy it into original array. As this approach takes max. 3 traversals so its complexity is O(n). -- 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] Microsoft Interview Question
Check this out, it works in O(n);
int i = 0;
int j = n-1;
while((in j= 0)(ij))
{
if(a[i]0 a[j]0)
{
swap(a[i],a[j]);
i++; j--;
}
else
{
if(a[i]0)
i++;
if(a[j]0)
j--;
}
}
Thanks,
Mani
On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder imamadco...@gmail.com wrote:
As nothing is written about space complexity, I am assuming that we can
take extra space.
Take a temporary array of length n.
1. Maintain a counter for the length of temporary array filled till now.
2. Traverse the given array. If value contained is negative insert it in
new array and update counter. After complete traversal all negative values
will be in the temporary array.
3. Traverse again the given array. Repeat step 2 but this time for
positive numbers.
Finally temporary array contains the required answer. If required copy it
into original array.
As this approach takes max. 3 traversals so its complexity is O(n).
--
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.
--
Thanks Regards,
Mani
http://www.sanidapa.com - The music Search engine
--
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] Microsoft Interview Question
Order may not be maintained necessarily by this solution
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Thu, Jun 14, 2012 at 1:47 PM, Manikanta Babu
manikantabab...@gmail.comwrote:
Check this out, it works in O(n);
int i = 0;
int j = n-1;
while((in j= 0)(ij))
{
if(a[i]0 a[j]0)
{
swap(a[i],a[j]);
i++; j--;
}
else
{
if(a[i]0)
i++;
if(a[j]0)
j--;
}
}
Thanks,
Mani
On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder imamadco...@gmail.com wrote:
As nothing is written about space complexity, I am assuming that we can
take extra space.
Take a temporary array of length n.
1. Maintain a counter for the length of temporary array filled till now.
2. Traverse the given array. If value contained is negative insert it in
new array and update counter. After complete traversal all negative values
will be in the temporary array.
3. Traverse again the given array. Repeat step 2 but this time for
positive numbers.
Finally temporary array contains the required answer. If required copy it
into original array.
As this approach takes max. 3 traversals so its complexity is O(n).
--
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.
--
Thanks Regards,
Mani
http://www.sanidapa.com - The music Search engine
--
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] Microsoft Interview Question
@all :- by segregating 0 and 1 or by taking quicksort approach
we have to swap no.s resulting which array becomes unordered.
my approach is start from right and if a negative no. occurs insert it
into another array temp[]
this will shift all positive no.s to right and in 2nd pass start from left
of original array and insert all the elements of temp.
time comp-O(n), space comp-O(n)
correct me if i am wrong
On Thu, Jun 14, 2012 at 1:53 PM, saurabh singh saurab...@gmail.com wrote:
Order may not be maintained necessarily by this solution
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Thu, Jun 14, 2012 at 1:47 PM, Manikanta Babu manikantabab...@gmail.com
wrote:
Check this out, it works in O(n);
int i = 0;
int j = n-1;
while((in j= 0)(ij))
{
if(a[i]0 a[j]0)
{
swap(a[i],a[j]);
i++; j--;
}
else
{
if(a[i]0)
i++;
if(a[j]0)
j--;
}
}
Thanks,
Mani
On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder imamadco...@gmail.com wrote:
As nothing is written about space complexity, I am assuming that we can
take extra space.
Take a temporary array of length n.
1. Maintain a counter for the length of temporary array filled till now.
2. Traverse the given array. If value contained is negative insert it in
new array and update counter. After complete traversal all negative values
will be in the temporary array.
3. Traverse again the given array. Repeat step 2 but this time for
positive numbers.
Finally temporary array contains the required answer. If required copy
it into original array.
As this approach takes max. 3 traversals so its complexity is O(n).
--
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.
--
Thanks Regards,
Mani
http://www.sanidapa.com - The music Search engine
--
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.
--
Utsav Sharma,
NIT Allahabad
--
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] Microsoft Interview Question
how to do it in space comp- O(1) . I mean without using additional arrays.
Could it be done ?
On Thu, Jun 14, 2012 at 3:46 PM, utsav sharma utsav.sharm...@gmail.comwrote:
@all :- by segregating 0 and 1 or by taking quicksort approach
we have to swap no.s resulting which array becomes unordered.
my approach is start from right and if a negative no. occurs insert it
into another array temp[]
this will shift all positive no.s to right and in 2nd pass start from left
of original array and insert all the elements of temp.
time comp-O(n), space comp-O(n)
correct me if i am wrong
On Thu, Jun 14, 2012 at 1:53 PM, saurabh singh saurab...@gmail.comwrote:
Order may not be maintained necessarily by this solution
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Thu, Jun 14, 2012 at 1:47 PM, Manikanta Babu
manikantabab...@gmail.com wrote:
Check this out, it works in O(n);
int i = 0;
int j = n-1;
while((in j= 0)(ij))
{
if(a[i]0 a[j]0)
{
swap(a[i],a[j]);
i++; j--;
}
else
{
if(a[i]0)
i++;
if(a[j]0)
j--;
}
}
Thanks,
Mani
On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder imamadco...@gmail.comwrote:
As nothing is written about space complexity, I am assuming that we can
take extra space.
Take a temporary array of length n.
1. Maintain a counter for the length of temporary array filled till now.
2. Traverse the given array. If value contained is negative insert it
in new array and update counter. After complete traversal all negative
values will be in the temporary array.
3. Traverse again the given array. Repeat step 2 but this time for
positive numbers.
Finally temporary array contains the required answer. If required copy
it into original array.
As this approach takes max. 3 traversals so its complexity is O(n).
--
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.
--
Thanks Regards,
Mani
http://www.sanidapa.com - The music Search engine
--
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.
--
Utsav Sharma,
NIT Allahabad
--
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.
[algogeeks] Microsoft Interview Question
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done in O(n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PebCCcpUXpIJ.
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] Microsoft Interview Question
int i=0;
int j=n-1;
while (ij) {
while (ij) (a[i]=0) i++;
while (ij) (a[j0) j--;
if (ij) swap(a[i],a[j]);
else break;
i++; j--;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jun 13, 2012 at 9:49 PM, Krishna Kishore
kknarenkris...@gmail.comwrote:
Given a array of integers both positive and negative and you need to shift
positive numbers to one side
and negative numbers to other side with the order intact.
ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done in O(n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PebCCcpUXpIJ.
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] Microsoft Interview Question
+1 Ashish solution -- Thanks Regards Saurabh Yadav -- 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] Microsoft Interview Question
@shiv relate the ashish solution with quick sort then you will understand easily On Thu, Jun 14, 2012 at 2:06 AM, Saurabh Yadav saurabh...@gmail.com wrote: +1 Ashish solution -- Thanks Regards Saurabh Yadav -- Thanks Regards Saurabh Yadav -- 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] Microsoft Interview Question
@Ashish @Saurabh , Recheck your solutions , order won't be maintained in
your solutions.
Its output will be = {-1 -6 -8 3 4 5 9 }
On Thu, Jun 14, 2012 at 2:08 AM, Saurabh Yadav saurabh...@gmail.com wrote:
@shiv relate the ashish solution with quick sort then you will understand
easily
On Thu, Jun 14, 2012 at 2:06 AM, Saurabh Yadav saurabh...@gmail.comwrote:
+1 Ashish solution
--
Thanks Regards
Saurabh Yadav
--
Thanks Regards
Saurabh Yadav
--
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.
--
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
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] Microsoft Interview Question
Think of the +ve numbers as 0 negative numbers as 1.Now the problem reduces to http://stackoverflow.com/questions/682171/arrange-0s-1s-in-a-array Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, Jun 14, 2012 at 3:00 AM, Piyush Kapoor pkjee2...@gmail.com wrote: your solutions , order won't be maintained in your solutions. -- 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] Microsoft interview question
By doing Ex-OR we can find if b is permutation of A suppose a -- 3 5 4 b -- 4 3 5 if A ^ B = 0 then both are permutation or else not shout loud if this has flaws :P -mithun On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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] Microsoft interview question
@mithun: Try A = 1, 6 B = 4, 3 A ^ B = 0. Alone Ex-OR cant solve this in O(n) time. On Monday, 21 May 2012 21:48:30 UTC+5:30, mithun wrote: By doing Ex-OR we can find if b is permutation of A suppose a -- 3 5 4 b -- 4 3 5 if A ^ B = 0 then both are permutation or else not shout loud if this has flaws :P -mithun On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/M16KXaNqGnEJ. 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] Microsoft interview question
it can be done by doing set of operation on the data. 1) check sum of the square of arr1 = arr2 2) sum of elements of arr1=arr2 3) xoring elements of arr1 and arr2 == 0 if all 3 condition are successful then..permutation found. On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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] Microsoft interview question
@atul:- why we require 1st condition(check sum of the square of arr1 = arr2) ?? On Sun, May 20, 2012 at 1:10 PM, atul anand atul.87fri...@gmail.com wrote: it can be done by doing set of operation on the data. 1) check sum of the square of arr1 = arr2 2) sum of elements of arr1=arr2 3) xoring elements of arr1 and arr2 == 0 if all 3 condition are successful then..permutation found. On Sun, May 20, 2012 at 12:59 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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. -- *DARPAN BAWEJA* *3rd year, I.T* *MNNIT Allahabad* -- 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.
[algogeeks] Microsoft interview question
given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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] Microsoft interview question
method is ryt but to find ith prime u cannot to it in constant time. On May 19, 2012 7:30 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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] Microsoft interview question
@malay --- we can do it by precomputing the prime arrays On Sun, May 20, 2012 at 1:10 AM, malay chakrabarti m1234...@gmail.comwrote: method is ryt but to find ith prime u cannot to it in constant time. On May 19, 2012 7:30 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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. -- HARSHIT PAHUJA M.N.N.I.T. ALLAHABAD -- 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] Microsoft interview question
dat defeats the o(1) space constraint. :-) On May 19, 2012 8:05 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: @malay --- we can do it by precomputing the prime arrays On Sun, May 20, 2012 at 1:10 AM, malay chakrabarti m1234...@gmail.comwrote: method is ryt but to find ith prime u cannot to it in constant time. On May 19, 2012 7:30 PM, HARSHIT PAHUJA hpahuja.mn...@gmail.com wrote: given 2 unsorted integer arrays a and b of equal size. Determine if b is a permutation of a. Can this be done in O(n) time and O(1) space ? please help me with my solution suppose a -- 3 5 4 b -- 4 3 5 now we replace a[i] with a[i]..th prime number and b with b[i] .. th prime number now array a becomes 5 11 7 array b becomes 7 5 11 now we take product of elements of array a and do the same with array b elements if product is equal then b is a permutation of a -- 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. -- HARSHIT PAHUJA M.N.N.I.T. ALLAHABAD -- 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.
[algogeeks] Microsoft Interview Question
Hello friends, I recently had an onsite MS interview. One of the questions that they asked was: - Given a directed graph, write a program that takes root of the graph and returns root of a tree which comprises of all the nodes of the graph in the same way as they appeared in the graph (the graph contains no cycles). -- Umer -- 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.
[algogeeks] MicroSoft Interview Question-9 February 2011
1. write a function to convert a decimal no. to Roman no. (10 marks)
2. Design a elevators system for 50 storied hotel.
condition are... at least one left should be available on ground
flore. Min. time is expected ot reach the any floore... (5 marks)
3. Design all the test case for function
String stringReverse(i am a good boy) --- out put is (boy
good a am i) ;
4. Do the boundary level and partition equivalence testing for the
following specification.
below 18 years too young to get insured
between 18 to 30 both inclusive get insured with 20% Discount.
above 30 get insured.
5. output
a = 10;
b=a+++a;
what is a and b ? a = 11 and b=20
6. foo(int x)
{ if(x0)
foo(--x);
printf(%d,x);
}
int main()
{ foo(5);
}
output = 0,0,1,2,3,4,5
7. char m[16]=MicroSoft;
a = 2 ; will the folloing code will compile if yes then output?
Printf(%d%d,(a+3)m,m(2)) some thing like but the answer was
sf
8. one network objective quetion.. which layer is responsible for the
reliable delivery of packets..
Transport Layer
9. one mathematical quetion on realibilty is 90% and MTTF(mean time to
failure) = 200 days. if
it would be 95%. and 5 day for repair.. then what MTTF
{a.200 b.205 c. 500 d.700 }
10. Output of Sql query
Translate((Replace(Ltrim(Rtrim($$JUNK##),#),
$)JU,**),*,'trouble');
--
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.
[algogeeks] Microsoft interview question
We have a text editor application where we can choose 1)between 100s of different fonts like arial,calibri,etc.. 2)different text sizes 3) different formatting such as bold, Italics,regular,etc.. Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application. I came up with different solutions but interviewer is not satisfied, -- 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] Microsoft interview question
How many test cases were you expected to give? I think one problem you will have is rendering a font on different sizes. A generic test case could be, randomly pick a font and format and then alternate between a few extremes of the font size range and check if they look the same. Another kind of test case would be to randomly take text from the Web and check if you editor is able to identify and render it the same way. You are essentially seeing if your editor is also good at identifying fonts. What were your test cases? Sent from my BlackBerry -Original Message- From: HARISH S.C s.c.har...@gmail.com Sender: algogeeks@googlegroups.com Date: Wed, 2 Feb 2011 01:14:00 To: algogeeks@googlegroups.com Reply-To: algogeeks@googlegroups.com Subject: [algogeeks] Microsoft interview question We have a text editor application where we can choose 1)between 100s of different fonts like arial,calibri,etc.. 2)different text sizes 3) different formatting such as bold, Italics,regular,etc.. Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application. I came up with different solutions but interviewer is not satisfied, -- 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] Microsoft interview question
@Sarma : He said we should finish testing within 2 days. @Gene: I said the same answer but he said its ok for size but for font it will not work because style of each and every font will differ and he said doing exhaustive test for all fonts is not a solution too. On Wed, Feb 2, 2011 at 7:38 AM, Sarma Tangirala tvssarma.ome...@gmail.comwrote: How many test cases were you expected to give? I think one problem you will have is rendering a font on different sizes. A generic test case could be, randomly pick a font and format and then alternate between a few extremes of the font size range and check if they look the same. Another kind of test case would be to randomly take text from the Web and check if you editor is able to identify and render it the same way. You are essentially seeing if your editor is also good at identifying fonts. What were your test cases? Sent from my BlackBerry -- *From: * HARISH S.C s.c.har...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Wed, 2 Feb 2011 01:14:00 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *[algogeeks] Microsoft interview question We have a text editor application where we can choose 1)between 100s of different fonts like arial,calibri,etc.. 2)different text sizes 3) different formatting such as bold, Italics,regular,etc.. Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application. I came up with different solutions but interviewer is not satisfied, -- 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.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 algogeeks@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 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] Microsoft interview question
@guys What's the right answer? Sent from my BlackBerry -Original Message- From: HARISH S.C s.c.har...@gmail.com Sender: algogeeks@googlegroups.com Date: Wed, 2 Feb 2011 13:01:59 To: algogeeks@googlegroups.com Reply-To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Microsoft interview question @Sarma : He said we should finish testing within 2 days. @Gene: I said the same answer but he said its ok for size but for font it will not work because style of each and every font will differ and he said doing exhaustive test for all fonts is not a solution too. On Wed, Feb 2, 2011 at 7:38 AM, Sarma Tangirala tvssarma.ome...@gmail.comwrote: How many test cases were you expected to give? I think one problem you will have is rendering a font on different sizes. A generic test case could be, randomly pick a font and format and then alternate between a few extremes of the font size range and check if they look the same. Another kind of test case would be to randomly take text from the Web and check if you editor is able to identify and render it the same way. You are essentially seeing if your editor is also good at identifying fonts. What were your test cases? Sent from my BlackBerry -- *From: * HARISH S.C s.c.har...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Wed, 2 Feb 2011 01:14:00 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *[algogeeks] Microsoft interview question We have a text editor application where we can choose 1)between 100s of different fonts like arial,calibri,etc.. 2)different text sizes 3) different formatting such as bold, Italics,regular,etc.. Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application. I came up with different solutions but interviewer is not satisfied, -- 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.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 algogeeks@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 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.
[algogeeks] microsoft interview question
write a recursive function to convert a BST into sorted doubly linked list. -- 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
see careercup.com On Sat, Dec 18, 2010 at 1:49 AM, anujbhambhani anuj.bhambh...@gmail.comwrote: write a recursive function to convert a BST into sorted doubly linked list. -- 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. -- DIPANKAR DUTTA M-TECH,Computer Science Engg. EC Dept,IIT ROORKEE Uttarakhand , India – 247667 --- website:http://people.iitr.ernet.in/shp/09535009/Website/index.html ph no-09045809987 Lab: 286454 email:dipan...@iitr.ernet.in email%3adipan...@iitr.ernet.in -- 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
http://cslibrary.stanford.edu/109/TreeListRecursion.html -- 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] Microsoft interview question
I can only think of one way off the top of my head:
class IndexedDocument {
HashTableString, int index;
String contents;
/// Build an index of words and their position in the document
void buildIndex() {
for each word in document {
add word, position to index
}
}
Boolean searchFor(String word) {
// use inxed to look up
}
}
--
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] Microsoft interview question
Help me in solving this problem... Define a data struct for the search engine which will represent whether given word is there in the document or not .It should be fast. -- 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
just search for the word in the document using an efficient string matching algorithm use Knuth Morris Pratt algorithm as it runs in O(m) time. or use a data structure called TRIE where u can search for the word in O(1) time any suggestions are always welcomed On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR gobind@gmail.com wrote: Help me in solving this problem... Define a data struct for the search engine which will represent whether given word is there in the document or not .It should be fast. -- 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
@ankit u can'nt use TRIE becoz , input will be given in form of text so generating the TRIE will be much expensive than linear search On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR gobind@gmail.com wrote: Help me in solving this problem... Define a data struct for the search engine which will represent whether given word is there in the document or not .It should be fast. -- 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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
it will give you an idea. http://en.wikipedia.org/wiki/Full_text_search On Fri, Dec 10, 2010 at 4:03 PM, ADITYA KUMAR aditya...@gmail.com wrote: @ankit u can'nt use TRIE becoz , input will be given in form of text so generating the TRIE will be much expensive than linear search On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR gobind@gmail.comwrote: Help me in solving this problem... Define a data struct for the search engine which will represent whether given word is there in the document or not .It should be fast. -- 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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. -- -- Manoj Lalavat -- 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
then u can just use or build a dynamic dictionary of words as done in LZW coding such that if the word is there in the dictionary it just gives u the indx of the word and if its not it just adds that word to the dictionary any suggestions are always welcomed thnx in advance On Fri, Dec 10, 2010 at 4:08 PM, manoj lalavat manoj.lala...@gmail.comwrote: it will give you an idea. http://en.wikipedia.org/wiki/Full_text_search On Fri, Dec 10, 2010 at 4:03 PM, ADITYA KUMAR aditya...@gmail.com wrote: @ankit u can'nt use TRIE becoz , input will be given in form of text so generating the TRIE will be much expensive than linear search On Fri, Dec 10, 2010 at 3:13 PM, GOBIND KUMAR gobind@gmail.comwrote: Help me in solving this problem... Define a data struct for the search engine which will represent whether given word is there in the document or not .It should be fast. -- 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. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- 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. -- -- Manoj Lalavat -- 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
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.
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] Microsoft interview question
Asked in microsoft interview Given a snapshot of an ongoing chess game, which probably is a one vs many game, identify whether it is a valid game or not. It would be great if someone would clarify on what conditions does validity of the game depend.. --Vrinda -- 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] Microsoft interview question
How to find last unique character in a given string. Unique character means non-repeated number. Give an optimized way. -- 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.
