Re: [algogeeks] Re: Amazon Interview Question
Counting sort does not run in O(1) space though. Optimally it will run in O(K) space, where A is an array of integer numbers and K = max(A) - min(A) On Saturday, February 9, 2013 9:52:01 PM UTC-5, Mohanabalan wrote: can use counting sort On Sun, Jul 15, 2012 at 6:37 PM, santosh thota santosh...@gmail.comjavascript: wrote: If we can retrieve ith prime efficiently, we can do the following... 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime 2.check if (prod% (ith_prime * ith_prime )==0) then return i; else prod=prod*ith_prime; 3.repeat it till end 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 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
A bit vector is basically just a sequence of bits such as a word or even an
array of words. Here is an example...
int x = 5; // 32 bit word size on Intel IA-32 Architecture In C
programming language.
A variable in C will be either located in a register in memory or in Main
Memory. You can even have bit vector data structures
reside on the hard disk. It just looks like this
10010101010010101...
If I'm interpreting the solution properly you will index into the bit
vector based on the number found in the array A that is
for j = 1... A.size
currentNumber = A[j] // The jth array element
bitVector[currentNumber] = ~ bitVector[currentNumber] ; // Toggle the
currentNumber bit
end for
Although this is a big memory save, you're still not using constant memory
because the size of your memory is dependent on the size of a word let's
say k
In worst case the space complexity will be 2*2^k = O(2^(K+1))
On Wednesday, April 3, 2013 9:58:23 AM UTC-8, ashekhar007 wrote:
hi sourab please explain what bit vector1 and bit vector 2 really are can
you give an example please?
On Saturday, February 16, 2013 11:20:59 PM UTC+5:30, sourabh wrote:
you can solve this problem using bitvector/bitset.
first scan :
scan the array set the bit on odd occurrence and unset on even or
0 occurrence.
second scan :
shift all the odd occurring elements in beginning of array and even
towards end.
third scan : till end of odd occurring elements.
take another bit vector
on first occurence :if bit is set in bv1 then unset it and set it in bv2.
on second occurence : if bv1 is not set and bv2 is set then these are the
array elements occuring 3rd time.
On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh prakhars...@gmail.comwrote:
Yes, thats a valid point Don.
Thats what i meant when i wrote //is that correct? in the comments on
the array line in code.
int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
On Wed, Feb 13, 2013 at 9:09 PM, Don dond...@gmail.com wrote:
The xor approach only works if there are no values which occur only
once. But the problem statement indicates that some numbers occur
once, some occur twice, and one occurs three times. So you will end up
with prod equal to the xor of all of the values which occur once or
three times. Put that in your input array and you'll find that you
don't get the desired output.
I don't know of a solution better than sorting and scanning the array.
Don
On Feb 12, 3:14 pm, prakhar singh prakharsngh.1...@gmail.com wrote:
#includestdio.h
int main()
{
int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
int prod=a[0];int i;
for(i=1;i(int)sizeof(a)/sizeof(a[0]);i++)
{
prod ^= a[i];
}
printf(%d\n,prod); //outputs 3, algorithm works as Sachin
described
it;
}
On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
sachinchital...@gmail.comwrote:
use ex-or operation for all array elements..
a^a=0
a^a^a=a
On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B
mohanabala...@gmail.comwrote:
can use counting sort
On Sun, Jul 15, 2012 at 6:37 PM, santosh thota
santoshthot...@gmail.comwrote:
If we can retrieve ith prime efficiently, we can do the
following...
1.maintain a prod=1, start from 1st element, say a[0]=n find n th
prime
2.check if (prod% (ith_prime * ith_prime )==0) then return i;
else prod=prod*ith_prime;
3.repeat it till end
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@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 unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+...@googlegroups.com.
For more options, visithttps://groups.google.com/groups/opt_out.
--
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation
--
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.
For more options,
[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.
[algogeeks] Re: RAID LEVEL
RAID Level 0 is used for high performance where data loss isn't critical. Bit stripping is still performed over multiple disks, but no mirroring or parity bits used for checking data integrity. On Aug 9, 2:56 pm, Vivek Srivastava srivastava.vivek1...@gmail.com wrote: On Wed, Aug 10, 2011 at 12:22 AM, raghavendhra rahul rahulraghavend...@gmail.com wrote: @krishnameena: i think its 5 correct me if i m wrong -- Regards Raghavendhra It's Raid level 3 changing the face can change nothing .. but facing the change can change everything -- 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] Re: C question.. increment decrement operator..
@puneet The provided faq is garbage, if you want to learn about the semantics of the C programming language, then refer to this original ISO spec here http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf I also suggest that for all programming languages (OCaml, Ruby, lua script, etc) It is definitely not the OS that determines how to execute a given fragment of C code, this is the job of the compiler. The compiler converts the code into machine code using grammar parsing techniques, and the validity of compiling C code such as this [CODE] int i = 1, j = 3; printf(%d, i+j); [/CODE] will more then likely depend on w/e compiler you're using. If it's a good compiler like gcc you can tell the compiler what standard to use. gcc -ansi -o foo foo.c gcc -c99 -o foo foo.c The only time an OS would do any parsing of code is if you built an interpreter such as the JVM on the bare metal of a machine. Benefit being you have a garbage collector cleaning up un-used memory. The OS is more of an abstraction between userspace and the hardware. On Aug 7, 3:22 pm, Puneet Gautam puneet.nsi...@gmail.com wrote: Also guys, this link:http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr discusses erroneous expns like a[i]=i++; But if u run this code..this gives no error on GNU compiler.. So, are we really referring to a reliable document here..?http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr I really doubt that...! Run it on as many different systems as you can...! Lets c what all results we get...!! Pls give ur feedback... On 8/8/11, Puneet Gautam puneet.nsi...@gmail.com wrote: @ Amit: Well, the link you have posted refers that i++*i++ is not an invalid expression, it just runs differently on different OS's because every OS has a different implementation on how to solve such expressions that use the same address space(Address of the integer i). As far as i know the value of a variable can be increased multiple times on most OS's ... i have tried it on TUrbo running on WIN 95 as well as Dev Cpp on WIN 7 OS. Though it may give different output on Unix OS's like Linux but:\ Hey, we can only predict the output as we see is apt as far as we have learnt in books. And the output in my first post does the processing the bookish way... BUT THE CODE WILL NOT GIVE ANY ERROR !!! On 8/3/11, Arun toarunb...@gmail.com wrote: What Amit told is exactly correct. But I would like to know the expression evaluation order of this in gcc and turboc Arun On Aug 3, 6:15 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: @amit:+1 On Wed, Aug 3, 2011 at 3:14 PM, amit karmakar amit.codenam...@gmail.comwrote: You are wrong. The above program invokes undefined behavior. Read the standard language draft to know about sequence points, side effects and undefined behavior. Between a previous and next sequence point a variable's value cannot be modified twice. c-faq should be quite useful http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr On Aug 3, 5:20 pm, Puneet Gautam puneet.nsi...@gmail.com wrote: As we know: In an expression, if pre n post occur simultaneously, pre inc the value then n there only n post executes it after that expression...and expression evaluates right to left... Also, the value of a variable in an expression can be modified multifold times...there is no restriction on dat... Here in this code: Print statement No.: 1. i++*i++ is equivalent to: output i*i(7*7) followed by i=i+1; i=i+1; prior to 2nd printf statement..that makes i=9 2. i++*++i expn. evaluates right to left: i inc. by one due to pre.. i is now 10 . output i*i(10*10) i=i+1 (due to post inc., it inc. the value after the output) i is now 11 3. ++i*i++ right to left evaluation, but post inc. increases value only after output.. coming to ++i in the expn., i inc. to 12 output: 12*12 i=i+1(due to postinc.) i is now 13 4. ++i*++i both pre inc operators, order of evaluation doesnt ,matter: i=i+1 i=i+1 output: 15*15 i finishes at 15 Hence the output: 49 100 144 225 I think i made it clear.. Feel free to point any loopholes.. Thanks. On 8/3/11, ankit sambyal ankitsamb...@gmail.com wrote: Its compiler dependent. Acc. to the C standard an object's stored value can be modified only once in an expression. -- 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
[algogeeks] Re: C question.. increment decrement operator..
I thought this was algogeeks, not company question geeks. On Aug 7, 4:27 pm, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote: please these questions are compiler dependent and have no standard answers...these are rarely asked by companies On Sun, Aug 7, 2011 at 1:23 PM, Gary Drocella gdroc...@gmail.com wrote: @puneet The provided faq is garbage, if you want to learn about the semantics of the C programming language, then refer to this original ISO spec here http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf I also suggest that for all programming languages (OCaml, Ruby, lua script, etc) It is definitely not the OS that determines how to execute a given fragment of C code, this is the job of the compiler. The compiler converts the code into machine code using grammar parsing techniques, and the validity of compiling C code such as this [CODE] int i = 1, j = 3; printf(%d, i+j); [/CODE] will more then likely depend on w/e compiler you're using. If it's a good compiler like gcc you can tell the compiler what standard to use. gcc -ansi -o foo foo.c gcc -c99 -o foo foo.c The only time an OS would do any parsing of code is if you built an interpreter such as the JVM on the bare metal of a machine. Benefit being you have a garbage collector cleaning up un-used memory. The OS is more of an abstraction between userspace and the hardware. On Aug 7, 3:22 pm, Puneet Gautam puneet.nsi...@gmail.com wrote: Also guys, this link:http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr discusses erroneous expns like a[i]=i++; But if u run this code..this gives no error on GNU compiler.. So, are we really referring to a reliable document here..? http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr I really doubt that...! Run it on as many different systems as you can...! Lets c what all results we get...!! Pls give ur feedback... On 8/8/11, Puneet Gautam puneet.nsi...@gmail.com wrote: @ Amit: Well, the link you have posted refers that i++*i++ is not an invalid expression, it just runs differently on different OS's because every OS has a different implementation on how to solve such expressions that use the same address space(Address of the integer i). As far as i know the value of a variable can be increased multiple times on most OS's ... i have tried it on TUrbo running on WIN 95 as well as Dev Cpp on WIN 7 OS. Though it may give different output on Unix OS's like Linux but:\ Hey, we can only predict the output as we see is apt as far as we have learnt in books. And the output in my first post does the processing the bookish way... BUT THE CODE WILL NOT GIVE ANY ERROR !!! On 8/3/11, Arun toarunb...@gmail.com wrote: What Amit told is exactly correct. But I would like to know the expression evaluation order of this in gcc and turboc Arun On Aug 3, 6:15 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote: @amit:+1 On Wed, Aug 3, 2011 at 3:14 PM, amit karmakar amit.codenam...@gmail.comwrote: You are wrong. The above program invokes undefined behavior. Read the standard language draft to know about sequence points, side effects and undefined behavior. Between a previous and next sequence point a variable's value cannot be modified twice. c-faq should be quite useful http://c-faq.com/~scs/cgi-bin/faqcat.cgi?sec=expr On Aug 3, 5:20 pm, Puneet Gautam puneet.nsi...@gmail.com wrote: As we know: In an expression, if pre n post occur simultaneously, pre inc the value then n there only n post executes it after that expression...and expression evaluates right to left... Also, the value of a variable in an expression can be modified multifold times...there is no restriction on dat... Here in this code: Print statement No.: 1. i++*i++ is equivalent to: output i*i(7*7) followed by i=i+1; i=i+1; prior to 2nd printf statement..that makes i=9 2. i++*++i expn. evaluates right to left: i inc. by one due to pre.. i is now 10 . output i*i(10*10) i=i+1 (due to post inc., it inc. the value after the output) i is now 11 3. ++i*i++ right to left evaluation, but post inc. increases value only after output.. coming to ++i in the expn., i inc. to 12 output: 12*12 i=i+1(due to postinc.) i is now 13 4. ++i*++i both pre inc operators, order of evaluation doesnt ,matter: i=i+1 i=i+1 output: 15*15 i finishes at 15 Hence the output: 49 100 144 225 I think i made it clear.. Feel free to point any loopholes.. Thanks. On 8/3/11, ankit sambyal ankitsamb...@gmail.com wrote: Its
[algogeeks] Re: Google Interview Question
Here is O(n) alg...
Does Waste Memory Though :) just don't have an array over 4G, and you
should be good.
proc Merge_Partition(A)
B = {};
index = 0;
count0 = 0;
count1 = (n/2);
while index to A.length
B[index++] = A[count0++];
B[index++] = A[count1++];
end while
return B
end proc
On Aug 1, 1:30 pm, Manmeet Singh mans.aus...@gmail.com wrote:
Your code does not works proper;y for all cases
On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan jalanha...@gmail.com wrote:
Here is the recursive algo:
Rearrange(A,p,q)
1. if p is not equal to q do the following
2. r ← (p+q)/2
3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
4. Rearrange(A,p,r)
5. Rearrange(A,r+1,q)
6. return
On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta
gupta.abh...@gmail.comwrote:
A is an array of size 2n such that first n elements are integers in any
order and last n elements are characters.
i.e. A={i1 i2 i3 in c1 c2 c3... cn}
then we have to rearrange the elements such that final array is
A ={ i1 c1 i2 c2 .. in cn}
Example :
input : A ={ 5,1,4,d,r,a};
output : A= {5,d,1,r,4,a};
--
Abhishek Gupta
MCA
NIT Calicut
Kerela
--
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 :
ROHIT JALAN
B.E. Graduate,
Computer Science Department,
RVCE, Bangalore
--
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] Re: Implementation of trie data structure
Knowing The Definition of a Trie Data Structure should be all you need to know how to implement a trie ADT. It's a structure where all the true (key,value) pairs are in the external nodes, and the guide keys/values are in the internal nodes. Examples of Trie Data structures are B+ Trees, B* Trees, Huffman Coding Trees, PR Quad Trees, PM QuadTrees, PM Octrees, etc. For a B+ Tree in particular, all you need to do is when you split a leaf (when it becomes full), pick the median of the leaf and that will be the guide value to the respective split left and right leafs. But each leaf and internal node can only contain a maximum of m children nodes, which is a B+ Tree of order m. On Jul 30, 6:45 am, AMAN AGARWAL mnnit.a...@gmail.com wrote: Hi, Can somebody please give me code snippet for implementing trie data structure??? -- AMAN AGARWAL Success is not final, Failure is not fatal: It is the courage to continue that counts! -- 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] Re: Tug of War
To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- 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/-/gVAGoc_nYhAJ. 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] Probabilistic Analysis and Randomized Algorithms
Hey, I spend most of my time researching systems computing, but these problems are fun and interesting (so bare with me :) This problem is from Chapter 5 of Introduction to Algorithms (MIT Press) 5.1-2 Describe an implementation of the procedure RANDOM(a,b) that only makes calls to RANDOM(0,1). What is the expected running time of your procedure, as a function of a and b? Here is my approach... It's asking for the expected running time of the procedure, and the expected value is E[X] = sum (0 to n) x*p(x) In this case n = b-a+1 p(x) = RANDOM(0,1) = 1/2 E[X] = (1/2) * sum (0 to (b-a+1)) 1 = (b-a+1)/2 It seems that the correct answer, I've found on the internet is lg(b-a) +1 I can sort of see this, because the first time we call random will be (1/2), second (1/2)*(1/2), etc.. which would be n calls.. (1/2^n). Can anyone explain further why my answer is probably wrong, and the lg(b-a)+1 is correct? Any help is greatly appreciated, Thank You! -- 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] Re: Reading Huge input from the terminal in least time.
You could just use a pseudo-random number generator to fill in the array. You may also want to consider the data type (each unsigned int would be 4 bytes, where a unsigned char would be 1 byte). Or, If it's truly necessary to read this much data from the console... You could use unix pipes, (cat file.out | ./myprog) pipes in unix shells will redirect from the standard i/o... The format of the file.out should be input0 input1 input2 ... inputn where I guess in your case n = 10^6 That should work, but I don't code in c++ (only c) On Apr 19, 10:11 pm, shubham shubh2...@gmail.com wrote: Hello Geeks, Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6 elements in it. Input is supplied one row at a time. Then what is the best possible way to read this much data in the least amount of time as scanf() or cin takes a lot of time? -- 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.
