Re: [algogeeks] Re: Generating mazes
There is another algorithm.. The one which involves random division. Basically, given an M x N matrix |...| |...| |...| |...| |...| |...| |...| |...| |...| |...| |...| Draw a random line intersecting the maze vertically, then draw another random line intersecting it horizontally. |.|.| |.|.| |.|.| |.|.| |__.|.| |.|.| |.|.| |.|.| |.|.| |.|.| |.|.| Now since you've got a 'plus' like formation of the two new lines, create an opening on each of the new intersecting lines, one on each side of the intersect |.|.| |.|.| |...| |..|| |_____|___..__| |.|.| |.|.| |.|.| |...| |.|.| |.|.| Now you've got 4 new matrices, recursively go ahead drawing more intersecting lines on them such that the new ones don't have one end point in the open. Regards On Wed, Jan 30, 2013 at 8:19 PM, Don dondod...@gmail.com wrote: It is George Marsaglia's multiply with carry pseudo-random number generator. It has a period of 2^32, which is long enough for this purpose. It is about as good as a 32-bit rng can be. In real life I use the Mersenne Twister, but I wanted something simple to include here. Don On Jan 29, 11:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: @Don can you give the logic of your rnd() function? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Anup Ghatage www.ghatage.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
*APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: perfect square condition checking....
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 30;
while(bit x) bit = 2;
while(bit)
{
if (x = res + bit)
{
x -= res + bit;
res = (res 1) + bit;
}
else
{
res = 1;
}
bit = 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com
wrote:
please suggest some efficient solution to check perfect square condition .
no matter how much large number is... eg..i/p-8949 o/p-93
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: perfect square condition checking....
@Gaurav: Does it work for n = 25 or for n = 8? I think you've confused
perfect square with power of two.
Dave
On Wednesday, February 6, 2013 11:32:55 PM UTC-6, Gaurav Rana wrote:
if(n(n-1)==0)
//perfect square
On Thu, Feb 7, 2013 at 3:01 AM, Don dond...@gmail.com javascript:wrote:
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 30;
while(bit x) bit = 2;
while(bit)
{
if (x = res + bit)
{
x -= res + bit;
res = (res 1) + bit;
}
else
{
res = 1;
}
bit = 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com
wrote:
please suggest some efficient solution to check perfect square
condition .
no matter how much large number is... eg..i/p-8949 o/p-93
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+...@googlegroups.com javascript:.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
@srikar : approach2 is wrong. ex: [1, 5, 7, 66, 7, 1, 77] first window [1,5,7] all are unique.oops On Wed, Feb 6, 2013 at 11:31 PM, Srikar srikar2...@gmail.com wrote: *APPROACH 1:* use a hashtable for both the questions ? Insert the integers as they are given in the array into a hashtable. The structure I am thinking is key (the integer) - [index]. Once all elements are inserted. Run through the hashtable and select the one which has len(value) == 1 and is least, since we want the first unique integer. for the second Q, its a more general Q of the first one. In first k=1. space: 2O(n) time: 2O(n) *APPROACH2: * When we say unique, we will have a pattern. Eg: [5, 5, 66, 66, 7, 1, 1, 77]. In this lets have moving window of 3. first consider (5,5,66). we can easily estab. that there is duplicate here. So move the window by 1 element so we get (5,66,66). Same here. move to next (66,66,7). Again dups here. next (66,7,1). No dups here! take the middle element as this has to be the first unique in the set. The left element belongs to the dup so could 1. Hence 7 is the first unique element. space: O(1) time: O(n) For seond Q I still think hashtable is best. As the numbers are streamed, keep inserting. Srikar On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur navneet.singhg...@gmail.com wrote: nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit k.anki...@gmail.com wrote: For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur navneet.singhg...@gmail.com wrote: 1. Given a array,find a first unique integer. 2. Integers are coming as online stream,have to find a kth unique integer till now. For 1. Even we cannot use sorting for solving this as if we sort it than our first number which is non-repetitive changes. The best I am able to do is nlogn using a space of O( n ). For 2. No idea -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
