[algogeeks] Google Interview question - Python
I got this question set in google interview, do any one have some knowledge how to do this, One way of imagining a lazy stream implementation in python is any class that implements the method: popNext() which returns the next element of the stream, if any, otherwise None. 1. Write the following classes that implement popNext() and be sure to implement each lazily: i) Randoms - returns a random stream of unique random numbers ii) Primes - returns a stream of ordered prime numbers iii) PrimeFactors - returns a stream of prime factors for a given integer 2. Implement the following higher-order functions to test your classes: map(fn, stream) Returns a stream where fn has been applied to each element. filter(fn, stream) Returns a stream containing only the elements of the stream for which fn returns True. zipWith(fn, streamA, streamB) Applies a given binary function pairwise to the elements of two given lists. prefixReduce(fn, stream, init) Where fn(x,y) is a function to perform a reduction across the stream, returns a stream where the nth element is the result of combining the first n elements of the input stream using fn. 3. Add the method: popN(num) that pops up to num elements from the stream. -- 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: Repeated values
It won't enter an infinite loop in that case. In fact, it would
immediately return.
Don
On Oct 31, 2:39 pm, Vikram Pradhan wrote:
> @Don It will be an infinite loop for some cases ...like try this i=1, and
> a[1] = 5 , a[5] = 5
>
> *Solution:*
>
> As the numbers are from 0 to N-1 so we can xor the value with its index in
> a loop . if the result is 0 then there is no repetition else there is some
> repetition.
>
> *int result = 0;*
> *for(int i=0;i *{*
> *result ^= i ^ array[i];*
> *}*
> *
> *
> *if(result==0)*
> *There is no repetition.*
> *else*
> *There is some repetition.*
>
> Time complexity O(N)
> Space Complexity : constant
>
> check this :http://ideone.com/RXyynB
>
> As the indexes are from 0 to N-1 and numbers are also from 0 to N-1 in
> random order. So if there is no repetition then there is exactly two copies
> of same number in set of (values and index) and when we xor all the indexes
> to all the numbers the result will be zero because xor of same no. is zero.
>
> --
> Vikram Pradhan | B.Tech| Computer Science & Engineering | NIT Jalandhar |
> 9740186063 |
--
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] Ternary operators
I cant get to you..please explain...what will first statement expanded to during compilation..??.and why 0 is converted to base..i know exp3 is convertered to exp to..so int to array..???base array comes in int???and what is 0??what if we have 1 in case of 0? On Thu, Nov 1, 2012 at 5:20 PM, Saurabh Kumar wrote: > There's nothing to do with the type of "A String". > The reason for which the first code gives compilation error is: operator > (<<) has higher precedence than ternary operator (?:) so, without braces > your are actually messing up the parsing of "cout << << << "stream. > > * cout << test ? "A String" : 0 << endl;* > > consider removing the last "*< > * cout << test ? "A String" : 0;* // this compiles and runs fine with my > compiler(g++ 4.5), but as *cout << test* will take precedence, there is > no point of putting a ternary operator there, unless you use braces, of > course. > > > In teh second case however, reason given is valid: > i.e. return type of ternary operator is determined by "A String" and the > expression 0 will be taken as address of a string location. Hence, there is > no guarantee of output. > > > On 31 October 2012 19:52, rahul sharma wrote: > >> plz read carefully >> >> >> On Wed, Oct 31, 2012 at 10:18 AM, Tamanna Afroze wrote: >> >>> sorry for my last post, i didn't look carefully at the code. I think >>> without bracket the ternary expression is incomplete, that's why; first >>> code doesn't compile correctly. >>> >>> >>> >>> On Wed, Oct 31, 2012 at 9:51 AM, Tamanna Afroze wrote: >>> both codes are same. Where is the difference? >>> >>> -- >>> 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. >> > > -- > 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] Re: Repeated values
@Vikram - your approach fails for [4 1 1 1 1]
On 1 November 2012 00:09, Vikram Pradhan wrote:
> @Don It will be an infinite loop for some cases ...like try this i=1, and
> a[1] = 5 , a[5] = 5
>
> *Solution:*
>
> As the numbers are from 0 to N-1 so we can xor the value with its index in
> a loop . if the result is 0 then there is no repetition else there is some
> repetition.
>
> *int result = 0;*
> *for(int i=0;i *{*
> *result ^= i ^ array[i];*
> *}*
> *
> *
> *if(result==0)*
> *There is no repetition.*
> *else*
> *There is some repetition.*
>
> Time complexity O(N)
> Space Complexity : constant
>
> check this : http://ideone.com/RXyynB
>
> As the indexes are from 0 to N-1 and numbers are also from 0 to N-1 in
> random order. So if there is no repetition then there is exactly two copies
> of same number in set of (values and index) and when we xor all the indexes
> to all the numbers the result will be zero because xor of same no. is zero.
>
>
> --
> Vikram Pradhan | B.Tech| Computer Science & Engineering | NIT Jalandhar |
> 9740186063 |
>
> --
> 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] Pre/Post L and r value
Yes, you are right. Pre increment simply increments and returns
*reference*to same object.
somewhat like:
int& operator++(int &n){
n = n+1;
return n;
}
On 31 October 2012 02:08, rahul sharma wrote:
> @saurabh..thnxplz provide me code snippet for pre increment also..it
> will help a lot..i can guess it will do n++ and return itself..plz give
> code snippet...
>
>
> On Mon, Oct 29, 2012 at 10:50 AM, Saurabh Kumar wrote:
>
>> Post increment returns temp object because it has to return the old value
>> of object not the new incremented one:
>> Simply put, the code for post increment somewhat goes like this:
>>
>> int operator++ (int &n){
>> int temp = n;
>> n = n+1;
>> return temp;
>> }
>>
>> that's also the reason you cannot use it as a lvalue in an exprression,
>> as you would be assigning nowhere.
>>
>> On 27 October 2012 20:09, rahul sharma wrote:
>>
>>> But y post returns temp. object
>>>
>>>
>>> On Fri, Oct 26, 2012 at 8:18 PM, Saurabh Kumar wrote:
>>>
i++: Post increment can't be a lvalue because Post increment internally
returns a temporary object (NOT the location of i) hence you cannot assign
anything to it. The result of i++ can be used only as a rvalue.
++i: whereas, in Pre-increment value gets incremented and the same
location is returned back to you, hence can be used as lvalue in an
expression.(C++ allows this)
Both can be used as rvalues though.
On 26 October 2012 18:54, rahul sharma wrote:
> why pre inc. is l value and post is r value..please explain
>
> --
> 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.
>>>
>>> --
>>> 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.
>>
>
> --
> 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] Problem
@prankur can we do in this manner, first find the middle of the array and make it as a root, and call recursively from 0 to mid-1 for left subtree and mid+1 to len-1 for right subtree..? -- 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] Ternary operators
There's nothing to do with the type of "A String". The reason for which the first code gives compilation error is: operator (<<) has higher precedence than ternary operator (?:) so, without braces your are actually messing up the parsing of "cout << << << "stream. * cout << test ? "A String" : 0 << endl;* consider removing the last "*< wrote: > plz read carefully > > > On Wed, Oct 31, 2012 at 10:18 AM, Tamanna Afroze wrote: > >> sorry for my last post, i didn't look carefully at the code. I think >> without bracket the ternary expression is incomplete, that's why; first >> code doesn't compile correctly. >> >> >> >> On Wed, Oct 31, 2012 at 9:51 AM, Tamanna Afroze wrote: >> >>> both codes are same. Where is the difference? >>> >> >> -- >> 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. > -- 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: You are given two 32-bit numbers, N and M, and two bit positions, i and j.
*Yes, you are right,* int left = max - ((1 << j+1) - 1); is correct. Bcz length of the string to be inserted is (j-i)+1 . -- 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/-/sd8lOJCX-TwJ. 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] what to modify in given code so that dublicate permutations should not come
You'd simply have to keep track of : has particular alphabet already been
used or not. You can do this by maintaining a 'used' array of 0/1 . Set and
unset the respective index before and after the recursion.
Here's the modified code:
#include
#include
#include
*void allLexicographicRecur (char *str, char* data, int *used, int last,
int index)*
{
int i, len = strlen(str);
// One by one fix all characters at the given index and recur for the
// subsequent indexes
for ( i=0; iwrote:
> void allLexicographicRecur (char *str, char* data, int last, int index)
> {
> int i, len = strlen(str);
>
> // One by one fix all characters at the given index and recur for the
> // subsequent indexes
> for ( i=0; i {
> // Fix the ith character at index and if this is not the last
> index
> // then recursively call for higher indexes
> data[index] = str[i] ;
>
> // If this is the last index then print the string stored in
> data[]
> if (index == last)
> printf("%s\n", data);
> else // Recur for higher indexes
> allLexicographicRecur (str, data, last, index+1);
> }
> }
>
> /* This function sorts input string, allocate memory for data (needed for
> allLexicographicRecur()) and calls allLexicographicRecur() for printing
> all
> permutations */
> void allLexicographic(char *str)
> {
> int len = strlen (str) ;
>
> // Create a temp array that will be used by allLexicographicRecur()
> char *data = (char *) malloc (sizeof(char) * (len + 1)) ;
> data[len] = '\0';
>
> // Sort the input string so that we get all output strings in
> // lexicographically sorted order
> qsort(str, len, sizeof(char), compare);
>
> // Now print all permutaions
> allLexicographicRecur (str, data, len-1, 0);
>
> // Free data to avoid memory leak
> free(data);
> }
>
> // Needed for library function qsort()
> int compare (const void * a, const void * b)
> {
> return ( *(char *)a - *(char *)b );
> }
>
> // Driver program to test above functions
> int main()
> {
> char str[] = "ABC";
> printf("All permutations with repetition of %s are: \n", str);
> allLexicographic(str);
> getchar();
> return 0;
> }
>
> --
> 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] Re: Informatica written que : C output
My that logic is incorrect and I am sorry for that .
fine it's buffer flushing issue not that.
On 31 October 2012 15:35, Rahul Kumar Patle wrote:
> @shivam: but when i replace
> printf("Hello"); by printf("Hello\n");
> it works correctly.. can you justify this by your logic..
>
>
> On Wed, Oct 31, 2012 at 1:07 PM, Shivam Rohilla <
> rohillashivam.jade...@gmail.com> wrote:
>
>> Yes it will print 30+ times.
>> fork() --> it's create the the child process which copie's the address
>> stack of the parent process.
>> now when you will do fork();
>> look 1st iteration --> it wil break; ( if parent process scheduled 1st by
>> the kernel )
>> when 2nd iteration --> it will again fork in child process. and will
>> print hello once and dan goes to parent dan break.
>> when 3rd iteration --> it will fork again and print hello twice and dan
>> break
>> when 4th iteration --> it will again fork and prnt hello 4 times i.e.
>> hello once by iteration and dan fork child will start process from start
>> and dan print hello 3 more times and dan parent will schedule and dan break.
>> and so on...
>>
>> On 31 October 2012 11:49, tendua wrote:
>>
>>> \n also flushes the standard output buffer. If it is not present, it is
>>> possible that you have previously entered data in it. Flushing also means
>>> it forces printf to print on the screen as soon as \n is processed.
>>> Otherwise it is buffered output and you can never predict how long would OS
>>> buffer your output and when precisely it chooses to actually print.
>>>
>>> --
>>> 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/-/cNFex4s9a8UJ.
>>>
>>> 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,
> India
> [image: Twitter]
>
>
> --
> 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.
