[algogeeks] Datastructure Space Complexity
My name is Gary Drocella, age 23, and got my BA in comp. sci. at University of Maryland College Park. I am reading a book for fun on my spare time Multidimensional and Metric Data Structures by Hanan Samet. They are talking about range trees, and they claim that a 1-dimensional range search for [B:E] is O(lg(N) + F) where N is number of nodes and F is number of points found, which makes sense because it's a binary tree. Then for higher spatial dimensions d; it becomes (O(lg(N)^d + F) What I don't understand is they also claim that the 1d structure only takes O(N) space. To me this is to low for a balanced binary tree where their are already N leaf nodes and I internal nodes. But as I'm explaining this I think I figured it out, but someone can just to make sure this is correct. So we have total space Total Space = N + I = (N + lg(N)) in O(N) Thanks for your remarks. -- 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: Amazon Interview Question
This will only work if each element in the array are relatively prime to
one another, that is for any two elements x, y in array A the gcd(x,y) = 1,
which is also just another way of saying no number divides another number
in the array. Once this rule is broken, then
the algorithm will no longer work. Here is a counter example
A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2}
You might be able to see now why this algorithm breaks down. It is because
the final product = 2^8*3^1 and of course 2^3 will easily divide this
number, but would return the wrong solution. It was of course a very good
try!
On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin wrote:
1)Find product of the array and store it in say prod o(n) and o(1)
2)now traverse the array and check if
static int i;
tag:
while(in)
if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
break;
//this may be the required element
//e-o-while
//now check is this is the element that is occuring three times o(n)
if(number is not the required one then)
goto tag;
On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
Given an array of integers where some numbers repeat once, some numbers
repeat twice and only one number repeats thrice, how do you find the number
that gets repeated 3 times?
Does this problem have an O(n) time and O(1) space solution?
No hashmaps please!
--
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: Datastructure Space Complexity
On Monday, April 29, 2013 4:06:50 PM UTC-8, Gary Drocella wrote: My name is Gary Drocella, age 23, and got my BA in comp. sci. at University of Maryland College Park. I am reading a book for fun on my spare time Multidimensional and Metric Data Structures by Hanan Samet. They are talking about range trees, and they claim that a 1-dimensional range search for [B:E] is O(lg(N) + F) where N is number of nodes and F is number of points found, which makes sense because it's a binary tree. Then for higher spatial dimensions d; it becomes (O(lg(N)^d + F) What I don't understand is they also claim that the 1d structure only takes O(N) space. To me this is to low for a balanced binary tree where their are already N leaf nodes and I internal nodes. But as I'm explaining this I think I figured it out, but someone can just to make sure this is correct. So we have total space Total Space = N + I = (N + lg(N)) in O(N) Re-thought this :). The height of the tree will be h = lg(N) so I = (sum of I=1 to h) 2^i = (1 - 2^(lg(N) / (1 - 2) = 2^lg(N) - 1 = N - 1 Therefore Total Space = N+I = (N + N-1) = 2N - 1 in O(N) got it!! Thanks for your remarks. -- 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: Amazon Interview Question
use XOR
On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella gdroc...@gmail.com wrote:
This will only work if each element in the array are relatively prime to
one another, that is for any two elements x, y in array A the gcd(x,y) = 1,
which is also just another way of saying no number divides another number
in the array. Once this rule is broken, then
the algorithm will no longer work. Here is a counter example
A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2}
You might be able to see now why this algorithm breaks down. It is
because the final product = 2^8*3^1 and of course 2^3 will easily divide
this number, but would return the wrong solution. It was of course a very
good try!
On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin wrote:
1)Find product of the array and store it in say prod o(n) and o(1)
2)now traverse the array and check if
static int i;
tag:
while(in)
if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
break;
//this may be the required element
//e-o-while
//now check is this is the element that is occuring three times o(n)
if(number is not the required one then)
goto tag;
On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
Given an array of integers where some numbers repeat once, some numbers
repeat twice and only one number repeats thrice, how do you find the number
that gets repeated 3 times?
Does this problem have an O(n) time and O(1) space solution?
No hashmaps please!
--
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.
--
regards
Parag Khanna
--
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.
