Re: [algogeeks] Google Interview Question: In how many intervals does a number exists

[Avi Dullu]

Read up on Interval trees .

Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.


On Sun, Jun 9, 2013 at 12:20 AM, Monish Gupta wrote:

> There are n Intervals. Given a set of m numbers, tell in how many
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in
> codechef but could not find the same.
>
> --
> 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.
>
>
>

-- 
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.

Re: [algogeeks] Google Interview Question: In how many intervals does a number exists

[Prateek Jain]

2->2 as 2 lies in [2,3] and [1,4] ?


On Sun, Jun 9, 2013 at 12:50 PM, Monish Gupta wrote:

> There are n Intervals. Given a set of m numbers, tell in how many
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in
> codechef but could not find the same.
>
> --
> 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.
>
>
>

-- 
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.

[algogeeks] Google Interview Question: In how many intervals does a number exists

[Monish Gupta]

There are n Intervals. Given a set of m numbers, tell in how many intervals 
does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 -> 1 as 2 lies only in 1 interval [2,3]
For 4 -> 3 as 4 lies in 3 intervals
For 11 -> 0 as 11 lies in none of the given 4 intervals.

It can be easily done in O(m*n) by traversing n intervals for each number 
in the given set of m numbers. How would improve this?

Note: I could not fully recall, but I have seen very similar question in 
codechef but could not find the same.

-- 
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.

[algogeeks] Google Facebook Pocket Gems Recruitment Drive

[shady]

I was interested in knowing if anyone had the experience of going through
any of the above mentioned companies interviews. What were the questions
asked and the format ?

-- 

[algogeeks] Google Interview question - Python

[Raghavan]

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.

Re: [algogeeks] google paper

[a g]

1. Print the zig-zag traversal of a BST.

2. There is a language Googley. There are two global registers X and Y both
of whom have the character 'A' stored in them. There are only two commands
in the language.
i) next
ii) print
next increments the character in the X register. After reaching 'Z', again
'A' will be there.
When print is executed, the character in the X register is printed and the
contents in the X and Y register are swapped.
Now you are given the result of the commands, you have to return a string
which contains all the commands which would have generated the final output.

These 2 questions were of 10 marks each.
There were 10 objective questions of 1 mark each too, out of which 4 had 4
options, and we had to write short one-two lines answers for the other six
questions. I remember little of the objective qs :

1. MCQ on various sorting algorithms
2. Numerical on networking ( sub-hosts, Class B )
3. Numerical on finding the Mean time to failure of a RAID system. Mean
time to failure of one disk was given as 10^6 hours and the mean time to
repair one disk was 10 hours.
4. Three processes with some mutexes were given. We were to tell if the
processes were deadlocked, and if they were, we had to rearrange to avoid
the deadlock.
5. Output :
  int16 value = 10 ;
while ( value > 0 ) value+= 10 ;
print value
6. Two threads were given. They operated on some variables. We had to tell
that after the two threads are done, what will be the value of a specific
variable k.
7. Numerical involving finding the average waiting time in a shortest job
first scheduling.
8. Out of 5 options, we had to tell which all functions we could use to
hash the variable x.

On Sat, Aug 11, 2012 at 2:39 PM, ~*~VICKY~*~ wrote:

> Can you share the coding questions asked. Thank you.
>
>
> On Fri, Aug 10, 2012 at 10:29 PM, Abhishek Kumar wrote:
>
>> two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr..
>>
>>
>> On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote:
>>
>>> Somebody from DCE plz tell the paper pattern of google...
>>>
>>> --
>>> 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/-/BjLRVjRlekIJ.
>>> 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.
>>
>
>
>
> --
> Cheers,
>
>   Vicky
>
>  --
> 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] google paper

[Karthikeyan V.B]

Hi,

Section A - objective type 10 technical questions in OS,Algorithms,DS,C.
each carries one mark. no negative marks

Section B - coding 2 questions
first was very simple
second - spiral level order traversal of a BST

-- 
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] google paper

[Abhishek Kumar]

one Q is zig zag traversal in a tree nd d other one is like - A new
language is defined called "googley " and it has two register only 'X' and
'Y'  and only two commands are avialable "next" and  "print" each one has
some specific function (i don't remember now) and now u are given a string
and u hav to write a series of these commands for d given string lyk for
"CBC" o/p is "next next next print".

hope this will give u some idea..


On Sat, Aug 11, 2012 at 2:39 PM, ~*~VICKY~*~ wrote:

> Can you share the coding questions asked. Thank you.
>
>
> On Fri, Aug 10, 2012 at 10:29 PM, Abhishek Kumar wrote:
>
>> two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr..
>>
>>
>> On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote:
>>
>>> Somebody from DCE plz tell the paper pattern of google...
>>>
>>> --
>>> 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/-/BjLRVjRlekIJ.
>>> 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.
>>
>
>
>
> --
> Cheers,
>
>   Vicky
>
>  --
> 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] google paper

[~*~VICKY~*~]

Can you share the coding questions asked. Thank you.

On Fri, Aug 10, 2012 at 10:29 PM, Abhishek Kumar wrote:

> two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr..
>
>
> On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote:
>
>> Somebody from DCE plz tell the paper pattern of google...
>>
>> --
>> 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/-/BjLRVjRlekIJ.
>> 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.
>



-- 
Cheers,

  Vicky

-- 
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] google paper

[Abhishek Kumar]

two coding Qs + some mcqs(more than 1 option correct),time is 1.5 hr..

On Fri, Aug 10, 2012 at 4:06 PM, deepikaanand wrote:

> Somebody from DCE plz tell the paper pattern of google...
>
> --
> 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/-/BjLRVjRlekIJ.
> 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] google paper

[deepikaanand]

Somebody from DCE plz tell the paper pattern of google...

-- 
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/-/BjLRVjRlekIJ.
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] [Google question]

[atul anand]

seems like Hungarian algorithm will work .

On Wed, Aug 1, 2012 at 12:18 PM, vikas rai  wrote:

> There is a set of 9 students and 3 schools Every school can be alloted
> atmax 3 students .Every school and student has its coordinates .Now we have
> to allot student in such a way that the sum of distance from all the
> student to the school should be minimum.
> We have to solve this in less than O(n^3) .
>
>  --
> 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] [Google question]

[vikas rai]

There is a set of 9 students and 3 schools Every school can be alloted
atmax 3 students .Every school and student has its coordinates .Now we have
to allot student in such a way that the sum of distance from all the
student to the school should be minimum.
We have to solve this in less than O(n^3) .

-- 
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] Google : Print in interleaved fashion

[atul anand]

http://www.geeksforgeeks.org/archives/17743

On Tue, Jul 10, 2012 at 11:16 PM, Navin Kumar wrote:

> Given two strings .Print all the interleavings of the two strings.
> Interleaving means that the if B comes after A .It should also come after
> A in the interleaved string.
> ex-
> AB and CD
> ABCD
> ACBD
> ACDB
> CABD
> CADB
> CDAB
>
> --
> 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/-/oAU32CrEVYYJ.
> 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] Google : Print in interleaved fashion

[Navin Kumar]

Given two strings .Print all the interleavings of the two strings.
Interleaving means that the if B comes after A .It should also come after A 
in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB

-- 
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/-/oAU32CrEVYYJ.
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] [Google] Finds all the elements that appear more than n/3 times

[Navin Kumar]

Design an algorithm that, given a list of n elements in an array, finds all 
the elements that appear more than n/3 times in the list. The algorithm 
should run in linear time

( n >=0 ).

You are expected to use comparisons and achieve linear time. No 
hashing/excessive space/ and don't use standard linear time deterministic 
selection algo.

-- 
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/-/dtpraFWNFSEJ.
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] Google Developer Group, New Delhi - HACK 2012 - Code for a Cause !

[Shrey Malhotra]

Dear all,

On behalf, of *Google Developer Group New Delhi *(formerly known as* GTUG
New Delhi*) , I would like to inform you that we are going to host *H-A-C-K
- "Code for a Cause", *a hackathon, on *16-17th June* at the *Indian
Habitat Center, New Delhi*.

 *HACK- "Code for a Cause"* is being organized with the goal of bringing
> together developers, designers, startups & NGOs to apply their talents to
> the social sector and build product ideas for social innovation. It is agreat 
> chance for the developers to code  good apps that do good.


The selected themes for the event are Education, Health, Information
Access, Women Security, Disaster Management and other related to social
sector.

Can your app help India achieve the threshold literacy level? Can you
> educate the 290 million illiterates? Can it make education fun?
> Can your app help a woman in danger? Make her feel safe?
> Can your app help people know more about their health? Can it help them
> prevent diseases?



To participate, Register yourself at www.gdg-hack.com

Stop complaining, take a step and make a difference!!

You can watch the teaser video for the event here -
http://youtu.be/PR68eEWB4bk
Regards,
Shrey Malhotra
GDG New Delhi , Organizer
+91-9711455462

-- 
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] Google Q : all anagrams next to each other

[partha sarathi Mohanty]

@ashish : couldnt get u.. can u give an example??

On Tue, May 22, 2012 at 5:45 PM, Prem Krishna Chettri wrote:

> What I Could possibly think of is
>
>  For each string S1 that is an anagram of some string S, use Map and Store
> the Key Value as (S1,S). Now there is a trick here abt how to reduce Time
> Complexity here...
>
>  Now its easy to put all string which has correspondence S next to each
> other. This is Simple one.
>
> Inplace.. Hv to think abt .. I doubt, as we need some space to get the
> anagrams Dude..
>
> Prem
>
> On Tue, May 22, 2012 at 5:18 PM, Ashish Goel  wrote:
>
>> Write a method to sort an array of strings so that all the anagrams are
>> next to each other.
>>
>> What i could think of is preparing a multi linked list( multimap) whereby
>> the key for each string is the sorted representation of the string(eg if
>> string is gac, its sorted representation is acg). Walk of all lists of this
>> multimap to give all anagrams.
>>
>> Is there any other better solution for this problem?
>> Can this be done *inplace*?
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>> --
>> 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] Google Q: longest word made of subwords within the list

[atul anand]

think in term of following input case :-

best
test
testbest

than i guess you will come to knw why i got confused at first place.
*madammadam*
*testtesttest *
ignore this type of test case.

On Wed, May 23, 2012 at 12:40 AM, Prem Krishna Chettri
wrote:

> Thank you to understanding Me..
>
>   Well For Trie.. I don't hv to say much more to say except the basic need
> which says "Collect Common Prefix" . If it didnt ring the bell.. than Hv a
> look at strings MADAM and MADAMIAMADAM stored in your TRIE .. Just draw a
> pictorial representation.
>
>
>
> On Wed, May 23, 2012 at 12:20 AM, atul anand wrote:
>
>> yes ,longest word can be found while inserting each word it the TRIE.
>>
>>  *By tracking Second and First Longest word found** -- *confused me
>> ...what you were trying to say.
>> tracking can be done but become little difficult if input is something
>> like this :-
>>
>> best
>> bestest
>> test
>> testbest
>> testbesttest
>>
>> btw TRIE containing only distinct word i.e words not made up of sub words
>> would be enough to solve the problem
>>
>> On Tue, May 22, 2012 at 11:40 PM, Prem Krishna Chettri <
>> hprem...@gmail.com> wrote:
>>
>>> Haha,, Do I hv to respond Here.. Anyways Guys And Specially Mr.Atul.
>>> Here is the Long way to Make you understand..
>>>
>>> Yes 2 ptr is Alwayz Enuf now Why??
>>>
>>>  Yes Words can be a assembly of words.. Like say you sample
>>> "testtesttest..n time".. So Lets go back to Simple recursion.. Tell me how
>>> U calculate recursive Factorial (n) ?? similarly to get testtest...n there
>>> must be one string called testtest...(n-1) and the other test right !!! So
>>> 2 ptr is alwayz enuf to resolve this.
>>>
>>>   Now as we all know the smart way to update these valuable pointers are
>>> keep looking for possible next level words.. So I've put.(*Updating
>>> Otherwise Accordingly)*
>>>
>>> For your second condescending question.
>>>
>>>   It is well known if U remember DWAG/TRIE that they
>>> have nodes which *MAY *contains Alphabets.. as we move down using
>>> branches alwayz. so. if U are Considering Node as Alphabets (Narrow way of
>>> thinking) than yes, but I would like to be more general and so will like to
>>> put as N=Number of Nodes to be visited.
>>>
>>> BR,
>>> Prem
>>>
>>>
>>> On Tue, May 22, 2012 at 10:41 PM, atul anand wrote:
>>>
 @krishna : tracking just second and first longest word would be enough??

 what if input has word which is made by repeating small word again and
 again
 test
 tester
 testertest
 testing
 testingtester
 testtesttesttesttest  // added word

 and by saying O(n) .. n= total number of alphabets in the file rite??

 On Tue, May 22, 2012 at 7:17 PM, Prem Krishna Chettri <
 hprem...@gmail.com> wrote:

> Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may
> be taken into consideration..
>
> T(O)=O(n) can be done easily.. ( By tracking Second and First Longest
> word found soFar and updating otherwise accordingly)
>
> Can someone do it better?
>
>
> On Tue, May 22, 2012 at 6:15 PM, Ashish Goel wrote:
>
>> write a program to find the longest word made of other words. For
>> instance, If my file has the following words (sorted):
>> test
>> tester
>> testertest
>> testing
>> testingtester
>>
>> The longest word should be testingtester. Trie is the solution, what
>> is the best Order possible?
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>> --
>> 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 a

Re: [algogeeks] Google Q: longest word made of subwords within the list

[Prem Krishna Chettri]

Thank you to understanding Me..

  Well For Trie.. I don't hv to say much more to say except the basic need
which says "Collect Common Prefix" . If it didnt ring the bell.. than Hv a
look at strings MADAM and MADAMIAMADAM stored in your TRIE .. Just draw a
pictorial representation.



On Wed, May 23, 2012 at 12:20 AM, atul anand wrote:

> yes ,longest word can be found while inserting each word it the TRIE.
>
>  *By tracking Second and First Longest word found** -- *confused me
> ...what you were trying to say.
> tracking can be done but become little difficult if input is something
> like this :-
>
> best
> bestest
> test
> testbest
> testbesttest
>
> btw TRIE containing only distinct word i.e words not made up of sub words
> would be enough to solve the problem
>
> On Tue, May 22, 2012 at 11:40 PM, Prem Krishna Chettri  > wrote:
>
>> Haha,, Do I hv to respond Here.. Anyways Guys And Specially Mr.Atul. Here
>> is the Long way to Make you understand..
>>
>> Yes 2 ptr is Alwayz Enuf now Why??
>>
>>  Yes Words can be a assembly of words.. Like say you sample
>> "testtesttest..n time".. So Lets go back to Simple recursion.. Tell me how
>> U calculate recursive Factorial (n) ?? similarly to get testtest...n there
>> must be one string called testtest...(n-1) and the other test right !!! So
>> 2 ptr is alwayz enuf to resolve this.
>>
>>   Now as we all know the smart way to update these valuable pointers are
>> keep looking for possible next level words.. So I've put.(*Updating
>> Otherwise Accordingly)*
>>
>> For your second condescending question.
>>
>>   It is well known if U remember DWAG/TRIE that they have
>> nodes which *MAY *contains Alphabets.. as we move down using branches
>> alwayz. so. if U are Considering Node as Alphabets (Narrow way of thinking)
>> than yes, but I would like to be more general and so will like to put as
>> N=Number of Nodes to be visited.
>>
>> BR,
>> Prem
>>
>>
>> On Tue, May 22, 2012 at 10:41 PM, atul anand wrote:
>>
>>> @krishna : tracking just second and first longest word would be enough??
>>>
>>> what if input has word which is made by repeating small word again and
>>> again
>>> test
>>> tester
>>> testertest
>>> testing
>>> testingtester
>>> testtesttesttesttest  // added word
>>>
>>> and by saying O(n) .. n= total number of alphabets in the file rite??
>>>
>>> On Tue, May 22, 2012 at 7:17 PM, Prem Krishna Chettri <
>>> hprem...@gmail.com> wrote:
>>>
 Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may be
 taken into consideration..

 T(O)=O(n) can be done easily.. ( By tracking Second and First Longest
 word found soFar and updating otherwise accordingly)

 Can someone do it better?


 On Tue, May 22, 2012 at 6:15 PM, Ashish Goel  wrote:

> write a program to find the longest word made of other words. For
> instance, If my file has the following words (sorted):
> test
> tester
> testertest
> testing
> testingtester
>
> The longest word should be testingtester. Trie is the solution, what
> is the best Order possible?
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> --
> 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 thi

Re: [algogeeks] Google Q: longest word made of subwords within the list

[atul anand]

yes ,longest word can be found while inserting each word it the TRIE.

 *By tracking Second and First Longest word found** -- *confused me ...what
you were trying to say.
tracking can be done but become little difficult if input is something like
this :-

best
bestest
test
testbest
testbesttest

btw TRIE containing only distinct word i.e words not made up of sub words
would be enough to solve the problem
On Tue, May 22, 2012 at 11:40 PM, Prem Krishna Chettri
wrote:

> Haha,, Do I hv to respond Here.. Anyways Guys And Specially Mr.Atul. Here
> is the Long way to Make you understand..
>
> Yes 2 ptr is Alwayz Enuf now Why??
>
>  Yes Words can be a assembly of words.. Like say you sample
> "testtesttest..n time".. So Lets go back to Simple recursion.. Tell me how
> U calculate recursive Factorial (n) ?? similarly to get testtest...n there
> must be one string called testtest...(n-1) and the other test right !!! So
> 2 ptr is alwayz enuf to resolve this.
>
>   Now as we all know the smart way to update these valuable pointers are
> keep looking for possible next level words.. So I've put.(*Updating
> Otherwise Accordingly)*
>
> For your second condescending question.
>
>   It is well known if U remember DWAG/TRIE that they have
> nodes which *MAY *contains Alphabets.. as we move down using branches
> alwayz. so. if U are Considering Node as Alphabets (Narrow way of thinking)
> than yes, but I would like to be more general and so will like to put as
> N=Number of Nodes to be visited.
>
> BR,
> Prem
>
>
> On Tue, May 22, 2012 at 10:41 PM, atul anand wrote:
>
>> @krishna : tracking just second and first longest word would be enough??
>>
>> what if input has word which is made by repeating small word again and
>> again
>> test
>> tester
>> testertest
>> testing
>> testingtester
>> testtesttesttesttest  // added word
>>
>> and by saying O(n) .. n= total number of alphabets in the file rite??
>>
>> On Tue, May 22, 2012 at 7:17 PM, Prem Krishna Chettri > > wrote:
>>
>>> Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may be
>>> taken into consideration..
>>>
>>> T(O)=O(n) can be done easily.. ( By tracking Second and First Longest
>>> word found soFar and updating otherwise accordingly)
>>>
>>> Can someone do it better?
>>>
>>>
>>> On Tue, May 22, 2012 at 6:15 PM, Ashish Goel  wrote:
>>>
 write a program to find the longest word made of other words. For
 instance, If my file has the following words (sorted):
 test
 tester
 testertest
 testing
 testingtester

 The longest word should be testingtester. Trie is the solution, what is
 the best Order possible?
 Best Regards
 Ashish Goel
 "Think positive and find fuel in failure"
 +919985813081
 +919966006652

 --
 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] Google Q: longest word made of subwords within the list

[atul anand]

@krishna : tracking just second and first longest word would be enough??

what if input has word which is made by repeating small word again and again
test
tester
testertest
testing
testingtester
testtesttesttesttest  // added word

and by saying O(n) .. n= total number of alphabets in the file rite??

On Tue, May 22, 2012 at 7:17 PM, Prem Krishna Chettri wrote:

> Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may be
> taken into consideration..
>
> T(O)=O(n) can be done easily.. ( By tracking Second and First Longest word
> found soFar and updating otherwise accordingly)
>
> Can someone do it better?
>
>
> On Tue, May 22, 2012 at 6:15 PM, Ashish Goel  wrote:
>
>> write a program to find the longest word made of other words. For
>> instance, If my file has the following words (sorted):
>> test
>> tester
>> testertest
>> testing
>> testingtester
>>
>> The longest word should be testingtester. Trie is the solution, what is
>> the best Order possible?
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>> --
>> 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] Google Q : all anagrams next to each other

[aanchal goyal]

Anyways we need to sort all the words atleast once,  one way is
To travel throught the list sorting each word and making  a pair of the
orginal and the sorted word.
For Ex. If one of the original word in list is "aanchal" sorted is
"aaachln". So store the pair <"aanchal", "aaachln">
Now sort this list of pairs based on 2nd value.

-- 
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] Google Q: longest word made of subwords within the list

[Prem Krishna Chettri]

Yea this is a Straight Cut Trie Question No Doubt.. Perhaps DWAG may be
taken into consideration..

T(O)=O(n) can be done easily.. ( By tracking Second and First Longest word
found soFar and updating otherwise accordingly)

Can someone do it better?


On Tue, May 22, 2012 at 6:15 PM, Ashish Goel  wrote:

> write a program to find the longest word made of other words. For
> instance, If my file has the following words (sorted):
> test
> tester
> testertest
> testing
> testingtester
>
> The longest word should be testingtester. Trie is the solution, what is
> the best Order possible?
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> --
> 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] Google Q: longest word made of subwords within the list

[Ashish Goel]

write a program to find the longest word made of other words. For instance,
If my file has the following words (sorted):
test
tester
testertest
testing
testingtester

The longest word should be testingtester. Trie is the solution, what is the
best Order possible?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652

-- 
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] Google Q : all anagrams next to each other

[Prem Krishna Chettri]

What I Could possibly think of is

 For each string S1 that is an anagram of some string S, use Map and Store
the Key Value as (S1,S). Now there is a trick here abt how to reduce Time
Complexity here...

 Now its easy to put all string which has correspondence S next to each
other. This is Simple one.

Inplace.. Hv to think abt .. I doubt, as we need some space to get the
anagrams Dude..

Prem

On Tue, May 22, 2012 at 5:18 PM, Ashish Goel  wrote:

> Write a method to sort an array of strings so that all the anagrams are
> next to each other.
>
> What i could think of is preparing a multi linked list( multimap) whereby
> the key for each string is the sorted representation of the string(eg if
> string is gac, its sorted representation is acg). Walk of all lists of this
> multimap to give all anagrams.
>
> Is there any other better solution for this problem?
> Can this be done *inplace*?
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> --
> 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] Google Q : all anagrams next to each other

[Ashish Goel]

Write a method to sort an array of strings so that all the anagrams are
next to each other.

What i could think of is preparing a multi linked list( multimap) whereby
the key for each string is the sorted representation of the string(eg if
string is gac, its sorted representation is acg). Walk of all lists of this
multimap to give all anagrams.

Is there any other better solution for this problem?
Can this be done *inplace*?

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652

-- 
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] google

[Karthikeyan V.B]

Hi,

Regd OS,

1.deadlock
2.diff between linux, windows and solaris in terms of internals design
3.diff between mutex and semaphore
4.spin lock
5.interrupts
6.steps in page fault handling
6.steps involved in booting an os
7.what is kernel
8.paging  & segmentation
9.process scheduling algorithms
10.RTOS & Buffer overflow attack

Regards,
Karthikeyan

-- 
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] google

[bharath chowdary]

sorry dude it came to ITBHU with tag of marketing so i could not be
helpful to u in this case.


On 4/1/12, Deepak Garg  wrote:
> hey guys!
>
> google is coming to our college, their main requirements is from
> operating systems and computer networks.
>
> can some one post the sample questions for it..
>
> thanks
> Deepak
>
> --
> 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] google

[Deepak Garg]

hey guys!

google is coming to our college, their main requirements is from
operating systems and computer networks.

can some one post the sample questions for it..

thanks
Deepak

-- 
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] Google Question Invoice -bills

[Ashish Goel]

the DP is not clear, can you give example on how this DP would work for n
invoices and k bills?
Why is F(0,k) = 1?

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Mon, Mar 26, 2012 at 2:16 PM, atul anand  wrote:

> it is similar to sum-subset problem following recurrance will solve this
> problem , you need to run algo for each invoice to find all combination
>
> F(n,k) = F(n,k-1) or F(n - a[k], k-1)
> base case :F(0,k)=1 for k>=0
> F(n,0)= 0 for n>0.
>
>
> On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra 
> wrote:
>
>> There are 210 Invoices and 1700 bills – these bills add up to these
>> invoices
>>
>> The association between  bills and invoices is lost . The only way to
>> match them is by adding them up to correct amounts that are equal to
>> the invoices.
>>
>> For Example :  there were 2 invoices for 80, 210 and you have bills
>> for these 50, 10 ,10, 30 , 20, 70, 100 values
>>
>> One of the possible solution is :
>>
>> 80=50 + 30
>> 210= 10 + 10 +20 + 70 + 100
>>
>> Other possible solution is
>>
>> 80=50 + 10 + 20
>> 210= 30 +20 + 70 + 100
>>
>>
>> What is the best possible way to get all solutions ? Remember you are
>> dealing with big datasets
>>
>> -Kabir
>>
>> --
>> 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] Google Question Invoice -bills

[atul anand]

@ankush: i told one approach above , but may i want clear . i am not saying
this is the best approach to do so but it is one naive soln i came up with.

so find all possible combination for each invoice and save it in some data
structure.
now start from 1st invoice and select 1st invoice combination say for
invoice 80 = 50 + 30
now search in next invoice(210) combination , if there is any combination
for this invoice which does not include 50 and 30
if yes there is one say  210= 10 + 10 +20 + 70 + 100 , we have a hit and do
similar with other invoice . every time you move fwd make sure that you
should search for combination which does not include any of those bill used
in prev finding.
if no, then we know that there is no point of moving fwd , so select
another combination from prev invoice in this case its 80 and follow same
as above.


On Mon, Mar 26, 2012 at 5:56 PM,  wrote:

> **
> You can use dp to find subsets . But how is dp used for the overall
> probkem
> Sent from BlackBerry® on Airtel
> --
> *From: * atul anand 
> *Sender: * algogeeks@googlegroups.com
> *Date: *Mon, 26 Mar 2012 16:52:08 +0530
> *To: *
> *ReplyTo: * algogeeks@googlegroups.com
> *Subject: *Re: [algogeeks] Google Question Invoice -bills
>
> @umer : dp approach is given in above post.
>
> On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq  wrote:
>
>> Well, they have specified in the question that "you are dealing with
>> big-data sets". So, recursion won't be a good option I guess.
>>
>> Can we solve it with dynamic programming technique?
>>
>>
>> On Mon, Mar 26, 2012 at 2:24 PM, atul anand wrote:
>>
>>> one way to do it , is say first combination for invoice 80= 50 + 30
>>> now remove 80 and 30 from the input bills while finding combination from
>>> 210 , check if it is possible
>>> if yes , we got one solution
>>> not select another invoice combination 80= 50 + 10 + 20
>>> now dont consider these values while find combination for 210.
>>>
>>> i guess there can be better way to solve this..
>>>
>>>
>>> On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra <
>>> ankush.bago...@gmail.com> wrote:
>>>
>>>> Ok now you have combination of each invoice .  What is the approach to
>>>> take mutual exclusive combinations for so that sum of all bills equals
>>>> sum of all invoices
>>>>
>>>> On Mon, Mar 26, 2012 at 2:16 PM, atul anand 
>>>> wrote:
>>>> > it is similar to sum-subset problem following recurrance will solve
>>>> this
>>>> > problem , you need to run algo for each invoice to find all
>>>> combination
>>>> >
>>>> > F(n,k) = F(n,k-1) or F(n - a[k], k-1)
>>>> > base case :F(0,k)=1 for k>=0
>>>> > F(n,0)= 0 for n>0.
>>>> >
>>>> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra <
>>>> ankush.bago...@gmail.com>
>>>> > wrote:
>>>> >>
>>>> >> There are 210 Invoices and 1700 bills – these bills add up to these
>>>> >> invoices
>>>> >>
>>>> >> The association between  bills and invoices is lost . The only way to
>>>> >> match them is by adding them up to correct amounts that are equal to
>>>> >> the invoices.
>>>> >>
>>>> >> For Example :  there were 2 invoices for 80, 210 and you have bills
>>>> >> for these 50, 10 ,10, 30 , 20, 70, 100 values
>>>> >>
>>>> >> One of the possible solution is :
>>>> >>
>>>> >> 80=50 + 30
>>>> >> 210= 10 + 10 +20 + 70 + 100
>>>> >>
>>>> >> Other possible solution is
>>>> >>
>>>> >> 80=50 + 10 + 20
>>>> >> 210= 30 +20 + 70 + 100
>>>> >>
>>>> >>
>>>> >> What is the best possible way to get all solutions ? Remember you are
>>>> >> dealing with big datasets
>>>> >>
>>>> >> -Kabir
>>>> >>
>>>> >> --
>>>> >> 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...@google

Re: [algogeeks] Google Question Invoice -bills

[ankush . bagotra]

You can use dp to find subsets . But how is dp used for the overall probkem 
Sent from BlackBerry® on Airtel

-Original Message-
From: atul anand 
Sender: algogeeks@googlegroups.com
Date: Mon, 26 Mar 2012 16:52:08 
To: 
Reply-To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Google Question Invoice -bills

@umer : dp approach is given in above post.

On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq  wrote:

> Well, they have specified in the question that "you are dealing with
> big-data sets". So, recursion won't be a good option I guess.
>
> Can we solve it with dynamic programming technique?
>
>
> On Mon, Mar 26, 2012 at 2:24 PM, atul anand wrote:
>
>> one way to do it , is say first combination for invoice 80= 50 + 30
>> now remove 80 and 30 from the input bills while finding combination from
>> 210 , check if it is possible
>> if yes , we got one solution
>> not select another invoice combination 80= 50 + 10 + 20
>> now dont consider these values while find combination for 210.
>>
>> i guess there can be better way to solve this..
>>
>>
>> On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra > > wrote:
>>
>>> Ok now you have combination of each invoice .  What is the approach to
>>> take mutual exclusive combinations for so that sum of all bills equals
>>> sum of all invoices
>>>
>>> On Mon, Mar 26, 2012 at 2:16 PM, atul anand 
>>> wrote:
>>> > it is similar to sum-subset problem following recurrance will solve
>>> this
>>> > problem , you need to run algo for each invoice to find all combination
>>> >
>>> > F(n,k) = F(n,k-1) or F(n - a[k], k-1)
>>> > base case :F(0,k)=1 for k>=0
>>> > F(n,0)= 0 for n>0.
>>> >
>>> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra <
>>> ankush.bago...@gmail.com>
>>> > wrote:
>>> >>
>>> >> There are 210 Invoices and 1700 bills – these bills add up to these
>>> >> invoices
>>> >>
>>> >> The association between  bills and invoices is lost . The only way to
>>> >> match them is by adding them up to correct amounts that are equal to
>>> >> the invoices.
>>> >>
>>> >> For Example :  there were 2 invoices for 80, 210 and you have bills
>>> >> for these 50, 10 ,10, 30 , 20, 70, 100 values
>>> >>
>>> >> One of the possible solution is :
>>> >>
>>> >> 80=50 + 30
>>> >> 210= 10 + 10 +20 + 70 + 100
>>> >>
>>> >> Other possible solution is
>>> >>
>>> >> 80=50 + 10 + 20
>>> >> 210= 30 +20 + 70 + 100
>>> >>
>>> >>
>>> >> What is the best possible way to get all solutions ? Remember you are
>>> >> dealing with big datasets
>>> >>
>>> >> -Kabir
>>> >>
>>> >> --
>>> >> 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 

Re: [algogeeks] Google Question Invoice -bills

[atul anand]

@umer : dp approach is given in above post.

On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq  wrote:

> Well, they have specified in the question that "you are dealing with
> big-data sets". So, recursion won't be a good option I guess.
>
> Can we solve it with dynamic programming technique?
>
>
> On Mon, Mar 26, 2012 at 2:24 PM, atul anand wrote:
>
>> one way to do it , is say first combination for invoice 80= 50 + 30
>> now remove 80 and 30 from the input bills while finding combination from
>> 210 , check if it is possible
>> if yes , we got one solution
>> not select another invoice combination 80= 50 + 10 + 20
>> now dont consider these values while find combination for 210.
>>
>> i guess there can be better way to solve this..
>>
>>
>> On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra > > wrote:
>>
>>> Ok now you have combination of each invoice .  What is the approach to
>>> take mutual exclusive combinations for so that sum of all bills equals
>>> sum of all invoices
>>>
>>> On Mon, Mar 26, 2012 at 2:16 PM, atul anand 
>>> wrote:
>>> > it is similar to sum-subset problem following recurrance will solve
>>> this
>>> > problem , you need to run algo for each invoice to find all combination
>>> >
>>> > F(n,k) = F(n,k-1) or F(n - a[k], k-1)
>>> > base case :F(0,k)=1 for k>=0
>>> > F(n,0)= 0 for n>0.
>>> >
>>> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra <
>>> ankush.bago...@gmail.com>
>>> > wrote:
>>> >>
>>> >> There are 210 Invoices and 1700 bills – these bills add up to these
>>> >> invoices
>>> >>
>>> >> The association between  bills and invoices is lost . The only way to
>>> >> match them is by adding them up to correct amounts that are equal to
>>> >> the invoices.
>>> >>
>>> >> For Example :  there were 2 invoices for 80, 210 and you have bills
>>> >> for these 50, 10 ,10, 30 , 20, 70, 100 values
>>> >>
>>> >> One of the possible solution is :
>>> >>
>>> >> 80=50 + 30
>>> >> 210= 10 + 10 +20 + 70 + 100
>>> >>
>>> >> Other possible solution is
>>> >>
>>> >> 80=50 + 10 + 20
>>> >> 210= 30 +20 + 70 + 100
>>> >>
>>> >>
>>> >> What is the best possible way to get all solutions ? Remember you are
>>> >> dealing with big datasets
>>> >>
>>> >> -Kabir
>>> >>
>>> >> --
>>> >> 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.
>>
>
>
>
> --
> 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.
>

-- 
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] Google Question Invoice -bills

[Umer Farooq]

Well, they have specified in the question that "you are dealing with
big-data sets". So, recursion won't be a good option I guess.

Can we solve it with dynamic programming technique?

On Mon, Mar 26, 2012 at 2:24 PM, atul anand  wrote:

> one way to do it , is say first combination for invoice 80= 50 + 30
> now remove 80 and 30 from the input bills while finding combination from
> 210 , check if it is possible
> if yes , we got one solution
> not select another invoice combination 80= 50 + 10 + 20
> now dont consider these values while find combination for 210.
>
> i guess there can be better way to solve this..
>
>
> On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra 
> wrote:
>
>> Ok now you have combination of each invoice .  What is the approach to
>> take mutual exclusive combinations for so that sum of all bills equals
>> sum of all invoices
>>
>> On Mon, Mar 26, 2012 at 2:16 PM, atul anand 
>> wrote:
>> > it is similar to sum-subset problem following recurrance will solve this
>> > problem , you need to run algo for each invoice to find all combination
>> >
>> > F(n,k) = F(n,k-1) or F(n - a[k], k-1)
>> > base case :F(0,k)=1 for k>=0
>> > F(n,0)= 0 for n>0.
>> >
>> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra <
>> ankush.bago...@gmail.com>
>> > wrote:
>> >>
>> >> There are 210 Invoices and 1700 bills – these bills add up to these
>> >> invoices
>> >>
>> >> The association between  bills and invoices is lost . The only way to
>> >> match them is by adding them up to correct amounts that are equal to
>> >> the invoices.
>> >>
>> >> For Example :  there were 2 invoices for 80, 210 and you have bills
>> >> for these 50, 10 ,10, 30 , 20, 70, 100 values
>> >>
>> >> One of the possible solution is :
>> >>
>> >> 80=50 + 30
>> >> 210= 10 + 10 +20 + 70 + 100
>> >>
>> >> Other possible solution is
>> >>
>> >> 80=50 + 10 + 20
>> >> 210= 30 +20 + 70 + 100
>> >>
>> >>
>> >> What is the best possible way to get all solutions ? Remember you are
>> >> dealing with big datasets
>> >>
>> >> -Kabir
>> >>
>> >> --
>> >> 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.
>



-- 
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.

Re: [algogeeks] Google Question Invoice -bills

[atul anand]

one way to do it , is say first combination for invoice 80= 50 + 30
now remove 80 and 30 from the input bills while finding combination from
210 , check if it is possible
if yes , we got one solution
not select another invoice combination 80= 50 + 10 + 20
now dont consider these values while find combination for 210.

i guess there can be better way to solve this..

On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra wrote:

> Ok now you have combination of each invoice .  What is the approach to
> take mutual exclusive combinations for so that sum of all bills equals
> sum of all invoices
>
> On Mon, Mar 26, 2012 at 2:16 PM, atul anand 
> wrote:
> > it is similar to sum-subset problem following recurrance will solve this
> > problem , you need to run algo for each invoice to find all combination
> >
> > F(n,k) = F(n,k-1) or F(n - a[k], k-1)
> > base case :F(0,k)=1 for k>=0
> > F(n,0)= 0 for n>0.
> >
> > On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra <
> ankush.bago...@gmail.com>
> > wrote:
> >>
> >> There are 210 Invoices and 1700 bills – these bills add up to these
> >> invoices
> >>
> >> The association between  bills and invoices is lost . The only way to
> >> match them is by adding them up to correct amounts that are equal to
> >> the invoices.
> >>
> >> For Example :  there were 2 invoices for 80, 210 and you have bills
> >> for these 50, 10 ,10, 30 , 20, 70, 100 values
> >>
> >> One of the possible solution is :
> >>
> >> 80=50 + 30
> >> 210= 10 + 10 +20 + 70 + 100
> >>
> >> Other possible solution is
> >>
> >> 80=50 + 10 + 20
> >> 210= 30 +20 + 70 + 100
> >>
> >>
> >> What is the best possible way to get all solutions ? Remember you are
> >> dealing with big datasets
> >>
> >> -Kabir
> >>
> >> --
> >> 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] Google Question Invoice -bills

[Ankush Bagotra]

Ok now you have combination of each invoice .  What is the approach to
take mutual exclusive combinations for so that sum of all bills equals
sum of all invoices

On Mon, Mar 26, 2012 at 2:16 PM, atul anand  wrote:
> it is similar to sum-subset problem following recurrance will solve this
> problem , you need to run algo for each invoice to find all combination
>
> F(n,k) = F(n,k-1) or F(n - a[k], k-1)
> base case :F(0,k)=1 for k>=0
>     F(n,0)= 0 for n>0.
>
> On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra 
> wrote:
>>
>> There are 210 Invoices and 1700 bills – these bills add up to these
>> invoices
>>
>> The association between  bills and invoices is lost . The only way to
>> match them is by adding them up to correct amounts that are equal to
>> the invoices.
>>
>> For Example :  there were 2 invoices for 80, 210 and you have bills
>> for these 50, 10 ,10, 30 , 20, 70, 100 values
>>
>> One of the possible solution is :
>>
>> 80=50 + 30
>> 210= 10 + 10 +20 + 70 + 100
>>
>> Other possible solution is
>>
>> 80=50 + 10 + 20
>> 210= 30 +20 + 70 + 100
>>
>>
>> What is the best possible way to get all solutions ? Remember you are
>> dealing with big datasets
>>
>> -Kabir
>>
>> --
>> 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] Google Question Invoice -bills

[atul anand]

it is similar to sum-subset problem following recurrance will solve this
problem , you need to run algo for each invoice to find all combination

F(n,k) = F(n,k-1) or F(n - a[k], k-1)
base case :F(0,k)=1 for k>=0
F(n,0)= 0 for n>0.

On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra wrote:

> There are 210 Invoices and 1700 bills – these bills add up to these
> invoices
>
> The association between  bills and invoices is lost . The only way to
> match them is by adding them up to correct amounts that are equal to
> the invoices.
>
> For Example :  there were 2 invoices for 80, 210 and you have bills
> for these 50, 10 ,10, 30 , 20, 70, 100 values
>
> One of the possible solution is :
>
> 80=50 + 30
> 210= 10 + 10 +20 + 70 + 100
>
> Other possible solution is
>
> 80=50 + 10 + 20
> 210= 30 +20 + 70 + 100
>
>
> What is the best possible way to get all solutions ? Remember you are
> dealing with big datasets
>
> -Kabir
>
> --
> 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] Google Question Invoice -bills

[Ankush Bagotra]

There are 210 Invoices and 1700 bills – these bills add up to these invoices

The association between  bills and invoices is lost . The only way to
match them is by adding them up to correct amounts that are equal to
the invoices.

For Example :  there were 2 invoices for 80, 210 and you have bills
for these 50, 10 ,10, 30 , 20, 70, 100 values

One of the possible solution is :

80=50 + 30
210= 10 + 10 +20 + 70 + 100

Other possible solution is

80=50 + 10 + 20
210= 30 +20 + 70 + 100


What is the best possible way to get all solutions ? Remember you are
dealing with big datasets

-Kabir

-- 
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] Google written test

[atul anand]

@Gene :  your code will work fine by changing the argument passed from
main(), you just need to call rite  f(n, 1, 1); from main instead of  f(n,
1, 0);

On Mon, Mar 19, 2012 at 10:10 AM, atul anand wrote:

> @all : i guess question is on Fibonacci coding.
>
> here you can find the algo :-
>
> http://en.wikipedia.org/wiki/Fibonacci_coding
>
>
>
>
> On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh wrote:
>
>> @Ravi...  there should be only one answer as for fibonacci representation
>> of a number we have to include the part of the fibonacci number just less
>> than the number then remaining part of the sum is filled by fibonacci
>> numbers starting from 1
>>
>> suppose we have to convert 6 into fibonacci representation
>> then 6 has two sum sets as {1,2,3} or {1,5}
>>
>> then the fibonacci number just less than 6 is 5 so bit representing 5 is
>> set then for completing the sum to 6 bit 1 is also set.
>> so *fibonacci representation of 6 is 1001 .* not 0111
>>
>>
>> ATul Singh | Final Year  | Computer Science & Engineering | NIT
>> Jalandhar  | 9530739855 |
>>
>>  --
>> 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] Google written test

[atul anand]

@all : i guess question is on Fibonacci coding.

here you can find the algo :-

http://en.wikipedia.org/wiki/Fibonacci_coding



On Sun, Mar 18, 2012 at 2:58 AM, Atul Singh  wrote:

> @Ravi...  there should be only one answer as for fibonacci representation
> of a number we have to include the part of the fibonacci number just less
> than the number then remaining part of the sum is filled by fibonacci
> numbers starting from 1
>
> suppose we have to convert 6 into fibonacci representation
> then 6 has two sum sets as {1,2,3} or {1,5}
>
> then the fibonacci number just less than 6 is 5 so bit representing 5 is
> set then for completing the sum to 6 bit 1 is also set.
> so *fibonacci representation of 6 is 1001 .* not 0111
>
>
> ATul Singh | Final Year  | Computer Science & Engineering | NIT Jalandhar
>  | 9530739855 |
>
>  --
> 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] Google written test

[Atul Singh]

@Ravi...  there should be only one answer as for fibonacci representation
of a number we have to include the part of the fibonacci number just less
than the number then remaining part of the sum is filled by fibonacci
numbers starting from 1

suppose we have to convert 6 into fibonacci representation
then 6 has two sum sets as {1,2,3} or {1,5}

then the fibonacci number just less than 6 is 5 so bit representing 5 is
set then for completing the sum to 6 bit 1 is also set.
so *fibonacci representation of 6 is 1001 .* not 0111


ATul Singh | Final Year  | Computer Science & Engineering | NIT
Jalandhar  | 9530739855
|

-- 
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] Google written test

[Ravi Ranjan]

@ if for a given number more than 1 answer exist then whats the answer???

-- 
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] Google written test

[Sourabh Chandak]

20 multiple choice questions out of which around 10 were from the GATE '12
paper.

1 coding question: Represent a no in its Fibonacci representation.

Ex- 15 can be represented as 100010 (1*13+0*8+0*5+0*3+1*2+0*1)

On Sat, Mar 17, 2012 at 6:39 PM, Ronit Douglas wrote:

> Hello!
>
> I got to know that Google visited several colleges in last week. They will
> be visiting my campus on 20th. Please let us know pattern & questions if
> you know.
>
> Thanks,
> - RD
>
> --
> 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.
>



-- 
Sourabh Chandak

-- 
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] Google written test

[Ronit Douglas]

Hello!

I got to know that Google visited several colleges in last week. They will
be visiting my campus on 20th. Please let us know pattern & questions if
you know.

Thanks,
- RD

-- 
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] Google written

[Ronit Douglas]

Hello All!

Google is going to visit my campus soon. Hence, I want to know -

   - Format of the test
   - Qs - in case you remember
   - Coding question in the apti

Please reply if you have information about this.

Thanks :)

-- 
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] google question

[atul anand]

i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup

n=pow(2,h+1) -1;
call(capacity,pour,0,n)

node* fillCup(float capacity,float pour,int left,int right)
{
node *root;
int mid;
if(left > right)
return NULL;

root=(node *)malloc(sizeof(node));
if(left==right)
{
if(pour >=capacity)
root->data=capacity;
else
root->data=pour;
root->left=root->right=NULL;
}
else
{
mid=left+(right-left)/2;
if(pour >= capacity)
{
root->data=capacity;
pour=pour-capacity;
pour=pour/2;
}
else
{
root->data=pour;
root->left=root->right=NULL;
return root;

}
root->left=fillCup(capacity,pour,left,mid-1);
root->right=fillCup(capacity,pour,mid+1,right);

}
return root;

}

On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan wrote:

> |_|
> |_| |_|
> |_| |_| |_|
> |_| |_| |_| |_|
> |_| |_| |_| |_| |_|
>
> Each cup has capacity C and once a cup gets full, it drops half extra
> amount to left child and half extra amount to right child
>
> for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
> will be divided equally to left and right child cup of next level
>
> i.e. C/2 to left child and C/2 to right child
>
> Write a function which takes input parameter as amount of liquid poured at
> top (L) and height of particular cup (h) index of that cup (i) and it
> should return amount of liquid absorbed in that cup.
>
> source
>
> http://www.careercup.com/question?id=12770661
>
>
> whats exactly the qestion???
>
> --
> 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] google question

[Ravi Ranjan]

|_|
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|

Each cup has capacity C and once a cup gets full, it drops half extra
amount to left child and half extra amount to right child

for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
will be divided equally to left and right child cup of next level

i.e. C/2 to left child and C/2 to right child

Write a function which takes input parameter as amount of liquid poured at
top (L) and height of particular cup (h) index of that cup (i) and it
should return amount of liquid absorbed in that cup.

source

http://www.careercup.com/question?id=12770661


whats exactly the qestion???

-- 
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] Google-Puzzle

[Ashish Goel]

max subsum problem
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Sat, Feb 25, 2012 at 1:03 PM, karthikeya s wrote:

> You have a circular track containing fuel pits at irregular intervals.
> The total amount of fuel available from all the pits together is just
> sufficient to travel round the track and finish where you started.
> Given the the circuit perimeter, list of each fuel pit location and
> the amount of fuel they contain, find the optimal start point on the
> track such that you never run out of fuel and complete circuit.
>
> my logic:
> we can use an array having element as
> fuel(in km)-dist to next pit
>
> so now aim is to traverse the array as always having some +ve
> resultant sum.nd plz we cant use here kadane's algo.there are
> cases in which it will not hold here
>
> --
> 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] Google-Puzzle

[karthikeya s]

You have a circular track containing fuel pits at irregular intervals.
The total amount of fuel available from all the pits together is just
sufficient to travel round the track and finish where you started.
Given the the circuit perimeter, list of each fuel pit location and
the amount of fuel they contain, find the optimal start point on the
track such that you never run out of fuel and complete circuit.

my logic:
we can use an array having element as
fuel(in km)-dist to next pit

so now aim is to traverse the array as always having some +ve
resultant sum.nd plz we cant use here kadane's algo.there are
cases in which it will not hold here

-- 
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] Google Question--Suggest Algo

[Piyush Grover]

Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???



On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg  wrote:

> You have an array with *n* elements. The elements are either 0 or 1. You
> want to *split the array into kcontiguous subarrays*. The size of each
> subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
> k << n. After you split the array into k subarrays. One element of each
> subarray will be randomly selected.
>
> Devise an algorithm for maximizing the sum of the randomly selected
> elements from the k subarrays. Basically means that we will want to split
> the array in such way such that the sum of all the expected values for the
> elements selected from each subarray is maximum.
>
> You can assume that n is a power of 2.
>
> Example:
>
> Array: [0,0,1,1,0,0,1,1,0,1,1,0]
> n = 12
> k = 3
> Size of subarrays can be: 2,3,4,5,6
>
> Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
> Expected Value of the sum of the elements randomly selected from the 
> subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
>
> Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
> Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
>
>
> Source ->  
> http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm
>
>  --
> 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] Google Question--Suggest Algo

[Ankur Garg]

You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k << n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.

Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.

You can assume that n is a power of 2.

Example:

Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6

Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433

Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333


Source ->  
http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm

-- 
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] Google interview question

[Nitin Garg]

Hi Guys
I saw this question
http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm
But couldn't get the solution which has been accepted, nor could work out
one on my own.
Please help!

-- 
Nitin Garg

"Personality can open doors, but only Character can keep them open"

-- 
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] Google Question--Suggest Algo

[Ankur Garg]

Can u provide a pseudo code for the same and c if it works


On Thu, Nov 17, 2011 at 2:37 AM, sravanreddy001 wrote:

> Start with counting sort of the input.
> Use shuffling algorithm on it.
>
> Store index as cumulative sums of counts.
>
> --
> 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/-/0Uoq_OqBLn8J.
> 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] Google Question--Suggest Algo

[sravanreddy001]

Start with counting sort of the input.
Use shuffling algorithm on it.

Store index as cumulative sums of counts.

-- 
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/-/0Uoq_OqBLn8J.
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] Google Question--Suggest Algo

[Ankur Garg]

Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.

Input: { a, b, b }, distance = 2
Output: { b, a, b }

How to approach this question ?

-- 
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] Google Interview Question

[Siddhartha Banerjee]

lol!!!

-- 
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] Google Interview Question

[Anup Ghatage]

FFS. here you go: http://lmgtfy.com/?q=google+careers

On Sat, Oct 1, 2011 at 2:09 PM, Deepak Garg  wrote:

> hey can pls share the link.
>
> thnks
>
>
> On Sat, Oct 1, 2011 at 2:04 PM, Rathish Kannan wrote:
>
>> apply through google careers site...
>>
>> --  RK :)
>>
>>
>>
>> On Sat, Oct 1, 2011 at 2:02 PM, Deepak Garg wrote:
>>
>>> hey,,,what is the process of attending google offcampus process.
>>>
>>> kindly let us know..
>>>
>>>
>>> On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan 
>>> wrote:
>>>
 off campus.

 --  RK :)



 On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote:

> Hi
> Are u attending off-campus or on-campus interview?
>
> On 10/1/11, R@TH!$H  wrote:
> > Hi,
> >
> > I am attending Google interview on Monday. Please help me with sample
> > questions.
> >
> > Thanks & Regards,
> > Rathish Kannan
> >
> > --
> > 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.

>>>
>>>
>>>
>>> --
>>> U.D.I.T
>>>
>>> Sent by Nokia OVI (c)
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> U.D.I.T
>
> Sent by Nokia OVI (c)
>
> --
> 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.
>



-- 
Anup Ghatage

-- 
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] Google Interview Question

[Deepak Garg]

hey can pls share the link.

thnks

On Sat, Oct 1, 2011 at 2:04 PM, Rathish Kannan wrote:

> apply through google careers site...
>
> --  RK :)
>
>
>
> On Sat, Oct 1, 2011 at 2:02 PM, Deepak Garg wrote:
>
>> hey,,,what is the process of attending google offcampus process.
>>
>> kindly let us know..
>>
>>
>> On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan 
>> wrote:
>>
>>> off campus.
>>>
>>> --  RK :)
>>>
>>>
>>>
>>> On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote:
>>>
 Hi
 Are u attending off-campus or on-campus interview?

 On 10/1/11, R@TH!$H  wrote:
 > Hi,
 >
 > I am attending Google interview on Monday. Please help me with sample
 > questions.
 >
 > Thanks & Regards,
 > Rathish Kannan
 >
 > --
 > 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.
>>>
>>
>>
>>
>> --
>> U.D.I.T
>>
>> Sent by Nokia OVI (c)
>>
>> --
>> 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.
>



-- 
U.D.I.T

Sent by Nokia OVI (c)

-- 
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] Google Interview Question

[Rathish Kannan]

apply through google careers site...

--  RK :)


On Sat, Oct 1, 2011 at 2:02 PM, Deepak Garg  wrote:

> hey,,,what is the process of attending google offcampus process.
>
> kindly let us know..
>
>
> On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan wrote:
>
>> off campus.
>>
>> --  RK :)
>>
>>
>>
>> On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote:
>>
>>> Hi
>>> Are u attending off-campus or on-campus interview?
>>>
>>> On 10/1/11, R@TH!$H  wrote:
>>> > Hi,
>>> >
>>> > I am attending Google interview on Monday. Please help me with sample
>>> > questions.
>>> >
>>> > Thanks & Regards,
>>> > Rathish Kannan
>>> >
>>> > --
>>> > 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.
>>
>
>
>
> --
> U.D.I.T
>
> Sent by Nokia OVI (c)
>
> --
> 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] Google Interview Question

[Deepak Garg]

hey,,,what is the process of attending google offcampus process.

kindly let us know..

On Sat, Oct 1, 2011 at 1:52 PM, Rathish Kannan wrote:

> off campus.
>
> --  RK :)
>
>
>
> On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar wrote:
>
>> Hi
>> Are u attending off-campus or on-campus interview?
>>
>> On 10/1/11, R@TH!$H  wrote:
>> > Hi,
>> >
>> > I am attending Google interview on Monday. Please help me with sample
>> > questions.
>> >
>> > Thanks & Regards,
>> > Rathish Kannan
>> >
>> > --
>> > 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.
>



-- 
U.D.I.T

Sent by Nokia OVI (c)

-- 
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] Google Interview Question

[Rathish Kannan]

off campus.

--  RK :)


On Sat, Oct 1, 2011 at 11:59 AM, arvind kumar  wrote:

> Hi
> Are u attending off-campus or on-campus interview?
>
> On 10/1/11, R@TH!$H  wrote:
> > Hi,
> >
> > I am attending Google interview on Monday. Please help me with sample
> > questions.
> >
> > Thanks & Regards,
> > Rathish Kannan
> >
> > --
> > 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] Google Interview Question

[arvind kumar]

Hi
Are u attending off-campus or on-campus interview?

On 10/1/11, R@TH!$H  wrote:
> Hi,
>
> I am attending Google interview on Monday. Please help me with sample
> questions.
>
> Thanks & Regards,
> Rathish Kannan
>
> --
> 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] Google Interview Question

[R@TH!$H]

Hi,

I am attending Google interview on Monday. Please help me with sample
questions.

Thanks & Regards,
Rathish Kannan

-- 
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] google os ques on pipelining

[gaurav yadav]

bharatkumar bagan...can u plz explain why u multipiled (160+5) with 999 ?

-- 
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] google os ques on pipelining

[bharatkumar bagana]

for the first instruction : 150+5+120+5+160+5+140=585 ns
for the rest of the instructions , though pipeline
max(150,120,160,140)=160

(160+5)*999=164835 ns
 we assume that there will be no extra stalls existed in our system
-585 + 164835 =165420 ns =165.4 us...
correct me if I'm wrong .

On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh wrote:

> A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
> (nano seconds)
> respectively. Registers that are used between the stages have a delay
> of 5 ns each. Assuming
> constant clocking rate, the total time taken to process 1000 data
> items on this pipeline will
> approximately be
> a. 120 us (micro seconds)
> b. 165 us
> c. 180 us
> d. 175 us
>
> ...plz give detailed explanation for the ans
>
> --
> 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
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*


-- 
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] google os ques on pipelining

[siva viknesh]

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns
(nano seconds)
respectively. Registers that are used between the stages have a delay
of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data
items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us

...plz give detailed explanation for the ans

-- 
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] Google Intern

[arvind kumar]

Hi all
CAn any1 temme d process followed by GOOGLE for internship-off-campus
and on-campus(both)?

-- 
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] google maps

[sukran dhawan]

How do you implement google maps ?

-- 
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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[rahul aravind]

@Abhishek:nice algo dude..

On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav  wrote:

> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise, you
> will ultimately reach a leaf node say 'nd'
> 2.  Now the two candidates for the answer would be
>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
> Now compare the original number with these two and minimum would be the
> answer.
>
> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
> the Inorder traversal of the tree.)
>
> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>
>> why traverse the whole tree?
>>
>> at each root keep the difference in a min_diff and min_ele.
>> if the entered value is less root then move to left or right.
>> repeat above two until whole tree is checked or min_diff becomes 0.
>>
>> pseudo code:
>>
>> min_diff = INF; // global variables
>> min_ele = 0;
>>
>> find_min_diff(node *root, int num)
>> {
>>
>>  if (root == null)
>>  return;
>>
>> // update the difference
>>  if(abs(root->val - num) < min_diff)
>>  {
>>   min_diff = abs(root->val - num);
>>   min_ele = root->val;
>>  }
>>  if ( min_diff == 0)
>>   return; // search is over
>>
>> // proceed to next element in tree which might be closer to the num
>>  if ( num < root-> val)
>>find_min_ele(root->left, num);
>>  else
>>find_min_ele(root->right, num);
>> }
>>
>> ^^ Complexity : O(logn)
>>
>> On 20 August 2011 12:36, Abhishek Yadav wrote:
>>
>>> yes, the interviewer said that there is a solution in O(log n)
>>>
>>>
>>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan 
>>> wrote:
>>>
 ur traversing the tree once so it shud be o(n).does the question demand
 0(logn) ?

 On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> what would be the complexity of your solution O(n) or O(log n)..?
>
>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> traverse bst inorder and each time u encounter a node find the
>> difference between the element and given element in question . if the
>> absolute difference is minimum after traversing the tree that is the 
>> element
>> . u can getback the element using another element which keeps sign of the
>> element so that original element can be obtained from diff
>>
>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Given a BST and a number, Find the closest node to that number in the
>>> BST. Give an algorithm for that.
>>> Let there be binary search tree having nodes with values
>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>>> would be 25 as it is the closest node.
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>>
>> ___
>>
>> Please do n

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[sandeep nagamalli]

1. I think if the given tree is BST then this problem cannot be solved in
o(log n), It can be solved in o(n)
Reason: If the given BST is skewed with numbers inserted in either
ascending/descending order. Now the given number to be searched is the the
one which is the leaf node of a BST, then there could be no algorithm which
can find this in o(logn)

2. So now if we think in terms of  o(n) algorithm:
   As Abhishek,Kunal and Naman said:h
  Traverse as we do to search for the given element in the BST, At the leaf
node there could be 3 possibilities:
  1. if(Given number == leaf node value) then  the given number is returned.
  2. if(Given number < leaf node value) would have been a Inorder successor
of the given element. Inorder predecessor in this should be one of the node
the path that we have traversed so far from the root. So which traversing
keep track of the node, with the minimum difference.
   Now the number to the returned will be decided from:  minimum difference
among 'given value and leaf node(inordersuccesor)' , difference amond the
given value and inorder predecessor.
   3. if(Given number < leaf node value) , this case could be handled
similar to case:2 with appropriate modifications.


Thanks,
-Sandeep.

On Sun, Aug 21, 2011 at 10:49 AM, Abhishek Yadav  wrote:

> @atul yes sure why not...
>
>
> On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor wrote:
>
>> i think there will be three candidate..
>> 1. TreeSuccessor(nd)  2. TreePredecessor(nd) 3. nd it self.
>>
>>
>> On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Hey i tried it now and got to another solution
>>> O(log n) solution:
>>> 1. try searching for the number , if found,return the node, otherwise,
>>> you will ultimately reach a leaf node say 'nd'
>>> 2.  Now the two candidates for the answer would be
>>>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
>>> Now compare the original number with these two and minimum would be the
>>> answer.
>>>
>>> (TreeSuccessor and TreePredecessor are the next and previous node resp.
>>> in the Inorder traversal of the tree.)
>>>
>>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>>>
 why traverse the whole tree?

 at each root keep the difference in a min_diff and min_ele.
 if the entered value is less root then move to left or right.
 repeat above two until whole tree is checked or min_diff becomes 0.

 pseudo code:

 min_diff = INF; // global variables
 min_ele = 0;

 find_min_diff(node *root, int num)
 {

  if (root == null)
  return;

 // update the difference
  if(abs(root->val - num) < min_diff)
  {
   min_diff = abs(root->val - num);
   min_ele = root->val;
  }
  if ( min_diff == 0)
   return; // search is over

 // proceed to next element in tree which might be closer to the num
  if ( num < root-> val)
find_min_ele(root->left, num);
  else
find_min_ele(root->right, num);
 }

 ^^ Complexity : O(logn)

 On 20 August 2011 12:36, Abhishek Yadav wrote:

> yes, the interviewer said that there is a solution in O(log n)
>
>
> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> ur traversing the tree once so it shud be o(n).does the question
>> demand 0(logn) ?
>>
>>  On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> what would be the complexity of your solution O(n) or O(log n)..?
>>>
>>>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
>>> sukrandha...@gmail.com> wrote:
>>>
 traverse bst inorder and each time u encounter a node find the
 difference between the element and given element in question . if the
 absolute difference is minimum after traversing the tree that is the 
 element
 . u can getback the element using another element which keeps sign of 
 the
 element so that original element can be obtained from diff

 On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> Given a BST and a number, Find the closest node to that number in
> the
> BST. Give an algorithm for that.
> Let there be binary search tree having nodes with values
> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
> would be 25 as it is the closest node.
>
> --
> 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

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

@atul yes sure why not...

On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor  wrote:

> i think there will be three candidate..
> 1. TreeSuccessor(nd)  2. TreePredecessor(nd) 3. nd it self.
>
>
> On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> Hey i tried it now and got to another solution
>> O(log n) solution:
>> 1. try searching for the number , if found,return the node, otherwise, you
>> will ultimately reach a leaf node say 'nd'
>> 2.  Now the two candidates for the answer would be
>>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
>> Now compare the original number with these two and minimum would be the
>> answer.
>>
>> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
>> the Inorder traversal of the tree.)
>>
>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>>
>>> why traverse the whole tree?
>>>
>>> at each root keep the difference in a min_diff and min_ele.
>>> if the entered value is less root then move to left or right.
>>> repeat above two until whole tree is checked or min_diff becomes 0.
>>>
>>> pseudo code:
>>>
>>> min_diff = INF; // global variables
>>> min_ele = 0;
>>>
>>> find_min_diff(node *root, int num)
>>> {
>>>
>>>  if (root == null)
>>>  return;
>>>
>>> // update the difference
>>>  if(abs(root->val - num) < min_diff)
>>>  {
>>>   min_diff = abs(root->val - num);
>>>   min_ele = root->val;
>>>  }
>>>  if ( min_diff == 0)
>>>   return; // search is over
>>>
>>> // proceed to next element in tree which might be closer to the num
>>>  if ( num < root-> val)
>>>find_min_ele(root->left, num);
>>>  else
>>>find_min_ele(root->right, num);
>>> }
>>>
>>> ^^ Complexity : O(logn)
>>>
>>> On 20 August 2011 12:36, Abhishek Yadav wrote:
>>>
 yes, the interviewer said that there is a solution in O(log n)


 On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan >>> > wrote:

> ur traversing the tree once so it shud be o(n).does the question demand
> 0(logn) ?
>
>  On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> what would be the complexity of your solution O(n) or O(log n)..?
>>
>>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
>> sukrandha...@gmail.com> wrote:
>>
>>> traverse bst inorder and each time u encounter a node find the
>>> difference between the element and given element in question . if the
>>> absolute difference is minimum after traversing the tree that is the 
>>> element
>>> . u can getback the element using another element which keeps sign of 
>>> the
>>> element so that original element can be obtained from diff
>>>
>>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>>> algowithabhis...@gmail.com> wrote:
>>>
 Given a BST and a number, Find the closest node to that number in
 the
 BST. Give an algorithm for that.
 Let there be binary search tree having nodes with values
 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
 would be 25 as it is the closest node.

 --
 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@googlegrou

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Naman Mahor]

i think there will be three candidate..
1. TreeSuccessor(nd)  2. TreePredecessor(nd) 3. nd it self.


On Sat, Aug 20, 2011 at 12:56 PM, Abhishek Yadav  wrote:

> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise, you
> will ultimately reach a leaf node say 'nd'
> 2.  Now the two candidates for the answer would be
>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
> Now compare the original number with these two and minimum would be the
> answer.
>
> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
> the Inorder traversal of the tree.)
>
> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>
>> why traverse the whole tree?
>>
>> at each root keep the difference in a min_diff and min_ele.
>> if the entered value is less root then move to left or right.
>> repeat above two until whole tree is checked or min_diff becomes 0.
>>
>> pseudo code:
>>
>> min_diff = INF; // global variables
>> min_ele = 0;
>>
>> find_min_diff(node *root, int num)
>> {
>>
>>  if (root == null)
>>  return;
>>
>> // update the difference
>>  if(abs(root->val - num) < min_diff)
>>  {
>>   min_diff = abs(root->val - num);
>>   min_ele = root->val;
>>  }
>>  if ( min_diff == 0)
>>   return; // search is over
>>
>> // proceed to next element in tree which might be closer to the num
>>  if ( num < root-> val)
>>find_min_ele(root->left, num);
>>  else
>>find_min_ele(root->right, num);
>> }
>>
>> ^^ Complexity : O(logn)
>>
>> On 20 August 2011 12:36, Abhishek Yadav wrote:
>>
>>> yes, the interviewer said that there is a solution in O(log n)
>>>
>>>
>>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan 
>>> wrote:
>>>
 ur traversing the tree once so it shud be o(n).does the question demand
 0(logn) ?

  On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> what would be the complexity of your solution O(n) or O(log n)..?
>
>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> traverse bst inorder and each time u encounter a node find the
>> difference between the element and given element in question . if the
>> absolute difference is minimum after traversing the tree that is the 
>> element
>> . u can getback the element using another element which keeps sign of the
>> element so that original element can be obtained from diff
>>
>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Given a BST and a number, Find the closest node to that number in the
>>> BST. Give an algorithm for that.
>>> Let there be binary search tree having nodes with values
>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>>> would be 25 as it is the closest node.
>>>
>>> --
>>> 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Atul Modi]

can any 1 suggest an algo without global vars pls


On Sat, Aug 20, 2011 at 1:29 PM, Abhishek Yadav
wrote:

> yes you are right thanks for correcting me, there would be 3 canditates.
>
>
> On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil  wrote:
>
>> @Abhishek:
>> Its not always that you reach a leaf through the node.
>> But still your logic seems correct.
>> There would be 3 candidates for minimum:
>> -->predecessor
>> -->current node
>> -->successor.
>>
>> On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> No your solution is correct tooits just that in your solution number
>>> of comparisons done with the original number are more, while in my solution
>>> they get down to 2. otherwise complexities of both the solution would be
>>> O(log n).
>>> I am stressing on no. of comparisons because in these kind of questions
>>> where we do compare something no. of comparisons matters.
>>> for example when we talk about finding largest and second largest in an
>>> array, we do try to minimize number of comparisons.
>>>
>>> Otherwise your solution is correct no doubt.
>>>
>>>
>>> On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro wrote:
>>>
 is there anything wrong in my algo?
 do tell me.


 On 20 August 2011 12:56, Abhishek Yadav wrote:

> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise,
> you will ultimately reach a leaf node say 'nd'
> 2.  Now the two candidates for the answer would be
>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
> Now compare the original number with these two and minimum would be the
> answer.
>
> (TreeSuccessor and TreePredecessor are the next and previous node resp.
> in the Inorder traversal of the tree.)
>
> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro 
> wrote:
>
>> why traverse the whole tree?
>>
>> at each root keep the difference in a min_diff and min_ele.
>> if the entered value is less root then move to left or right.
>> repeat above two until whole tree is checked or min_diff becomes 0.
>>
>> pseudo code:
>>
>> min_diff = INF; // global variables
>> min_ele = 0;
>>
>> find_min_diff(node *root, int num)
>> {
>>
>>  if (root == null)
>>  return;
>>
>> // update the difference
>>  if(abs(root->val - num) < min_diff)
>>  {
>>   min_diff = abs(root->val - num);
>>   min_ele = root->val;
>>  }
>>  if ( min_diff == 0)
>>   return; // search is over
>>
>> // proceed to next element in tree which might be closer to the num
>>  if ( num < root-> val)
>>find_min_ele(root->left, num);
>>  else
>>find_min_ele(root->right, num);
>> }
>>
>> ^^ Complexity : O(logn)
>>
>> On 20 August 2011 12:36, Abhishek Yadav 
>> wrote:
>>
>>> yes, the interviewer said that there is a solution in O(log n)
>>>
>>>
>>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan <
>>> sukrandha...@gmail.com> wrote:
>>>
 ur traversing the tree once so it shud be o(n).does the question
 demand 0(logn) ?

 On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> what would be the complexity of your solution O(n) or O(log n)..?
>
>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> traverse bst inorder and each time u encounter a node find the
>> difference between the element and given element in question . if the
>> absolute difference is minimum after traversing the tree that is the 
>> element
>> . u can getback the element using another element which keeps sign 
>> of the
>> element so that original element can be obtained from diff
>>
>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Given a BST and a number, Find the closest node to that number in
>>> the
>>> BST. Give an algorithm for that.
>>> Let there be binary search tree having nodes with values
>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the
>>> answer
>>> would be 25 as it is the closest node.
>>>
>>> --
>>> 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 recei

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

yes you are right thanks for correcting me, there would be 3 canditates.

On Sat, Aug 20, 2011 at 1:28 PM, Kunal Patil  wrote:

> @Abhishek:
> Its not always that you reach a leaf through the node.
> But still your logic seems correct.
> There would be 3 candidates for minimum:
> -->predecessor
> -->current node
> -->successor.
>
> On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> No your solution is correct tooits just that in your solution number
>> of comparisons done with the original number are more, while in my solution
>> they get down to 2. otherwise complexities of both the solution would be
>> O(log n).
>> I am stressing on no. of comparisons because in these kind of questions
>> where we do compare something no. of comparisons matters.
>> for example when we talk about finding largest and second largest in an
>> array, we do try to minimize number of comparisons.
>>
>> Otherwise your solution is correct no doubt.
>>
>>
>> On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro wrote:
>>
>>> is there anything wrong in my algo?
>>> do tell me.
>>>
>>>
>>> On 20 August 2011 12:56, Abhishek Yadav wrote:
>>>
 Hey i tried it now and got to another solution
 O(log n) solution:
 1. try searching for the number , if found,return the node, otherwise,
 you will ultimately reach a leaf node say 'nd'
 2.  Now the two candidates for the answer would be
1. TreeSuccessor(nd)  2. TreePredecessor(nd)
 Now compare the original number with these two and minimum would be the
 answer.

 (TreeSuccessor and TreePredecessor are the next and previous node resp.
 in the Inorder traversal of the tree.)

 On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro 
 wrote:

> why traverse the whole tree?
>
> at each root keep the difference in a min_diff and min_ele.
> if the entered value is less root then move to left or right.
> repeat above two until whole tree is checked or min_diff becomes 0.
>
> pseudo code:
>
> min_diff = INF; // global variables
> min_ele = 0;
>
> find_min_diff(node *root, int num)
> {
>
>  if (root == null)
>  return;
>
> // update the difference
>  if(abs(root->val - num) < min_diff)
>  {
>   min_diff = abs(root->val - num);
>   min_ele = root->val;
>  }
>  if ( min_diff == 0)
>   return; // search is over
>
> // proceed to next element in tree which might be closer to the num
>  if ( num < root-> val)
>find_min_ele(root->left, num);
>  else
>find_min_ele(root->right, num);
> }
>
> ^^ Complexity : O(logn)
>
> On 20 August 2011 12:36, Abhishek Yadav wrote:
>
>> yes, the interviewer said that there is a solution in O(log n)
>>
>>
>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan <
>> sukrandha...@gmail.com> wrote:
>>
>>> ur traversing the tree once so it shud be o(n).does the question
>>> demand 0(logn) ?
>>>
>>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>>> algowithabhis...@gmail.com> wrote:
>>>
 what would be the complexity of your solution O(n) or O(log n)..?

  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
 sukrandha...@gmail.com> wrote:

> traverse bst inorder and each time u encounter a node find the
> difference between the element and given element in question . if the
> absolute difference is minimum after traversing the tree that is the 
> element
> . u can getback the element using another element which keeps sign of 
> the
> element so that original element can be obtained from diff
>
> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> Given a BST and a number, Find the closest node to that number in
>> the
>> BST. Give an algorithm for that.
>> Let there be binary search tree having nodes with values
>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>> would be 25 as it is the closest node.
>>
>> --
>> 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...@goo

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Kunal Patil]

@Abhishek:
Its not always that you reach a leaf through the node.
But still your logic seems correct.
There would be 3 candidates for minimum:
-->predecessor
-->current node
-->successor.

On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav
wrote:

> No your solution is correct tooits just that in your solution number of
> comparisons done with the original number are more, while in my solution
> they get down to 2. otherwise complexities of both the solution would be
> O(log n).
> I am stressing on no. of comparisons because in these kind of questions
> where we do compare something no. of comparisons matters.
> for example when we talk about finding largest and second largest in an
> array, we do try to minimize number of comparisons.
>
> Otherwise your solution is correct no doubt.
>
>
> On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro wrote:
>
>> is there anything wrong in my algo?
>> do tell me.
>>
>>
>> On 20 August 2011 12:56, Abhishek Yadav wrote:
>>
>>> Hey i tried it now and got to another solution
>>> O(log n) solution:
>>> 1. try searching for the number , if found,return the node, otherwise,
>>> you will ultimately reach a leaf node say 'nd'
>>> 2.  Now the two candidates for the answer would be
>>>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
>>> Now compare the original number with these two and minimum would be the
>>> answer.
>>>
>>> (TreeSuccessor and TreePredecessor are the next and previous node resp.
>>> in the Inorder traversal of the tree.)
>>>
>>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>>>
 why traverse the whole tree?

 at each root keep the difference in a min_diff and min_ele.
 if the entered value is less root then move to left or right.
 repeat above two until whole tree is checked or min_diff becomes 0.

 pseudo code:

 min_diff = INF; // global variables
 min_ele = 0;

 find_min_diff(node *root, int num)
 {

  if (root == null)
  return;

 // update the difference
  if(abs(root->val - num) < min_diff)
  {
   min_diff = abs(root->val - num);
   min_ele = root->val;
  }
  if ( min_diff == 0)
   return; // search is over

 // proceed to next element in tree which might be closer to the num
  if ( num < root-> val)
find_min_ele(root->left, num);
  else
find_min_ele(root->right, num);
 }

 ^^ Complexity : O(logn)

 On 20 August 2011 12:36, Abhishek Yadav wrote:

> yes, the interviewer said that there is a solution in O(log n)
>
>
> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> ur traversing the tree once so it shud be o(n).does the question
>> demand 0(logn) ?
>>
>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> what would be the complexity of your solution O(n) or O(log n)..?
>>>
>>>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
>>> sukrandha...@gmail.com> wrote:
>>>
 traverse bst inorder and each time u encounter a node find the
 difference between the element and given element in question . if the
 absolute difference is minimum after traversing the tree that is the 
 element
 . u can getback the element using another element which keeps sign of 
 the
 element so that original element can be obtained from diff

 On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> Given a BST and a number, Find the closest node to that number in
> the
> BST. Give an algorithm for that.
> Let there be binary search tree having nodes with values
> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
> would be 25 as it is the closest node.
>
> --
> 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 t

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

No your solution is correct tooits just that in your solution number of
comparisons done with the original number are more, while in my solution
they get down to 2. otherwise complexities of both the solution would be
O(log n).
I am stressing on no. of comparisons because in these kind of questions
where we do compare something no. of comparisons matters.
for example when we talk about finding largest and second largest in an
array, we do try to minimize number of comparisons.

Otherwise your solution is correct no doubt.

On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro wrote:

> is there anything wrong in my algo?
> do tell me.
>
>
> On 20 August 2011 12:56, Abhishek Yadav wrote:
>
>> Hey i tried it now and got to another solution
>> O(log n) solution:
>> 1. try searching for the number , if found,return the node, otherwise, you
>> will ultimately reach a leaf node say 'nd'
>> 2.  Now the two candidates for the answer would be
>>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
>> Now compare the original number with these two and minimum would be the
>> answer.
>>
>> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
>> the Inorder traversal of the tree.)
>>
>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>>
>>> why traverse the whole tree?
>>>
>>> at each root keep the difference in a min_diff and min_ele.
>>> if the entered value is less root then move to left or right.
>>> repeat above two until whole tree is checked or min_diff becomes 0.
>>>
>>> pseudo code:
>>>
>>> min_diff = INF; // global variables
>>> min_ele = 0;
>>>
>>> find_min_diff(node *root, int num)
>>> {
>>>
>>>  if (root == null)
>>>  return;
>>>
>>> // update the difference
>>>  if(abs(root->val - num) < min_diff)
>>>  {
>>>   min_diff = abs(root->val - num);
>>>   min_ele = root->val;
>>>  }
>>>  if ( min_diff == 0)
>>>   return; // search is over
>>>
>>> // proceed to next element in tree which might be closer to the num
>>>  if ( num < root-> val)
>>>find_min_ele(root->left, num);
>>>  else
>>>find_min_ele(root->right, num);
>>> }
>>>
>>> ^^ Complexity : O(logn)
>>>
>>> On 20 August 2011 12:36, Abhishek Yadav wrote:
>>>
 yes, the interviewer said that there is a solution in O(log n)


 On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan >>> > wrote:

> ur traversing the tree once so it shud be o(n).does the question demand
> 0(logn) ?
>
> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> what would be the complexity of your solution O(n) or O(log n)..?
>>
>>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
>> sukrandha...@gmail.com> wrote:
>>
>>> traverse bst inorder and each time u encounter a node find the
>>> difference between the element and given element in question . if the
>>> absolute difference is minimum after traversing the tree that is the 
>>> element
>>> . u can getback the element using another element which keeps sign of 
>>> the
>>> element so that original element can be obtained from diff
>>>
>>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>>> algowithabhis...@gmail.com> wrote:
>>>
 Given a BST and a number, Find the closest node to that number in
 the
 BST. Give an algorithm for that.
 Let there be binary search tree having nodes with values
 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
 would be 25 as it is the closest node.

 --
 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 algo

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Dipankar Patro]

is there anything wrong in my algo?
do tell me.

On 20 August 2011 12:56, Abhishek Yadav  wrote:

> Hey i tried it now and got to another solution
> O(log n) solution:
> 1. try searching for the number , if found,return the node, otherwise, you
> will ultimately reach a leaf node say 'nd'
> 2.  Now the two candidates for the answer would be
>1. TreeSuccessor(nd)  2. TreePredecessor(nd)
> Now compare the original number with these two and minimum would be the
> answer.
>
> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
> the Inorder traversal of the tree.)
>
> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:
>
>> why traverse the whole tree?
>>
>> at each root keep the difference in a min_diff and min_ele.
>> if the entered value is less root then move to left or right.
>> repeat above two until whole tree is checked or min_diff becomes 0.
>>
>> pseudo code:
>>
>> min_diff = INF; // global variables
>> min_ele = 0;
>>
>> find_min_diff(node *root, int num)
>> {
>>
>>  if (root == null)
>>  return;
>>
>> // update the difference
>>  if(abs(root->val - num) < min_diff)
>>  {
>>   min_diff = abs(root->val - num);
>>   min_ele = root->val;
>>  }
>>  if ( min_diff == 0)
>>   return; // search is over
>>
>> // proceed to next element in tree which might be closer to the num
>>  if ( num < root-> val)
>>find_min_ele(root->left, num);
>>  else
>>find_min_ele(root->right, num);
>> }
>>
>> ^^ Complexity : O(logn)
>>
>> On 20 August 2011 12:36, Abhishek Yadav wrote:
>>
>>> yes, the interviewer said that there is a solution in O(log n)
>>>
>>>
>>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan 
>>> wrote:
>>>
 ur traversing the tree once so it shud be o(n).does the question demand
 0(logn) ?

 On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> what would be the complexity of your solution O(n) or O(log n)..?
>
>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
> sukrandha...@gmail.com> wrote:
>
>> traverse bst inorder and each time u encounter a node find the
>> difference between the element and given element in question . if the
>> absolute difference is minimum after traversing the tree that is the 
>> element
>> . u can getback the element using another element which keeps sign of the
>> element so that original element can be obtained from diff
>>
>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Given a BST and a number, Find the closest node to that number in the
>>> BST. Give an algorithm for that.
>>> Let there be binary search tree having nodes with values
>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>>> would be 25 as it is the closest node.
>>>
>>> --
>>> 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

Hey i tried it now and got to another solution
O(log n) solution:
1. try searching for the number , if found,return the node, otherwise, you
will ultimately reach a leaf node say 'nd'
2.  Now the two candidates for the answer would be
   1. TreeSuccessor(nd)  2. TreePredecessor(nd)
Now compare the original number with these two and minimum would be the
answer.

(TreeSuccessor and TreePredecessor are the next and previous node resp. in
the Inorder traversal of the tree.)

On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro wrote:

> why traverse the whole tree?
>
> at each root keep the difference in a min_diff and min_ele.
> if the entered value is less root then move to left or right.
> repeat above two until whole tree is checked or min_diff becomes 0.
>
> pseudo code:
>
> min_diff = INF; // global variables
> min_ele = 0;
>
> find_min_diff(node *root, int num)
> {
>
>  if (root == null)
>  return;
>
> // update the difference
>  if(abs(root->val - num) < min_diff)
>  {
>   min_diff = abs(root->val - num);
>   min_ele = root->val;
>  }
>  if ( min_diff == 0)
>   return; // search is over
>
> // proceed to next element in tree which might be closer to the num
>  if ( num < root-> val)
>find_min_ele(root->left, num);
>  else
>find_min_ele(root->right, num);
> }
>
> ^^ Complexity : O(logn)
>
> On 20 August 2011 12:36, Abhishek Yadav wrote:
>
>> yes, the interviewer said that there is a solution in O(log n)
>>
>>
>> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan 
>> wrote:
>>
>>> ur traversing the tree once so it shud be o(n).does the question demand
>>> 0(logn) ?
>>>
>>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>>> algowithabhis...@gmail.com> wrote:
>>>
 what would be the complexity of your solution O(n) or O(log n)..?

  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <
 sukrandha...@gmail.com> wrote:

> traverse bst inorder and each time u encounter a node find the
> difference between the element and given element in question . if the
> absolute difference is minimum after traversing the tree that is the 
> element
> . u can getback the element using another element which keeps sign of the
> element so that original element can be obtained from diff
>
> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> Given a BST and a number, Find the closest node to that number in the
>> BST. Give an algorithm for that.
>> Let there be binary search tree having nodes with values
>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>> would be 25 as it is the closest node.
>>
>> --
>> 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.
>>
>
>
>
> --
>
> ___
>
> Please do not print this e-mail until urgent requirement. Go Green!!
> Save Papers <=> Save Trees
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to al

Re: [algogeeks] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Dipankar Patro]

why traverse the whole tree?

at each root keep the difference in a min_diff and min_ele.
if the entered value is less root then move to left or right.
repeat above two until whole tree is checked or min_diff becomes 0.

pseudo code:

min_diff = INF; // global variables
min_ele = 0;

find_min_diff(node *root, int num)
{

 if (root == null)
 return;

// update the difference
 if(abs(root->val - num) < min_diff)
 {
  min_diff = abs(root->val - num);
  min_ele = root->val;
 }
 if ( min_diff == 0)
  return; // search is over

// proceed to next element in tree which might be closer to the num
 if ( num < root-> val)
   find_min_ele(root->left, num);
 else
   find_min_ele(root->right, num);
}

^^ Complexity : O(logn)

On 20 August 2011 12:36, Abhishek Yadav  wrote:

> yes, the interviewer said that there is a solution in O(log n)
>
>
> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan wrote:
>
>> ur traversing the tree once so it shud be o(n).does the question demand
>> 0(logn) ?
>>
>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> what would be the complexity of your solution O(n) or O(log n)..?
>>>
>>>  On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan >> > wrote:
>>>
 traverse bst inorder and each time u encounter a node find the
 difference between the element and given element in question . if the
 absolute difference is minimum after traversing the tree that is the 
 element
 . u can getback the element using another element which keeps sign of the
 element so that original element can be obtained from diff

 On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
 algowithabhis...@gmail.com> wrote:

> Given a BST and a number, Find the closest node to that number in the
> BST. Give an algorithm for that.
> Let there be binary search tree having nodes with values
> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
> would be 25 as it is the closest node.
>
> --
> 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.
>



-- 
___

Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees

-- 
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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

yes, the interviewer said that there is a solution in O(log n)

On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan wrote:

> ur traversing the tree once so it shud be o(n).does the question demand
> 0(logn) ?
>
> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> what would be the complexity of your solution O(n) or O(log n)..?
>>
>> On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan 
>> wrote:
>>
>>> traverse bst inorder and each time u encounter a node find the difference
>>> between the element and given element in question . if the absolute
>>> difference is minimum after traversing the tree that is the element . u can
>>> getback the element using another element which keeps sign of the element so
>>> that original element can be obtained from diff
>>>
>>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>>> algowithabhis...@gmail.com> wrote:
>>>
 Given a BST and a number, Find the closest node to that number in the
 BST. Give an algorithm for that.
 Let there be binary search tree having nodes with values
 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
 would be 25 as it is the closest node.

 --
 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[sukran dhawan]

ur traversing the tree once so it shud be o(n).does the question demand
0(logn) ?

On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav  wrote:

> what would be the complexity of your solution O(n) or O(log n)..?
>
> On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote:
>
>> traverse bst inorder and each time u encounter a node find the difference
>> between the element and given element in question . if the absolute
>> difference is minimum after traversing the tree that is the element . u can
>> getback the element using another element which keeps sign of the element so
>> that original element can be obtained from diff
>>
>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>> algowithabhis...@gmail.com> wrote:
>>
>>> Given a BST and a number, Find the closest node to that number in the
>>> BST. Give an algorithm for that.
>>> Let there be binary search tree having nodes with values
>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>>> would be 25 as it is the closest node.
>>>
>>> --
>>> 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

what would be the complexity of your solution O(n) or O(log n)..?

On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan wrote:

> traverse bst inorder and each time u encounter a node find the difference
> between the element and given element in question . if the absolute
> difference is minimum after traversing the tree that is the element . u can
> getback the element using another element which keeps sign of the element so
> that original element can be obtained from diff
>
> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
> algowithabhis...@gmail.com> wrote:
>
>> Given a BST and a number, Find the closest node to that number in the
>> BST. Give an algorithm for that.
>> Let there be binary search tree having nodes with values
>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>> would be 25 as it is the closest node.
>>
>> --
>> 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[sukran dhawan]

traverse bst inorder and each time u encounter a node find the difference
between the element and given element in question . if the absolute
difference is minimum after traversing the tree that is the element . u can
getback the element using another element which keeps sign of the element so
that original element can be obtained from diff

On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav  wrote:

> Given a BST and a number, Find the closest node to that number in the
> BST. Give an algorithm for that.
> Let there be binary search tree having nodes with values
> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
> would be 25 as it is the closest node.
>
> --
> 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] Google Question:Given a BST and a number, Find the closest node to that number in the BST.

[Abhishek Yadav]

Given a BST and a number, Find the closest node to that number in the
BST. Give an algorithm for that.
Let there be binary search tree having nodes with values
12,34,64,23,64,25,76,6 and the number given is 28, then the answer
would be 25 as it is the closest node.

-- 
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] Google Telephonic interview

[surender sanke]

@Anand Shastri, if tasks enter randomly in runtime,
structure needs to add a member start_time, which will be different from
reference_time (till now u been considering it as same start time of every
task). finally GOOD work!!

surender

On Fri, Aug 5, 2011 at 9:42 AM, Gaurav Menghani
wrote:

> Then that has to be mentioned in the question. Premature optimization
> is the root of all evil, in the words of Don Knuth.
>
> On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri 
> wrote:
> > what if new task gets added every time.
> >
> > On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani <
> gaurav.mengh...@gmail.com>
> > wrote:
> >>
> >> Instead of a heap, sort the array once. Pick the first element every
> >> time, and remove it from the array, or just move the 'head pointer'
> >> ahead.
> >>
> >> On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri <
> anand.shastr...@gmail.com>
> >> wrote:
> >> > /* Create a Timer Task that takes in the running time and it's
> >> > associated
> >> >function to be called after its running time is elapsed */
> >> > #include 
> >> >
> >> > #define NUM 5
> >> > typedef void (*funcToBeCalled)(void);
> >> >
> >> > typedef struct timer TIMER;
> >> >
> >> > struct timer
> >> > {
> >> >   int runningTime;
> >> >   funcToBeCalled func;
> >> > };
> >> >
> >> > static TIMER timerArray[NUM];
> >> > static time_t reference;
> >> > static int count;
> >> >
> >> > int LEFT(int index)
> >> > {
> >> >   if(index < NUM)
> >> >  return (index * 2 + 1);
> >> > }
> >> > int RIGHT(int index)
> >> > {
> >> >   if(index < NUM)
> >> >  return (index * 2 + 2);
> >> > }
> >> > static void print(void)
> >> > {
> >> >printf("Timer task has been called\n");
> >> > }
> >> >
> >> > // Initialise the timer data structure
> >> > void Init()
> >> > {
> >> >int index;
> >> >count = NUM;
> >> >// Note down the reference time
> >> >reference = time(0);
> >> >printf("reference : %ld\n", reference);
> >> >
> >> >// Initialise the data structure such that associate function gets
> >> >// called after 3, 6, 9, 12, 15 seconds respectively.
> >> >for(index = 0; index < count; index++)
> >> >{
> >> >   timerArray[index].runningTime = (index + 1) * 3;
> >> >   timerArray[index].func = print;
> >> >}
> >> > }
> >> >
> >> > // This function check the min heap property and arrange
> >> > // the element such that at every node, root node should be
> >> > // less than its right and left child element.
> >> > Heapify(int index)
> >> > {
> >> >   int left, right, minIndex;
> >> >   TIMER temp;
> >> >   left = LEFT(index);
> >> >   right = RIGHT(index);
> >> >   if(left < (count) &&
> >> > (timerArray[left].runningTime < timerArray[index].runningTime))
> >> >   {
> >> >  minIndex = left;
> >> >   }
> >> >   else
> >> >   {
> >> >  minIndex = index;
> >> >   }
> >> >   if(right < (count) &&
> >> > (timerArray[right].runningTime <
> timerArray[minIndex].runningTime))
> >> >   {
> >> >  minIndex = right;
> >> >   }
> >> >   if(minIndex != index)
> >> >   {
> >> > temp.runningTime = timerArray[index].runningTime;
> >> > temp.func = timerArray[index].func;
> >> >
> >> > timerArray[index].runningTime = timerArray[minIndex].runningTime;
> >> > timerArray[index].func = timerArray[minIndex].func;
> >> >
> >> > timerArray[minIndex].runningTime = temp.runningTime;
> >> > timerArray[minIndex].func   = temp.func;
> >> >
> >> > Heapify(minIndex);
> >> >   }
> >> > }
> >> >
> >> > // This function builds the MIN heap data structure
> >> > void BuildHeap()
> >> > {
> >> >   int len, i;
> >> >   len = sizeof(timerArray)/sizeof(timerArray[0]);
> >> >   i = (len - 1)/2;
> >> >   while(i >= 0)
> >> >   {
> >> > Heapify(i);
> >> > i--;
> >> >   }
> >> >   Heapify(0);
> >> > }
> >> >
> >> >
> >> > // This function extract the top element of the heap
> >> > // Min heap has the min  element at the top always.
> >> > int HeapExtract()
> >> > {
> >> >   TIMER temp;
> >> >   // Swap the 0 the element with last element of the array
> >> >   temp.runningTime = timerArray[0].runningTime;
> >> >   temp.func = timerArray[0].func;
> >> >
> >> >   timerArray[0].runningTime = timerArray[count-1].runningTime;
> >> >   timerArray[0].func = timerArray[count-1].func;
> >> >
> >> >   timerArray[count-1].runningTime = temp.runningTime;
> >> >   timerArray[count-1].func = temp.func;
> >> >   count--;
> >> >   // Check the heap property heapify if it got violated
> >> >   Heapify(0);
> >> >   // return the minimum element of the heap
> >> >   return (count);
> >> > }
> >> > void scheduler()
> >> > {
> >> >   time_t now;
> >> >   int diff_time, minIndex;
> >> >   while(count >= 0)
> >> >   {
> >> >  now = time(0);
> >> >  printf("Current Time: %ld\n", time(0));
> >> >  diff_time = now- reference;
> >> >  printf("diff_time : %ld\n", diff_time);
> >> >  if(diff_time >= timerArray[0].runningTime)
> >> >  {
> >> >minIndex  = HeapExtract();
> 

Re: [algogeeks] Google Telephonic interview

[Gaurav Menghani]

Then that has to be mentioned in the question. Premature optimization
is the root of all evil, in the words of Don Knuth.

On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri  wrote:
> what if new task gets added every time.
>
> On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani 
> wrote:
>>
>> Instead of a heap, sort the array once. Pick the first element every
>> time, and remove it from the array, or just move the 'head pointer'
>> ahead.
>>
>> On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri 
>> wrote:
>> > /* Create a Timer Task that takes in the running time and it's
>> > associated
>> >    function to be called after its running time is elapsed */
>> > #include 
>> >
>> > #define NUM 5
>> > typedef void (*funcToBeCalled)(void);
>> >
>> > typedef struct timer TIMER;
>> >
>> > struct timer
>> > {
>> >   int runningTime;
>> >   funcToBeCalled func;
>> > };
>> >
>> > static TIMER timerArray[NUM];
>> > static time_t reference;
>> > static int count;
>> >
>> > int LEFT(int index)
>> > {
>> >   if(index < NUM)
>> >  return (index * 2 + 1);
>> > }
>> > int RIGHT(int index)
>> > {
>> >   if(index < NUM)
>> >  return (index * 2 + 2);
>> > }
>> > static void print(void)
>> > {
>> >    printf("Timer task has been called\n");
>> > }
>> >
>> > // Initialise the timer data structure
>> > void Init()
>> > {
>> >    int index;
>> >    count = NUM;
>> >    // Note down the reference time
>> >    reference = time(0);
>> >    printf("reference : %ld\n", reference);
>> >
>> >    // Initialise the data structure such that associate function gets
>> >    // called after 3, 6, 9, 12, 15 seconds respectively.
>> >    for(index = 0; index < count; index++)
>> >    {
>> >   timerArray[index].runningTime = (index + 1) * 3;
>> >   timerArray[index].func = print;
>> >    }
>> > }
>> >
>> > // This function check the min heap property and arrange
>> > // the element such that at every node, root node should be
>> > // less than its right and left child element.
>> > Heapify(int index)
>> > {
>> >   int left, right, minIndex;
>> >   TIMER temp;
>> >   left = LEFT(index);
>> >   right = RIGHT(index);
>> >   if(left < (count) &&
>> >     (timerArray[left].runningTime < timerArray[index].runningTime))
>> >   {
>> >  minIndex = left;
>> >   }
>> >   else
>> >   {
>> >  minIndex = index;
>> >   }
>> >   if(right < (count) &&
>> >     (timerArray[right].runningTime < timerArray[minIndex].runningTime))
>> >   {
>> >  minIndex = right;
>> >   }
>> >   if(minIndex != index)
>> >   {
>> >     temp.runningTime = timerArray[index].runningTime;
>> >     temp.func = timerArray[index].func;
>> >
>> >     timerArray[index].runningTime = timerArray[minIndex].runningTime;
>> >     timerArray[index].func = timerArray[minIndex].func;
>> >
>> >     timerArray[minIndex].runningTime = temp.runningTime;
>> >     timerArray[minIndex].func   = temp.func;
>> >
>> >     Heapify(minIndex);
>> >   }
>> > }
>> >
>> > // This function builds the MIN heap data structure
>> > void BuildHeap()
>> > {
>> >   int len, i;
>> >   len = sizeof(timerArray)/sizeof(timerArray[0]);
>> >   i = (len - 1)/2;
>> >   while(i >= 0)
>> >   {
>> >     Heapify(i);
>> >     i--;
>> >   }
>> >   Heapify(0);
>> > }
>> >
>> >
>> > // This function extract the top element of the heap
>> > // Min heap has the min  element at the top always.
>> > int HeapExtract()
>> > {
>> >   TIMER temp;
>> >   // Swap the 0 the element with last element of the array
>> >   temp.runningTime = timerArray[0].runningTime;
>> >   temp.func = timerArray[0].func;
>> >
>> >   timerArray[0].runningTime = timerArray[count-1].runningTime;
>> >   timerArray[0].func = timerArray[count-1].func;
>> >
>> >   timerArray[count-1].runningTime = temp.runningTime;
>> >   timerArray[count-1].func = temp.func;
>> >   count--;
>> >   // Check the heap property heapify if it got violated
>> >   Heapify(0);
>> >   // return the minimum element of the heap
>> >   return (count);
>> > }
>> > void scheduler()
>> > {
>> >   time_t now;
>> >   int diff_time, minIndex;
>> >   while(count >= 0)
>> >   {
>> >  now = time(0);
>> >  printf("Current Time: %ld\n", time(0));
>> >  diff_time = now- reference;
>> >  printf("diff_time : %ld\n", diff_time);
>> >  if(diff_time >= timerArray[0].runningTime)
>> >  {
>> >    minIndex  = HeapExtract();
>> >    timerArray[minIndex].func();
>> >  }
>> >  else
>> >  {
>> >     sleep(timerArray[0].runningTime - diff_time);
>> >  }
>> >   }
>> > }
>> > main()
>> > {
>> >   int index, minIndex;
>> >   TIMER temp;
>> >
>> >   // Initialise the data structure
>> >   Init();
>> >
>> >   // Build MIn heap data structure
>> >   BuildHeap(timerArray);
>> >
>> >   // Run the scheduler
>> >   scheduler();
>> >
>> >    return;
>> > }
>> > The ouput of above code is
>> >
>> > Timer Task is about to run
>> > reference : 1312510772
>> >
>> > Current Time: 1312510775
>> > diff_time : 3
>> > Timer task has been called
>> >
>> > Current Time: 1312510778

Re: [algogeeks] Google Telephonic interview

[Anand Shastri]

what if new task gets added every time.

On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani
wrote:

> Instead of a heap, sort the array once. Pick the first element every
> time, and remove it from the array, or just move the 'head pointer'
> ahead.
>
> On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri 
> wrote:
> > /* Create a Timer Task that takes in the running time and it's associated
> >function to be called after its running time is elapsed */
> > #include 
> >
> > #define NUM 5
> > typedef void (*funcToBeCalled)(void);
> >
> > typedef struct timer TIMER;
> >
> > struct timer
> > {
> >   int runningTime;
> >   funcToBeCalled func;
> > };
> >
> > static TIMER timerArray[NUM];
> > static time_t reference;
> > static int count;
> >
> > int LEFT(int index)
> > {
> >   if(index < NUM)
> >  return (index * 2 + 1);
> > }
> > int RIGHT(int index)
> > {
> >   if(index < NUM)
> >  return (index * 2 + 2);
> > }
> > static void print(void)
> > {
> >printf("Timer task has been called\n");
> > }
> >
> > // Initialise the timer data structure
> > void Init()
> > {
> >int index;
> >count = NUM;
> >// Note down the reference time
> >reference = time(0);
> >printf("reference : %ld\n", reference);
> >
> >// Initialise the data structure such that associate function gets
> >// called after 3, 6, 9, 12, 15 seconds respectively.
> >for(index = 0; index < count; index++)
> >{
> >   timerArray[index].runningTime = (index + 1) * 3;
> >   timerArray[index].func = print;
> >}
> > }
> >
> > // This function check the min heap property and arrange
> > // the element such that at every node, root node should be
> > // less than its right and left child element.
> > Heapify(int index)
> > {
> >   int left, right, minIndex;
> >   TIMER temp;
> >   left = LEFT(index);
> >   right = RIGHT(index);
> >   if(left < (count) &&
> > (timerArray[left].runningTime < timerArray[index].runningTime))
> >   {
> >  minIndex = left;
> >   }
> >   else
> >   {
> >  minIndex = index;
> >   }
> >   if(right < (count) &&
> > (timerArray[right].runningTime < timerArray[minIndex].runningTime))
> >   {
> >  minIndex = right;
> >   }
> >   if(minIndex != index)
> >   {
> > temp.runningTime = timerArray[index].runningTime;
> > temp.func = timerArray[index].func;
> >
> > timerArray[index].runningTime = timerArray[minIndex].runningTime;
> > timerArray[index].func = timerArray[minIndex].func;
> >
> > timerArray[minIndex].runningTime = temp.runningTime;
> > timerArray[minIndex].func   = temp.func;
> >
> > Heapify(minIndex);
> >   }
> > }
> >
> > // This function builds the MIN heap data structure
> > void BuildHeap()
> > {
> >   int len, i;
> >   len = sizeof(timerArray)/sizeof(timerArray[0]);
> >   i = (len - 1)/2;
> >   while(i >= 0)
> >   {
> > Heapify(i);
> > i--;
> >   }
> >   Heapify(0);
> > }
> >
> >
> > // This function extract the top element of the heap
> > // Min heap has the min  element at the top always.
> > int HeapExtract()
> > {
> >   TIMER temp;
> >   // Swap the 0 the element with last element of the array
> >   temp.runningTime = timerArray[0].runningTime;
> >   temp.func = timerArray[0].func;
> >
> >   timerArray[0].runningTime = timerArray[count-1].runningTime;
> >   timerArray[0].func = timerArray[count-1].func;
> >
> >   timerArray[count-1].runningTime = temp.runningTime;
> >   timerArray[count-1].func = temp.func;
> >   count--;
> >   // Check the heap property heapify if it got violated
> >   Heapify(0);
> >   // return the minimum element of the heap
> >   return (count);
> > }
> > void scheduler()
> > {
> >   time_t now;
> >   int diff_time, minIndex;
> >   while(count >= 0)
> >   {
> >  now = time(0);
> >  printf("Current Time: %ld\n", time(0));
> >  diff_time = now- reference;
> >  printf("diff_time : %ld\n", diff_time);
> >  if(diff_time >= timerArray[0].runningTime)
> >  {
> >minIndex  = HeapExtract();
> >timerArray[minIndex].func();
> >  }
> >  else
> >  {
> > sleep(timerArray[0].runningTime - diff_time);
> >  }
> >   }
> > }
> > main()
> > {
> >   int index, minIndex;
> >   TIMER temp;
> >
> >   // Initialise the data structure
> >   Init();
> >
> >   // Build MIn heap data structure
> >   BuildHeap(timerArray);
> >
> >   // Run the scheduler
> >   scheduler();
> >
> >return;
> > }
> > The ouput of above code is
> >
> > Timer Task is about to run
> > reference : 1312510772
> >
> > Current Time: 1312510775
> > diff_time : 3
> > Timer task has been called
> >
> > Current Time: 1312510778
> > diff_time : 6
> > Timer task has been called
> > Current Time: 1312510781
> > diff_time : 9
> > Timer task has been called
> >
> > Current Time: 1312510784
> > diff_time : 12
> > Timer task has been called
> >
> > Current Time: 1312510787
> > diff_time : 15
> > Timer task has been called
> >
> > Please share your comments
> >
> > On Thu, Aug 4, 2011 at 11:43 AM, A

Re: [algogeeks] Google Telephonic interview

[Gaurav Menghani]

Instead of a heap, sort the array once. Pick the first element every
time, and remove it from the array, or just move the 'head pointer'
ahead.

On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri  wrote:
> /* Create a Timer Task that takes in the running time and it's associated
>    function to be called after its running time is elapsed */
> #include 
>
> #define NUM 5
> typedef void (*funcToBeCalled)(void);
>
> typedef struct timer TIMER;
>
> struct timer
> {
>   int runningTime;
>   funcToBeCalled func;
> };
>
> static TIMER timerArray[NUM];
> static time_t reference;
> static int count;
>
> int LEFT(int index)
> {
>   if(index < NUM)
>  return (index * 2 + 1);
> }
> int RIGHT(int index)
> {
>   if(index < NUM)
>  return (index * 2 + 2);
> }
> static void print(void)
> {
>    printf("Timer task has been called\n");
> }
>
> // Initialise the timer data structure
> void Init()
> {
>    int index;
>    count = NUM;
>    // Note down the reference time
>    reference = time(0);
>    printf("reference : %ld\n", reference);
>
>    // Initialise the data structure such that associate function gets
>    // called after 3, 6, 9, 12, 15 seconds respectively.
>    for(index = 0; index < count; index++)
>    {
>   timerArray[index].runningTime = (index + 1) * 3;
>   timerArray[index].func = print;
>    }
> }
>
> // This function check the min heap property and arrange
> // the element such that at every node, root node should be
> // less than its right and left child element.
> Heapify(int index)
> {
>   int left, right, minIndex;
>   TIMER temp;
>   left = LEFT(index);
>   right = RIGHT(index);
>   if(left < (count) &&
>     (timerArray[left].runningTime < timerArray[index].runningTime))
>   {
>  minIndex = left;
>   }
>   else
>   {
>  minIndex = index;
>   }
>   if(right < (count) &&
>     (timerArray[right].runningTime < timerArray[minIndex].runningTime))
>   {
>  minIndex = right;
>   }
>   if(minIndex != index)
>   {
>     temp.runningTime = timerArray[index].runningTime;
>     temp.func = timerArray[index].func;
>
>     timerArray[index].runningTime = timerArray[minIndex].runningTime;
>     timerArray[index].func = timerArray[minIndex].func;
>
>     timerArray[minIndex].runningTime = temp.runningTime;
>     timerArray[minIndex].func   = temp.func;
>
>     Heapify(minIndex);
>   }
> }
>
> // This function builds the MIN heap data structure
> void BuildHeap()
> {
>   int len, i;
>   len = sizeof(timerArray)/sizeof(timerArray[0]);
>   i = (len - 1)/2;
>   while(i >= 0)
>   {
>     Heapify(i);
>     i--;
>   }
>   Heapify(0);
> }
>
>
> // This function extract the top element of the heap
> // Min heap has the min  element at the top always.
> int HeapExtract()
> {
>   TIMER temp;
>   // Swap the 0 the element with last element of the array
>   temp.runningTime = timerArray[0].runningTime;
>   temp.func = timerArray[0].func;
>
>   timerArray[0].runningTime = timerArray[count-1].runningTime;
>   timerArray[0].func = timerArray[count-1].func;
>
>   timerArray[count-1].runningTime = temp.runningTime;
>   timerArray[count-1].func = temp.func;
>   count--;
>   // Check the heap property heapify if it got violated
>   Heapify(0);
>   // return the minimum element of the heap
>   return (count);
> }
> void scheduler()
> {
>   time_t now;
>   int diff_time, minIndex;
>   while(count >= 0)
>   {
>  now = time(0);
>  printf("Current Time: %ld\n", time(0));
>  diff_time = now- reference;
>  printf("diff_time : %ld\n", diff_time);
>  if(diff_time >= timerArray[0].runningTime)
>  {
>    minIndex  = HeapExtract();
>    timerArray[minIndex].func();
>  }
>  else
>  {
>     sleep(timerArray[0].runningTime - diff_time);
>  }
>   }
> }
> main()
> {
>   int index, minIndex;
>   TIMER temp;
>
>   // Initialise the data structure
>   Init();
>
>   // Build MIn heap data structure
>   BuildHeap(timerArray);
>
>   // Run the scheduler
>   scheduler();
>
>    return;
> }
> The ouput of above code is
>
> Timer Task is about to run
> reference : 1312510772
>
> Current Time: 1312510775
> diff_time : 3
> Timer task has been called
>
> Current Time: 1312510778
> diff_time : 6
> Timer task has been called
> Current Time: 1312510781
> diff_time : 9
> Timer task has been called
>
> Current Time: 1312510784
> diff_time : 12
> Timer task has been called
>
> Current Time: 1312510787
> diff_time : 15
> Timer task has been called
>
> Please share your comments
>
> On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri 
> wrote:
>>
>> Obviously you need to run the task that a closet running time.
>>
>> For Example
>>
>> Task 1 : running time = 2 secs
>>
>> Task 2: running time = 4 secs
>>
>> This means I want to run the task 1 after 2 secs and task 2 after 4
>> second.
>>
>> How I hope the question is clear to you know
>>
>> On Thu, Aug 4, 2011 at 11:37 AM, mohit verma 
>> wrote:
>>>
>>> there is nothing like "search min or max time and then call function"
>>> given . It can be the c

Re: [algogeeks] Google Telephonic interview

[Anand Shastri]

/* Create a Timer Task that takes in the running time and it's associated
   function to be called after its running time is elapsed */
#include 

#define NUM 5
typedef void (*funcToBeCalled)(void);

typedef struct timer TIMER;

struct timer
{
  int runningTime;
  funcToBeCalled func;
};
static TIMER timerArray[NUM];
static time_t reference;
static int count;

int LEFT(int index)
{
  if(index < NUM)
 return (index * 2 + 1);
}
int RIGHT(int index)
{
  if(index < NUM)
 return (index * 2 + 2);
}
static void print(void)
{
   printf("Timer task has been called\n");
}

// Initialise the timer data structure
void Init()
{
   int index;

   count = NUM;
   // Note down the reference time
   reference = time(0);
   printf("reference : %ld\n", reference);

   // Initialise the data structure such that associate function gets
   // called after 3, 6, 9, 12, 15 seconds respectively.
   for(index = 0; index < count; index++)
   {
  timerArray[index].runningTime = (index + 1) * 3;
  timerArray[index].func = print;
   }
}

// This function check the min heap property and arrange
// the element such that at every node, root node should be
// less than its right and left child element.
Heapify(int index)
{
  int left, right, minIndex;
  TIMER temp;
  left = LEFT(index);
  right = RIGHT(index);
  if(left < (count) &&
(timerArray[left].runningTime < timerArray[index].runningTime))
  {
 minIndex = left;
  }
  else
  {
 minIndex = index;
  }
  if(right < (count) &&
(timerArray[right].runningTime < timerArray[minIndex].runningTime))
  {
 minIndex = right;
  }
  if(minIndex != index)
  {
temp.runningTime = timerArray[index].runningTime;
temp.func = timerArray[index].func;

timerArray[index].runningTime = timerArray[minIndex].runningTime;
timerArray[index].func = timerArray[minIndex].func;

timerArray[minIndex].runningTime = temp.runningTime;
timerArray[minIndex].func   = temp.func;

Heapify(minIndex);
  }
}

// This function builds the MIN heap data structure
void BuildHeap()
{
  int len, i;
  len = sizeof(timerArray)/sizeof(timerArray[0]);
  i = (len - 1)/2;
  while(i >= 0)
  {
Heapify(i);
i--;
  }
  Heapify(0);
}


// This function extract the top element of the heap
// Min heap has the min  element at the top always.
int HeapExtract()
{
  TIMER temp;
  // Swap the 0 the element with last element of the array
  temp.runningTime = timerArray[0].runningTime;
  temp.func = timerArray[0].func;

  timerArray[0].runningTime = timerArray[count-1].runningTime;
  timerArray[0].func = timerArray[count-1].func;

  timerArray[count-1].runningTime = temp.runningTime;
  timerArray[count-1].func = temp.func;

  count--;

  // Check the heap property heapify if it got violated
  Heapify(0);
  // return the minimum element of the heap
  return (count);
}
void scheduler()
{
  time_t now;
  int diff_time, minIndex;
  while(count >= 0)
  {
 now = time(0);
 printf("Current Time: %ld\n", time(0));
 diff_time = now- reference;
 printf("diff_time : %ld\n", diff_time);
 if(diff_time >= timerArray[0].runningTime)
 {
   minIndex  = HeapExtract();
   timerArray[minIndex].func();
 }
 else
 {
sleep(timerArray[0].runningTime - diff_time);
 }
  }
}
main()
{
  int index, minIndex;
  TIMER temp;

  // Initialise the data structure
  Init();

  // Build MIn heap data structure
  BuildHeap(timerArray);

  // Run the scheduler
  scheduler();

   return;
}
The ouput of above code is

Timer Task is about to run
reference : 1312510772


Current Time: 1312510775
diff_time : 3
Timer task has been called

Current Time: 1312510778
diff_time : 6
Timer task has been called

Current Time: 1312510781
diff_time : 9
Timer task has been called

Current Time: 1312510784
diff_time : 12
Timer task has been called

Current Time: 1312510787
diff_time : 15
Timer task has been called

Please share your comments

On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri wrote:

> Obviously you need to run the task that a closet running time.
>
> For Example
>
> Task 1 : running time = 2 secs
>
> Task 2: running time = 4 secs
>
> This means I want to run the task 1 after 2 secs and task 2 after 4 second.
>
> How I hope the question is clear to you know
>
>   On Thu, Aug 4, 2011 at 11:37 AM, mohit verma wrote:
>
>> there is nothing like "search min or max time and then call function"
>> given . It can be the case: "call the functions in order of nodes or times
>> saved in objects". M i wrong?
>>
>>
>> On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri > > wrote:
>>
>>> You mean to say linked to maintain all time task with its corresponding
>>> running time and associate function. In that case how will find the task
>>> which has the closed running time.
>>>
>>> If you use min heap it would be easy to find the task that has closest
>>> runing time in O(1) complexity.
>>>
>>>   On Thu, Aug 4, 2011 at 10:57 AM, mohit verma wrote:
>>>
 why are u maintaining heap? can't we use

Re: [algogeeks] Google Telephonic interview

[Anand Shastri]

Obviously you need to run the task that a closet running time.

For Example

Task 1 : running time = 2 secs

Task 2: running time = 4 secs

This means I want to run the task 1 after 2 secs and task 2 after 4 second.

How I hope the question is clear to you know

On Thu, Aug 4, 2011 at 11:37 AM, mohit verma  wrote:

> there is nothing like "search min or max time and then call function" given
> . It can be the case: "call the functions in order of nodes or times saved
> in objects". M i wrong?
>
>
> On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri 
> wrote:
>
>> You mean to say linked to maintain all time task with its corresponding
>> running time and associate function. In that case how will find the task
>> which has the closed running time.
>>
>> If you use min heap it would be easy to find the task that has closest
>> runing time in O(1) complexity.
>>
>>   On Thu, Aug 4, 2011 at 10:57 AM, mohit verma wrote:
>>
>>> why are u maintaining heap? can't we use link list here?
>>>
>>>   On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri <
>>> anand.shastr...@gmail.com> wrote:
>>>
   *You have given a structure which has two member, One which stores
 the
 time and other stores the function pointer Your function has to call the
 *
 *function stored in the fuction poitner after the time given in the
 structure elapses.
 Design that function? *

 Approach: To design this function I would use a min Heap data structure.
 Each node of a heap has
 two parameters one is the running time and other one is
 the function pointer.

 // Initialise a function pointer
 typedef void (*functionToBeCalled)(int arg1, int arg2);

 // Timer structure
 typedef struct timer
 {
float runingTime;   // in terms of seconds
functionToBeCalled funcToBeCall; // function pointer
 }TIMER;

 void initTimer()
 {
Initialise few nodes with running time and its corresponding function
Initialise a MIN heap data structure
 }

 void addTimer(uint32 runingTime, functionToBeCalled func)
 {
  TIMER *temp;
   temp = (TIMER *)malloc(sizeof(TIMER));
   temp->runingTime = runningTime
   temp->funcToBeCall = func;
   HeapAdd(temp);
   Heapify();
 }

 void scheduler()
 {
 uint32 currentTime = ObtainCurrentTime();
 // Obtain the runing time of top most element of the min
 Heap
 uint32 runingTime = PeakHeap();
 // if the runningTime is equal to current time then extract
 the top most
 // element of the heap and execute the function associate
 with it
 // Heapify the MIN heap data structure
 // Obtain the runing time of top most element of the min
 heap
 // scheduler sleep for that much amount of time.
 if(runingTime == currentTime)
 {
  TIMER * node = ExtractMinHeap();
   CreateThread(node->func, Thread);
   Heapify();
   runingTime = PeakHeap();
  sleep(runningTime);
 }
 else
 {
// scheduler updates its sleep time
   // if runing time is not equal to current time
   sleep(runningTime);
 }

  }

 Let me know your comments

 --
 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.

>>>
>>>
>>>
>>> --
>>> 
>>> *MOHIT VERMA*
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> 
> *MOHIT VERMA*
>
> --
> 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 

Re: [algogeeks] Google Telephonic interview

[mohit verma]

there is nothing like "search min or max time and then call function" given
. It can be the case: "call the functions in order of nodes or times saved
in objects". M i wrong?

On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri wrote:

> You mean to say linked to maintain all time task with its corresponding
> running time and associate function. In that case how will find the task
> which has the closed running time.
>
> If you use min heap it would be easy to find the task that has closest
> runing time in O(1) complexity.
>
> On Thu, Aug 4, 2011 at 10:57 AM, mohit verma wrote:
>
>> why are u maintaining heap? can't we use link list here?
>>
>>   On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri <
>> anand.shastr...@gmail.com> wrote:
>>
>>>   *You have given a structure which has two member, One which stores the
>>>
>>> time and other stores the function pointer Your function has to call the
>>> *
>>> *function stored in the fuction poitner after the time given in the
>>> structure elapses.
>>> Design that function? *
>>>
>>> Approach: To design this function I would use a min Heap data structure.
>>> Each node of a heap has
>>> two parameters one is the running time and other one is
>>> the function pointer.
>>>
>>> // Initialise a function pointer
>>> typedef void (*functionToBeCalled)(int arg1, int arg2);
>>>
>>> // Timer structure
>>> typedef struct timer
>>> {
>>>float runingTime;   // in terms of seconds
>>>functionToBeCalled funcToBeCall; // function pointer
>>> }TIMER;
>>>
>>> void initTimer()
>>> {
>>>Initialise few nodes with running time and its corresponding function
>>>Initialise a MIN heap data structure
>>> }
>>>
>>> void addTimer(uint32 runingTime, functionToBeCalled func)
>>> {
>>>  TIMER *temp;
>>>   temp = (TIMER *)malloc(sizeof(TIMER));
>>>   temp->runingTime = runningTime
>>>   temp->funcToBeCall = func;
>>>   HeapAdd(temp);
>>>   Heapify();
>>> }
>>>
>>> void scheduler()
>>> {
>>> uint32 currentTime = ObtainCurrentTime();
>>> // Obtain the runing time of top most element of the min Heap
>>> uint32 runingTime = PeakHeap();
>>> // if the runningTime is equal to current time then extract
>>> the top most
>>> // element of the heap and execute the function associate
>>> with it
>>> // Heapify the MIN heap data structure
>>> // Obtain the runing time of top most element of the min heap
>>> // scheduler sleep for that much amount of time.
>>> if(runingTime == currentTime)
>>> {
>>>  TIMER * node = ExtractMinHeap();
>>>   CreateThread(node->func, Thread);
>>>   Heapify();
>>>   runingTime = PeakHeap();
>>>  sleep(runningTime);
>>> }
>>> else
>>> {
>>>// scheduler updates its sleep time
>>>   // if runing time is not equal to current time
>>>   sleep(runningTime);
>>> }
>>>
>>>  }
>>>
>>> Let me know your comments
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> 
>> *MOHIT VERMA*
>>
>> --
>> 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.
>



-- 

*MOHIT VERMA*

-- 
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] Google Telephonic interview

[Anand Shastri]

You mean to say linked to maintain all time task with its corresponding
running time and associate function. In that case how will find the task
which has the closed running time.

If you use min heap it would be easy to find the task that has closest
runing time in O(1) complexity.

On Thu, Aug 4, 2011 at 10:57 AM, mohit verma  wrote:

> why are u maintaining heap? can't we use link list here?
>
>   On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri <
> anand.shastr...@gmail.com> wrote:
>
>>   *You have given a structure which has two member, One which stores the
>> time and other stores the function pointer Your function has to call the
>> *
>> *function stored in the fuction poitner after the time given in the
>> structure elapses.
>> Design that function? *
>>
>> Approach: To design this function I would use a min Heap data structure.
>> Each node of a heap has
>> two parameters one is the running time and other one is
>> the function pointer.
>>
>> // Initialise a function pointer
>> typedef void (*functionToBeCalled)(int arg1, int arg2);
>>
>> // Timer structure
>> typedef struct timer
>> {
>>float runingTime;   // in terms of seconds
>>functionToBeCalled funcToBeCall; // function pointer
>> }TIMER;
>>
>> void initTimer()
>> {
>>Initialise few nodes with running time and its corresponding function
>>Initialise a MIN heap data structure
>> }
>>
>> void addTimer(uint32 runingTime, functionToBeCalled func)
>> {
>>  TIMER *temp;
>>   temp = (TIMER *)malloc(sizeof(TIMER));
>>   temp->runingTime = runningTime
>>   temp->funcToBeCall = func;
>>   HeapAdd(temp);
>>   Heapify();
>> }
>>
>> void scheduler()
>> {
>> uint32 currentTime = ObtainCurrentTime();
>> // Obtain the runing time of top most element of the min Heap
>> uint32 runingTime = PeakHeap();
>> // if the runningTime is equal to current time then extract
>> the top most
>> // element of the heap and execute the function associate with
>> it
>> // Heapify the MIN heap data structure
>> // Obtain the runing time of top most element of the min heap
>> // scheduler sleep for that much amount of time.
>> if(runingTime == currentTime)
>> {
>>  TIMER * node = ExtractMinHeap();
>>   CreateThread(node->func, Thread);
>>   Heapify();
>>   runingTime = PeakHeap();
>>  sleep(runningTime);
>> }
>> else
>> {
>>// scheduler updates its sleep time
>>   // if runing time is not equal to current time
>>   sleep(runningTime);
>> }
>>
>>  }
>>
>> Let me know your comments
>>
>> --
>> 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.
>>
>
>
>
> --
> 
> *MOHIT VERMA*
>
> --
> 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] Google Telephonic interview

[mohit verma]

why are u maintaining heap? can't we use link list here?

On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri wrote:

> *You have given a structure which has two member, One which stores the
> time and other stores the function pointer Your function has to call the *
> *function stored in the fuction poitner after the time given in the
> structure elapses.
> Design that function? *
>
> Approach: To design this function I would use a min Heap data structure.
> Each node of a heap has
> two parameters one is the running time and other one is the
> function pointer.
>
> // Initialise a function pointer
> typedef void (*functionToBeCalled)(int arg1, int arg2);
>
> // Timer structure
> typedef struct timer
> {
>float runingTime;   // in terms of seconds
>functionToBeCalled funcToBeCall; // function pointer
> }TIMER;
>
> void initTimer()
> {
>Initialise few nodes with running time and its corresponding function
>Initialise a MIN heap data structure
> }
>
> void addTimer(uint32 runingTime, functionToBeCalled func)
> {
>  TIMER *temp;
>   temp = (TIMER *)malloc(sizeof(TIMER));
>   temp->runingTime = runningTime
>   temp->funcToBeCall = func;
>   HeapAdd(temp);
>   Heapify();
> }
>
> void scheduler()
> {
> uint32 currentTime = ObtainCurrentTime();
> // Obtain the runing time of top most element of the min Heap
> uint32 runingTime = PeakHeap();
> // if the runningTime is equal to current time then extract the
> top most
> // element of the heap and execute the function associate with
> it
> // Heapify the MIN heap data structure
> // Obtain the runing time of top most element of the min heap
> // scheduler sleep for that much amount of time.
> if(runingTime == currentTime)
> {
>  TIMER * node = ExtractMinHeap();
>   CreateThread(node->func, Thread);
>   Heapify();
>   runingTime = PeakHeap();
>  sleep(runningTime);
> }
> else
> {
>// scheduler updates its sleep time
>   // if runing time is not equal to current time
>   sleep(runningTime);
> }
>
>  }
>
> Let me know your comments
>
> --
> 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.
>



-- 

*MOHIT VERMA*

-- 
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] Google Telephonic interview

[Anand Shastri]

*You have given a structure which has two member, One which stores the
time and other stores the function pointer Your function has to call the *
*function stored in the fuction poitner after the time given in the
structure elapses.
Design that function? *

Approach: To design this function I would use a min Heap data structure.
Each node of a heap has
two parameters one is the running time and other one is the
function pointer.

// Initialise a function pointer
typedef void (*functionToBeCalled)(int arg1, int arg2);

// Timer structure
typedef struct timer
{
   float runingTime;   // in terms of seconds
   functionToBeCalled funcToBeCall; // function pointer
}TIMER;

void initTimer()
{
   Initialise few nodes with running time and its corresponding function
   Initialise a MIN heap data structure
}

void addTimer(uint32 runingTime, functionToBeCalled func)
{
 TIMER *temp;
  temp = (TIMER *)malloc(sizeof(TIMER));
  temp->runingTime = runningTime
  temp->funcToBeCall = func;
  HeapAdd(temp);
  Heapify();
}

void scheduler()
{
uint32 currentTime = ObtainCurrentTime();
// Obtain the runing time of top most element of the min Heap
uint32 runingTime = PeakHeap();
// if the runningTime is equal to current time then extract the
top most
// element of the heap and execute the function associate with
it
// Heapify the MIN heap data structure
// Obtain the runing time of top most element of the min heap
// scheduler sleep for that much amount of time.
if(runingTime == currentTime)
{
 TIMER * node = ExtractMinHeap();
  CreateThread(node->func, Thread);
  Heapify();
  runingTime = PeakHeap();
 sleep(runningTime);
}
else
{
   // scheduler updates its sleep time
  // if runing time is not equal to current time
  sleep(runningTime);
}

 }

Let me know your comments

-- 
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] Google Interview preparation

[Amit Mittal]

I have my google interview at the end of this month.
can any body provide me some tips/suggestions/questions ?
I am sure some of you guys here must have appeared in google interviews
before,
your help will be very valuable and much appreciated.


Thanks

-- 
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] Google Interview Question

[Manmeet Singh]

Your code does not works proper;y for all cases

On Mon, Aug 1, 2011 at 10:42 PM, Rohit jalan  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 wrote:
>
>> 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.

Re: [algogeeks] Google Interview Question

[Rohit jalan]

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 wrote:

> 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.

Re: [algogeeks] Google Interview Question

[kumar raja]

It is a bit tricky without using external memory .It is like insertion sort.
correct me if i am wrong.

for(i=n;i<2*n;i++)
{
   x=a[i];
for(j=i-1;;j--)
 {
if(j==0 || a[j-1]=='c')  // 'c' indicates some  character you can
check its ascii value
break;
a[j+1]=a[j];
  }

 a[j+1]=x;
}




On 1 August 2011 10:02, kumar raja  wrote:

> It is a bit tricky without using external memory
> correct me if i am wrong.
>
> for(i=n;i<2*n;i++)
> {
>
>
>
> On 1 August 2011 02:42, shady  wrote:
>
>> when was this question asked in Google ? approximate date ? position ?
>>
>>
>> On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta wrote:
>>
>>> 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.
>>>
>>
>>  --
>> 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
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> 10it60...@iitkgp.ac.in
> 7797137043.
> 09491690115.
>
>


-- 
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
7797137043.
09491690115.

-- 
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] Google Interview Question

[kumar raja]

It is a bit tricky without using external memory
correct me if i am wrong.

for(i=n;i<2*n;i++)
{


On 1 August 2011 02:42, shady  wrote:

> when was this question asked in Google ? approximate date ? position ?
>
>
> On Mon, Aug 1, 2011 at 1:45 PM, Abhishek Gupta wrote:
>
>> 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.
>>
>
>  --
> 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
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
7797137043.
09491690115.

-- 
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.