Re: [algogeeks] Re: Amazon Job openings

[Rahul Vatsa]

It's great to see this group active after such a long time, though it was
not for discussing an algo, but I think it's fine if a member in the group
needs some help in his/her professional career and asks for the same here.
Many members in this group are in this industry from more than a decade or
so and are definitely able to help the new guys.
I think I joined this group 12 years back and in those days it used to be
very active. Over time it has become a silent group, let it be a useful
forum in some way.

On Fri, Jul 16, 2021 at 3:46 PM Artemij Art  wrote:

> Hello, guys!
> Have a nice day. Greetings from Russia.
>
> пт, 16 июл. 2021 г., 09:19 Himanshu Singh :
>
>> Hello Guys,
>>
>> Sorry to say pls stop spamming whole group.
>>
>> Thanks.
>>
>>
>> On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal <
>> khandelwalyash...@gmail.com> wrote:
>>
>>> Done kindly check the mail
>>>
>>> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
>>> kingston.imman...@gmail.com> wrote:
>>>
 Please send a note to me on king...@amazon.com

 Thanks,
 Kingston

 On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
 kingston.imman...@gmail.com> wrote:

> Hi all,
>
> I am a hiring manager at Amazon. We are hiring for SDE and Applied
> Science roles in my team. Please send a short note about yourself, the 
> role
> you wish to apply for and your updated CV.
>
> Thanks,
> Kingston
>
 --
 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.
 To view this discussion on the web visit
 https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.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.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CABbfMraU624PR_fKEs5RJ%3DwQd1NGw_gmiCBCV_i5beheNB91GA%40mail.gmail.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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAK%2BYZjJK64zB0D8-wwWHrbasygLm7yJevzfA9dA8KVbcW1B12A%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Artemij Art]

Hello, guys!
Have a nice day. Greetings from Russia.

пт, 16 июл. 2021 г., 09:19 Himanshu Singh :

> Hello Guys,
>
> Sorry to say pls stop spamming whole group.
>
> Thanks.
>
>
> On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal <
> khandelwalyash...@gmail.com> wrote:
>
>> Done kindly check the mail
>>
>> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> Please send a note to me on king...@amazon.com
>>>
>>> Thanks,
>>> Kingston
>>>
>>> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
>>> kingston.imman...@gmail.com> wrote:
>>>
 Hi all,

 I am a hiring manager at Amazon. We are hiring for SDE and Applied
 Science roles in my team. Please send a short note about yourself, the role
 you wish to apply for and your updated CV.

 Thanks,
 Kingston

>>> --
>>> 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.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CABbfMraU624PR_fKEs5RJ%3DwQd1NGw_gmiCBCV_i5beheNB91GA%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Himanshu Singh]

Hello Guys,

Sorry to say pls stop spamming whole group.

Thanks.


On Fri, Jul 16, 2021, 11:46 AM Yash Khandelwal 
wrote:

> Done kindly check the mail
>
> On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Please send a note to me on king...@amazon.com
>>
>> Thanks,
>> Kingston
>>
>> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
>> kingston.imman...@gmail.com> wrote:
>>
>>> Hi all,
>>>
>>> I am a hiring manager at Amazon. We are hiring for SDE and Applied
>>> Science roles in my team. Please send a short note about yourself, the role
>>> you wish to apply for and your updated CV.
>>>
>>> Thanks,
>>> Kingston
>>>
>> --
>> 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.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAHwkYYrM7DdSXb1e_Mqis_K-_Y8HUwVJeCKSD0YpLeWiQUA5Vg%40mail.gmail.com.

Re: [algogeeks] Re: Amazon Job openings

[Yash Khandelwal]

Done kindly check the mail

On Fri, Jul 16, 2021, 11:41 AM immanuel kingston <
kingston.imman...@gmail.com> wrote:

> Please send a note to me on king...@amazon.com
>
> Thanks,
> Kingston
>
> On Fri, Jul 16, 2021 at 11:16 AM immanuel kingston <
> kingston.imman...@gmail.com> wrote:
>
>> Hi all,
>>
>> I am a hiring manager at Amazon. We are hiring for SDE and Applied
>> Science roles in my team. Please send a short note about yourself, the role
>> you wish to apply for and your updated CV.
>>
>> Thanks,
>> Kingston
>>
> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/algogeeks/CACOkDGdqjf%2BCUbBEoZcBQUpOsGwyJ8SMq0gDf89tZYiS0K-H-Q%40mail.gmail.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.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/algogeeks/CAJKd1Pcup_HeQNq%2B3f%2BCcnT8puZ9zwZytnGhwkPHJzsLDdiR_g%40mail.gmail.com.

Re: [algogeeks] Re: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.

[Ganesh P Kumar]

The O(1) space constraint is impossible, for any traversal will take
Omega(n) stack space in the worst case.

On Sep 5, 2017 10:38 PM, "deepikaanand"  wrote:

> using iterators:
>
>
> __author__ = 'deepika'
>
> """
> This code will return iterator for inorder traversal of a BST
> """
> class TreeNode(object):
>  def __init__(self, x):
>  self.val = x
>  self.left = None
>  self.right = None
>
>  def __repr__(self):
>  return str(self.val)
>
> class InorderIterator:
>
> def __init__(self, root):
> self.root = root
> self.stack = []
> self.appendLeftTree()
>
> def appendLeftTree(self, start=None):
> temp = self.root if start is None else start
> while temp:
> self.stack.append(temp)
> temp = temp.left
>
>
> def next(self):
> if self.stack:
> next_item = self.stack.pop()
> if next_item.right:
> self.appendLeftTree(next_item.right)
> return next_item.val
> return None
>
> class ReverseInOrderIterator:
>
> def __init__(self, root):
> self.root = root
> self.stack = []
> self.appendRightTree()
>
> def appendRightTree(self, start=None):
> temp = self.root if start is None else start
> while temp:
> self.stack.append(temp)
> temp = temp.right
>
>
> def next(self):
> if self.stack:
> next_item = self.stack.pop()
> if next_item.left:
> self.appendRightTree(next_item.left)
> return next_item.val
> return None
>
> class Solution:
>
> def binarySearchBST(self, root, key):
> left_itr = InorderIterator(root)
> right_itr = ReverseInOrderIterator(root)
> left_val = left_itr.next()
> right_val = right_itr.next()
> while True:
> if left_val >= right_val:
> break
> if left_val + right_val == key:
> print " Found: ", left_val, " ", right_val
> if left_val + right_val < key:
> left_val = left_itr.next()
> else:
> right_val = right_itr.next()
>
> root=TreeNode(10)
> root.left=TreeNode(5)
> root.right=TreeNode(11)
> root.left.left=TreeNode(1)
> root.left.right=TreeNode(8)
> root.left.right.left=TreeNode(7)
> root.right.right=TreeNode(14)
> itr = InorderIterator(root)
> result = []
> for i in range(7):
> result.append(itr.next())
> print result
>
> result = []
> itr = ReverseInOrderIterator(root)
> for i in range(7):
> result.append(itr.next())
> print result
>
> s=Solution()
> s.binarySearchBST(root, 18)
>
>
> On Sunday, September 2, 2012 at 1:02:57 PM UTC-7, Navin Kumar wrote:
>>
>>
>> --
> 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] Re: 25march

[Tarun Sharma]

Check here
http://www.writeulearn.com/defective-ball-puzzle/

On Mon, Mar 28, 2011 at 5:54 PM, Subhransu 
wrote:

> Worst Case scenario you will get in 3 steps
>
> 9 balls
>
> Compare 1st:123| 456| 789
> if (first > second)
> //The ball is in 1st
> Second compare :
> else (second > third)
> take the heavy one now you have 3 balls
>
> Third compare :
> lets send is heaver then you have 3 balls (4, 5 , 6)
> Compare 4 to 5
> if both equals then heaver is 6th one or out of 4 & 5 one is heaver
>
>
> *Subhransu Panigrahi *
> *Mobile:* *+91-9840931538 <%2B91-9840931538>*
> *Email:* subhransu.panigr...@gmail.com
>
>
>
>
>
>> On Mar 25, 2:46 am, Lavesh Rawat  wrote:
>> > *Weighing Problem Solution*
>> > *
>> > *There are 9 similar balls. Eight of them weigh the same and the ninth
>> is a
>> > bit heavier.
>> > How would you identify the heavier ball if you could use a two-pan
>> balance
>> > scale only twice?
>> >
>> > Update Your Answers at : Click
>> > Here<
>> http://dailybrainteaser.blogspot.com/2011/03/25march.html?lavesh=lavesh>
>> >
>> > Solution:
>> > Will be updated after 1 day
>> >
>> > Soln
>> >
>> > --
>> > Posted By lavesh to brain teaser
>> > solutions<
>> http://solution-dailybrainteaser.blogspot.com/2011/03/25march.html>at
>> > 3/25/2011 12:01:00 AM
>> >
>> > --
>> >
>> > "Never explain yourself. Your friends don’t need it
>> and
>> > your enemies won’t believe it" .
>>
>> --
>> 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
Tarun Sharma

-- 
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] Re: Find max sum of elements in an array ( with twist)

[Saurabh Paliwal]

you don't need to have arrays to store everything. A more memory efficient
way is to store 2 values at each iteration whether to take this number or
not. Below is a python code doing just that.

def main():
numbers = map(int, raw_input().split())
maxTakingThis = 0
maxNotTakingThis = 0
for number in numbers:
maxTakingPrevious = maxTakingThis
maxNotTakingPrevious = maxNotTakingThis
maxTakingThis = number +
max(maxTakingPrevious,maxNotTakingPrevious)
maxNotTakingThis = maxTakingPrevious
print max(maxTakingThis,maxNotTakingThis)
return 0
if(__name__=="__main__"):
main()

On Tue, Jan 12, 2016 at 9:51 PM, yomama  wrote:
>
> Here's a solution in javascript
> var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
> function max(array) {
> var i = array[0];
> array.forEach(function(val) {
> if(val > i)
> i = val;
> });
> return i;
> }
> function maxSum(i, data, canSkip) {
>var len = data.length  - i;
>if( len === 1) {
>if(canSkip && data[i] < 0) {
>return 0;
>} else {
>return data[i];
>}
>} else if(len <1) {
>   return 0;
>}
>var skippedI =  maxSum(i + 1, data, false);
>var notSkippedISkippedJ =  maxSum(i + 1, data, true) + data[i];
>var notSkippedINotSkippedJ =  maxSum(i + 2, data, true) + data[i] +
(data[i+1] || 0);
>if(canSkip) {
> return max([skippedI, notSkippedISkippedJ,
notSkippedINotSkippedJ]);
>} else {
> return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
>}
> }
>
> console.log(maxSum(0, data, true));
>
> On Tuesday, March 24, 2015 at 6:47:46 AM UTC-7, atul007 wrote:
>>
>> Given a array with +ve and -ve integer , find the maximum sum such that
you are not allowed to skip 2 contiguous elements ( i.e you have to select
atleast one of them to move forward).
>>
>> eg :-
>>
>> 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3
>>
>> Output : 10+20+30-10+40-1 = 89
>>
>>
> --
> 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.




-- 
 -Saurabh Paliwal

   B-Tech. Comp. Science and Engg.

   IIT ROORKEE

-- 
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] Re: [BANNED!!!] Urgent need Lead - Java Developer in Atlanta, GA

[Shachindra A C]

Well, you need to ban a whole lot more people.

On Mon, Nov 2, 2015 at 10:16 AM, saurabh singh  wrote:

> FYI, have banned this user and several others who mistook this group for a
> recruitment platform. Can we revive the legacy of this group again?
>
>
> On Mon, Nov 2, 2015 at 11:36 PM Shaik Asif 
> wrote:
>
>> Hi Partner,
>>
>> This is Shaik from Deegit Inc. Partner find the below requirement for
>> your consultants. If there are available. Please get back to me ASAP on
>> sh...@deegit.com
>>
>> *WE ARE LOOKING FOR 10+ YEAR'S RESUME'S*
>>
>> *Position: Lead - Java Developer *
>>
>> Location: Atlanta, GA 30301
>>
>> Duration: Long Term
>>
>>
>>
>> *Required skills: *
>>
>> · Experience in Unemployment Insurance
>>
>> · Core java, Spring MVC, SQL Transactions Annotations
>>
>> · experience with systems consulting, development and systems
>> engineering in software projects technical design and development of Java
>> based systems
>>
>> · Experience developing systems within the framework and
>> governance of a well-defined Systems Engineering Life Cycle (SELC)
>>
>> · Experience in the role of systems consultant on projects of
>> high complexity that typically have multiple concurrent and related
>> activities
>>
>> · Delivery role handling complex Java projects
>>
>> · demonstrated technical experience with:
>>
>> · Java, JSP/Servlets, XML,
>>
>> · SOAP, Struts/Spring/Hibernate
>>
>> · Knowledge of Design Patterns, UML and Web Services.
>>
>> · Knowledge of Weblogic.
>>
>> · Understanding of SQL queries, Stored procedure, DB Design etc.
>>
>> · Knowledge of Junit Framework and Testing Techniques,
>> Code-Coverage using java based tools like Eclipse
>>
>> Best Regards,
>>
>> ___
>>
>>
>>
>> Shaik | Deegit Inc |
>>
>> 1900 East Golf Rd., Suite 925 | Schaumburg, IL 60173 |
>>
>> Ph: 847.440.2436 ext - 358 | Fax: 847.330.1987
>>
>> sh...@deegit.com | www.deegit.com |
>>
>>
>>
>> “GSA Approved - GS-35F-0405V”
>>
>> "Certified Minority Business Enterprise (MBE)"
>>
>> "Winner - Deloitte Technology Fast 500 for 2008"
>>
>> "Winner - Inc. 5000 fastest growing firm for 2008"
>>
>> "Winner - Inc. 5000 fastest growing firm for 2009"
>>
>>
>>
>> "Right Person for the Right Job in the Right Time"
>>
>>
>>
>> The information transmitted is intended only for the person or entity to
>> which it is addressed and may contain confidential and/or privileged
>> material. Any review, retransmission, dissemination or other use of, or
>> taking of any action in reliance upon, this information by persons or
>> entities other than the intended recipient is prohibited. If you received
>> this in error, please contact the sender and delete the material from any
>> computer.
>>
>> --
>> 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.
>



-- 
Regards,
Shachindra A C

-- 
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] Re: [BANNED!!!] Urgent need Lead - Java Developer in Atlanta, GA

[Deshank Baranwal]

I guess we need new admins who can actively moderate the group.


On Mon, Nov 2, 2015 at 6:30 PM, Shachindra A C 
wrote:

> Well, you need to ban a whole lot more people.
>
> On Mon, Nov 2, 2015 at 10:16 AM, saurabh singh 
> wrote:
>
>> FYI, have banned this user and several others who mistook this group for
>> a recruitment platform. Can we revive the legacy of this group again?
>>
>>
>> On Mon, Nov 2, 2015 at 11:36 PM Shaik Asif 
>> wrote:
>>
>>> Hi Partner,
>>>
>>> This is Shaik from Deegit Inc. Partner find the below requirement for
>>> your consultants. If there are available. Please get back to me ASAP on
>>> sh...@deegit.com
>>>
>>> *WE ARE LOOKING FOR 10+ YEAR'S RESUME'S*
>>>
>>> *Position: Lead - Java Developer *
>>>
>>> Location: Atlanta, GA 30301
>>>
>>> Duration: Long Term
>>>
>>>
>>>
>>> *Required skills: *
>>>
>>> · Experience in Unemployment Insurance
>>>
>>> · Core java, Spring MVC, SQL Transactions Annotations
>>>
>>> · experience with systems consulting, development and systems
>>> engineering in software projects technical design and development of Java
>>> based systems
>>>
>>> · Experience developing systems within the framework and
>>> governance of a well-defined Systems Engineering Life Cycle (SELC)
>>>
>>> · Experience in the role of systems consultant on projects of
>>> high complexity that typically have multiple concurrent and related
>>> activities
>>>
>>> · Delivery role handling complex Java projects
>>>
>>> · demonstrated technical experience with:
>>>
>>> · Java, JSP/Servlets, XML,
>>>
>>> · SOAP, Struts/Spring/Hibernate
>>>
>>> · Knowledge of Design Patterns, UML and Web Services.
>>>
>>> · Knowledge of Weblogic.
>>>
>>> · Understanding of SQL queries, Stored procedure, DB Design
>>> etc.
>>>
>>> · Knowledge of Junit Framework and Testing Techniques,
>>> Code-Coverage using java based tools like Eclipse
>>>
>>> Best Regards,
>>>
>>> ___
>>>
>>>
>>>
>>> Shaik | Deegit Inc |
>>>
>>> 1900 East Golf Rd., Suite 925 | Schaumburg, IL 60173 |
>>>
>>> Ph: 847.440.2436 ext - 358 | Fax: 847.330.1987
>>>
>>> sh...@deegit.com | www.deegit.com |
>>>
>>>
>>>
>>> “GSA Approved - GS-35F-0405V”
>>>
>>> "Certified Minority Business Enterprise (MBE)"
>>>
>>> "Winner - Deloitte Technology Fast 500 for 2008"
>>>
>>> "Winner - Inc. 5000 fastest growing firm for 2008"
>>>
>>> "Winner - Inc. 5000 fastest growing firm for 2009"
>>>
>>>
>>>
>>> "Right Person for the Right Job in the Right Time"
>>>
>>>
>>>
>>> The information transmitted is intended only for the person or entity to
>>> which it is addressed and may contain confidential and/or privileged
>>> material. Any review, retransmission, dissemination or other use of, or
>>> taking of any action in reliance upon, this information by persons or
>>> entities other than the intended recipient is prohibited. If you received
>>> this in error, please contact the sender and delete the material from any
>>> computer.
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Regards,
> Shachindra A C
>
> --
> 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] Re: [BANNED!!!] Urgent need Lead - Java Developer in Atlanta, GA

[saurabh singh]

Yes, I would like that. I am sure about other admins, but I am guilty of
ignoring mails on the group. I am finding it hard to manage things between
job, other interests and google groups that I own/moderate. People who want
to volunteer to moderate this group, please reply (unicast to me,
*avoid reply all).*
Obviously also post stuff proactively so that the discussions can resume. :)

On Tue, Nov 3, 2015 at 12:02 AM Deshank Baranwal  wrote:

> I guess we need new admins who can actively moderate the group.
>
>
> On Mon, Nov 2, 2015 at 6:30 PM, Shachindra A C 
> wrote:
>
>> Well, you need to ban a whole lot more people.
>>
>> On Mon, Nov 2, 2015 at 10:16 AM, saurabh singh 
>> wrote:
>>
>>> FYI, have banned this user and several others who mistook this group for
>>> a recruitment platform. Can we revive the legacy of this group again?
>>>
>>>
>>> On Mon, Nov 2, 2015 at 11:36 PM Shaik Asif 
>>> wrote:
>>>
 Hi Partner,

 This is Shaik from Deegit Inc. Partner find the below requirement for
 your consultants. If there are available. Please get back to me ASAP on
 sh...@deegit.com

 *WE ARE LOOKING FOR 10+ YEAR'S RESUME'S*

 *Position: Lead - Java Developer *

 Location: Atlanta, GA 30301

 Duration: Long Term



 *Required skills: *

 · Experience in Unemployment Insurance

 · Core java, Spring MVC, SQL Transactions Annotations

 · experience with systems consulting, development and systems
 engineering in software projects technical design and development of Java
 based systems

 · Experience developing systems within the framework and
 governance of a well-defined Systems Engineering Life Cycle (SELC)

 · Experience in the role of systems consultant on projects of
 high complexity that typically have multiple concurrent and related
 activities

 · Delivery role handling complex Java projects

 · demonstrated technical experience with:

 · Java, JSP/Servlets, XML,

 · SOAP, Struts/Spring/Hibernate

 · Knowledge of Design Patterns, UML and Web Services.

 · Knowledge of Weblogic.

 · Understanding of SQL queries, Stored procedure, DB Design
 etc.

 · Knowledge of Junit Framework and Testing Techniques,
 Code-Coverage using java based tools like Eclipse

 Best Regards,

 ___



 Shaik | Deegit Inc |

 1900 East Golf Rd., Suite 925 | Schaumburg, IL 60173 |

 Ph: 847.440.2436 ext - 358 | Fax: 847.330.1987

 sh...@deegit.com | www.deegit.com |



 “GSA Approved - GS-35F-0405V”

 "Certified Minority Business Enterprise (MBE)"

 "Winner - Deloitte Technology Fast 500 for 2008"

 "Winner - Inc. 5000 fastest growing firm for 2008"

 "Winner - Inc. 5000 fastest growing firm for 2009"



 "Right Person for the Right Job in the Right Time"



 The information transmitted is intended only for the person or entity
 to which it is addressed and may contain confidential and/or privileged
 material. Any review, retransmission, dissemination or other use of, or
 taking of any action in reliance upon, this information by persons or
 entities other than the intended recipient is prohibited. If you received
 this in error, please contact the sender and delete the material from any
 computer.

 --
 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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Shachindra A C
>>
>> --
>> 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.
>

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

Re: [algogeeks] Re: Openings in Flipkart BLR

[Shachindra A C]

Sadly, this has become no more than a job portal without any discussions on
algorithms at all...

~Sac

On Sun, Oct 4, 2015 at 10:18 PM, taruna arora  wrote:

> Dear Sir,
>
> I am Taruna Arora working as Software Engineer with Indian Oil Corporation
> Limited (PSU), Hire Date : 29th July, 2013.
>
> I came across your post today and wish to apply for the post of SDE1.
> Sir,I know its pretty late but I am enclosing my resume for further
> reference.
>
> Looking towards for opportunity from your side!!!
>
>
> Regards & Thanks
> Taruna Arora
>
> On Tuesday, 1 September 2015 21:38:43 UTC+5:30, Sachin Chitale wrote:
>
>> Hi folks,
>>
>> There are following open position in  flipkart if someone is interested
>> do send your resume.
>>
>> 1. SDE2/SDET 2/UI2 (2+ yrs)
>> 2. APM/PM/EM
>> 3. Engineering Directors
>> 4. Architect
>> 5. Data Scientist
>>
>> Regards,
>> Sachin
>>
> --
> 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.
>



-- 
Regards,
Shachindra A C

-- 
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] Re: how to convert JSONObject object to java object ??

[Ankit Agarwal]

You can use Object Mapper, provided by com.fasterxml.jackson.core.

There is a readValue which can convert string type object to any class
object which you want.

Check this maven repo
http://mvnrepository.com/artifact/com.fasterxml.jackson.core/jackson-core/2.6.0-rc2
for
the jar


Thanks  Regards

On Fri, Jun 19, 2015 at 2:43 AM, Nand Kumar Singh nandkuma...@gmail.com
wrote:

 Rest Url : 
 http://localhost:8080//rest/hotel?{location:28.666045,77.185059,longitube:null,latitude:null,pincode:null,childrens:0,adults:1,dateCheckIn:143468460,dateCheckOut:143472420,searchedString:Sarai
 Rohilla Railway Station, Railway Officers Colony, New Delhi,
 India,marker:1,city:Delhi,rooms:0}


 On Friday, 19 June 2015 02:24:27 UTC+5:30, Nand Kumar Singh wrote:

 How am i trying till now .

 @RequestMapping(value = /rest/hotel, method = RequestMethod.GET)
 @Produces(application/json)
 @Consumes(application/json)
 public @ResponseBody ListHotelBO search(JSONObject inputJsonObj) throws 
 ParseException, IOException {

 Gson gson = new Gson();
 GsonBuilder builder = new GsonBuilder();
 Search vc = gson.fromJson(inputJsonObj.toString(), Search.class);
   *}*


 *but its not working any idea ?*

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an
 email to algogeeks+unsubscr...@googlegroups.com.




-- 

*Ankit Agarwal*
*Software Engineer*
*Seller **Platform*
*Flipkart Internet Pvt. Ltd.*
*Ph. No. +91-8095470278*

-- 
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] Re: Comparing string of unequal length

[Prateek Khandelwal]

I think this question can be done in O((m-n)*n) where m is the length of
larger string and n is the length of smaller string

Prateek Khandelwal
Software Engineer in Directi
+91-7042393719

On Tue, Oct 7, 2014 at 6:06 PM, vikas vikas.rastogi2...@gmail.com wrote:

 question unclear ?What is to be minimize ?
 in given example:
 ca*d*bch
 abc

 what is role of d ?


 On Monday, 6 October 2014 22:52:10 UTC+5:30, Rishav wrote:

 Hi everyone,

 I was asked this question recently in an interview: Given two strings of
 unequal length, you have to pad the smaller string (either at the beginning
 or the end or both, no insertions allowed) with any character you want. The
 idea is to minimize the index-wise non-similar elements in both the strings.

 Example:
 abc
 cadbch

 The character we want should be:

 **abc*, such that the difference is just one(b and c are same for both
 strings in this position). I only found a solution with O(mn) complexity.
 Anybody can suggest any optimizations?

  --
 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] Re: Comparing string of unequal length

[Prateek Khandelwal]

Just think in this manner that put 0 star in front, then 1 star in front
and so on and while doing this just compare both the strings. If you are
not able to understand just tell me I will mail my code to you.

Prateek Khandelwal
Software Engineer in Directi
+91-7042393719

On Tue, Oct 7, 2014 at 11:23 PM, Prateek Khandelwal pratv...@gmail.com
wrote:

 I think this question can be done in O((m-n)*n) where m is the length of
 larger string and n is the length of smaller string

 Prateek Khandelwal
 Software Engineer in Directi
 +91-7042393719

 On Tue, Oct 7, 2014 at 6:06 PM, vikas vikas.rastogi2...@gmail.com wrote:

 question unclear ?What is to be minimize ?
 in given example:
 ca*d*bch
 abc

 what is role of d ?


 On Monday, 6 October 2014 22:52:10 UTC+5:30, Rishav wrote:

 Hi everyone,

 I was asked this question recently in an interview: Given two strings of
 unequal length, you have to pad the smaller string (either at the beginning
 or the end or both, no insertions allowed) with any character you want. The
 idea is to minimize the index-wise non-similar elements in both the strings.

 Example:
 abc
 cadbch

 The character we want should be:

 **abc*, such that the difference is just one(b and c are same for both
 strings in this position). I only found a solution with O(mn) complexity.
 Anybody can suggest any optimizations?

  --
 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] Re: Comparing string of unequal length

[Rishav Mishra]

Hi Vikas and Prateek,

Vikas, the 'd' is arbitrary. The question is simply to return the padded
string such that the number of similar characters in the padded smaller
string (which is now equal in length to the bigger string) and the bigger
string is the minimum.

Prateek, I can understand the solution you mentioned- be great if you can
send your code.

However, I understand that the smaller string has to be moved (m-n) times
and each time there are n comparisons. If anybody has any ideas for
additional optimizations (even with lets say additional space complexity),
it would be awesome to hear!

On Tue, Oct 7, 2014 at 11:29 PM, Prateek Khandelwal pratv...@gmail.com
wrote:

 Just think in this manner that put 0 star in front, then 1 star in front
 and so on and while doing this just compare both the strings. If you are
 not able to understand just tell me I will mail my code to you.

 Prateek Khandelwal
 Software Engineer in Directi
 +91-7042393719

 On Tue, Oct 7, 2014 at 11:23 PM, Prateek Khandelwal pratv...@gmail.com
 wrote:

 I think this question can be done in O((m-n)*n) where m is the length of
 larger string and n is the length of smaller string

 Prateek Khandelwal
 Software Engineer in Directi
 +91-7042393719

 On Tue, Oct 7, 2014 at 6:06 PM, vikas vikas.rastogi2...@gmail.com
 wrote:

 question unclear ?What is to be minimize ?
 in given example:
 ca*d*bch
 abc

 what is role of d ?


 On Monday, 6 October 2014 22:52:10 UTC+5:30, Rishav wrote:

 Hi everyone,

 I was asked this question recently in an interview: Given two strings
 of unequal length, you have to pad the smaller string (either at the
 beginning or the end or both, no insertions allowed) with any character you
 want. The idea is to minimize the index-wise non-similar elements in both
 the strings.

 Example:
 abc
 cadbch

 The character we want should be:

 **abc*, such that the difference is just one(b and c are same for both
 strings in this position). I only found a solution with O(mn) complexity.
 Anybody can suggest any optimizations?

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


-- 
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] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[Carl Barton]

Almost certainly yes, but that website also gives the links to the files
used in the benchmark. So you can just check yourself.


On 8 August 2014 10:23, wtx...@gmail.com wtx...@gmail.com wrote:

 Here is Google Suffix array testing result website.

 https://sites.google.com/site/yuta256/sais

 I want to know if the testing corpus contains DNA bio information?

 It has a file named chr22.dna. Is it chromosome 22 DNA?

 Weng

 On Thursday, August 7, 2014 6:26:19 PM UTC-7, wtx...@gmail.com wrote:

 I am developing a new algorithm constructing Suffix Array that is not
 based on KA, AS-IS or Skew algorithms. Its performance depends on Max(LCPs)
 (the largest of longest common prefix) of the suffix array.  It will
 work perfectly for 8-bit character string without any code change. It needs
 some refine to deal with genome code.

 I want to know some special knowledge about genome DNA testing code. I
 know nothing about DNA sequence and biology.

 1. Which are the best books about genome DNA sequence processing
 suitable for me who is developing a new algorithm constructing suffix array
 and want the algorithm better workable for DNA analyses.
 2. I want to know if there is any algorithm constructing Suffix Array
 whose performance depends on Max(LCPs)?
 3. Genome DNA testing file contains only 4 characters: A,C,G and T. Is
 it right? I found another char U in RNA. Does the file still contain 4
 characters?
 4. If the number of chars in a file is limited to 4, and all repeatable
 patterns are known, I can specially design some technical refinement to
 improve my algorithm performance. I want know, in addition to 1 char, 2
 chars, 3 chars and 4 chars repentance, 5 chars or
 more repeatable sequence are common? And if common, the largest common
 chars repentance contains how many different chars?
 1 char repentance: ...
 2 char repentance: ACACACACACACACA...

 Thank you.

 Weng

  --
 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] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[Carl Barton]

It's just a plain text file, use whatever text editor you like


On 8 August 2014 10:42, wtx...@gmail.com wtx...@gmail.com wrote:

 *I downloaded the file chr22.dna. I don't know what software should be
 used to browse the contents and view its data pattern. This file is really
 what I need to view its data pattern.* *Please help tell me what **software
 should be used to browse the contents.*
 *Weng*
  *Can't Open .DNA Files ?*You need to clean your Windows Registry and
 repair the Broken Windows File Associations. RegCure  is the tool that
 automates this tedious task... *[image: Warning]There is a 97% chance
 your computer has registry problems.*

 If you can't open/run .DNA files chances are you are experiencing Registry
 problems. To prevent further corruption of registry error pile ups that
 slow down your PC, it is *highly recommended* that this errors should be
 fixed immediately.

 Not repairing this kind of errors can lead to system crashes, blue
 screens, and hardware failure.. Don't waste any more time, use the
 RegCure  http://www.filedocs.net/download_RegCure.php tool and your
 computer will be humming in less than 2 minutes.  (This version includes
 all the latest security fixes and updates.)
 [image: Free Download Now!] http://www.filedocs.net/download_RegCure.php
 File size: 4.9MB, Download time: 1min (Cable/DSL)


- [image: 12] *E*asily Open/Repair .DNA files!


 On Thursday, August 7, 2014 6:26:19 PM UTC-7, wtx...@gmail.com wrote:

 I am developing a new algorithm constructing Suffix Array that is not
 based on KA, AS-IS or Skew algorithms. Its performance depends on Max(LCPs)
 (the largest of longest common prefix) of the suffix array.  It will
 work perfectly for 8-bit character string without any code change. It needs
 some refine to deal with genome code.

 I want to know some special knowledge about genome DNA testing code. I
 know nothing about DNA sequence and biology.

 1. Which are the best books about genome DNA sequence processing
 suitable for me who is developing a new algorithm constructing suffix array
 and want the algorithm better workable for DNA analyses.
 2. I want to know if there is any algorithm constructing Suffix Array
 whose performance depends on Max(LCPs)?
 3. Genome DNA testing file contains only 4 characters: A,C,G and T. Is
 it right? I found another char U in RNA. Does the file still contain 4
 characters?
 4. If the number of chars in a file is limited to 4, and all repeatable
 patterns are known, I can specially design some technical refinement to
 improve my algorithm performance. I want know, in addition to 1 char, 2
 chars, 3 chars and 4 chars repentance, 5 chars or
 more repeatable sequence are common? And if common, the largest common
 chars repentance contains how many different chars?
 1 char repentance: ...
 2 char repentance: ACACACACACACACA...

 Thank you.

 Weng

  --
 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] Re: Solving coin change problem with limited coins.

[Don]

 Shashwat, very nice.
Don

-- 
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] Re: Shortest path in grid with dynamic programming.

[Don]

BFS might be faster, though.
Don

On Tuesday, April 22, 2014 1:11:00 AM UTC-4, bujji wrote:

 Hi Don,
   At most we can reach a point from 4 adjacent points. So, 
 time complexity will be O(XY) only.

 -Thanks,
 Bujji.


 On Mon, Apr 21, 2014 at 1:38 PM, bujji jajala jajal...@gmail.comjavascript:
  wrote:

 Hi Don,
  Nice solution. good.  Looks like in  your  markShortestPath(int 
 i, int i, int d)  function 
 you missed to set  distance[i][j] = d; as first statement.

 It looks like time complexity of this program is greater than O(XY). It 
 depends on number of multiple paths
 to a point with different path lengths and order of evaluation of 
 paths.Evaluating recursion paths from greater 
 run length to smaller run lengths will result in updating  distance[i][j] 
 several times. 

 Any improvements can we think of to improve this to achieve O(XY) bound?


 -Thanks 
  Bujji.



 On Mon, Apr 21, 2014 at 10:01 AM, Don dond...@gmail.com javascript:wrote:

 bool bad[X][Y];
 int distance[X][Y];
 void markShortestPath(int i, int i, int d)
 {
 if ((i = 0)  (j = 0)  (i  X)  (j  Y)  (distance[i][j]  
 d)  !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1); 
}
 }
 void findShortestPath()
 {
int i,j;
for(i = 0; i  X; ++i)
   for(j = 0; j  Y; ++j)
  distance[i][j] = 10;

markShortestPath(X-1, Y-1, 0);

if (distance[0][0] == 10)
{
   printf(No path exists\n);
   return;
}

i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
   if (distance[i+1][j] == distance[i][j]-1) ++i;
   else if (distance[i-1][j] == distance[i][j]-1) --i;
   else if (distance[i][j+1] == distance[i][j]-1) ++j;
   else if (distance[i][j-1] == distance[i][j]-1) --j;
   printf(Move to (%d, %d)\n, i,j);

}
 }

 On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:

 Create a matrix distance[x][y] and set all values to a large number.
 This will represent the distance to travel to the destination on the 
 shortest route.
 Now set the distance at the destination to zero.
 Set all adjacent locations to one, and repeat the process recursively, 
 always setting valid adjacent locations with a larger distance value to 
 the 
 distance from the current location plus one. In the end, you will have the 
 distance from every location on the grid. Now you can find the shortest 
 path from any location by always moving to a space which is closer than 
 your current location.

 Don

 On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:

 Consider a city whose streets are defined by an X ×Y grid. We are 
 interested in
 walking from the upper left-hand corner of the grid to the lower 
 right-hand corner.
 Unfortunately, the city has bad neighborhoods, whose intersections we 
 do not want
 to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” 
 if and
 only if the intersection between streets i and j is in a neighborhood 
 to avoid.

 Give an O(XY ) algorithm to find the shortest path across the grid 
 that avoids
 bad neighborhoods. You may assume that all blocks are of equal length. 
 For partial
 credit, give an O(X^2 Y^2) algorithm.

  If we walk in down or right directions only Dynamic programming 
 solution would be simple. But because of bad intersection points,  we may 
 need to walk in up, down, right or left directions.

 -Thanks 
 Bujji


  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com javascript:.





-- 
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] Re: Solving coin change problem with limited coins.

[Don]

In my solution, the line which reads:

if (sum  result) sum = result;

Should read

if (sum  result) result = sum;

Don

On Friday, May 16, 2014 11:51:52 PM UTC-4, Shashwat Anand wrote:

 @Don 
 int coins [] = {1, 3, 5}; 
 int cnt [] = {7, 3, 1}; 
 int S = 9; 
 Your code returns 9, for the aforementioned test case.  Should not it 
 return 3 ? 




-- 
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] Re: Solving coin change problem with limited coins.

[Don]

If you find a way to do that for more than a few coins I'd be interested in 
seeing it too.
Don

On Thursday, May 15, 2014 3:00:04 PM UTC-4, atul007 wrote:

 @Don : i am intersted in DP bottom up approach with less time complexity.
 solving it recursively is a simpler approach...
 On 15 May 2014 22:25, Don dond...@gmail.com javascript: wrote:

 How about this:

 const int N = 6;
 unsigned int coins[N] = {100,50,25,10,5,1};
 unsigned int count[N] = {2, 1, 1, 5, 4, 10};
 int best = 10;

 int minCoins(int s, int f=0, int d=0)
 {
if (d == 0) best = s; // It can never take more than s coins
if (s  1) return 0;  // No coins required
if (d = best) return 100; // We've already used too many coins.
int result=best;
for(int i = f; i  N; ++i) // Don't regress
{
   if (count[i])  // Only try coins which are available
   {
  if (coins[i]  s) // Try using this coin
  {
 --count[i];
 int sum = 1 + minCoins(s-coins[i], i, d+1);
 if (sum  result) sum = result;
 if ((d == 0)  (sum  best)) best = sum;
 ++count[i];
  }
  else if (coins[i] == s) return 1; // This coin is all we need
   }
}
return result;
 }

 int main()
 {
int s;
scanf(%d, s);
printf(The fewest coins to total to %d is %d\n, s, minCoins(s));
return 0;
 }

 On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:

 Solving coin change problem with limited coins.

 Given an array of denominations and array Count , find minimum number of 
 coins required to form sum S.

 for eg: coins[]={1,2,3};
   count[]={1,1,3};
 i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.

 input S = 6
 output = 2 

 possible combination : 3+3 = 6
  
  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.



-- 
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] Re: Solving coin change problem with limited coins.

[Shashwat Anand]

@Don
int coins [] = {1, 3, 5};
int cnt [] = {7, 3, 1};
int S = 9;
Your code returns 9, for the aforementioned test case.  Should not it return 3 ?

Here is my take which takes O (|number of denominators| x |S| x
|maximum count for any coin|) time and
O (|number of denominators| x |S|) time.   It is quite naive dp, but I
am not too sure if there is scope of improvement.

int coins [] = {1, 3, 5};
int cnt [] = {7, 3, 1};
const int INF = 0x3f3f3f3f;
int memo [55][1005];

int
solve (int idx, int s) {
if (s == 0) return 0;
if (s  0 || idx  0) return INF;
if (memo [idx][s] != -1) return memo [idx][s];
int ret = INF;
for (int i = 0; i = cnt [idx]; i++)
ret = min (ret, i + solve (idx - 1, s - coins [idx] * i));  //
Take i coins from coin [idx].
return memo [idx][s] = ret;
}

int
main () {
#ifdef LOCALHOST
freopen (test.in, r, stdin);
// freopen (test.out, w, stdout);
#endif
memset (memo, -1, sizeof (memo));
int S = 9;
int ret = solve (sizeof (coins) / sizeof (coins [0]) - 1, S);
ret = ret = INF ? -1 : ret;
printf (%d\n, ret);

return 0;
}


@Atul
What is the issue in recursive approach ?

On Sat, May 17, 2014 at 12:42 AM, Don dondod...@gmail.com wrote:
 If you find a way to do that for more than a few coins I'd be interested in
 seeing it too.
 Don


 On Thursday, May 15, 2014 3:00:04 PM UTC-4, atul007 wrote:

 @Don : i am intersted in DP bottom up approach with less time complexity.
 solving it recursively is a simpler approach...

 On 15 May 2014 22:25, Don dond...@gmail.com wrote:

 How about this:

 const int N = 6;
 unsigned int coins[N] = {100,50,25,10,5,1};
 unsigned int count[N] = {2, 1, 1, 5, 4, 10};
 int best = 10;

 int minCoins(int s, int f=0, int d=0)
 {
if (d == 0) best = s; // It can never take more than s coins
if (s  1) return 0;  // No coins required
if (d = best) return 100; // We've already used too many coins.
int result=best;
for(int i = f; i  N; ++i) // Don't regress
{
   if (count[i])  // Only try coins which are available
   {
  if (coins[i]  s) // Try using this coin
  {
 --count[i];
 int sum = 1 + minCoins(s-coins[i], i, d+1);
 if (sum  result) sum = result;
 if ((d == 0)  (sum  best)) best = sum;
 ++count[i];
  }
  else if (coins[i] == s) return 1; // This coin is all we need
   }
}
return result;
 }

 int main()
 {
int s;
scanf(%d, s);
printf(The fewest coins to total to %d is %d\n, s, minCoins(s));
return 0;
 }

 On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:

 Solving coin change problem with limited coins.

 Given an array of denominations and array Count , find minimum number of
 coins required to form sum S.

 for eg: coins[]={1,2,3};
   count[]={1,1,3};
 i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.

 input S = 6
 output = 2

 possible combination : 3+3 = 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an
 email to algogeeks+...@googlegroups.com.

 --
 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] Re: Solving coin change problem with limited coins.

[atul anand]

@Don : i am intersted in DP bottom up approach with less time complexity.
solving it recursively is a simpler approach...
On 15 May 2014 22:25, Don dondod...@gmail.com wrote:

 How about this:

 const int N = 6;
 unsigned int coins[N] = {100,50,25,10,5,1};
 unsigned int count[N] = {2, 1, 1, 5, 4, 10};
 int best = 10;

 int minCoins(int s, int f=0, int d=0)
 {
if (d == 0) best = s; // It can never take more than s coins
if (s  1) return 0;  // No coins required
if (d = best) return 100; // We've already used too many coins.
int result=best;
for(int i = f; i  N; ++i) // Don't regress
{
   if (count[i])  // Only try coins which are available
   {
  if (coins[i]  s) // Try using this coin
  {
 --count[i];
 int sum = 1 + minCoins(s-coins[i], i, d+1);
 if (sum  result) sum = result;
 if ((d == 0)  (sum  best)) best = sum;
 ++count[i];
  }
  else if (coins[i] == s) return 1; // This coin is all we need
   }
}
return result;
 }

 int main()
 {
int s;
scanf(%d, s);
printf(The fewest coins to total to %d is %d\n, s, minCoins(s));
return 0;
 }

 On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote:

 Solving coin change problem with limited coins.

 Given an array of denominations and array Count , find minimum number of
 coins required to form sum S.

 for eg: coins[]={1,2,3};
   count[]={1,1,3};
 i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$.

 input S = 6
 output = 2

 possible combination : 3+3 = 6

  --
 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] Re: Shortest path in grid with dynamic programming.

[bujji jajala]

Hi Don,
 Nice solution. good.  Looks like in  your  markShortestPath(int
i, int i, int d)  function
you missed to set  distance[i][j] = d; as first statement.

It looks like time complexity of this program is greater than O(XY). It
depends on number of multiple paths
to a point with different path lengths and order of evaluation of
paths.Evaluating recursion paths from greater
run length to smaller run lengths will result in updating  distance[i][j]
several times.

Any improvements can we think of to improve this to achieve O(XY) bound?


-Thanks
Bujji.



On Mon, Apr 21, 2014 at 10:01 AM, Don dondod...@gmail.com wrote:

 bool bad[X][Y];
 int distance[X][Y];
 void markShortestPath(int i, int i, int d)
 {
 if ((i = 0)  (j = 0)  (i  X)  (j  Y)  (distance[i][j]  d)
  !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
 }
 void findShortestPath()
 {
int i,j;
for(i = 0; i  X; ++i)
   for(j = 0; j  Y; ++j)
  distance[i][j] = 10;

markShortestPath(X-1, Y-1, 0);

if (distance[0][0] == 10)
{
   printf(No path exists\n);
   return;
}

i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
   if (distance[i+1][j] == distance[i][j]-1) ++i;
   else if (distance[i-1][j] == distance[i][j]-1) --i;
   else if (distance[i][j+1] == distance[i][j]-1) ++j;
   else if (distance[i][j-1] == distance[i][j]-1) --j;
   printf(Move to (%d, %d)\n, i,j);

}
 }

 On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:

 Create a matrix distance[x][y] and set all values to a large number.
 This will represent the distance to travel to the destination on the
 shortest route.
 Now set the distance at the destination to zero.
 Set all adjacent locations to one, and repeat the process recursively,
 always setting valid adjacent locations with a larger distance value to the
 distance from the current location plus one. In the end, you will have the
 distance from every location on the grid. Now you can find the shortest
 path from any location by always moving to a space which is closer than
 your current location.

 Don

 On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:

 Consider a city whose streets are defined by an X ×Y grid. We are
 interested in
 walking from the upper left-hand corner of the grid to the lower
 right-hand corner.
 Unfortunately, the city has bad neighborhoods, whose intersections we do
 not want
 to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
 and
 only if the intersection between streets i and j is in a neighborhood to
 avoid.

 Give an O(XY ) algorithm to find the shortest path across the grid that
 avoids
 bad neighborhoods. You may assume that all blocks are of equal length.
 For partial
 credit, give an O(X^2 Y^2) algorithm.

  If we walk in down or right directions only Dynamic programming
 solution would be simple. But because of bad intersection points,  we may
 need to walk in up, down, right or left directions.

 -Thanks
 Bujji


  --
 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] Re: Shortest path in grid with dynamic programming.

[bujji jajala]

Hi Don,
  At most we can reach a point from 4 adjacent points. So, time
complexity will be O(XY) only.

-Thanks,
Bujji.


On Mon, Apr 21, 2014 at 1:38 PM, bujji jajala jajalabu...@gmail.com wrote:

 Hi Don,
  Nice solution. good.  Looks like in  your  markShortestPath(int
 i, int i, int d)  function
 you missed to set  distance[i][j] = d; as first statement.

 It looks like time complexity of this program is greater than O(XY). It
 depends on number of multiple paths
 to a point with different path lengths and order of evaluation of
 paths.Evaluating recursion paths from greater
 run length to smaller run lengths will result in updating  distance[i][j]
 several times.

 Any improvements can we think of to improve this to achieve O(XY) bound?


 -Thanks
 Bujji.



 On Mon, Apr 21, 2014 at 10:01 AM, Don dondod...@gmail.com wrote:

 bool bad[X][Y];
 int distance[X][Y];
 void markShortestPath(int i, int i, int d)
 {
 if ((i = 0)  (j = 0)  (i  X)  (j  Y)  (distance[i][j] 
 d)  !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
 }
 void findShortestPath()
 {
int i,j;
for(i = 0; i  X; ++i)
   for(j = 0; j  Y; ++j)
  distance[i][j] = 10;

markShortestPath(X-1, Y-1, 0);

if (distance[0][0] == 10)
{
   printf(No path exists\n);
   return;
}

i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
   if (distance[i+1][j] == distance[i][j]-1) ++i;
   else if (distance[i-1][j] == distance[i][j]-1) --i;
   else if (distance[i][j+1] == distance[i][j]-1) ++j;
   else if (distance[i][j-1] == distance[i][j]-1) --j;
   printf(Move to (%d, %d)\n, i,j);

}
 }

 On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:

 Create a matrix distance[x][y] and set all values to a large number.
 This will represent the distance to travel to the destination on the
 shortest route.
 Now set the distance at the destination to zero.
 Set all adjacent locations to one, and repeat the process recursively,
 always setting valid adjacent locations with a larger distance value to the
 distance from the current location plus one. In the end, you will have the
 distance from every location on the grid. Now you can find the shortest
 path from any location by always moving to a space which is closer than
 your current location.

 Don

 On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:

 Consider a city whose streets are defined by an X ×Y grid. We are
 interested in
 walking from the upper left-hand corner of the grid to the lower
 right-hand corner.
 Unfortunately, the city has bad neighborhoods, whose intersections we
 do not want
 to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
 and
 only if the intersection between streets i and j is in a neighborhood
 to avoid.

 Give an O(XY ) algorithm to find the shortest path across the grid that
 avoids
 bad neighborhoods. You may assume that all blocks are of equal length.
 For partial
 credit, give an O(X^2 Y^2) algorithm.

  If we walk in down or right directions only Dynamic programming
 solution would be simple. But because of bad intersection points,  we may
 need to walk in up, down, right or left directions.

 -Thanks
 Bujji


  --
 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] Re: Calculating C(n.r)

[kumar raja]

Thanks for the idea.


On 9 April 2014 10:25, Dave dave_and_da...@juno.com wrote:

 What you want to do is automate the process of cancelling common factors
 that you would do if you were calculating nCr by hand. Fill an array a[]
 with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[]
 with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j
 and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both
 a[i] and b[j] by the gcd. When the loops finish, you will have cancelled
 the common factors from all of the terms, and in fact, all of the
 denominator terms will be 1. In a final loop, compute the product of the
 numerator terms. There are some obvious optimizations.

 Dave


 On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote:

 Hi all,

 I know the way to calculate value of C(n,r) using pascals identity. But i
 have a different requirement.

  C(n,r) =  n (n-1) (n-2) ... (n-r+1) / r!

 Suppose the numerator is such that it cant fit into existing data type.

 So i remember there is a way to strike off the common factors in
 numerator and denominator  then calculate the result of it. But the logic
 is not striking to me. Googled but could not find much. So please share the
 clever way to calculate the above value w/o actually computing the
 factorials and then making division.

 My actual requirement is to calculate the value of

 (n1+n2++nk)! / (n1!.n2!.n3!.nk!) .


 Regards,
 Kumar Raja.


  --
 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] Re: Implement lastindexofastring(String s1,String s2)

[Carl Barton]

What I suggested is optimal and doesn't require you to reverse the strings.
It's not hard to see that it takes O(n + m) which cannot be improved on.

Additionally it works for any other search algorithm than KMP.


On 7 April 2014 20:41, Dan dant...@aol.com wrote:

 Depends on what language you are using???

 Fortran has this capability built directly into it's standard Index()
 routine ( ie.  it does what you might call a 'backwards' search).   I
 imagine other languages have a similar capability.  If not,  and the
 strings are not huge memory hogs...  or if you are ok with overwriting your
 original string, s1 in the process:

 Invert both strings.ie   rearrange them such that the last letter of
 each string becomes the first, etc., etc.

 Then use your languages normal INDEXED type of search.

 Otherwise,  you'll just have to do an Indexed search repeatedly to find
 the last occurrence...  or...  write your own special Index function.  I'm
 not sure what the fastest search algorithm is for that.  I seem to remember
 reading up on it a long time ago.  It's not a brute force method if I
 recall correctly.

 Dan   :-)

 --
 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] Re: maximum subsquare such that all four borders are filled black

[Don]

00
00
010100
011100
01
00

In this case, when i and j are 1, your algorithm will set s = 3. The if 
statement will fail, and it will never notice that it could have formed a 
square with s=2.

Don

On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote:

 @don :  According to question we want to find  the maximum subsquare.
 can you give me test case for which this wont work?



 On Fri, Mar 28, 2014 at 9:41 PM, Don dond...@gmail.com javascript:wrote:

 No, that is not the same.
 It won't find a square smaller than s.
 Don


 On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:

 @Don : your algo time complexity is O(n^2) 

 It can be reduced to this :- 

 // Now look for largest square with top left corner at (i,j) 
   for(i = 0; i  n; ++i) 
   for(j = 0; j  n; ++j) 
   { 
 s = Min(countRight[i][j], countDown[i][j]); 
 if (countRight[i][j]  countDown[i][j]  
 (countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax) 
 { 
bestI = i; bestJ = j; max = s; 
 } 
   } 

 On 1/25/13, Don dond...@gmail.com wrote: 
  The worst case I know of is when the matrix is solid black except for 
  the lower right quadrant. In this case, it does break down into O(n^3) 
  runtime. It took about 8 times as long to run n=4000 as it took for 
  n=2000. 
  Don 
  
  On Jan 24, 10:29 am, Don dondod...@gmail.com wrote: 
  I'm not sure I understand your case. However, I stated that there are 
  cases where it is worse than O(N^2). The runtime is highly dependent 
  on the contents of the matrix. In many cases it takes fewer than N^2 
  iterations. Occasionally it takes more. On average it seems to be 
  roughly O(N^2), but again that depends a lot on what is in the 
 matrix. 
  I got that result by trying different ways of filling the matrix. I 
  tried things like randomly setting each pixel with various 
  probabilities, placing random horizontal and vertical segments, 
  placing random squares, or placing random filled squares. I did all 
 of 
  those both in black on white and white on black. In all of those 
  cases, going from n=1000 to n=2000 resulted in a runtime increase of 
  less than a factor of 4. 
  
  Don 
  
  On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote: 
  
  
  
  
  
  
  
   @Don: the solution is very nice.. But, how can u prove that it is 
   O(n^2).. 
   for me it seems to be O(n^3) .. 
  
   Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). 
   all 1s from (n/2,0) to (n,0). 
  
   On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote: 
The downside is that it uses a bunch of extra space. 
The upside is that it is pretty fast. It only does the 
 time-consuming 
task of scanning the matrix for contiguous pixels once, it only 
searches for squares larger than what it has already found, and 
 it 
doesn't look in places where such squares could not be. In 
 practice 
it 
performs at O(n^2) or better for most inputs I tried. But if you 
 are 
devious you can come up with an input which takes longer. 
Don 
  
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote: 
 awesome solution Don . Thanks. 
  
 On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti 
 wrote: 
  
  Imagine there is a square matrix with n x n cells. Each cell 
 is 
  either 
  filled with a black pixel or a white pixel. Design an 
 algorithm 
  to 
find the 
  maximum subsquare such that all four borders are filled with 
  black 
pixels; 
  optimize the algorithm as much as possible 
  
-- 
  
  -- 
  
  
  

  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.




-- 
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] Re: maximum subsquare such that all four borders are filled black

[atul anand]

@Don:  what is the point of considering s=2 when we have already found
s=3.As question says find the maximum subsquare. Which is of size 3 and
this the expected outcome.


On Mon, Mar 31, 2014 at 11:28 PM, Don dondod...@gmail.com wrote:

 00
 00
 010100
 011100
 01
 00

 In this case, when i and j are 1, your algorithm will set s = 3. The if
 statement will fail, and it will never notice that it could have formed a
 square with s=2.

 Don


 On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote:

 @don :  According to question we want to find  the maximum subsquare.
 can you give me test case for which this wont work?



 On Fri, Mar 28, 2014 at 9:41 PM, Don dond...@gmail.com wrote:

 No, that is not the same.
 It won't find a square smaller than s.
 Don


 On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:

 @Don : your algo time complexity is O(n^2)

 It can be reduced to this :-

 // Now look for largest square with top left corner at (i,j)
   for(i = 0; i  n; ++i)
   for(j = 0; j  n; ++j)
   {
 s = Min(countRight[i][j], countDown[i][j]);
 if (countRight[i][j]  countDown[i][j] 
 (countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax)
 {
bestI = i; bestJ = j; max = s;
 }
   }

 On 1/25/13, Don dond...@gmail.com wrote:
  The worst case I know of is when the matrix is solid black except for
  the lower right quadrant. In this case, it does break down into
 O(n^3)
  runtime. It took about 8 times as long to run n=4000 as it took for
  n=2000.
  Don
 
  On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
  I'm not sure I understand your case. However, I stated that there
 are
  cases where it is worse than O(N^2). The runtime is highly dependent
  on the contents of the matrix. In many cases it takes fewer than N^2
  iterations. Occasionally it takes more. On average it seems to be
  roughly O(N^2), but again that depends a lot on what is in the
 matrix.
  I got that result by trying different ways of filling the matrix. I
  tried things like randomly setting each pixel with various
  probabilities, placing random horizontal and vertical segments,
  placing random squares, or placing random filled squares. I did all
 of
  those both in black on white and white on black. In all of those
  cases, going from n=1000 to n=2000 resulted in a runtime increase of
  less than a factor of 4.
 
  Don
 
  On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:
 
 
 
 
 
 
 
   @Don: the solution is very nice.. But, how can u prove that it is
   O(n^2)..
   for me it seems to be O(n^3) ..
 
   Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
   all 1s from (n/2,0) to (n,0).
 
   On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the
 time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and
 it
doesn't look in places where such squares could not be. In
 practice
it
performs at O(n^2) or better for most inputs I tried. But if you
 are
devious you can come up with an input which takes longer.
Don
 
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
 awesome solution Don . Thanks.
 
 On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti
 wrote:
 
  Imagine there is a square matrix with n x n cells. Each cell
 is
  either
  filled with a black pixel or a white pixel. Design an
 algorithm
  to
find the
  maximum subsquare such that all four borders are filled with
  black
pixels;
  optimize the algorithm as much as possible
 
--
 
  --
 
 
 

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@googlegroups.com.


  --
 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] Re: maximum subsquare such that all four borders are filled black

[Don]

The only square is found when s=2. Your program will look at s=3 and not 
find a square, so it will never find the square.

Try it and you will see what I mean..

Don

On Monday, March 31, 2014 2:42:13 PM UTC-4, atul007 wrote:

 @Don:  what is the point of considering s=2 when we have already found 
 s=3.As question says find the maximum subsquare. Which is of size 3 and 
 this the expected outcome.


 On Mon, Mar 31, 2014 at 11:28 PM, Don dond...@gmail.com javascript:wrote:

 00
 00
 010100
 011100
 01
 00

 In this case, when i and j are 1, your algorithm will set s = 3. The if 
 statement will fail, and it will never notice that it could have formed a 
 square with s=2.

 Don


 On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote:

 @don :  According to question we want to find  the maximum subsquare.
 can you give me test case for which this wont work?



 On Fri, Mar 28, 2014 at 9:41 PM, Don dond...@gmail.com wrote:

 No, that is not the same.
 It won't find a square smaller than s.
 Don


 On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:

 @Don : your algo time complexity is O(n^2) 

 It can be reduced to this :- 

 // Now look for largest square with top left corner at (i,j) 
   for(i = 0; i  n; ++i) 
   for(j = 0; j  n; ++j) 
   { 
 s = Min(countRight[i][j], countDown[i][j]); 
 if (countRight[i][j]  countDown[i][j]  
 (countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax) 
 { 
bestI = i; bestJ = j; max = s; 
 } 
   } 

 On 1/25/13, Don dond...@gmail.com wrote: 
  The worst case I know of is when the matrix is solid black except 
 for 
  the lower right quadrant. In this case, it does break down into 
 O(n^3) 
  runtime. It took about 8 times as long to run n=4000 as it took for 
  n=2000. 
  Don 
  
  On Jan 24, 10:29 am, Don dondod...@gmail.com wrote: 
  I'm not sure I understand your case. However, I stated that there 
 are 
  cases where it is worse than O(N^2). The runtime is highly 
 dependent 
  on the contents of the matrix. In many cases it takes fewer than 
 N^2 
  iterations. Occasionally it takes more. On average it seems to be 
  roughly O(N^2), but again that depends a lot on what is in the 
 matrix. 
  I got that result by trying different ways of filling the matrix. I 
  tried things like randomly setting each pixel with various 
  probabilities, placing random horizontal and vertical segments, 
  placing random squares, or placing random filled squares. I did all 
 of 
  those both in black on white and white on black. In all of those 
  cases, going from n=1000 to n=2000 resulted in a runtime increase 
 of 
  less than a factor of 4. 
  
  Don 
  
  On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com 
 wrote: 
  
  
  
  
  
  
  
   @Don: the solution is very nice.. But, how can u prove that it is 
   O(n^2).. 
   for me it seems to be O(n^3) .. 
  
   Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). 
   all 1s from (n/2,0) to (n,0). 
  
   On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com 
 wrote: 
The downside is that it uses a bunch of extra space. 
The upside is that it is pretty fast. It only does the 
 time-consuming 
task of scanning the matrix for contiguous pixels once, it only 
searches for squares larger than what it has already found, and 
 it 
doesn't look in places where such squares could not be. In 
 practice 
it 
performs at O(n^2) or better for most inputs I tried. But if 
 you are 
devious you can come up with an input which takes longer. 
Don 
  
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote: 
 awesome solution Don . Thanks. 
  
 On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti 
 wrote: 
  
  Imagine there is a square matrix with n x n cells. Each 
 cell is 
  either 
  filled with a black pixel or a white pixel. Design an 
 algorithm 
  to 
find the 
  maximum subsquare such that all four borders are filled 
 with 
  black 
pixels; 
  optimize the algorithm as much as possible 
  
-- 
  
  -- 
  
  
  

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.




-- 
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] Re: maximum subsquare such that all four borders are filled black

[atul anand]

@don :  According to question we want to find  the maximum subsquare.
can you give me test case for which this wont work?



On Fri, Mar 28, 2014 at 9:41 PM, Don dondod...@gmail.com wrote:

 No, that is not the same.
 It won't find a square smaller than s.
 Don


 On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:

 @Don : your algo time complexity is O(n^2)

 It can be reduced to this :-

 // Now look for largest square with top left corner at (i,j)
   for(i = 0; i  n; ++i)
   for(j = 0; j  n; ++j)
   {
 s = Min(countRight[i][j], countDown[i][j]);
 if (countRight[i][j]  countDown[i][j] 
 (countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax)
 {
bestI = i; bestJ = j; max = s;
 }
   }

 On 1/25/13, Don dond...@gmail.com wrote:
  The worst case I know of is when the matrix is solid black except for
  the lower right quadrant. In this case, it does break down into O(n^3)
  runtime. It took about 8 times as long to run n=4000 as it took for
  n=2000.
  Don
 
  On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
  I'm not sure I understand your case. However, I stated that there are
  cases where it is worse than O(N^2). The runtime is highly dependent
  on the contents of the matrix. In many cases it takes fewer than N^2
  iterations. Occasionally it takes more. On average it seems to be
  roughly O(N^2), but again that depends a lot on what is in the matrix.
  I got that result by trying different ways of filling the matrix. I
  tried things like randomly setting each pixel with various
  probabilities, placing random horizontal and vertical segments,
  placing random squares, or placing random filled squares. I did all of
  those both in black on white and white on black. In all of those
  cases, going from n=1000 to n=2000 resulted in a runtime increase of
  less than a factor of 4.
 
  Don
 
  On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:
 
 
 
 
 
 
 
   @Don: the solution is very nice.. But, how can u prove that it is
   O(n^2)..
   for me it seems to be O(n^3) ..
 
   Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
   all 1s from (n/2,0) to (n,0).
 
   On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the
 time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and it
doesn't look in places where such squares could not be. In
 practice
it
performs at O(n^2) or better for most inputs I tried. But if you
 are
devious you can come up with an input which takes longer.
Don
 
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
 awesome solution Don . Thanks.
 
 On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:
 
  Imagine there is a square matrix with n x n cells. Each cell
 is
  either
  filled with a black pixel or a white pixel. Design an
 algorithm
  to
find the
  maximum subsquare such that all four borders are filled with
  black
pixels;
  optimize the algorithm as much as possible
 
--
 
  --
 
 
 

  --
 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] Re: maximum subsquare such that all four borders are filled black

[Don]

No, that is not the same.
It won't find a square smaller than s.
Don

On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:

 @Don : your algo time complexity is O(n^2) 

 It can be reduced to this :- 

 // Now look for largest square with top left corner at (i,j) 
   for(i = 0; i  n; ++i) 
   for(j = 0; j  n; ++j) 
   { 
 s = Min(countRight[i][j], countDown[i][j]); 
 if (countRight[i][j]  countDown[i][j]  
 (countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax) 
 { 
bestI = i; bestJ = j; max = s; 
 } 
   } 

 On 1/25/13, Don dond...@gmail.com javascript: wrote: 
  The worst case I know of is when the matrix is solid black except for 
  the lower right quadrant. In this case, it does break down into O(n^3) 
  runtime. It took about 8 times as long to run n=4000 as it took for 
  n=2000. 
  Don 
  
  On Jan 24, 10:29 am, Don dondod...@gmail.com wrote: 
  I'm not sure I understand your case. However, I stated that there are 
  cases where it is worse than O(N^2). The runtime is highly dependent 
  on the contents of the matrix. In many cases it takes fewer than N^2 
  iterations. Occasionally it takes more. On average it seems to be 
  roughly O(N^2), but again that depends a lot on what is in the matrix. 
  I got that result by trying different ways of filling the matrix. I 
  tried things like randomly setting each pixel with various 
  probabilities, placing random horizontal and vertical segments, 
  placing random squares, or placing random filled squares. I did all of 
  those both in black on white and white on black. In all of those 
  cases, going from n=1000 to n=2000 resulted in a runtime increase of 
  less than a factor of 4. 
  
  Don 
  
  On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote: 
  
  
  
  
  
  
  
   @Don: the solution is very nice.. But, how can u prove that it is 
   O(n^2).. 
   for me it seems to be O(n^3) .. 
  
   Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). 
   all 1s from (n/2,0) to (n,0). 
  
   On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote: 
The downside is that it uses a bunch of extra space. 
The upside is that it is pretty fast. It only does the 
 time-consuming 
task of scanning the matrix for contiguous pixels once, it only 
searches for squares larger than what it has already found, and it 
doesn't look in places where such squares could not be. In practice 
it 
performs at O(n^2) or better for most inputs I tried. But if you 
 are 
devious you can come up with an input which takes longer. 
Don 
  
On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote: 
 awesome solution Don . Thanks. 
  
 On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote: 
  
  Imagine there is a square matrix with n x n cells. Each cell is 
  either 
  filled with a black pixel or a white pixel. Design an algorithm 
  to 
find the 
  maximum subsquare such that all four borders are filled with 
  black 
pixels; 
  optimize the algorithm as much as possible 
  
-- 
  
  -- 
  
  
  


-- 
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] Re: maximum subsquare such that all four borders are filled black

[atul anand]

@Don : your algo time complexity is O(n^2)

It can be reduced to this :-

// Now look for largest square with top left corner at (i,j)
  for(i = 0; i  n; ++i)
  for(j = 0; j  n; ++j)
  {
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j]  countDown[i][j] 
(countRight[i+s][j] = s)  (countDown[i][j+s] = s)  smax)
{
   bestI = i; bestJ = j; max = s;
}
  }

On 1/25/13, Don dondod...@gmail.com wrote:
 The worst case I know of is when the matrix is solid black except for
 the lower right quadrant. In this case, it does break down into O(n^3)
 runtime. It took about 8 times as long to run n=4000 as it took for
 n=2000.
 Don

 On Jan 24, 10:29 am, Don dondod...@gmail.com wrote:
 I'm not sure I understand your case. However, I stated that there are
 cases where it is worse than O(N^2). The runtime is highly dependent
 on the contents of the matrix. In many cases it takes fewer than N^2
 iterations. Occasionally it takes more. On average it seems to be
 roughly O(N^2), but again that depends a lot on what is in the matrix.
 I got that result by trying different ways of filling the matrix. I
 tried things like randomly setting each pixel with various
 probabilities, placing random horizontal and vertical segments,
 placing random squares, or placing random filled squares. I did all of
 those both in black on white and white on black. In all of those
 cases, going from n=1000 to n=2000 resulted in a runtime increase of
 less than a factor of 4.

 Don

 On Jan 23, 10:33 pm, bharat b bagana.bharatku...@gmail.com wrote:







  @Don: the solution is very nice.. But, how can u prove that it is
  O(n^2)..
  for me it seems to be O(n^3) ..

  Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
  all 1s from (n/2,0) to (n,0).

  On Thu, Jan 17, 2013 at 9:28 PM, Don dondod...@gmail.com wrote:
   The downside is that it uses a bunch of extra space.
   The upside is that it is pretty fast. It only does the time-consuming
   task of scanning the matrix for contiguous pixels once, it only
   searches for squares larger than what it has already found, and it
   doesn't look in places where such squares could not be. In practice
   it
   performs at O(n^2) or better for most inputs I tried. But if you are
   devious you can come up with an input which takes longer.
   Don

   On Jan 17, 10:14 am, marti amritsa...@gmail.com wrote:
awesome solution Don . Thanks.

On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:

 Imagine there is a square matrix with n x n cells. Each cell is
 either
 filled with a black pixel or a white pixel. Design an algorithm
 to
   find the
 maximum subsquare such that all four borders are filled with
 black
   pixels;
 optimize the algorithm as much as possible

   --

 --




-- 
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] Re: strictly sorting by adding or subtracting a range of numbers

[atul anand]

@bhargav : could you please explain your algorithmn

On 3/25/14, bhargav krishna yb ybbkris...@gmail.com wrote:
 Even i completed it :). It was from one of the coding challenges...

 public class Hill {

 /**
 * @param args
 */
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
 hill(l);
 }
 public static void hill(Integer[] l) {
 int max = 0;
 for(int i=0;il.length;i++) {
 if(maxl[i]) {
 max = l[i];
 }
 }
 int min =0 ;
 while(true) {
 int av = (max+min)/2;
 if(min==max) {
 if(isHill(l, av)) {
 System.out.println(min);
 }
 else {
 System.out.println(broke);
 }
 break;
 }
 if(isHill(l, av)) {
 max = av;
 }
 else {
 min= av+1;
 }
 }
 }
 public static Boolean isHill(Integer[] l, int i) {
 int prev = -1;
 for(int j=0;jl.length;j++) {
 int max = Math.max(prev+1, l[j]-i);
 if(Math.abs(max-l[j])i) {
 return false;
 }
 prev = max;
 }
 return true;
 }
 }

 On Tue, Mar 25, 2014 at 10:14 AM, Dan dant...@aol.com wrote:


 I just stumbled upon this one (I know, a little late).  At least this
 way...
 it's too late to be helpful if it was a Homework assignent.  :-)

 This is one of those problems that, at first, appears difficult,  but ,
 upon
 closer inspection, turns out to have a very straight forward (elegant?)
 solution.

 Take any two adjacent values from the list...  call them  a b

 In the worst case scenario,  the value of   a  is higher than the value
 of
 b... a  b

 Therefore,   we need an  X  value that solves the inequality   a - X
 
 b + X

 Rearrange this  equation just slightly to another equivalent equation...
 a
 - b2X

 This indicates that a slightly different (but, still equivalent) problem
 can
 be solved to arrive at a correct solution.

 Only allow values from 0 to 2X,  [0,2X]  to be added to the original
 values
 in the array (ie. no subtractions).  This simplifies things greatly and
 allows for a clear algorithm solution that can be easily performed in a
 single pass through the array.  Essentially, you find a value of 2X that
 works... then divide that in half, and convert the resulting float type
 value to a whole integer value to get the final  X value that solves the
 'original' problem statement.

 The fortran code below has been tested and appears to work just fine.
 The real algorithm of note is the function routine:FUNCTION
 TransformArray( v ).
 Note that the important code is only 7 simple lines long and should
 be easy to recode in most any language.
 It runs extremely fast,  even for array sizes of 1.
 There's also 'fluff' code here, written to test multiple test sets to
 check
 the value of X arrived and to time everything. at is the desired answer.

 Does anyone know of any Practical applications for this algorithm??  I'm
 guessing it's just an interesting problem.

 Dan:-)

 Module Transform

   Contains

Function TransformArray( v )   Result(x)
!---
! Find a minium X value to transform the array, v(:)
! Transformed array values can be negative.  It is a trivial task to
! alter this to guarantee no negative values in the transformed array.
!---
Integer, intent(in)  :: v(:)
Integer  :: x
Integer  :: i, b
x = 0
b = v(1)
Do i = 2, Size(v)
   b = Max( b+1,   v(i) )
   x = Max(  x , b-v(i) )
End Do
x = Ceiling( x/2.0 )  ! smallest integer greater/equal to the
 value.
End Function TransformArray


Subroutine Validate_X( v, x )
!-
! Given a value of x, see if the array can be successfully transformed
! This is merely code to see if the X value arrived at is correct.
!-
Integer, intent(in)  :: v(:)
Integer, intent(in)  :: x
Integer, allocatable :: vt(:), xt(:)
Integer  :: i, n

n = Size(v)
Allocate( vt(n), xt(n) )

vt(1) = v(1) - x
xt(1) = -x

Do i = 2, n
   vt(i) = Max( vt(i-1)+1, v(i)-x )
   xt(i) = vt(i)-v(i)
End Do

write(*,'(a,2i6)')  '  v = ', v
write(*,'(a,2i6)')  ' xt = ', xt
write(*,'(a,2i6)')  ' vt = ', vt

If(   Any( abs(xt)  x )   ) Then
   write(*,'(a)' )  ' A higher x value was required during the
 transformation.'
   write(*,'(a,i0,a)')  ' X = ', x,  '  does not work.'
End If

If(  Any( vt(1:n-1) = vt(2:n) )   ) 
write(*,'(a)')  ' ERROR: Transformed array is not in Strictly
 Ascending
 order!'

End Subroutine Validate_X

 End Module Transform



 Program Main
 !--
 Use Transform
 Implicit None
 Integer, parameter   :: nmax=1
 Integer  :: n, x
 Integer, allocatable :: v(:)
 Real,allocatable :: r(:)
 Integer  :: it1, it2

 Allocate( v(nmax), 

Re: [algogeeks] Re: strictly sorting by adding or subtracting a range of numbers

[ybbkrishna]

‎We can go by binary search approach like first consider the largest number as 
it is an obvious  sol^n then consider max/2 n so on running time O(log(max)) .

Sent from my BlackBerry 10 smartphone.
  Original Message  
From: atul anand
Sent: Wednesday 26 March 2014 12:20 PM
To: algogeeks@googlegroups.com
Reply To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: strictly sorting by adding or subtracting a range 
of numbers

@bhargav : could you please explain your algorithmn

On 3/25/14, bhargav krishna yb ybbkris...@gmail.com wrote:
 Even i completed it :). It was from one of the coding challenges...

 public class Hill {

 /**
 * @param args
 */
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
 hill(l);
 }
 public static void hill(Integer[] l) {
 int max = 0;
 for(int i=0;il.length;i++) {
 if(maxl[i]) {
 max = l[i];
 }
 }
 int min =0 ;
 while(true) {
 int av = (max+min)/2;
 if(min==max) {
 if(isHill(l, av)) {
 System.out.println(min);
 }
 else {
 System.out.println(broke);
 }
 break;
 }
 if(isHill(l, av)) {
 max = av;
 }
 else {
 min= av+1;
 }
 }
 }
 public static Boolean isHill(Integer[] l, int i) {
 int prev = -1;
 for(int j=0;jl.length;j++) {
 int max = Math.max(prev+1, l[j]-i);
 if(Math.abs(max-l[j])i) {
 return false;
 }
 prev = max;
 }
 return true;
 }
 }

 On Tue, Mar 25, 2014 at 10:14 AM, Dan dant...@aol.com wrote:


 I just stumbled upon this one (I know, a little late). At least this
 way...
 it's too late to be helpful if it was a Homework assignent. :-)

 This is one of those problems that, at first, appears difficult, but ,
 upon
 closer inspection, turns out to have a very straight forward (elegant?)
 solution.

 Take any two adjacent values from the list... call them a  b

 In the worst case scenario, the value of a is higher than the value
 of
 b... a  b

 Therefore, we need an X value that solves the inequality a - X
 
 b + X

 Rearrange this equation just slightly to another equivalent equation...
 a
 - b  2X

 This indicates that a slightly different (but, still equivalent) problem
 can
 be solved to arrive at a correct solution.

 Only allow values from 0 to 2X, [0,2X] to be added to the original
 values
 in the array (ie. no subtractions). This simplifies things greatly and
 allows for a clear algorithm solution that can be easily performed in a
 single pass through the array. Essentially, you find a value of 2X that
 works... then divide that in half, and convert the resulting float type
 value to a whole integer value to get the final X value that solves the
 'original' problem statement.

 The fortran code below has been tested and appears to work just fine.
 The real algorithm of note is the function routine: FUNCTION
 TransformArray( v ).
 Note that the important code is only 7 simple lines long and should
 be easy to recode in most any language.
 It runs extremely fast, even for array sizes of 1.
 There's also 'fluff' code here, written to test multiple test sets to
 check
 the value of X arrived and to time everything. at is the desired answer.

 Does anyone know of any Practical applications for this algorithm?? I'm
 guessing it's just an interesting problem.

 Dan :-)

 Module Transform

 Contains

 Function TransformArray( v ) Result(x)
 !---
 ! Find a minium X value to transform the array, v(:)
 ! Transformed array values can be negative. It is a trivial task to
 ! alter this to guarantee no negative values in the transformed array.
 !---
 Integer, intent(in) :: v(:)
 Integer :: x
 Integer :: i, b
 x = 0
 b = v(1)
 Do i = 2, Size(v)
 b = Max( b+1, v(i) )
 x = Max( x , b-v(i) )
 End Do
 x = Ceiling( x/2.0 ) ! smallest integer greater/equal to the
 value.
 End Function TransformArray


 Subroutine Validate_X( v, x )
 !-
 ! Given a value of x, see if the array can be successfully transformed
 ! This is merely code to see if the X value arrived at is correct.
 !-
 Integer, intent(in) :: v(:)
 Integer, intent(in) :: x
 Integer, allocatable :: vt(:), xt(:)
 Integer :: i, n

 n = Size(v)
 Allocate( vt(n), xt(n) )

 vt(1) = v(1) - x
 xt(1) = -x

 Do i = 2, n
 vt(i) = Max( vt(i-1)+1, v(i)-x )
 xt(i) = vt(i)-v(i)
 End Do

 write(*,'(a,2i6)') ' v = ', v
 write(*,'(a,2i6)') ' xt = ', xt
 write(*,'(a,2i6)') ' vt = ', vt

 If( Any( abs(xt)  x ) ) Then
 write(*,'(a)' ) ' A higher x value was required during the
 transformation.'
 write(*,'(a,i0,a)') ' X = ', x, ' does not work.'
 End If

 If( Any( vt(1:n-1) = vt(2:n) ) ) 
 write(*,'(a)') ' ERROR: Transformed array is not in Strictly
 Ascending
 order!'

 End Subroutine Validate_X

 End Module Transform



 Program Main
 !--
 Use Transform
 Implicit None
 Integer, parameter

Re: [algogeeks] Re: strictly sorting by adding or subtracting a range of numbers

[bhargav krishna yb]

Even i completed it :). It was from one of the coding challenges...

public class Hill {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
hill(l);
}
public static void hill(Integer[] l) {
int max = 0;
for(int i=0;il.length;i++) {
if(maxl[i]) {
max = l[i];
}
}
int min =0 ;
while(true) {
int av = (max+min)/2;
if(min==max) {
if(isHill(l, av)) {
System.out.println(min);
}
else {
System.out.println(broke);
}
break;
}
if(isHill(l, av)) {
max = av;
}
else {
min= av+1;
}
}
}
public static Boolean isHill(Integer[] l, int i) {
int prev = -1;
for(int j=0;jl.length;j++) {
int max = Math.max(prev+1, l[j]-i);
if(Math.abs(max-l[j])i) {
return false;
}
prev = max;
}
return true;
}
}

On Tue, Mar 25, 2014 at 10:14 AM, Dan dant...@aol.com wrote:


 I just stumbled upon this one (I know, a little late).  At least this way...
 it's too late to be helpful if it was a Homework assignent.  :-)

 This is one of those problems that, at first, appears difficult,  but , upon
 closer inspection, turns out to have a very straight forward (elegant?)
 solution.

 Take any two adjacent values from the list...  call them  a b

 In the worst case scenario,  the value of   a  is higher than the value of
 b... a  b

 Therefore,   we need an  X  value that solves the inequality   a - X  
 b + X

 Rearrange this  equation just slightly to another equivalent equation...   a
 - b2X

 This indicates that a slightly different (but, still equivalent) problem can
 be solved to arrive at a correct solution.

 Only allow values from 0 to 2X,  [0,2X]  to be added to the original values
 in the array (ie. no subtractions).  This simplifies things greatly and
 allows for a clear algorithm solution that can be easily performed in a
 single pass through the array.  Essentially, you find a value of 2X that
 works... then divide that in half, and convert the resulting float type
 value to a whole integer value to get the final  X value that solves the
 'original' problem statement.

 The fortran code below has been tested and appears to work just fine.
 The real algorithm of note is the function routine:FUNCTION
 TransformArray( v ).
 Note that the important code is only 7 simple lines long and should
 be easy to recode in most any language.
 It runs extremely fast,  even for array sizes of 1.
 There's also 'fluff' code here, written to test multiple test sets to check
 the value of X arrived and to time everything. at is the desired answer.

 Does anyone know of any Practical applications for this algorithm??  I'm
 guessing it's just an interesting problem.

 Dan:-)

 Module Transform

   Contains

Function TransformArray( v )   Result(x)
!---
! Find a minium X value to transform the array, v(:)
! Transformed array values can be negative.  It is a trivial task to
! alter this to guarantee no negative values in the transformed array.
!---
Integer, intent(in)  :: v(:)
Integer  :: x
Integer  :: i, b
x = 0
b = v(1)
Do i = 2, Size(v)
   b = Max( b+1,   v(i) )
   x = Max(  x , b-v(i) )
End Do
x = Ceiling( x/2.0 )  ! smallest integer greater/equal to the
 value.
End Function TransformArray


Subroutine Validate_X( v, x )
!-
! Given a value of x, see if the array can be successfully transformed
! This is merely code to see if the X value arrived at is correct.
!-
Integer, intent(in)  :: v(:)
Integer, intent(in)  :: x
Integer, allocatable :: vt(:), xt(:)
Integer  :: i, n

n = Size(v)
Allocate( vt(n), xt(n) )

vt(1) = v(1) - x
xt(1) = -x

Do i = 2, n
   vt(i) = Max( vt(i-1)+1, v(i)-x )
   xt(i) = vt(i)-v(i)
End Do

write(*,'(a,2i6)')  '  v = ', v
write(*,'(a,2i6)')  ' xt = ', xt
write(*,'(a,2i6)')  ' vt = ', vt

If(   Any( abs(xt)  x )   ) Then
   write(*,'(a)' )  ' A higher x value was required during the
 transformation.'
   write(*,'(a,i0,a)')  ' X = ', x,  '  does not work.'
End If

If(  Any( vt(1:n-1) = vt(2:n) )   ) 
write(*,'(a)')  ' ERROR: Transformed array is not in Strictly Ascending
 order!'

End Subroutine Validate_X

 End Module Transform



 Program Main
 !--
 Use Transform
 Implicit None
 Integer, parameter   :: nmax=1
 Integer  :: n, x
 Integer, allocatable :: v(:)
 Real,allocatable :: r(:)
 Integer  :: it1, it2

 Allocate( v(nmax), r(nmax) )

 call timer(it1)
 write(*,*)
 write(*,*) 'Test Case #1:  array size = 5,  Easy to check'
 n = 5
 v(1:n) = (/5,4,3,2,8/)
 Call Solve_for_X()
 write(*,*) 

Re: [algogeeks] Re: DISTINCT Permutations ( Not Easy)

[navneet singh gaur]

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
 printf(%s\n, a);

   for (j = i; j = n; j++)
   {
if(a[i] != a[j])
{   swap(a[i], a[j]);   //just check before swapping if
you are swapping different elements
 //or not, if not then don't swap
permute(a, i+1, n);
swap([ai], a[j]);
 }
}
}


On Sat, Jan 11, 2014 at 4:09 PM, bujji jajala jajalabu...@gmail.com wrote:
 Hi Don,
  Good one :) Nice to see different approaches for this problem.

 -Thanks,
 Bujji


 On Fri, Jan 10, 2014 at 9:11 AM, Don dondod...@gmail.com wrote:

 Sort the input string and remove duplicates, keeping a count of the number
 of occurrences of each character.
 They you can build the permutations easily.

 For your example, you would start with

 char *str = aba;
 int len = strlen(str);

 Which would be converted to

 char *str ab;
 int rep[N] = {2,1,0};  // The string contained 2 'a's and 1 'b'
 char result[N];

 Then call permute(str,rep,len)

 void permute(char *str, int *rep, int len, int p=0)
 {
if (plen)
{
   for(int i = 0; str[i]; ++i)
  if (rep[i])
  {
 result[p] = str[i];
 --rep[i];
 permute(str, rep, len,p+1);
 ++rep[i];
  }
}
else printf(%s\n, result);

 }

 On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:

 generate all possible DISTINCT permutations of a given string with some
 possible repeated characters. Use as minimal memory as possible.

 if given string contains n characters in total with m  n distinct
 characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m
 = n

 program should generate n! / ( n_1! * n_2! * * n_m!  )  strings.

 Ex:
  aba  is given string

 Output:

 aab
 aba
 baa


 -Thanks,
 Bujji

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



-- 
navneet singh gaur

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: DISTINCT Permutations ( Not Easy)

[navneet singh gaur]

formatting changes .

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
 printf(%s\n, a);

   for (j = i; j = n; j++)
   {
if(a[i] != a[j])  check before swapping if you are
swapping different elements or not, if not then don't.
{   swap(a[i], a[j]);
permute(a, i+1, n);
swap([ai], a[j]);

 }
}
}

-


On Wed, Mar 12, 2014 at 11:59 AM, navneet singh gaur
navneet.singhg...@gmail.com wrote:
 void permute(char *a, int i, int n)
 {
int j;
if (i == n)
  printf(%s\n, a);

for (j = i; j = n; j++)
{
 if(a[i] != a[j])
 {   swap(a[i], a[j]);   //just check before swapping if
 you are swapping different elements
  //or not, if not then don't swap
 permute(a, i+1, n);
 swap([ai], a[j]);
  }
 }
 }


 On Sat, Jan 11, 2014 at 4:09 PM, bujji jajala jajalabu...@gmail.com wrote:
 Hi Don,
  Good one :) Nice to see different approaches for this problem.

 -Thanks,
 Bujji


 On Fri, Jan 10, 2014 at 9:11 AM, Don dondod...@gmail.com wrote:

 Sort the input string and remove duplicates, keeping a count of the number
 of occurrences of each character.
 They you can build the permutations easily.

 For your example, you would start with

 char *str = aba;
 int len = strlen(str);

 Which would be converted to

 char *str ab;
 int rep[N] = {2,1,0};  // The string contained 2 'a's and 1 'b'
 char result[N];

 Then call permute(str,rep,len)

 void permute(char *str, int *rep, int len, int p=0)
 {
if (plen)
{
   for(int i = 0; str[i]; ++i)
  if (rep[i])
  {
 result[p] = str[i];
 --rep[i];
 permute(str, rep, len,p+1);
 ++rep[i];
  }
}
else printf(%s\n, result);

 }

 On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:

 generate all possible DISTINCT permutations of a given string with some
 possible repeated characters. Use as minimal memory as possible.

 if given string contains n characters in total with m  n distinct
 characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m
 = n

 program should generate n! / ( n_1! * n_2! * * n_m!  )  strings.

 Ex:
  aba  is given string

 Output:

 aab
 aba
 baa


 -Thanks,
 Bujji

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



 --
 navneet singh gaur



-- 
navneet singh gaur

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Find 3 digit number.

[Shashwat Anand]

@Don, amazing solution.

Let us say, I don't have the insight to see the greedy solution mentioned
by @Don there is an obvious dp solution for the general case.


typedef long long int64;
const int64 LINF = (int64) 1e16 + 5;
map int64, int64 memo;

int64
solve (int n) {
if (n  10) return n;
if (memo.count (n)) return memo [n];
int64 ret = LINF;
for (int i = 9; i = 2; i--)
if (n % i == 0)
ret = min (ret, 10 * solve (n / i) + i);
return memo [n] = ret;
}

int
main () {
#ifdef LOCALHOST
freopen (test.in, r, stdin);
// freopen (test.out, w, stdout);
#endif
int n = 100;
int64 ret = solve (n);
if (ret = LINF) ret = -1;  // Solution does not exist.

return 0;
}

This solution won't work when result exceed 64 bit integers but can easily
be
modified to work with strings.


On Thu, Feb 13, 2014 at 5:57 PM, bhargav ybbkris...@gmail.com wrote:

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
 import java.util.Scanner;


 public class PrimeFactors {

 /**
  * @param args
  */
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
 ListInteger counts = new ArrayListInteger();
 ListInteger l = new ArrayListInteger();
  l.add(2);
 l.add(3);
 l.add(5);
 l.add(7);
  for(int i=0;il.size();i++) {
 int j=0;
 while(n%l.get(i)==0) {
  n = n/l.get(i);
 j++;
 }
 counts.add(j);
  }
 if(n!=1) {
 System.out.println(-1);
 }
  else {
 System.out.println(counts);
 System.out.println(generateComb(counts));
  }
 }
  public static int generateComb(ListInteger l) {
  ListInteger li = new ArrayListInteger();
 int temp=0;
 for(int i=0;il.size();i++) {
  int k = 0;
 int j =0;
 if(l.get(i)==0temp==1i==1) {
  li.add(2);
 }
 if(l.get(i)==0) {
 continue;
  }
 switch (i) {
 case 0: k = l.get(i)%3;
  if(k!=l.get(i)) {
  j = l.get(i)/3;
  while(j!=0) {
  li.add(8);
  j--;
  }
  }
  if(k==2)
  li.add(2*k);
  temp=k;
  break;
 case 1:  k = l.get(i)%2;
  if(k!=l.get(i)) {
  j = l.get(i)/2;
  while(j!=0) {
  li.add(9);
  j--;
  }
  }
  if(temp==1k==1) {
  li.add(6);
  }
  else if(k==1) {
  li.add(3);
  }
  else if(temp==1) {
  li.add(2);
  }
  break;
 case 2:  k = l.get(i);
  while(k!=0) {
  li.add(5);
  k--;
  }
  break;
 case 3:  k = l.get(i);
 while(k!=0) {
  li.add(7);
  k--;
  }
  break;
 }
  }
 Collections.sort(li);
 return generateNumFromArray(li);
  }
 public static int generateNumFromArray(ListInteger l) {
 int num=0;
  for(int i=0;il.size();i++) {
 num = num*10 + l.get(i);
 }
  return num;
 }
 }


 btw was this from interviewstreet interview ?? :P

 --
 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] Re: Generate random number from 1 to 10.

[Don]

https://groups.google.com/forum/#!original/comp.lang.java.programmer/Z8lfFIDhS7k/wbPLDldPSSgJ

The Multiply With Carry generator is ok for some purposes. There are 
generators with longer periods and better statistical properties, but they 
are more complicated. The link I provided has code for a 64-bit multiply 
with carry generator, while what I posted was a 32-bit multiply with carry 
generator.

Don

On Saturday, February 8, 2014 2:26:34 AM UTC-5, atul007 wrote:

 @don : awesome  +1 . I was not aware of George Marsaglia's Multiply 
 With Carry generator. But it is soo clll . If you have any good link 
 for its proof or explanation of the idea behind it then please mention it.
 I never knew generating random number can be few lines of code :)
 Thanks :)



 On Sat, Feb 8, 2014 at 1:28 AM, Don dond...@gmail.com javascript:wrote:

 A random generator will not always (or even usually) produce a 
 permutation of the possible values before repeating. 
 If you call my function 10 million times and tally up the results, you 
 will get a distribution with about a million of each value, as close as you 
 would expect for a random sample.
 Your question was to randomly generate values in the range 1-10, not to 
 generate permutations.

 Here is a way to generate a permutation without swapping:

 unsigned int X = time(0);
 int n[10];
 n[0] = 10;
 for(i = 1; i  10; ++i)
 {
X = 63663 * (X65535) + (X16);
int j = (X  65535) % (i+1);
n[i] = n[j];
n[j] = i;  
 }

 // n now contains a permutation of the values 1-10.


 On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:

 @don: algo look fine..i tested it ,but it did not generate 1-10 with 
 probabilty of 1/10 everytime.
 actually question was asked in an intrview.
 question started with displaying all elements in an array randomly 
 without repetition i.e only once( probabilty 1/10)...which can be done with 
 fisher yates .
 then interviewer said that u are not allowed to swap elements which is 
 requied in fishr yates.
 his hint was: how will you generate randomly number from 1-10 without 
 use of rand() function.
 expected time complexity : O(n)
 On 7 Feb 2014 03:17, Don dond...@gmail.com wrote:

  Just noticed that you asked for 1-10, and my code will clearly 
 generate 0-9. Add one for the desired range.
 Don

 On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:

 // Using George Marsaglia's Multiply With Carry generator
 int rnd10()
 {
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x  65535) % 10;
 }

 On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:

 Generate random number form 1 - 10 with probability of 1/10.You are 
 not allowed to used rand() function.

 any simple way of achieving above with using any complex 
 implementation of random number generators algorithm . 
  
  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.

  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.




-- 
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] Re: Generate random number from 1 to 10.

[Don]

A random generator will not always (or even usually) produce a permutation 
of the possible values before repeating. 
If you call my function 10 million times and tally up the results, you will 
get a distribution with about a million of each value, as close as you 
would expect for a random sample.
Your question was to randomly generate values in the range 1-10, not to 
generate permutations.

Here is a way to generate a permutation without swapping:

unsigned int X = time(0);
int n[10];
n[0] = 10;
for(i = 1; i  10; ++i)
{
   X = 63663 * (X65535) + (X16);
   int j = (X  65535) % (i+1);
   n[i] = n[j];
   n[j] = i;  
}

// n now contains a permutation of the values 1-10.

On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:

 @don: algo look fine..i tested it ,but it did not generate 1-10 with 
 probabilty of 1/10 everytime.
 actually question was asked in an intrview.
 question started with displaying all elements in an array randomly without 
 repetition i.e only once( probabilty 1/10)...which can be done with fisher 
 yates .
 then interviewer said that u are not allowed to swap elements which is 
 requied in fishr yates.
 his hint was: how will you generate randomly number from 1-10 without use 
 of rand() function.
 expected time complexity : O(n)
 On 7 Feb 2014 03:17, Don dond...@gmail.com javascript: wrote:

 Just noticed that you asked for 1-10, and my code will clearly generate 
 0-9. Add one for the desired range.
 Don

 On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:

 // Using George Marsaglia's Multiply With Carry generator
 int rnd10()
 {
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x  65535) % 10;
 }

 On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:

 Generate random number form 1 - 10 with probability of 1/10.You are not 
 allowed to used rand() function.

 any simple way of achieving above with using any complex implementation 
 of random number generators algorithm . 
  
  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.



-- 
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] Re: Generate random number from 1 to 10.

[atul anand]

@don : awesome  +1 . I was not aware of George Marsaglia's Multiply
With Carry generator. But it is soo clll . If you have any good link
for its proof or explanation of the idea behind it then please mention it.
I never knew generating random number can be few lines of code :)
Thanks :)



On Sat, Feb 8, 2014 at 1:28 AM, Don dondod...@gmail.com wrote:

 A random generator will not always (or even usually) produce a permutation
 of the possible values before repeating.
 If you call my function 10 million times and tally up the results, you
 will get a distribution with about a million of each value, as close as you
 would expect for a random sample.
 Your question was to randomly generate values in the range 1-10, not to
 generate permutations.

 Here is a way to generate a permutation without swapping:

 unsigned int X = time(0);
 int n[10];
 n[0] = 10;
 for(i = 1; i  10; ++i)
 {
X = 63663 * (X65535) + (X16);
int j = (X  65535) % (i+1);
n[i] = n[j];
n[j] = i;
 }

 // n now contains a permutation of the values 1-10.


 On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote:

 @don: algo look fine..i tested it ,but it did not generate 1-10 with
 probabilty of 1/10 everytime.
 actually question was asked in an intrview.
 question started with displaying all elements in an array randomly
 without repetition i.e only once( probabilty 1/10)...which can be done with
 fisher yates .
 then interviewer said that u are not allowed to swap elements which is
 requied in fishr yates.
 his hint was: how will you generate randomly number from 1-10 without use
 of rand() function.
 expected time complexity : O(n)
 On 7 Feb 2014 03:17, Don dond...@gmail.com wrote:

 Just noticed that you asked for 1-10, and my code will clearly generate
 0-9. Add one for the desired range.
 Don

 On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:

 // Using George Marsaglia's Multiply With Carry generator
 int rnd10()
 {
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x  65535) % 10;
 }

 On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:

 Generate random number form 1 - 10 with probability of 1/10.You are
 not allowed to used rand() function.

 any simple way of achieving above with using any complex
 implementation of random number generators algorithm .

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@googlegroups.com.

  --
 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] Re: Generate random number from 1 to 10.

[atul anand]

@don: algo look fine..i tested it ,but it did not generate 1-10 with
probabilty of 1/10 everytime.
actually question was asked in an intrview.
question started with displaying all elements in an array randomly without
repetition i.e only once( probabilty 1/10)...which can be done with fisher
yates .
then interviewer said that u are not allowed to swap elements which is
requied in fishr yates.
his hint was: how will you generate randomly number from 1-10 without use
of rand() function.
expected time complexity : O(n)
On 7 Feb 2014 03:17, Don dondod...@gmail.com wrote:

 Just noticed that you asked for 1-10, and my code will clearly generate
 0-9. Add one for the desired range.
 Don

 On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:

 // Using George Marsaglia's Multiply With Carry generator
 int rnd10()
 {
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return (x  65535) % 10;
 }

 On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:

 Generate random number form 1 - 10 with probability of 1/10.You are not
 allowed to used rand() function.

 any simple way of achieving above with using any complex implementation
 of random number generators algorithm .

  --
 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] Re: changing structure of binary tree based on gravity and node selected.

[Amol Sharma]

Even if its collapsing into almost a straight line, the structure is still
a tree with a node having a maximum of 3 nodes, thus can be called a
ternary tree.


--
Thanks and Regards,
Amol Sharma



On Mon, Jan 20, 2014 at 10:50 PM, Don dondod...@gmail.com wrote:

 Good point, Vikas.

 What if the balls all have a negative charge and repel each other?


 On Thursday, January 16, 2014 6:36:06 AM UTC-5, vikas wrote:

 it will all collapse and form a single monolithic straight line with
 bunch of balls hanging in between :D

 On Wednesday, 15 January 2014 10:47:47 UTC+5:30, atul007 wrote:

 Imagine a binary tree lying on the floor with nodes as balls and edges
 as threads, you are given a pointer to a node. When you pick the tree
 from that node up what will be the structure of the tree. You have
 gravity changing the structure of the tree

  --
 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] Re: DISTINCT Permutations ( Not Easy)

[bujji jajala]

Hi Don,
 Good one :) Nice to see different approaches for this problem.

-Thanks,
Bujji


On Fri, Jan 10, 2014 at 9:11 AM, Don dondod...@gmail.com wrote:

 Sort the input string and remove duplicates, keeping a count of the number
 of occurrences of each character.
 They you can build the permutations easily.

 For your example, you would start with

 char *str = aba;
 int len = strlen(str);

 Which would be converted to

 char *str ab;
 int rep[N] = {2,1,0};  // The string contained 2 'a's and 1 'b'
 char result[N];

 Then call permute(str,rep,len)

 void permute(char *str, int *rep, int len, int p=0)
 {
if (plen)
{
   for(int i = 0; str[i]; ++i)
  if (rep[i])
  {
 result[p] = str[i];
 --rep[i];
 permute(str, rep, len,p+1);
 ++rep[i];
  }
}
else printf(%s\n, result);

 }

 On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:

 generate all possible DISTINCT permutations of a given string with some
 possible repeated characters. Use as minimal memory as possible.

 if given string contains n characters in total with m  n distinct
 characters each occuring n_1, n_2, n_m times where n_1 + n_2 + ...+ n_m
 = n

 program should generate n! / ( n_1! * n_2! * * n_m!  )  strings.

 Ex:
  aba  is given string

 Output:

 aab
 aba
 baa


 -Thanks,
 Bujji

  --
 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] Re: Median Finding in Sorted Arrays

[Don]

http://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

This gives a reasonable solution. However, I would use iteration instead of 
tail recursion.

Don

On Monday, January 6, 2014 4:15:41 AM UTC-5, atul007 wrote:

 @dave : could you provide pseudo code for ur approach
 On 6 Jan 2014 07:39, Dave dave_an...@juno.com javascript: wrote:

 Use a binary search. Assume that you have arrays a[m] and b[n] sorted in 
 ascending order. If a[i] is the kth smallest element, then b[k-i-2] must be 
 smaller than a[i], and b[k-i-1] must be larger (assuming arrays are 
 zero-based). After using a binary search to find the value of i to meet 
 this condition with k = (m+n)/2, you have to determine if a[i] or b[k-i-1] 
 is the final answer. The complexity is O(log m).

 Dave

 On Sunday, January 5, 2014 5:34:12 AM UTC-6, Sanjay Rajpal wrote:

 Hi guys,

 Please help me in finding median of two sorted arrays of length m and n 
 in minimum possible time.


 Thanks,
 Sanjay

  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.



-- 
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] Re: Median Finding in Sorted Arrays

[atul anand]

@dave : could you provide pseudo code for ur approach
On 6 Jan 2014 07:39, Dave dave_and_da...@juno.com wrote:

 Use a binary search. Assume that you have arrays a[m] and b[n] sorted in
 ascending order. If a[i] is the kth smallest element, then b[k-i-2] must be
 smaller than a[i], and b[k-i-1] must be larger (assuming arrays are
 zero-based). After using a binary search to find the value of i to meet
 this condition with k = (m+n)/2, you have to determine if a[i] or b[k-i-1]
 is the final answer. The complexity is O(log m).

 Dave

 On Sunday, January 5, 2014 5:34:12 AM UTC-6, Sanjay Rajpal wrote:

 Hi guys,

 Please help me in finding median of two sorted arrays of length m and n
 in minimum possible time.


 Thanks,
 Sanjay

  --
 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] Re: Saving and restoring Binary trees in files

[Don]

The data file contains the pre-order traversal. For each node indicate the 
contents of the node and two bits to indicate if it has a left and/or right 
subtree. I did this with a tree containing strings. Each node was one line 
in the file, with the first character being 'A' if the node is a leaf, 'B' 
if it has only a left subtree, 'C' if it has only a right subtree, and 'D' 
if it has both left and right subtrees. Then you read the line, store the 
string minus the first character, and recursively build the left and then 
right subtree, as appropriate.

Don

On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:

 @don : i did not get it , what will be data in file?


 On Mon, Nov 11, 2013 at 10:14 PM, Don dond...@gmail.com javascript:wrote:

 Save in preorder, tagging each node with two bits indicating if that node 
 has a left and right subtree.

 Then rebuild like this:

 Tree rebuild()
 {
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;

 }

 On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will 
 not work in this case. 

 @kumar : save pre-order and in-order traversal with some delimiter in 
 b/w traversals. 

 pre-order : a b c d e 
 in-order   : c b e a d 

 write in file :- 

 a b c d e # c b e a d 

 now use pre-order and in-order traversal to re-create binary tree. 

 2) consider null node as # ..now write in file preorder traversal. 

 for eg :  a b c # # # d # # 

 3) save level order traversal of binary tree, where each level uses 
 # to distinguish between levels and * to mark null nodes 
 eg : a # b c # e * 
 a - level 1 
 b c - level 2 
 e NULL - level 3 

 shortcoming in 2 and 3 is use of character that can be part of tree 
 itself.So if node can contain # then you have to use some other 
 character to distinguish. 

 for solution 1 , you can write traversal in 2 lines instead of using # 

 On 11/8/13, Vishnu vish...@gmail.com wrote: 
  1) save the nodes(value, left and right pointer) in pre-order 
 traversal 
  2) also save pointers of all node in same order 
  
  to restore 
  1) create new N nodes 
  2) do pointer mapping from old - new 
  3) restore nodes and replace old pointers to new 
  
  
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote: 
  
  Save it in pre-order. 
  Rebuild by inserting nodes in the order they occur in the file. 
  
  
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote: 
  
  What is the effective way to save and restore the binary trees to 
 files 
  effectively? 
  
  
  
  
  
  
  
  
  
  
  
  
  
  Regards, 
  Kumar Raja. 
  
   -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, 
 send an 
  email to algogeeks+...@googlegroups.com. 
  
  
  
  
  -- 
  Thanks, 
  Vishnu 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, send 
 an 
  email to algogeeks+...@googlegroups.com. 
  

  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.




-- 
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] Re: Saving and restoring Binary trees in files

[Dave]

@Don: Excellent solution. It requires little extra data to be stored, and 
it is easy to implement.
 
Dave

On Wednesday, November 13, 2013 9:31:47 AM UTC-6, Don wrote:

 The data file contains the pre-order traversal. For each node indicate the 
 contents of the node and two bits to indicate if it has a left and/or right 
 subtree. I did this with a tree containing strings. Each node was one line 
 in the file, with the first character being 'A' if the node is a leaf, 'B' 
 if it has only a left subtree, 'C' if it has only a right subtree, and 'D' 
 if it has both left and right subtrees. Then you read the line, store the 
 string minus the first character, and recursively build the left and then 
 right subtree, as appropriate.

 Don

 On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:

 @don : i did not get it , what will be data in file?


 On Mon, Nov 11, 2013 at 10:14 PM, Don dond...@gmail.com wrote:

 Save in preorder, tagging each node with two bits indicating if that 
 node has a left and right subtree.

 Then rebuild like this:

 Tree rebuild()
 {
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;

 }

 On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will 
 not work in this case. 

 @kumar : save pre-order and in-order traversal with some delimiter in 
 b/w traversals. 

 pre-order : a b c d e 
 in-order   : c b e a d 

 write in file :- 

 a b c d e # c b e a d 

 now use pre-order and in-order traversal to re-create binary tree. 

 2) consider null node as # ..now write in file preorder traversal. 

 for eg :  a b c # # # d # # 

 3) save level order traversal of binary tree, where each level uses 
 # to distinguish between levels and * to mark null nodes 
 eg : a # b c # e * 
 a - level 1 
 b c - level 2 
 e NULL - level 3 

 shortcoming in 2 and 3 is use of character that can be part of tree 
 itself.So if node can contain # then you have to use some other 
 character to distinguish. 

 for solution 1 , you can write traversal in 2 lines instead of using 
 # 

 On 11/8/13, Vishnu vish...@gmail.com wrote: 
  1) save the nodes(value, left and right pointer) in pre-order 
 traversal 
  2) also save pointers of all node in same order 
  
  to restore 
  1) create new N nodes 
  2) do pointer mapping from old - new 
  3) restore nodes and replace old pointers to new 
  
  
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote: 
  
  Save it in pre-order. 
  Rebuild by inserting nodes in the order they occur in the file. 
  
  
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote: 
  
  What is the effective way to save and restore the binary trees to 
 files 
  effectively? 
  
  
  
  
  
  
  
  
  
  
  
  
  
  Regards, 
  Kumar Raja. 
  
   -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, 
 send an 
  email to algogeeks+...@googlegroups.com. 
  
  
  
  
  -- 
  Thanks, 
  Vishnu 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, 
 send an 
  email to algogeeks+...@googlegroups.com. 
  

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.




-- 
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] Re: Saving and restoring Binary trees in files

[atul anand]

@Don : +1 ..got it ..thanks


On Wed, Nov 13, 2013 at 10:35 PM, Dave dave_and_da...@juno.com wrote:

 @Don: Excellent solution. It requires little extra data to be stored, and
 it is easy to implement.

 Dave

 On Wednesday, November 13, 2013 9:31:47 AM UTC-6, Don wrote:

 The data file contains the pre-order traversal. For each node indicate
 the contents of the node and two bits to indicate if it has a left and/or
 right subtree. I did this with a tree containing strings. Each node was one
 line in the file, with the first character being 'A' if the node is a leaf,
 'B' if it has only a left subtree, 'C' if it has only a right subtree, and
 'D' if it has both left and right subtrees. Then you read the line, store
 the string minus the first character, and recursively build the left and
 then right subtree, as appropriate.

 Don

 On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:

 @don : i did not get it , what will be data in file?


 On Mon, Nov 11, 2013 at 10:14 PM, Don dond...@gmail.com wrote:

 Save in preorder, tagging each node with two bits indicating if that
 node has a left and right subtree.

 Then rebuild like this:

 Tree rebuild()
 {
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;

 }

 On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will
 not work in this case.

 @kumar : save pre-order and in-order traversal with some delimiter in
 b/w traversals.

 pre-order : a b c d e
 in-order   : c b e a d

 write in file :-

 a b c d e # c b e a d

 now use pre-order and in-order traversal to re-create binary tree.

 2) consider null node as # ..now write in file preorder traversal.

 for eg :  a b c # # # d # #

 3) save level order traversal of binary tree, where each level uses
 # to distinguish between levels and * to mark null nodes
 eg : a # b c # e *
 a - level 1
 b c - level 2
 e NULL - level 3

 shortcoming in 2 and 3 is use of character that can be part of tree
 itself.So if node can contain # then you have to use some other
 character to distinguish.

 for solution 1 , you can write traversal in 2 lines instead of using
 #

 On 11/8/13, Vishnu vish...@gmail.com wrote:
  1) save the nodes(value, left and right pointer) in pre-order
 traversal
  2) also save pointers of all node in same order
 
  to restore
  1) create new N nodes
  2) do pointer mapping from old - new
  3) restore nodes and replace old pointers to new
 
 
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote:
 
  Save it in pre-order.
  Rebuild by inserting nodes in the order they occur in the file.
 
 
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:
 
  What is the effective way to save and restore the binary trees to
 files
  effectively?
 
 
 
 
 
 
 
 
 
 
 
 
 
  Regards,
  Kumar Raja.
 
   --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
 send an
  email to algogeeks+...@googlegroups.com.
 
 
 
 
  --
  Thanks,
  Vishnu
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
 send an
  email to algogeeks+...@googlegroups.com.
 

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@googlegroups.com.


  --
 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] Re: Saving and restoring Binary trees in files

[Don]

Save in preorder, tagging each node with two bits indicating if that node 
has a left and right subtree.

Then rebuild like this:

Tree rebuild()
{
   Tree result = readNode();
   Tree-left = hasLeftSubtree ? rebuild() : 0;
   Tree-right = hasRightSubtree ? rebuild() : 0;
   return result;
}

On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will 
 not work in this case. 

 @kumar : save pre-order and in-order traversal with some delimiter in 
 b/w traversals. 

 pre-order : a b c d e 
 in-order   : c b e a d 

 write in file :- 

 a b c d e # c b e a d 

 now use pre-order and in-order traversal to re-create binary tree. 

 2) consider null node as # ..now write in file preorder traversal. 

 for eg :  a b c # # # d # # 

 3) save level order traversal of binary tree, where each level uses 
 # to distinguish between levels and * to mark null nodes 
 eg : a # b c # e * 
 a - level 1 
 b c - level 2 
 e NULL - level 3 

 shortcoming in 2 and 3 is use of character that can be part of tree 
 itself.So if node can contain # then you have to use some other 
 character to distinguish. 

 for solution 1 , you can write traversal in 2 lines instead of using # 

 On 11/8/13, Vishnu vish...@gmail.com javascript: wrote: 
  1) save the nodes(value, left and right pointer) in pre-order traversal 
  2) also save pointers of all node in same order 
  
  to restore 
  1) create new N nodes 
  2) do pointer mapping from old - new 
  3) restore nodes and replace old pointers to new 
  
  
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com javascript: 
 wrote: 
  
  Save it in pre-order. 
  Rebuild by inserting nodes in the order they occur in the file. 
  
  
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote: 
  
  What is the effective way to save and restore the binary trees to 
 files 
  effectively? 
  
  
  
  
  
  
  
  
  
  
  
  
  
  Regards, 
  Kumar Raja. 
  
   -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, send 
 an 
  email to algogeeks+...@googlegroups.com javascript:. 
  
  
  
  
  -- 
  Thanks, 
  Vishnu 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, send 
 an 
  email to algogeeks+...@googlegroups.com javascript:. 
  


-- 
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] Re: Saving and restoring Binary trees in files

[atul anand]

@don : i did not get it , what will be data in file?


On Mon, Nov 11, 2013 at 10:14 PM, Don dondod...@gmail.com wrote:

 Save in preorder, tagging each node with two bits indicating if that node
 has a left and right subtree.

 Then rebuild like this:

 Tree rebuild()
 {
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;

 }

 On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will
 not work in this case.

 @kumar : save pre-order and in-order traversal with some delimiter in
 b/w traversals.

 pre-order : a b c d e
 in-order   : c b e a d

 write in file :-

 a b c d e # c b e a d

 now use pre-order and in-order traversal to re-create binary tree.

 2) consider null node as # ..now write in file preorder traversal.

 for eg :  a b c # # # d # #

 3) save level order traversal of binary tree, where each level uses
 # to distinguish between levels and * to mark null nodes
 eg : a # b c # e *
 a - level 1
 b c - level 2
 e NULL - level 3

 shortcoming in 2 and 3 is use of character that can be part of tree
 itself.So if node can contain # then you have to use some other
 character to distinguish.

 for solution 1 , you can write traversal in 2 lines instead of using #

 On 11/8/13, Vishnu vish...@gmail.com wrote:
  1) save the nodes(value, left and right pointer) in pre-order traversal
  2) also save pointers of all node in same order
 
  to restore
  1) create new N nodes
  2) do pointer mapping from old - new
  3) restore nodes and replace old pointers to new
 
 
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote:
 
  Save it in pre-order.
  Rebuild by inserting nodes in the order they occur in the file.
 
 
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:
 
  What is the effective way to save and restore the binary trees to
 files
  effectively?
 
 
 
 
 
 
 
 
 
 
 
 
 
  Regards,
  Kumar Raja.
 
   --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send
 an
  email to algogeeks+...@googlegroups.com.
 
 
 
 
  --
  Thanks,
  Vishnu
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send
 an
  email to algogeeks+...@googlegroups.com.
 

  --
 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] Re: Saving and restoring Binary trees in files

[Vishnu]

1) save the nodes(value, left and right pointer) in pre-order traversal
2) also save pointers of all node in same order

to restore
1) create new N nodes
2) do pointer mapping from old - new
3) restore nodes and replace old pointers to new


On Fri, Nov 8, 2013 at 8:50 PM, Don dondod...@gmail.com wrote:

 Save it in pre-order.
 Rebuild by inserting nodes in the order they occur in the file.


 On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:

 What is the effective way to save and restore the binary trees to files
 effectively?













 Regards,
 Kumar Raja.

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




-- 
Thanks,
Vishnu

-- 
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] Re: Saving and restoring Binary trees in files

[atul anand]

@don :  it is not BST ,  it is binary tree ...so your approach will
not work in this case.

@kumar : save pre-order and in-order traversal with some delimiter in
b/w traversals.

pre-order : a b c d e
in-order   : c b e a d

write in file :-

a b c d e # c b e a d

now use pre-order and in-order traversal to re-create binary tree.

2) consider null node as # ..now write in file preorder traversal.

for eg :  a b c # # # d # #

3) save level order traversal of binary tree, where each level uses
# to distinguish between levels and * to mark null nodes
eg : a # b c # e *
a - level 1
b c - level 2
e NULL - level 3

shortcoming in 2 and 3 is use of character that can be part of tree
itself.So if node can contain # then you have to use some other
character to distinguish.

for solution 1 , you can write traversal in 2 lines instead of using #

On 11/8/13, Vishnu vishnu...@gmail.com wrote:
 1) save the nodes(value, left and right pointer) in pre-order traversal
 2) also save pointers of all node in same order

 to restore
 1) create new N nodes
 2) do pointer mapping from old - new
 3) restore nodes and replace old pointers to new


 On Fri, Nov 8, 2013 at 8:50 PM, Don dondod...@gmail.com wrote:

 Save it in pre-order.
 Rebuild by inserting nodes in the order they occur in the file.


 On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote:

 What is the effective way to save and restore the binary trees to files
 effectively?













 Regards,
 Kumar Raja.

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




 --
 Thanks,
 Vishnu

 --
 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] Re: find the contiguous subarray which produce largest sum

[Ajay Jampale]

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/


On Fri, Aug 30, 2013 at 11:49 PM, Don dondod...@gmail.com wrote:

 Use Kadane's algorithm.
 http://en.wikipedia.org/wiki/Maximum_subarray_problem
 Don


 On Thursday, August 29, 2013 11:09:59 PM UTC-4, yash wrote:

 1. find largest sum contiguous subarray
 2. find the contiguous  subarray which produce largest sum

 Ex:
 a[7] = {2,1,-7,5,8,-1,-3}
 Ans is:  a[3] to a[5] and array is :{5,8} maxsum=13
 or pls find the minsum  and is a[2] ={-7}

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




-- 
Ajay A Jampale | Lead Engineer,
Samsung RD Institute,
Bangalore,India
M:+91.9741494304

-- 
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] Re: Algorithm page

[Wladimir Tavares]

http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Fjosephus-problem.html


http://translate.google.com.br/translate?hl=pt-BRsl=pttl=enu=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F08%2Flinks-da-semana-i.html


google translate doesn't translate page with mathjax :(

Wladimir Araujo Tavares
*Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*




On Tue, Mar 26, 2013 at 11:52 PM, Wladimir Tavares wladimir...@gmail.comwrote:


 http://translate.google.com.br/translate?hl=pt-BRsl=pttl=enu=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2013%2F03%2Fusando-busca-binaria-ensinando-pescar.html

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *




 On Thu, Jan 17, 2013 at 4:12 PM, Wladimir Tavares 
 wladimir...@gmail.comwrote:


 http://marathoncode.blogspot.com.br/2013/01/representacao-do-ponto-flutuante-em.html

 http://marathoncode.blogspot.com.br/2013/01/soma-de-subconjunto-subset-sum.html
 http://marathoncode.blogspot.com.br/2013/01/conjuntos-disjuntos.html

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *




 On Wed, Nov 28, 2012 at 12:56 PM, Wladimir Tavares wladimir...@gmail.com
  wrote:

 Exception C


 http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=http%3A%2F%2Fmarathoncode.blogspot.com.br%2F2012%2F11%2Fexcecoes-em-c.html

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *




 On Wed, Nov 28, 2012 at 8:32 AM, Wladimir Tavares wladimir...@gmail.com
  wrote:

 Simple problems on graphs


 http://translate.google.com.br/translate?sl=pttl=enjs=nprev=_thl=pt-BRie=UTF-8layout=2eotf=1u=marathoncode.blogspot.com.br%2F2012%2F11%2Fproblemas-em-grafos.html

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *




 On Tue, Sep 11, 2012 at 10:15 AM, Wladimir Tavares 
 wladimir...@gmail.com wrote:

 http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane.html
 http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane-2d.html


 http://marathoncode.blogspot.com.br/2012/08/as-proximas-cinco-linguagens-para-voce.html


 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *




 On Tue, Aug 28, 2012 at 11:10 PM, Wladimir Tavares 
 wladimir...@gmail.com wrote:

 http://marathoncode.blogspot.com.br/2012/08/ano-turing.html
 http://marathoncode.blogspot.com.br/2012/08/logaritmo-discreto.html

 http://marathoncode.blogspot.com.br/2012/08/registrador-de-deslocamento.html

 http://marathoncode.blogspot.com.br/2012/08/paradoxo-do-aniversario.html

 http://marathoncode.blogspot.com.br/2012/08/algoritmo-pollards-rho.html
 http://marathoncode.blogspot.com.br/2012/08/fatoracao-de-fermat.html








-- 
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] Re: Interview Question

[Ila Jain]

No distinction has been amongst stduents. I think it is abt incraesing the
distance between any two students.


On Sun, Jul 28, 2013 at 10:45 AM, Dave dave_and_da...@juno.com wrote:

 @Enchantress: I'm assuming that you are talking about cheating by copying
 from nearby students.

 If this is not the first exam, based on prior grades, put the A students
 in the back of the room, with the B students in front of the A students,
 the C students in front of the B students, the D students in front of the C
 students, and the F students in the front of the room.

 Put as many of the C students as you can in alternate seats, e.g., columns
 1, 3, 5,  If you can alternate all of the C students, put as many of
 the B students as you can in alternate seats. If you can alternate all of
 the B students, put as many of the D students as you can in alternate
 seats. If you can alternate all of the D students, put as many F students
 as you can in alternate seats. Finally, if you can alternate all of the F
 students, put as many A students as you can in alternate seats.

 Rationale: An A or B student won't copy from anyone else, because he
 doesn't want someone else's mistake to mess up his grade. The C students
 have the most to gain by copying, but they will be spread out as much as
 possible. The D and F students will have only D and F students to copy
 from, so they won't gain much from copying.

 Probably not the solution you were looking for, but I think an effective
 one.

 Dave

 On Saturday, July 27, 2013 1:02:11 PM UTC-5, enchantress wrote:

 Given m*n matrix and k students how can they be placed such that cheatig
 is minimised.


  --
 You received this message because you are subscribed to a topic in the
 Google Groups Algorithm Geeks group.
 To unsubscribe from this topic, visit
 https://groups.google.com/d/topic/algogeeks/l94hz2VTqWk/unsubscribe.
 To unsubscribe from this group and all its topics, 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] Re: why does this work?

[dinesh sohu]

Hi all,

Party at my house on 28 July, 5 pm.

Unlimited drinks.

All are welcome. :)

Regards,
Dinesh Sohu


On Thu, Jul 18, 2013 at 9:19 PM, Don dondod...@gmail.com wrote:

 When I try this using g++, *temp = 5; produces a segv.
 If it does not produce that result for you, perhaps it is because the
 optimizer optimizes the statement out. This might happen if the value is
 not used.

 Try this:

int *temp=0;
*temp = 5;
printf(I got here\n);
int x = *temp;
printf(%d\n, x);

 You know that x=*temp; will crash, but I'm guessing that it will not reach
 the first printf.

 Don


 On Thursday, July 18, 2013 9:33:51 AM UTC-4, phoenix wrote:


 I tried the following on ideone

 #include stdio.h
  int main(){
 int *temp;
 printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(value 
 is %p\n,temp);
 return 0;}


  it prints that :
 value is (nil)
 which am assuming is NULL

 if I try to print *temp it gives me segv which I would expect.

 However if I do something as
 *temp=5;

 it does not segv. How does this happen? If it was a NULL pointer it
 cannot dereference it right?

 Arun

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






-- 
*This e-mail is composed by-*
*Dinesh Sohu*
Business Technology Analyst,
Deloitte USI Pvt. Limited,
Udhyog Vihar IV, Gurgaon.
Contact: +91-9717220097

-- 
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] Re: why does this work?

[Don]

Just mail me a check for my drinks.
Thanks!
Don

On Thursday, July 18, 2013 2:43:46 PM UTC-4, .bashrc wrote:

 Hi all,

 Party at my house on 28 July, 5 pm.

 Unlimited drinks.

 All are welcome. :)

 Regards,
 Dinesh Sohu


 On Thu, Jul 18, 2013 at 9:19 PM, Don dond...@gmail.com javascript:wrote:

 When I try this using g++, *temp = 5; produces a segv.
 If it does not produce that result for you, perhaps it is because the 
 optimizer optimizes the statement out. This might happen if the value is 
 not used.

 Try this:

int *temp=0;
*temp = 5;
printf(I got here\n);
int x = *temp;
printf(%d\n, x);

 You know that x=*temp; will crash, but I'm guessing that it will not 
 reach the first printf.

 Don


 On Thursday, July 18, 2013 9:33:51 AM UTC-4, phoenix wrote:


 I tried the following on ideone

 #include stdio.h
  int main(){
 int *temp;
 printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(value
  is %p\n,temp);
 return 0;}

  
  it prints that :
 value is (nil)
 which am assuming is NULL

 if I try to print *temp it gives me segv which I would expect.

 However if I do something as
 *temp=5;

 it does not segv. How does this happen? If it was a NULL pointer it 
 cannot dereference it right?

 Arun

   -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




 -- 
 *This e-mail is composed by-*
 *Dinesh Sohu*
 Business Technology Analyst,
 Deloitte USI Pvt. Limited,
 Udhyog Vihar IV, Gurgaon.
 Contact: +91-9717220097
  

-- 
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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Dave]

@Don: You certainly can get by with only one workspace of size O(n). One 
side of the partitioning is done in-place, with the other side accumulated 
in the workspace and then copied back into the input array. That's a lot 
better than the O(n^2) worst case workspace required by your original 
algorithm.
 
Dave

On Tuesday, July 16, 2013 10:40:29 AM UTC-5, Don wrote:

 It definitely complicates things. I think that I would replaced the vector 
 parameters with pointers to the beginning and end of each array. The 
 partition is tricky because you need to make sure that both subtrees end up 
 in the same order they started in, which is difficult because most 
 partition algorithms are not stable. That's really the question I was 
 asking. Can you do that partition in place?

 Don


 On Sunday, July 14, 2013 2:48:46 PM UTC-4, sourabh wrote:

 You don't need to take vector for this you can have input in array also. 
 You just need to check the elements in each partition .
 On 12-Jul-2013 8:27 PM, Don dond...@gmail.com wrote:

 Can anyone modify this solution so that it does not duplicate the memory 
 at each level of recursion?

 (Here is my solution with the fix mentioned above)

 typedef std::vectorint btree;

 bool sameBstFormed(btree t1, btree t2)
 {
bool result;
if (t1.size() != t2.size()) result = false;
else if (t1.size() == 0) result = true;
else if (t1[0] != t2[0]) result = false;
else if (t1.size() == 1) result = true;
else
{
   btree left1, right1, left2, right2;
   for(int i = 1; i  t1.size(); ++i)
   {
  if (t1[i]  t1[0]) left1.push_back(t1[i]);
  else right1.push_back(t1[i]);
  if (t2[i]  t2[0]) left2.push_back(t2[i]);
  else right2.push_back(t2[i]);
   }
   result = sameBstFormed(left1, left2)  sameBstFormed(right1, 
 right2);
}
return result;
 }

 On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:

 Yes, you are right. Good catch.

 On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the 
 code: if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with 
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees 
 are equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, 
 right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding 
 whether the BSTs formed by the given input order would be identical or 
 not 
 without actually forming the tree? 

 Link: 
 http://www.careercup.**com**/question?id=19016700http://www.careercup.com/question?id=19016700
  
  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, 
 send an email to algogeeks+...@googlegroups.com**.
  
  


  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.
  
  



-- 
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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Don]

It definitely complicates things. I think that I would replaced the vector 
parameters with pointers to the beginning and end of each array. The 
partition is tricky because you need to make sure that both subtrees end up 
in the same order they started in, which is difficult because most 
partition algorithms are not stable. That's really the question I was 
asking. Can you do that partition in place?

Don


On Sunday, July 14, 2013 2:48:46 PM UTC-4, sourabh wrote:

 You don't need to take vector for this you can have input in array also. 
 You just need to check the elements in each partition .
 On 12-Jul-2013 8:27 PM, Don dond...@gmail.com javascript: wrote:

 Can anyone modify this solution so that it does not duplicate the memory 
 at each level of recursion?

 (Here is my solution with the fix mentioned above)

 typedef std::vectorint btree;

 bool sameBstFormed(btree t1, btree t2)
 {
bool result;
if (t1.size() != t2.size()) result = false;
else if (t1.size() == 0) result = true;
else if (t1[0] != t2[0]) result = false;
else if (t1.size() == 1) result = true;
else
{
   btree left1, right1, left2, right2;
   for(int i = 1; i  t1.size(); ++i)
   {
  if (t1[i]  t1[0]) left1.push_back(t1[i]);
  else right1.push_back(t1[i]);
  if (t2[i]  t2[0]) left2.push_back(t2[i]);
  else right2.push_back(t2[i]);
   }
   result = sameBstFormed(left1, left2)  sameBstFormed(right1, 
 right2);
}
return result;
 }

 On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:

 Yes, you are right. Good catch.

 On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the 
 code: if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with 
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees 
 are equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding 
 whether the BSTs formed by the given input order would be identical or 
 not 
 without actually forming the tree? 

 Link: 
 http://www.careercup.**com**/question?id=19016700http://www.careercup.com/question?id=19016700
  
  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com**.
  
  


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  



-- 
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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[sourabh jain]

You don't need to take vector for this you can have input in array also.
You just need to check the elements in each partition .
On 12-Jul-2013 8:27 PM, Don dondod...@gmail.com wrote:

 Can anyone modify this solution so that it does not duplicate the memory
 at each level of recursion?

 (Here is my solution with the fix mentioned above)

 typedef std::vectorint btree;

 bool sameBstFormed(btree t1, btree t2)
 {
bool result;
if (t1.size() != t2.size()) result = false;
else if (t1.size() == 0) result = true;
else if (t1[0] != t2[0]) result = false;
else if (t1.size() == 1) result = true;
else
{
   btree left1, right1, left2, right2;
   for(int i = 1; i  t1.size(); ++i)
   {
  if (t1[i]  t1[0]) left1.push_back(t1[i]);
  else right1.push_back(t1[i]);
  if (t2[i]  t2[0]) left2.push_back(t2[i]);
  else right2.push_back(t2[i]);
   }
   result = sameBstFormed(left1, left2)  sameBstFormed(right1,
 right2);
}
return result;
 }

 On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:

 Yes, you are right. Good catch.

 On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the
 code: if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees
 are equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding
 whether the BSTs formed by the given input order would be identical or not
 without actually forming the tree?

 Link: 
 http://www.careercup.**com**/question?id=19016700http://www.careercup.com/question?id=19016700

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@googlegroups.com**.




  --
 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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Don]

Can anyone modify this solution so that it does not duplicate the memory at 
each level of recursion?

(Here is my solution with the fix mentioned above)

typedef std::vectorint btree;

bool sameBstFormed(btree t1, btree t2)
{
   bool result;
   if (t1.size() != t2.size()) result = false;
   else if (t1.size() == 0) result = true;
   else if (t1[0] != t2[0]) result = false;
   else if (t1.size() == 1) result = true;
   else
   {
  btree left1, right1, left2, right2;
  for(int i = 1; i  t1.size(); ++i)
  {
 if (t1[i]  t1[0]) left1.push_back(t1[i]);
 else right1.push_back(t1[i]);
 if (t2[i]  t2[0]) left2.push_back(t2[i]);
 else right2.push_back(t2[i]);
  }
  result = sameBstFormed(left1, left2)  sameBstFormed(right1, right2);
   }
   return result;
}

On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:

 Yes, you are right. Good catch.

 On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the code: 
 if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with 
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees 
 are equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding 
 whether the BSTs formed by the given input order would be identical or not 
 without actually forming the tree? 

 Link: 
 http://www.careercup.**com/question?id=19016700http://www.careercup.com/question?id=19016700
  
  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.
  
  




-- 
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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Sambhavna Singh]

Amazing solution Don, thank you :)  You missed a small check in the code:
if(t1[0] != t2[0]) return 0;


On Tue, Jul 9, 2013 at 11:27 PM, Don dondod...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with different
 number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees are
 equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding
 whether the BSTs formed by the given input order would be identical or not
 without actually forming the tree?

 Link: 
 http://www.careercup.**com/question?id=19016700http://www.careercup.com/question?id=19016700

  --
 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] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Don]

Yes, you are right. Good catch.

On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the code: 
 if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com javascript:wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with 
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees are 
 equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding 
 whether the BSTs formed by the given input order would be identical or not 
 without actually forming the tree? 

 Link: 
 http://www.careercup.**com/question?id=19016700http://www.careercup.com/question?id=19016700
  
  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




-- 
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] Re:

[shubham saini]

thanx Don for your algos, bt i m not able to understand your second
approach can you please explain it a liitle


On Fri, Jun 21, 2013 at 9:50 PM, Don dondod...@gmail.com wrote:

 int bitCount(int n)
 {
if (n  3) return n;
int x=31-__builtin_clz(n);
n -= 1x;
return x*(1(x-1)) + bitCount(n) + n + 1;

  }

 On Thursday, June 20, 2013 11:03:35 PM UTC-4, shubham saini wrote:

 How to count no of set bits for all numbers from 1 to n for a given n...

 i knew brute force any better solution ??

  --
 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] Re:

[Don]

The n3 condition is the base case. For n=0,1, or 2 the answer is n.

x is floor(log2(n))

This can be computed in constant time by the built in function provided. It 
is the same as the position of the highest bit set in n.

Then the number of bits in 0..n is the number of times the xth bit is set 
plus the number of bits in 0..n-2^x. That is what the last line computes.

Don

On Friday, June 21, 2013 1:42:08 PM UTC-4, shubham saini wrote:

 thanx Don for your algos, bt i m not able to understand your second 
 approach can you please explain it a liitle


 On Fri, Jun 21, 2013 at 9:50 PM, Don dond...@gmail.com javascript:wrote:

 int bitCount(int n)
 {
if (n  3) return n;
int x=31-__builtin_clz(n);
n -= 1x;
return x*(1(x-1)) + bitCount(n) + n + 1;

  }

 On Thursday, June 20, 2013 11:03:35 PM UTC-4, shubham saini wrote:

 How to count no of set bits for all numbers from 1 to n for a given n...

 i knew brute force any better solution ?? 

  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




-- 
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] Re:

[sourabh jain]

here is the code ... my solution covers the range for all integers ..

#include stdio.h
#include string.h
#include math.h
#include stdlib.h
int BT[256];
int main(){
int t=0;
BT[0]=0;
for (int i = 0; i  256; i++){
  BT[i] = (i  1) + BT[i / 2];
}
 int s=1;
int e=0;
//scanf(%d,s); //not reading s here just keeping it 1
 scanf(%d,e);
//printf(%d %d,s,e);
int range=e-s;
 int i=0;
int ct=0;
for(i=0;i=range;i++){
 unsigned int v=s+i;
 ct+=BT[v  0xff] +  BT[(v  8)  0xff] +   BT[(v  16)  0xff] +  BT[v
 24];

printf(%d\n,ct);
}
return 0;
}


On Fri, Jun 21, 2013 at 11:44 PM, Don dondod...@gmail.com wrote:

 The n3 condition is the base case. For n=0,1, or 2 the answer is n.

 x is floor(log2(n))

 This can be computed in constant time by the built in function provided.
 It is the same as the position of the highest bit set in n.

 Then the number of bits in 0..n is the number of times the xth bit is set
 plus the number of bits in 0..n-2^x. That is what the last line computes.

 Don


 On Friday, June 21, 2013 1:42:08 PM UTC-4, shubham saini wrote:

 thanx Don for your algos, bt i m not able to understand your second
 approach can you please explain it a liitle


 On Fri, Jun 21, 2013 at 9:50 PM, Don dond...@gmail.com wrote:

 int bitCount(int n)
 {
if (n  3) return n;
int x=31-__builtin_clz(n);
n -= 1x;
return x*(1(x-1)) + bitCount(n) + n + 1;

  }

 On Thursday, June 20, 2013 11:03:35 PM UTC-4, shubham saini wrote:

 How to count no of set bits for all numbers from 1 to n for a given n...

 i knew brute force any better solution ??

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.




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






-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
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] Re: Sorting a very large number of intergers

[Roberto Abreu]

I agree with what Don said.

Furhter, I would recommend going to http://sortbenchmark.org/ and reading
through some of the papers.

Cheers,
Roberto Abreu





On Thu, Jun 13, 2013 at 3:34 PM, Don dondod...@gmail.com wrote:

 I should mention that this process is file I/O bound, so having four
 threads will not help significantly unless each thread can use a
 different disk device.
 Don

 On Jun 13, 3:31 pm, Don dondod...@gmail.com wrote:
  I would suggest splitting the data into four pieces and having each
  thread do an external sort on one piece. Essentially that means
  breaking up the data into chunks which can be stored in memory,
  sorting them, and then merging the chunks back into one piece. After
  the 4 threads are done sorting their piece, use two threads to merge
  the four pieces into two pieces, and then use one thread to merge
  those into the one final output file.
 
  On Jun 13, 5:06 am, MAC macatad...@gmail.com wrote:
 
 
 
 
 
 
 
   How would one sort 1 billion integers.  .. I gave external sorting
 answer
   but he waned more .. What should i say ?
 
   Asked me to tell him how would the problem change  if total of  4
 threads
   are given. How would you solve ?
 
   thanks
   --mac

 --
 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] Re: Intrestting problem

[Nishant Pandey]

juat want to ask why the last region was not flipped from o to x?


On Tue, Jun 11, 2013 at 11:57 PM, Don dondod...@gmail.com wrote:

 // Flip a region including location (x,y) from from to to.
 // Returns true if region is surrounded.
 bool flip(char board[][], int n, int x, int y, char from, char to)
 {
if ((x = 0)  (y = 0)  (x  n)  (y  n)) return false;
if (board[x][y] != from) return true;
board[x][y] = to;
return flip(board,n,x-1,y)  flip(board,n,x+1,y) 
 flip(board,n,x,y-1)  flip(board,n,x,y+1);
 }

 // Flips all regions of 'O' completely surrounded by 'X' to 'X'
 void captureSurrounded(char board[][], int n, int x, int y)
 {
 int x,y;
 for(x = 0; x  n; ++x)
for(y = 0; y  n; ++y)
if (flip(board,n,x,y,'O','v'))
flip(board,n,x,y, 'v', 'X');

 // Set regions not surrounded back to 'O'
 for(x = 0; x  n; ++x)
for(y = 0; y  n; ++y)
if (board[x][y] == 'v') board[x][y] = 'O';
 }

 On Jun 11, 3:05 am, Jai Shri Ram del7...@gmail.com wrote:
  Given a 2D board containing 'X' and 'O', capture all regions surrounded
 by
  'X'.
 
  A region is captured by flipping all 'O's into 'X's in that surrounded
  region .
 
  For example,
 
  X X X X
  X O O X
  X X O X
  X O X X
 
  After running your function, the board should be:
 
  X X X X
  X X X X
  X X X X
  X O X X

 --
 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] Re: Median of two sorted arrays of different sizes

[Abhirup Ghosh]

How is this code dealing with the scenario where two arrays have common
number. For example where two arrays are same. A[] = {1,2,3,4} and B[] =
{1,2,3,4}. Here the median position is not (4+4)/2 rather it is 4/2.



On Sun, Jun 9, 2013 at 3:12 PM, rahul sharma rahul23111...@gmail.comwrote:

 @doncan u plz explain the approach used.I didnt get this.

 On 4/25/13, Don dondod...@gmail.com wrote:
  Let's say you have two arrays: A[x] and B[y].
  The median is the (x+y)/2th value.
  If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
  A[i].
  You can use a binary search to find the point where that condition
  occurs. Of course you want to search on the smaller array.
  You'll need some logic at the end to determine if the median is in A
  or in B.
 
  // Input arrays A and B, sizeA = sizeB
  int A[sizeA];
  int B[sizeB];
 
  int min = 0;
  int max = sizeA;
  const int medianPos = (sizeA + sizeB) / 2;
  while(max = min)
  {
i = (min + max) / 2;
j = medianPos-i;
if (B[j]  A[i]) min = i+1;
else if (B[j+1]  A[i]) max = i-1;
else break;
  }
 
  printf(Median is %d\n, (A[i]  B[j]) ? A[i] : B[j]);
 
  Don
 
  On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
  IS this code correct?
 
  float findMedianUtil( int A[], int N, int B[], int M )
  {
  // If the smaller array has only one element
  if( N == 1 )
  {
  // Case 1: If the larger array also has one element, simply call
  MO2()
  if( M == 1 )
  return MO2( A[0], B[0] );
 
  // Case 2: If the larger array has odd number of elements, then
  consider
  // the middle 3 elements of larger array and the only element of
  // smaller array. Take few examples like following
  // A = {9}, B[] = {5, 8, 10, 20, 30} and
  // A[] = {1}, B[] = {5, 8, 10, 20, 30}
  if( M  1 )
  return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
 
  // Case 3: If the larger array has even number of element, then
  median
  // will be one of the following 3 elements
  // ... The middle two elements of larger array
  // ... The only element of smaller array
  return MO3( B[M/2], B[M/2 - 1], A[0] );
  }
 
  // If the smaller array has two elements
  else if( N == 2 )
  {
  // Case 4: If the larger array also has two elements, simply
 call
  MO4()
  if( M == 2 )
  return MO4( A[0], A[1], B[0], B[1] );
 
  // Case 5: If the larger array has odd number of elements, then
  median
  // will be one of the following 3 elements
  // 1. Middle element of larger array
  // 2. Max of first element of smaller array and element just
  //before the middle in bigger array
  // 3. Min of second element of smaller array and element just
  //after the middle in bigger array
  if( M  1 )
  return MO3 ( B[M/2],
   max( A[0], B[M/2 - 1] ),
   min( A[1], B[M/2 + 1] )
 );
 
  // Case 6: If the larger array has even number of elements, then
  // median will be one of the following 4 elements
  // 1)  2) The middle two elements of larger array
  // 3) Max of first element of smaller array and element
  //just before the first middle element in bigger array
  // 4. Min of second element of smaller array and element
  //just after the second middle in bigger array
  return MO4 ( B[M/2],
   B[M/2 - 1],
   max( A[0], B[M/2 - 2] ),
   min( A[1], B[M/2 + 1] )
 );
  }
 
  int idxA = ( N - 1 ) / 2;
  int idxB = ( M - 1 ) / 2;
 
   /* if A[idxA] = B[idxB], then median must exist in
  A[idxA] and B[idxB] */
  if( A[idxA] = B[idxB] )
  return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
 
  /* if A[idxA]  B[idxB], then median must exist in
 A[...idxA] and B[idxB] */
  return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
 
  }
 
  In the end I suspect the following part:-
 
if( A[idxA] = B[idxB] )
  return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
 
  /* if A[idxA]  B[idxB], then median must exist in
 A[...idxA] and B[idxB] */
  return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
 
  plz comment
 
  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send an
  email to algogeeks+unsubscr...@googlegroups.com.
  For more options, visit https://groups.google.com/groups/opt_out.
 
 
 

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, 

Re: [algogeeks] Re: Max-Overlapping Intervals

[Ritesh Mishra]

it is better to use Binary Index Tree ( Fenwick Tree) with time complexity
O(log n) to update and O(n * log n) for finding max overlapping interval .
http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=binaryIndexedTrees
this link can be useful for understanding how it will work.

Regards,

Ritesh Kumar Mishra
Information Technology
Third Year Undergraduate
MNNIT Allahabad


On Mon, Feb 25, 2013 at 10:46 AM, Sairam ravu...@gmail.com wrote:

 First sort the intervals

 So, in our example it will be as follows
 (2,7),(5,10),(6,15).

 make a map which has got interval with corresponding number of overlaps
 Now, iterate through each of the interval
  for(i=0;i(n-1);i++)
   for(j=0;jn;j++)
  update the map with the number of overlaps.





 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an
 email to algogeeks+unsubscr...@googlegroups.com.
 For more options, visit https://groups.google.com/groups/opt_out.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

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

[Avi Dullu]

Can you tell the 'size' of your array 'f' if the intervals are [0, 10],
[10, 9223372036854775808] ?

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 Mon, Jun 10, 2013 at 10:12 PM, sunny sharadsin...@gmail.com wrote:

 yeah interval tree and binary indexed tree is a one solution which will
 give you answer in log(n) time for each query ,but if i got all the
 interval at the beigning of time i can get solution in O(1) time by O(n
 ) preprocessing take array f initialize with zero,now for each
 interval(l,r) do f[l]++ and f[r+1]--  once you are done wi all queries take
 prefix sum value of each index will tell you in how many interval it was


 On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, 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] Re: Median of two sorted arrays of different sizes

[rahul sharma]

@doncan u plz explain the approach used.I didnt get this.

On 4/25/13, Don dondod...@gmail.com wrote:
 Let's say you have two arrays: A[x] and B[y].
 The median is the (x+y)/2th value.
 If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
 A[i].
 You can use a binary search to find the point where that condition
 occurs. Of course you want to search on the smaller array.
 You'll need some logic at the end to determine if the median is in A
 or in B.

 // Input arrays A and B, sizeA = sizeB
 int A[sizeA];
 int B[sizeB];

 int min = 0;
 int max = sizeA;
 const int medianPos = (sizeA + sizeB) / 2;
 while(max = min)
 {
   i = (min + max) / 2;
   j = medianPos-i;
   if (B[j]  A[i]) min = i+1;
   else if (B[j+1]  A[i]) max = i-1;
   else break;
 }

 printf(Median is %d\n, (A[i]  B[j]) ? A[i] : B[j]);

 Don

 On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
 IS this code correct?

 float findMedianUtil( int A[], int N, int B[], int M )
 {
     // If the smaller array has only one element
     if( N == 1 )
     {
         // Case 1: If the larger array also has one element, simply call
 MO2()
         if( M == 1 )
             return MO2( A[0], B[0] );

         // Case 2: If the larger array has odd number of elements, then
 consider
         // the middle 3 elements of larger array and the only element of
         // smaller array. Take few examples like following
         // A = {9}, B[] = {5, 8, 10, 20, 30} and
         // A[] = {1}, B[] = {5, 8, 10, 20, 30}
         if( M  1 )
             return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );

         // Case 3: If the larger array has even number of element, then
 median
         // will be one of the following 3 elements
         // ... The middle two elements of larger array
         // ... The only element of smaller array
         return MO3( B[M/2], B[M/2 - 1], A[0] );
     }

     // If the smaller array has two elements
     else if( N == 2 )
     {
         // Case 4: If the larger array also has two elements, simply call
 MO4()
         if( M == 2 )
             return MO4( A[0], A[1], B[0], B[1] );

         // Case 5: If the larger array has odd number of elements, then
 median
         // will be one of the following 3 elements
         // 1. Middle element of larger array
         // 2. Max of first element of smaller array and element just
         //    before the middle in bigger array
         // 3. Min of second element of smaller array and element just
         //    after the middle in bigger array
         if( M  1 )
             return MO3 ( B[M/2],
                          max( A[0], B[M/2 - 1] ),
                          min( A[1], B[M/2 + 1] )
                        );

         // Case 6: If the larger array has even number of elements, then
         // median will be one of the following 4 elements
         // 1)  2) The middle two elements of larger array
         // 3) Max of first element of smaller array and element
         //    just before the first middle element in bigger array
         // 4. Min of second element of smaller array and element
         //    just after the second middle in bigger array
         return MO4 ( B[M/2],
                      B[M/2 - 1],
                      max( A[0], B[M/2 - 2] ),
                      min( A[1], B[M/2 + 1] )
                    );
     }

     int idxA = ( N - 1 ) / 2;
     int idxB = ( M - 1 ) / 2;

      /* if A[idxA] = B[idxB], then median must exist in
         A[idxA] and B[idxB] */
     if( A[idxA] = B[idxB] )
         return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );

     /* if A[idxA]  B[idxB], then median must exist in
        A[...idxA] and B[idxB] */
     return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );

 }

 In the end I suspect the following part:-

   if( A[idxA] = B[idxB] )
         return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );

     /* if A[idxA]  B[idxB], then median must exist in
        A[...idxA] and B[idxB] */
     return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );

 plz comment

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an
 email to algogeeks+unsubscr...@googlegroups.com.
 For more options, visit https://groups.google.com/groups/opt_out.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: t9 dictionary

[sourabh jain]

hi this is my java implementation of trie with 26 keys.

public class Trie {
public Trie [] childs;
char data;
 boolean isEnd;
TreeSetString ts;
String possiblity;
 public Trie(){
childs=new Trie[26];
isEnd=false;
 ts=new TreeSetString();
}
public void add(String s){
 char ar[]=s.toLowerCase().toCharArray();
 StringBuffer sb=new StringBuffer();
 for(int i=0;iar.length;i++){
if('a'=ar[i]  'z'=ar[i]){
sb.append(ar[i]);
 }else if('A'=ar[i]  'Z'=ar[i]){
sb.append((char)('a'+ar[i]-'A'));
 }
}
ar=sb.toString().toCharArray();
if(ar.length1) return;
 ts.add(sb.toString());
_add(this,ar,0);
 }
public void _add(Trie root,char ar[],int index){
if(root.childs[ar[index]-'a']==null){
 root.childs[ar[index]-'a']=new Trie();
root.childs[ar[index]-'a'].data=ar[index];
 }
 if(ar.length-1==index){
root.childs[ar[index]-'a'].isEnd=true;
 root.childs[ar[index]-'a'].possiblity=new String(ar);
return;
}
 _add(root.childs[ar[index]-'a'],ar,index+1);
}
public boolean search(String s){
 if(s.indexOf( )!=-1){ System.out.println(s); return;}
char ar[]=s.toLowerCase().toCharArray();
 if( _search(this,ar,0)){
return true;
}
return false;
 }
 public boolean _search(Trie root,char ar[],int index){
 if(index = ar.length) return false;
if(root==null) return false;
return (index==ar.length-1  root.childs[ar[index]-'a']!=null 
root.childs[ar[index]-'a'].isEnd)? true:
_search(root.childs[ar[index]-'a'],ar,index+1);
 }
}


On Mon, Jun 3, 2013 at 11:22 PM, rahul sharma rahul23111...@gmail.comwrote:

 Can i implement by trie which is having structure as 9 pointers for 9
 digits..like if it comes 4663...i will make a path 4663 from root to leaf
 and in end i will have a linked list to store dataany more optimized
 solution anyone having???plz suggest


 On Thu, May 30, 2013 at 2:37 AM, rahul sharma rahul23111...@gmail.comwrote:

 how to implement with trie.???is trie the best way..plz provide me raw
 algo to start with,


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






-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
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] Re: searching all matching words in a Trie with a given filter.

[avinesh saini]

@Rahul,  The problem is to get all the words matching to a given filter
like *...n..p  *from already built trie.

@Don, I'm storing words at the ending node, now I'm trying to modify this
function so that it returns only one random word from all words matching
that filter with equal probability for each word, I'm trying like this

char* randomWord(trie *root, char *k)
{
int m;
if(!root || flag) return;

if(*k == '\0') {
if(root-word) {
strcpy(mWord,root-word);   // storing the random word
in mWord.
flag = 1;
}
return;
}
else if(*k == '.') {
for(m=0;m26;m++) {
if(root-children[mark[m]]){//
 where mark[26] is an array containing numbers [0,1,2,.,25] on random
indices.
randomWord(root-children[mark[m]],k+1);
}
}
randomize();   //
 randomize function shuffles mark[].
}
else
randomWord(root-children[*k-'a'],k+1);
}

But this is not giving words with equal probability. It is returning words
more frequently which are having consecutive same letters.


On Thu, May 30, 2013 at 2:34 AM, rahul sharma rahul23111...@gmail.comwrote:

 wat exaclty the question is.
 We have to make a tire with filter or we have a trie(whole dictionary) and
 we have to check filter out the elements.

 plz explain question


 On Wed, May 29, 2013 at 7:55 PM, Don dondod...@gmail.com wrote:

 There has to be some way to know that a node is the end of a word, and
 to know what that word is. This might be done by using a parent
 pointer which lets you traverse the trie back to the root, rebuilding
 the word, or you could keep track of the word as you traverse down the
 trie. Putting the whole word in the node where the word ends would be
 the most simple and time-efficient approach, if you have the memory to
 support it.

 Here is a different way to do it, if the trie has a wordEnd flag and
 does not store the word in the node.

 void findWords(trie *root, char *filter, String word=)
 {
 if (!root) return;

 if (*filter == 0)  // When you reach the end of the filter at the
 end of a valid word, add the word.
 {
 if (root-wordEnd) words.add(word);
 }
 else if (*filter == '.')   // Search for words with any letter
 {
 for(int i = 'a'; i = 'z' ; ++i)
 findWords(root-link[i], filter+1, word+i);
 }
 else  // Search for words with the required letter
 {
  findWords(root-link[*filter], filter+1, word+*filter);
 }
 }

 On May 28, 11:36 pm, avinesh saini avinesh.sa...@gmail.com wrote:
  Thank you Don, I was also trying in similar way. But here I'm confused
 how
  you are storing the traversed words. Are you adding whole words at the
 node
  on which word is ending during insertion.
 
 
 
 
 
 
 
 
 
  On Wed, May 29, 2013 at 12:36 AM, Don dondod...@gmail.com wrote:
   void findWords(trie *root, char *filter)
   {
   if (!root) return;
 
   if (*filter == 0)  // When you reach the end of the filter at the
   end of a valid word, add the word.
   {
   if (root-words) words.add(root-word);
   }
   else if (*filter == '.')   // Search for words with any letter
   {
   for(int i = 'a'; i = 'z' ; ++i)
   findWords(root-link[i], filter+1);
   }
   else  // Search for words with the required letter
   {
findWords(root-link[*filter], filter+1);
   }
   }
 
   On May 28, 4:47 am, avinesh saini avinesh.sa...@gmail.com wrote:
How to search all the matching words for a filter in a trie.
e.g.
searching by filter  ...r..m will find all the words(of length =
 7) in
trie in which 4th character is 'r' and 7th character is 'm'.
 
--
*
*
*thanks  regards,*
*Avinesh
*
 
   --
   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.
 
  --
  *
  *
  *thanks  regards,*
  *Avinesh
  *

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






-- 
*
*
*regards,*
*Avinesh Kumar
National Institute of Technology, Calicut.*
*Kerala- 673601*
*+91 7849080702*
*http://www.facebook.com/avinesh.saini*

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

Re: [algogeeks] Re: searching all matching words in a Trie with a given filter.

[rahul sharma]

wat exaclty the question is.
We have to make a tire with filter or we have a trie(whole dictionary) and
we have to check filter out the elements.

plz explain question


On Wed, May 29, 2013 at 7:55 PM, Don dondod...@gmail.com wrote:

 There has to be some way to know that a node is the end of a word, and
 to know what that word is. This might be done by using a parent
 pointer which lets you traverse the trie back to the root, rebuilding
 the word, or you could keep track of the word as you traverse down the
 trie. Putting the whole word in the node where the word ends would be
 the most simple and time-efficient approach, if you have the memory to
 support it.

 Here is a different way to do it, if the trie has a wordEnd flag and
 does not store the word in the node.

 void findWords(trie *root, char *filter, String word=)
 {
 if (!root) return;

 if (*filter == 0)  // When you reach the end of the filter at the
 end of a valid word, add the word.
 {
 if (root-wordEnd) words.add(word);
 }
 else if (*filter == '.')   // Search for words with any letter
 {
 for(int i = 'a'; i = 'z' ; ++i)
 findWords(root-link[i], filter+1, word+i);
 }
 else  // Search for words with the required letter
 {
  findWords(root-link[*filter], filter+1, word+*filter);
 }
 }

 On May 28, 11:36 pm, avinesh saini avinesh.sa...@gmail.com wrote:
  Thank you Don, I was also trying in similar way. But here I'm confused
 how
  you are storing the traversed words. Are you adding whole words at the
 node
  on which word is ending during insertion.
 
 
 
 
 
 
 
 
 
  On Wed, May 29, 2013 at 12:36 AM, Don dondod...@gmail.com wrote:
   void findWords(trie *root, char *filter)
   {
   if (!root) return;
 
   if (*filter == 0)  // When you reach the end of the filter at the
   end of a valid word, add the word.
   {
   if (root-words) words.add(root-word);
   }
   else if (*filter == '.')   // Search for words with any letter
   {
   for(int i = 'a'; i = 'z' ; ++i)
   findWords(root-link[i], filter+1);
   }
   else  // Search for words with the required letter
   {
findWords(root-link[*filter], filter+1);
   }
   }
 
   On May 28, 4:47 am, avinesh saini avinesh.sa...@gmail.com wrote:
How to search all the matching words for a filter in a trie.
e.g.
searching by filter  ...r..m will find all the words(of length =
 7) in
trie in which 4th character is 'r' and 7th character is 'm'.
 
--
*
*
*thanks  regards,*
*Avinesh
*
 
   --
   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.
 
  --
  *
  *
  *thanks  regards,*
  *Avinesh
  *

 --
 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] Re: Highest reminder

[Ankit Sambyal]

Hi Ankit,

If that is the case, I can very well say, 23 = 2 X 1 + 21

If you divide 23 by 11, remainder would be 1 and not 12.


On Thu, May 30, 2013 at 1:16 PM, Ankit Agarwal ankuagarw...@gmail.comwrote:

 Hi,

 23 = 11 X 1 + 12. Thus 12  would the highest remainder. Not 11



 On Thu, May 30, 2013 at 10:24 AM, Sreenivas Sigharam 
 sighar...@gmail.comwrote:

 Dave's explanation was clear..and informative.. Thank you Dave..

 Thank you , Soumya Prasad, for a simple but nice topic..

 Thank you,
 Sigharam.


 On Thu, May 30, 2013 at 10:16 AM, Sanjay Rajpal sanjay.raj...@live.inwrote:

 Hi Ankit,

 for 23, how can the remainder be 12 ? Can you elaborate more ?

 *Regards,*
 *Sanjay Kumar*
 *Software Engineer(Development)*
 *Winshuttle Softwares(India) Pvt. Ltd.*
 *Mobile +91-89012-36292, +91-80535-66286*
 *Email: sanjay.ku...@winshuttle.com*
 *
 ***

 * *

 **
 *
 *


 On Thu, May 30, 2013 at 9:40 AM, Ankit Agarwal 
 ankuagarw...@gmail.comwrote:

 @Dave:

 For N = 23, the highest remainder is 12, not 11


 On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote:

 The highest remainder when dividing n by a number less than n is
 floor((n-1)/2).
 For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
 For n = 17, floor((17-1)/2) = 8
 For n = 23, floor((23-1)/2) = 11

 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
 Etc.

 Dave


 On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal ankitsam...@gmail.com
  wrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but
 your formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar 
 niksin...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and
 we need greatest remainder, so we need the least no. which will give 
 the
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be
  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil
 wrote:


 For a given number when divided by a number between 1 and n. I
 figured out that highest reminder can be got if I divide the number by
 (⌊(n/2)⌋+1) .Can anyone give me pointers ?

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it,
 send an email to algogeeks+...@**googlegroups.com.




  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it,
 send an email to algogeeks+...@**googlegroups.com.






 --

 *Ankit Agarwal*


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






 --

 *Ankit Agarwal*
 *Software Engineer*
 *Datacenter  Cloud Division*
 *Citrix RD India Pvt. Ltd.*
 *Ph. No. +91-8095470278*

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




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






 --

 *Ankit Agarwal*


  --
 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] Re: Array Problem

[avinesh saini]

I was going through this problem on stackoverflow, and I found this classic
article on this very topic

http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem

Definitely, worth a read.




-- 
*
*
*thanks  regards,*
*Avinesh Kumar
National Institute of Technology, Calicut.*
*Kerala- 673601*
*+91 7849080702*

-- 
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] Re: Highest reminder

[Ankit Agarwal]

Hi,

23 = 11 X 1 + 12. Thus 12  would the highest remainder. Not 11



On Thu, May 30, 2013 at 10:24 AM, Sreenivas Sigharam sighar...@gmail.comwrote:

 Dave's explanation was clear..and informative.. Thank you Dave..

 Thank you , Soumya Prasad, for a simple but nice topic..

 Thank you,
 Sigharam.


 On Thu, May 30, 2013 at 10:16 AM, Sanjay Rajpal sanjay.raj...@live.inwrote:

 Hi Ankit,

 for 23, how can the remainder be 12 ? Can you elaborate more ?

 *Regards,*
 *Sanjay Kumar*
 *Software Engineer(Development)*
 *Winshuttle Softwares(India) Pvt. Ltd.*
 *Mobile +91-89012-36292, +91-80535-66286*
 *Email: sanjay.ku...@winshuttle.com*
 *
 ***

 * *

 **
 *
 *


 On Thu, May 30, 2013 at 9:40 AM, Ankit Agarwal ankuagarw...@gmail.comwrote:

 @Dave:

 For N = 23, the highest remainder is 12, not 11


 On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote:

 The highest remainder when dividing n by a number less than n is
 floor((n-1)/2).
 For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
 For n = 17, floor((17-1)/2) = 8
 For n = 23, floor((23-1)/2) = 11

 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
 Etc.

 Dave


 On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal 
 ankitsam...@gmail.comwrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but
 your formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksin...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we
 need greatest remainder, so we need the least no. which will give the
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be
  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I
 figured out that highest reminder can be got if I divide the number by
 (⌊(n/2)⌋+1) .Can anyone give me pointers ?

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it,
 send an email to algogeeks+...@**googlegroups.com.




  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it,
 send an email to algogeeks+...@**googlegroups.com.






 --

 *Ankit Agarwal*


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






 --

 *Ankit Agarwal*
 *Software Engineer*
 *Datacenter  Cloud Division*
 *Citrix RD India Pvt. Ltd.*
 *Ph. No. +91-8095470278*

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




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






-- 

*Ankit Agarwal*

-- 
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] Re: Highest reminder

[Sanjay Rajpal]

23 =  11 * 2 + 1

-- 
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] Re: Highest reminder

[Ankit Sambyal]

Hi Nikhil,

Highest remainder can't be floor(n/2) - 1.
If n = 11, highest remainder would be 5 when it is divided by 6, but your
formula gives 4.


On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksingha...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we need
 greatest remainder, so we need the least no. which will give the quotient 1
 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I figured
 out that highest reminder can be got if I divide the number by (⌊(n/2)⌋+1
 ) .Can anyone give me pointers ?

  --
 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] Re: Highest reminder

[Ankit Agarwal]

Hi,

Number 23: =  11 * 1 + 12   Number/2 = 11.5

Number 17: = 9 * 1 + 8   Number/2 = 8.5

So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal
ankitsambyal1...@gmail.comwrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but your
 formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksingha...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we need
 greatest remainder, so we need the least no. which will give the quotient 1
 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I figured
 out that highest reminder can be got if I divide the number by (⌊(n/2)⌋+
 1) .Can anyone give me pointers ?

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






-- 

*Ankit Agarwal*

-- 
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] Re: Highest reminder

[Dave]

The highest remainder when dividing n by a number less than n is 
floor((n-1)/2).
For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
For n = 17, floor((17-1)/2) = 8
For n = 23, floor((23-1)/2) = 11
 
For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
Etc.
 
Dave
 

On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal 
 ankitsam...@gmail.comjavascript:
  wrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but your 
 formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar 
 niksin...@gmail.comjavascript:
  wrote:

 Since we need to divide so the quotient should be at least 1, and we 
 need greatest remainder, so we need the least no. which will give the 
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I figured 
 out that highest reminder can be got if I divide the number by (⌊(n/2)⌋
 +1) .Can anyone give me pointers ?

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com javascript:.
  
  


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




 -- 

 *Ankit Agarwal*


 

-- 
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] Re: Highest reminder

[Ankit Agarwal]

@Dave:

For N = 23, the highest remainder is 12, not 11


On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote:

 The highest remainder when dividing n by a number less than n is
 floor((n-1)/2).
 For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
 For n = 17, floor((17-1)/2) = 8
 For n = 23, floor((23-1)/2) = 11

 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
 Etc.

 Dave


 On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal ankitsam...@gmail.comwrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but
 your formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksin...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we
 need greatest remainder, so we need the least no. which will give the
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be  floor(n/2)-1
 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I figured
 out that highest reminder can be got if I divide the number by (⌊(n/2)
 ⌋+1) .Can anyone give me pointers ?

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.




  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.






 --

 *Ankit Agarwal*


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






-- 

*Ankit Agarwal*
*Software Engineer*
*Datacenter  Cloud Division*
*Citrix RD India Pvt. Ltd.*
*Ph. No. +91-8095470278*

-- 
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] Re: Highest reminder

[Sanjay Rajpal]

Hi Ankit,

for 23, how can the remainder be 12 ? Can you elaborate more ?

*Regards,*
*Sanjay Kumar*
*Software Engineer(Development)*
*Winshuttle Softwares(India) Pvt. Ltd.*
*Mobile +91-89012-36292, +91-80535-66286*
*Email: sanjay.ku...@winshuttle.com*
*
***

* *

**
*
*


On Thu, May 30, 2013 at 9:40 AM, Ankit Agarwal ankuagarw...@gmail.comwrote:

 @Dave:

 For N = 23, the highest remainder is 12, not 11


 On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote:

 The highest remainder when dividing n by a number less than n is
 floor((n-1)/2).
 For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
 For n = 17, floor((17-1)/2) = 8
 For n = 23, floor((23-1)/2) = 11

 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
 Etc.

 Dave


 On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal ankitsam...@gmail.comwrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but
 your formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksin...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we
 need greatest remainder, so we need the least no. which will give the
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be
  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I
 figured out that highest reminder can be got if I divide the number by
 (⌊(n/2)⌋+1) .Can anyone give me pointers ?

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.




  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.






 --

 *Ankit Agarwal*


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






 --

 *Ankit Agarwal*
 *Software Engineer*
 *Datacenter  Cloud Division*
 *Citrix RD India Pvt. Ltd.*
 *Ph. No. +91-8095470278*

  --
 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] Re: Highest reminder

[Sreenivas Sigharam]

Dave's explanation was clear..and informative.. Thank you Dave..

Thank you , Soumya Prasad, for a simple but nice topic..

Thank you,
Sigharam.


On Thu, May 30, 2013 at 10:16 AM, Sanjay Rajpal sanjay.raj...@live.inwrote:

 Hi Ankit,

 for 23, how can the remainder be 12 ? Can you elaborate more ?

 *Regards,*
 *Sanjay Kumar*
 *Software Engineer(Development)*
 *Winshuttle Softwares(India) Pvt. Ltd.*
 *Mobile +91-89012-36292, +91-80535-66286*
 *Email: sanjay.ku...@winshuttle.com*
 *
 ***

 * *

 **
 *
 *


 On Thu, May 30, 2013 at 9:40 AM, Ankit Agarwal ankuagarw...@gmail.comwrote:

 @Dave:

 For N = 23, the highest remainder is 12, not 11


 On Thu, May 30, 2013 at 5:02 AM, Dave dave_and_da...@juno.com wrote:

 The highest remainder when dividing n by a number less than n is
 floor((n-1)/2).
 For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
 For n = 17, floor((17-1)/2) = 8
 For n = 23, floor((23-1)/2) = 11

 For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
 Etc.

 Dave


 On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal 
 ankitsam...@gmail.comwrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but
 your formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar niksin...@gmail.comwrote:

 Since we need to divide so the quotient should be at least 1, and we
 need greatest remainder, so we need the least no. which will give the
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be
  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I
 figured out that highest reminder can be got if I divide the number by
 (⌊(n/2)⌋+1) .Can anyone give me pointers ?

  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it,
 send an email to algogeeks+...@**googlegroups.com.




  --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@**googlegroups.com.






 --

 *Ankit Agarwal*


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






 --

 *Ankit Agarwal*
 *Software Engineer*
 *Datacenter  Cloud Division*
 *Citrix RD India Pvt. Ltd.*
 *Ph. No. +91-8095470278*

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




-- 
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] Re: searching all matching words in a Trie with a given filter.

[avinesh saini]

Thank you Don, I was also trying in similar way. But here I'm confused how
you are storing the traversed words. Are you adding whole words at the node
on which word is ending during insertion.


On Wed, May 29, 2013 at 12:36 AM, Don dondod...@gmail.com wrote:

 void findWords(trie *root, char *filter)
 {
 if (!root) return;

 if (*filter == 0)  // When you reach the end of the filter at the
 end of a valid word, add the word.
 {
 if (root-words) words.add(root-word);
 }
 else if (*filter == '.')   // Search for words with any letter
 {
 for(int i = 'a'; i = 'z' ; ++i)
 findWords(root-link[i], filter+1);
 }
 else  // Search for words with the required letter
 {
  findWords(root-link[*filter], filter+1);
 }
 }

 On May 28, 4:47 am, avinesh saini avinesh.sa...@gmail.com wrote:
  How to search all the matching words for a filter in a trie.
  e.g.
  searching by filter  ...r..m will find all the words(of length = 7) in
  trie in which 4th character is 'r' and 7th character is 'm'.
 
  --
  *
  *
  *thanks  regards,*
  *Avinesh
  *

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





-- 
*
*
*thanks  regards,*
*Avinesh
*

-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[bharat b]

@Nishant :
Don's algo :

first he is counting #of bits of all numbers from 0 to 65536 and
maintaining in an array bitCount.

Converted the input array into of type short. short range is 0 to 65536.
for the given input, he is getting the number of bits set using bitCount[]
.. its like memorization process...



On Sun, May 26, 2013 at 9:18 PM, Nishant Pandey 
nishant.bits.me...@gmail.com wrote:

 @DOn can u explain ur first algo, it would be helpful.


 On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:

 My program works with any numbers.
 Don

 On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
  This above program works only if the array contains consecutive numbers
  starting from 1 to n. What to do if the array contains random numbers?
 
 
 
 
 
 
 
  On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
   Counting the set bits in one integer is not the problem which was
   asked.
   However, I think that something like this is both faster and more easy
   to understand than what you have written:
 
   int bitCount(unsigned int x)
   {
  int result = 0;
  while(x)
  {
 if (x  1) ++result;
 x = 1;
  }
  return result;
   }
 
   On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
 oly fr
+ve, just a tweak will make it to work with -ves also ..
 
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
 
printf(%d\n,count );
getch();
 
}
 
   --
   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.



  --
 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] Re: PLease suggest the Algo for this problem

[Karan Sewani]

Create a BST from given list such that team that has won should be
right child of node and and teams that has lost should be left child
of node and then traverse the tree in reverse in order.

Karan

On Thu, May 23, 2013 at 10:58 PM, bharat b bagana.bharatku...@gmail.com wrote:
 @Don : you are correct but hamiltanion path problem is NPC right?
 quicksort algorithm is good solution. I already shared algorithm in above
 link.


 On Thu, May 23, 2013 at 10:25 PM, Don dondod...@gmail.com wrote:

 If you create a directed graph where each node is a team and an edge
 exists from A-B if A lost to B, then find a Hamiltonian Path in the
 graph. That path will be the sequence you need.
 Don

 On May 23, 12:02 pm, bharat b bagana.bharatku...@gmail.com wrote:
  http://www.careercup.com/question?id=14804702
 
  On Thu, May 23, 2013 at 8:53 PM, Nishant Pandey 
 
 
 
 
 
 
 
  nishant.bits.me...@gmail.com wrote:
   @DON,
 
   For example if in a particular order, the teams appeared as T1, T2,
   T3, T4
   … then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to
   T4… It
   may be possible that T3 lost to T1 .. but that need not be taken into
   consideration while writing the order. Only the neighboring elements
   should
   be such that the element on the left has lost to the element on the
   right.
 
   On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote:
 
   This is not necessarily possible.
 
   If you have teams A, B, and C, it is possible that
   A beat B
   B beat C
   C beat A.
 
   Based on the first two games the ranking should be A,B,C. But based
   on
   the third game, C should be ranked higher than A.
 
   Don
 
   On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com
   wrote:
I have a list of N teams T1, T2, T3 … Tn. Each of these teams has
   played a
match against every other team. I have a function
displayResult(Team T1,
Team T2), it returns the team which won the match between any two
given
teams T1 and T2.
I have to write the teams in an order such the (n-1)th team (in the
   order)
had lost to the nth team which in turn had lost to (n+1)th team.
 
I want optimize code for this, please help.
 
   --
   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.

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



-- 
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] Re: stack. Mid element in o(1)

[Karan Sewani]

It' similar to implement min in O(1) in stack.
http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1

suppose you have implemented stack through linked list.

you can maintain another stack in parallel (say midstack)where you
keep the pointer of middle element for corresponding element in
main_stack, you will have to maintain a counter starting from 0 while
pushing elements (you can do it through a static variable or global
variable or just pass a parameter), if counter=2 then push [middle
here is top element in midstack] middle-next in midstack
corresponding to that position and reset the counter, else if counter
=1 just push the value at top of midstack again.

// pseudo code
push function:
  main_stack.push(element);
  counter++;
  if (counter==2)
if (midstack.peek()!=NULL)
 midstack.push(midstack.peek()-next);
else
 midstack.push(head_of_main_stack); // initial condition.
counter=0;
  else
midstack.push(midstack.peek());

pop function can be implemented on similar lines.

On Wed, May 22, 2013 at 9:37 PM, MAC macatad...@gmail.com wrote:
 i meant the middle elemnt

 so if 1 ,2,3 --top then 2 is mid value /..


 accessing a middle element via the index is not right as it would mean you
 are not using it as a stack , but as an array ..

 thanks
 --mac


 On Wed, May 22, 2013 at 9:34 PM, Don dondod...@gmail.com wrote:

 Do you mean the middle position or median value?

 If you implement the stack in an array, finding the middle position
 should be easy.

 Don

 On May 22, 11:45 am, MAC macatad...@gmail.com wrote:
  Saw this on  a seperate group .. Since answer not known to me sharing it
  here
 
  you have a stack . Exposed functionality is push and pop only .
 
  What minimal modifications would you do such that
  you should find middle element in o(1) time .
 
  I think this is only possible if you make sure that at push you store
  the
  middle element with the top element as well .. this would mean push
  would
  cease to be o(1)become o(n) .. . or is there some other trick ?
 
  thanks
  --mac

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



-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[rahul sharma]

guys ..i got solution here
http://www.geeksforgeeks.org/program-to-count-number-of-set-bits-in-an-big-array/

plz tell how its complexity is logn.


On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:

 Counting the set bits in one integer is not the problem which was
 asked.
 However, I think that something like this is both faster and more easy
 to understand than what you have written:

 int bitCount(unsigned int x)
 {
int result = 0;
while(x)
{
   if (x  1) ++result;
   x = 1;
}
return result;
 }

 On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
  as bitwise operators are fast can count by following logic, works oly fr
  +ve, just a tweak will make it to work with -ves also ..
 
  #include stdio.h
  main() {
  unsigned int x=12312,a;
  a=x1;
  //printf(%u,a);
  int count=0;
  while(x0) {
  a = x1;
  //printf(%u \n,a);
  if(ax)
  count++;
  x=a;}
 
  printf(%d\n,count );
  getch();
 
 
 
 
 
 
 
  }

 --
 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] Re: count number of set bits in an (big) array (Asked in Google interview)

[rahul sharma]

and how this is working
void init()
{
bitCount[0] = 0;
for(int i = 1; i  65536; ++i) bitCount[i] = bitCount[i/2] + (i1);
}
it is working fine..but plz tell the logic behind this


On Thu, May 23, 2013 at 11:12 AM, rahul sharma rahul23111...@gmail.comwrote:


 @don...i got  it...its complexity is logn..how?


 On Thu, May 23, 2013 at 11:10 AM, rahul sharma rahul23111...@gmail.comwrote:

 @don..you are counting in an integer only...correct if wrng?


 On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:

 My program works with any numbers.
 Don

 On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
  This above program works only if the array contains consecutive numbers
  starting from 1 to n. What to do if the array contains random numbers?
 
 
 
 
 
 
 
  On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
   Counting the set bits in one integer is not the problem which was
   asked.
   However, I think that something like this is both faster and more
 easy
   to understand than what you have written:
 
   int bitCount(unsigned int x)
   {
  int result = 0;
  while(x)
  {
 if (x  1) ++result;
 x = 1;
  }
  return result;
   }
 
   On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
 oly fr
+ve, just a tweak will make it to work with -ves also ..
 
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
 
printf(%d\n,count );
getch();
 
}
 
   --
   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.






-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[rahul sharma]

@pramidathat can be done in 0(n)..lets say int takes 4 bytes
i will make and array of first 256 numbers ...
while finding for inte i will take a char pointer pointing to first byte
and then using array of 256 int i will count in that byte and increent
array and count in it.and so on...access all the 4 bits...0(1) to create
the first 256 numbers array and 0(n) to access array.hope m clear


On Wed, May 22, 2013 at 1:15 PM, Pramida Tumma pramida.tu...@gmail.comwrote:

 This above program works only if the array contains consecutive numbers
 starting from 1 to n. What to do if the array contains random numbers?


 On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:

 Counting the set bits in one integer is not the problem which was
 asked.
 However, I think that something like this is both faster and more easy
 to understand than what you have written:

 int bitCount(unsigned int x)
 {
int result = 0;
while(x)
{
   if (x  1) ++result;
   x = 1;
}
return result;
 }

 On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
  as bitwise operators are fast can count by following logic, works oly fr
  +ve, just a tweak will make it to work with -ves also ..
 
  #include stdio.h
  main() {
  unsigned int x=12312,a;
  a=x1;
  //printf(%u,a);
  int count=0;
  while(x0) {
  a = x1;
  //printf(%u \n,a);
  if(ax)
  count++;
  x=a;}
 
  printf(%d\n,count );
  getch();
 
 
 
 
 
 
 
  }

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




-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[rahul sharma]

@don...i got  it...its complexity is logn..how?


On Thu, May 23, 2013 at 11:10 AM, rahul sharma rahul23111...@gmail.comwrote:

 @don..you are counting in an integer only...correct if wrng?


 On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:

 My program works with any numbers.
 Don

 On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
  This above program works only if the array contains consecutive numbers
  starting from 1 to n. What to do if the array contains random numbers?
 
 
 
 
 
 
 
  On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
   Counting the set bits in one integer is not the problem which was
   asked.
   However, I think that something like this is both faster and more easy
   to understand than what you have written:
 
   int bitCount(unsigned int x)
   {
  int result = 0;
  while(x)
  {
 if (x  1) ++result;
 x = 1;
  }
  return result;
   }
 
   On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
 oly fr
+ve, just a tweak will make it to work with -ves also ..
 
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
 
printf(%d\n,count );
getch();
 
}
 
   --
   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.





-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[Mangal Dev Gupta]

Hi Don,

instead of searching 1 at all places we can use this :

while(n!=0){
count++;
n = n  n-1;
}


On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:

 Counting the set bits in one integer is not the problem which was
 asked.
 However, I think that something like this is both faster and more easy
 to understand than what you have written:

 int bitCount(unsigned int x)
 {
int result = 0;
while(x)
{
   if (x  1) ++result;
   x = 1;
}
return result;
 }

 On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
  as bitwise operators are fast can count by following logic, works oly fr
  +ve, just a tweak will make it to work with -ves also ..
 
  #include stdio.h
  main() {
  unsigned int x=12312,a;
  a=x1;
  //printf(%u,a);
  int count=0;
  while(x0) {
  a = x1;
  //printf(%u \n,a);
  if(ax)
  count++;
  x=a;}
 
  printf(%d\n,count );
  getch();
 
 
 
 
 
 
 
  }

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





-- 
Mangal Dev
Ph No. 7411627654
Member Technical Staff
Oracle India Pvt Ltd
mangal@oracle.com mangal.d...@oracle.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] Re: stack. Mid element in o(1)

[Richard Reed]

We could also use a queue.

1. Put the first element in the stack
2. load the next element in a queue
3. Continue to load into queue until front of queue is no longer the
midpoint
4. dequeue and place into stack
5. Repeat from 2.

Pop is now O(n) because we would need to dequeue into the stack and then
re-queue to the midpoint. Midpoint O(1) and push is O(1)

The best solution is to the implementation of the stack and take the
midpoint via something like array[midpoint], or using a dictionary to hash
the indexes to their objects (which takes more memory than adding a queue
that is based on a linked list).

On Wed, May 22, 2013 at 1:16 PM, Don dondod...@gmail.com wrote:

 I thought you were asking how I could modify a stack class to allow
 the getMiddle operation?

 class stackMid
 {
 public:
 stackMid() { top = 0; }
 void push(int n) { s[top++] = n; }
 int pop() { return top ? s[--top] : 0; }
 int mid() { return s[top/2]; }
 bool isEmpty() { return (top == 0); }
 private:
 vectorint s;
 int top;
 };

 On May 22, 12:07 pm, MAC macatad...@gmail.com wrote:
  i meant the middle elemnt
 
  so if 1 ,2,3 --top then 2 is mid value /..
 
  accessing a middle element via the index is not right as it would mean
 you
  are not using it as a stack , but as an array ..
 
  thanks
  --mac
 
 
 
 
 
 
 
  On Wed, May 22, 2013 at 9:34 PM, Don dondod...@gmail.com wrote:
   Do you mean the middle position or median value?
 
   If you implement the stack in an array, finding the middle position
   should be easy.
 
   Don
 
   On May 22, 11:45 am, MAC macatad...@gmail.com wrote:
Saw this on  a seperate group .. Since answer not known to me
 sharing it
here
 
you have a stack . Exposed functionality is push and pop only .
 
What minimal modifications would you do such that
you should find middle element in o(1) time .
 
I think this is only possible if you make sure that at push you
 store the
middle element with the top element as well .. this would mean push
 would
cease to be o(1)become o(n) .. . or is there some other trick ?
 
thanks
--mac
 
   --
   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.




-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[rahul sharma]

@don..you are counting in an integer only...correct if wrng?


On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:

 My program works with any numbers.
 Don

 On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
  This above program works only if the array contains consecutive numbers
  starting from 1 to n. What to do if the array contains random numbers?
 
 
 
 
 
 
 
  On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
   Counting the set bits in one integer is not the problem which was
   asked.
   However, I think that something like this is both faster and more easy
   to understand than what you have written:
 
   int bitCount(unsigned int x)
   {
  int result = 0;
  while(x)
  {
 if (x  1) ++result;
 x = 1;
  }
  return result;
   }
 
   On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
 oly fr
+ve, just a tweak will make it to work with -ves also ..
 
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
 
printf(%d\n,count );
getch();
 
}
 
   --
   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.




-- 
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] Re: count number of set bits in an (big) array (Asked in Google interview)

[Nishant Pandey]

@DOn can u explain ur first algo, it would be helpful.


On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:

 My program works with any numbers.
 Don

 On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
  This above program works only if the array contains consecutive numbers
  starting from 1 to n. What to do if the array contains random numbers?
 
 
 
 
 
 
 
  On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
   Counting the set bits in one integer is not the problem which was
   asked.
   However, I think that something like this is both faster and more easy
   to understand than what you have written:
 
   int bitCount(unsigned int x)
   {
  int result = 0;
  while(x)
  {
 if (x  1) ++result;
 x = 1;
  }
  return result;
   }
 
   On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
 oly fr
+ve, just a tweak will make it to work with -ves also ..
 
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
 
printf(%d\n,count );
getch();
 
}
 
   --
   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.




-- 
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] Re: PLease suggest the Algo for this problem

[Nishant Pandey]

@DON,

For example if in a particular order, the teams appeared as T1, T2, T3, T4
… then team T1 had lost to T2, T2 had lost to T3, and T3 had lost to T4… It
may be possible that T3 lost to T1 .. but that need not be taken into
consideration while writing the order. Only the neighboring elements should
be such that the element on the left has lost to the element on the right.


On Thu, May 23, 2013 at 8:47 PM, Don dondod...@gmail.com wrote:

 This is not necessarily possible.

 If you have teams A, B, and C, it is possible that
 A beat B
 B beat C
 C beat A.

 Based on the first two games the ranking should be A,B,C. But based on
 the third game, C should be ranked higher than A.

 Don

 On May 23, 11:06 am, Nishant Pandey nishant.bits.me...@gmail.com
 wrote:
  I have a list of N teams T1, T2, T3 … Tn. Each of these teams has played
 a
  match against every other team. I have a function displayResult(Team T1,
  Team T2), it returns the team which won the match between any two given
  teams T1 and T2.
  I have to write the teams in an order such the (n-1)th team (in the
 order)
  had lost to the nth team which in turn had lost to (n+1)th team.
 
  I want optimize code for this, please help.

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