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.

[algogeeks] Re: Amazon Job openings

[immanuel kingston]

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.

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.

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

[deepikaanand]

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.

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.

[algogeeks] Re: Minimal number of swaps

[Dave]

Use the quicksort algorithm: Set the swap counter to 0. Search from the 
beginning of the array for the first 0, and from the end of the array for 
the first 1. If the pointers cross, you are done; otherwise increment the 
swap counter and continue the searches.

On Tuesday, March 29, 2016 at 9:00:21 AM UTC-5, Régis Bacra wrote:
>
> This puzzle comes from a contribution on codingame.com (link to the puzzle 
> ). Any idea to 
> solve it efficiently?
>
> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
> list in a minimum number of steps. A step is the interchange of two 
> elements located at different positions.
> The expected result is the minimum number of steps required to obtain a 
> sorted list.
>
> Examples:
> 1 0 1 0 1 -> 1
> 0 1 0 1 1 1 0 -> 2
>

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

[algogeeks] Re: Minimal number of swaps

[icy`]

oh, nevermind, sorry ;P  you want the 1's at the beginning, not the end... 
  //friday

On Friday, April 22, 2016 at 4:07:53 PM UTC-4, icy` wrote:
>
> Hi,
> I'm not sure I understand the second example.  Shouldn't the second one 
> also produce an answer of  1 (swap the one in index 1 with the zero in the 
> last index)
> 0 *1* 0 1 1 1 *0*
>
> icy`
>
> On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote:
>>
>> This puzzle comes from a contribution on codingame.com (link to the 
>> puzzle ). Any 
>> idea to solve it efficiently?
>>
>> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
>> list in a minimum number of steps. A step is the interchange of two 
>> elements located at different positions.
>> The expected result is the minimum number of steps required to obtain a 
>> sorted list.
>>
>> Examples:
>> 1 0 1 0 1 -> 1
>> 0 1 0 1 1 1 0 -> 2
>>
>

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

[algogeeks] Re: Minimal number of swaps

[icy`]

Hi,
I'm not sure I understand the second example.  Shouldn't the second one 
also produce an answer of  1 (swap the one in index 1 with the zero in the 
last index)
0 *1* 0 1 1 1 *0*

icy`

On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote:
>
> This puzzle comes from a contribution on codingame.com (link to the puzzle 
> ). Any idea to 
> solve it efficiently?
>
> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
> list in a minimum number of steps. A step is the interchange of two 
> elements located at different positions.
> The expected result is the minimum number of steps required to obtain a 
> sorted list.
>
> Examples:
> 1 0 1 0 1 -> 1
> 0 1 0 1 1 1 0 -> 2
>

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

[algogeeks] Re: Buying candy

[Igor Pro]

It is like bubble sort type of algorithm. I'm not tested it on different 
data sets, created just for fun and your critic)

struct valuePos {int val; int pos;}
valuePos[,] data = new valuePos[n,n]; // assign input data array to [val] 
properties
// initialize by maximum val in data +1 or just unreachable value
// if index is not in use, calculated CompetitiveSwaps value will be less 
than zero and we use this as flag
int[] CompetitiveSwaps = {1,1,...}; // array of values to compare
int[] indexCount = {0,0,0...,0}; // size of n

sort each column of data by val

// input matrixval(index) after sort
6(1) 200(1)   20(1)150(1)   | 4(2)  3(2) 2(2)10(3)
4(2) 3(2)  2(2)  100(2)   | 6(1)  30(3)20(1)   
100(2)
300(3)  30(3)400(3)  10(3) | 300(3)  200(1)   300(4)  150(1)
400(4)  300(4)  300(4)  400(4)   | 400(4)   300(4)  400(3)  400(4)

int swapRow=1;

while(indexCount.indexof(0) != -1) // until all indexes will be used once, 
so all elements in indexCount array are "1"
{
 for(int i =0; i 

[algogeeks] Re: Find all the subarrays in a given array with sum=k

[Igor Pro]

void findSum(int[] arr, int startPos, int finPos, int reqiredSum)  // 
recursion procedure
{
 int sum =0;
// calculating sum of current(subarray) segment of array. imo single 
element is also a subarray so here we have  i <= finPos in case  when 
startPos == finPos
 for(int i = startPos, i <= finPos; i++ ) 
{
sum +=arr[i];
}

  if (sum == reqiredSum) console.WtiteLine("start {0}  fin {1} ",startPos, 
 finPos);
   
  if (finPos - startPos >= 1) 
 {
   if (startPos < arr.length)  findSum(arr, startPos+1, finPos, 
reqiredSum);
   if (finPos >0)  findSum(arr, startPos, finPos-1, reqiredSum);
 }
}

void main()
{
   int[] arr = new int[]{1, 3, 1, 7, -4, -11, 3, 4, 8};
   reqiredSum =12;
   findSum(arr, 0, arr.length -1, reqiredSum);
}

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

[algogeeks] Re: Largest Rectangle

[Igor Pro]

Use data structure to hold first position and last position of line // line 
- sequence of "0" elements in one of the dimensions in your matrix

Search lines in each dimension and store in array of line[s] //for 
optimization, store in separate array for each dimension: 
array1stDimension,array2ndDimension, array3Dimension
For each line in array[n]stDimension search intersections( +/- 1 diagonal) 
with lines in array[n+1]Dimension (perpendicular),
if found two or more such(perpendicular) lines 
   search parallel line from array[n]stDimension that 
have intersections at least with two of given perpendicular lines
   if found, calculate area of such rectangle 
and compare to current max value, // here in case of 3d, store rectangle as 
surface structure in array
if greater than max value, set max:= 
current val and remember coordinates of submatrix

In case of 2d array(matrix), it's all. 
For 3d array most easy way is to implement structure surface, and search 
intersections with other surface[s] to get cube

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

[algogeeks] Re: Find all the subarrays in a given array with sum=k

[Ian Martin Ajzenszmidt]

http://stackoverflow.com/questions/14948258/given-an-input-array-find-all-subarrays-with-given-sum-k

On Sunday, 21 February 2016 20:48:42 UTC+11, Shubh Aggarwal wrote:
>
> Given an array of n elements(both +ve -ve allowed)
> Find all the subarrays with a given sum k!
> I know the solution using dynamic programming. It has to be done by 
> recursion (as asked by the interviewer)
>
> For ex
>
> arr = 1 3 1 7 -4 -11 3 4 8
>
> k = 12
>
> answer = {1 3 1 7},  {4 8}, {1 3 1 7 -4 -11 3 4 8}
>
> You have to print {from index,  to last index} so for above example {0, 
> 3}; {0,8}; {7,8} is the answer
>

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

[algogeeks] Re: Buying candy

[Trevor]

Don  writes:

> 
> JVC is a multi-part algorithm which consists of a shortest augmenting
> path algorithm (JV) followed by a modified auction algorithm (C). It
> is best implemented as a sparse matrix. JVC is definitely an example
> of efficiency requiring a significant increase in complexity. The code
> implementing JVC is several times larger than Munkres or a standard
> auction algorithm.
> 
> Here are some references:
> 
> A description of JVC is here:
> O.E. Drummond, D.A. Castanon, M.S. Bellovin.
> Comparison of 2-D Assignment for Sparse, Rect-
> angular, Floating Point, Cost Matrix. Journal of
> the SDI Panels on Tracking, Institute for Defense
> Analyses, Issue No.4, 1990, pp.4-81 to 4-97.
> 

Does anybody know where I can find/purchase this reference? I can't find it
on SPIE and googling didn't turn up anything either. It is
referenced a lot, so I am wondering where everyone is finding it.

Thanks!
Trevor



-- 
You received this message because you are 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.

[algogeeks] Re: Find max sum of elements in an array ( with twist)

[yomama]

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.

[algogeeks] Re: Find max sum of elements in an array ( with twist)

[yomama]

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, false) + data[i] + 
(data[i+1] || 0);
   if(canSkip) {
return max([skippedI, notSkippedISkippedJ, notSkippedINotSkippedJ]);
   } else {
return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
   }
}

console.log(maxSum(0, data, false));

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.

[algogeeks] Re: Range Modulo Problem

[Gideon Rosales]

function solution( c1, c2, c3, c4 ) {

var min;
var max;
var x;

for( var y = c1; y <= c2; y++ ) {

for( var z = c3; z <= c4; z++ ) {

x = y % z;

if ( !min ) {
min = x;
}

if ( !max ) {
max = x;
}

if ( x <= min ) {
min = x;
}

if ( x >= max ) {
max = x;
}
}

}

console.log( 'min: ', min, 'max: ', max );

}

On Thursday, June 25, 2015 at 11:23:19 AM UTC+8, sagar wrote:
>
> You are given a range of modulo operands and find the range of modulo 
> result.
>
> Expression :- *x = y % z*
>
> where range of y is [ c1, c2 ] 
> c1, c2 are real numbers ( can be +ve or -ve ) and  c2 >c1
>
> where range of z is [c3,c4]
>  c3, c4 are real numbers ( can be +ve or -ve ) and  c3 >c4
>
> Range of x is [c5,c6]
>
> Input: User will input constant numbers( +ve or -ve ) corresponding to 
> c1,c2,c3,c4.
>
> Output : c5 and c6.
>
> Write an algorithm for it .
>
>
>

-- 
You received this message because you are 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 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

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

[algogeeks] Re: [BANNED!!!] Urgent need Lead - Java Developer in Atlanta, GA

[saurabh singh]

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.

[algogeeks] Re: Question on algo

[Dave]

Very simple. If MAXOR of the entire input set is not equal to zero, there 
are no subsets with equal MAXORs. If MAXOR of the entire set is zero, then 
any two complementary subsets have equal MAXORs. Since there are 2^N (^ is 
the exponential operator) subsets of a set of N elements, Little Panda 
needs to calculate mod((2^N)!,17) (! is the factorial symbol). 

Dave

On Monday, October 5, 2015 at 10:48:11 PM UTC-5, gopi wrote:

> Little Black Panda is mad about XOR operation. Presently he has gone mad 
> and he won't stop performing XOR operation on various numbers.
> Given an array of N numbers, for each subset of the array Little Panda 
> performs MAXOR operation for the subset. MAXOR operation means that he 
> finds XOR of all elements in that subset (if the subset is [1,2,3] then 
> MAXOR is 1^2^3=0) . Little Panda is now exhausted and wants to do something 
> else. Little Panda wants to pick any two subsets the MAXOR of whose are 
> same. Little Panda needs to find the number of selections that he can make. 
> He is very very weak in programming so he wants the answer from you. Please 
> help little panda in finding out his query.
> Since the output can be very large output it modulo 17.
>
> Input Format
> The first line contains N i.e. the length of the array.
> N lines follow, each containing a non-negative integer.
>
> Output Format
> Output Little Panda's Query in a single line.
>
> Constraints
> 1 <= N <= 10
> 0 <= A[i] <= 100
> (where A[i] denotes the value of array element)
>

-- 
You received this message because you are 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: 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.

[algogeeks] Re: Openings in Flipkart BLR

[taruna arora]

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.


RESUME_taruna (1).pdf
Description: Adobe PDF document

[algogeeks] Re: Openings in Flipkart BLR

[taruna arora]

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.


RESUME_taruna (1).pdf
Description: Adobe PDF document

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

for
the jar


Thanks & Regards

On Fri, Jun 19, 2015 at 2:43 AM, Nand Kumar Singh 
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 List 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.

[algogeeks] Re: how to convert JSONObject object to java object ??

[Nand Kumar Singh]

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

[algogeeks] Re: Openings in Snapdeal

[NH]

Thanks for the information . Can you also mention the job location ?

On Wednesday, 18 February 2015 23:47:46 UTC-6, Romil... wrote:
>
> Hi everyone,
>
> Snapdeal is having a lot of open positions for developers both at senior 
> and junior level.
>
> Send your resumes to me at vamos...@gmail.com 
> Java people are highly preferred but not mandatory.
>
> -- 
> Romil
>  

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

[algogeeks] Re: Openings in Snapdeal

[Romil Goyal]

Forgot to mention: Applications only from tier 1 colleges will be preferred.

On Thu, Feb 19, 2015 at 11:17 AM, Romil Goyal  wrote:

> Hi everyone,
>
> Snapdeal is having a lot of open positions for developers both at senior
> and junior level.
>
> Send your resumes to me at vamosro...@gmail.com
> Java people are highly preferred but not mandatory.
>
> --
> Romil
>



-- 
Romil

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

[algogeeks] Re: Opening in Microsoft India Development center, hyderabad.

[~*~VICKY~*~]

Missed to add, preferably 1 year+ experience.

On Sat, Jan 31, 2015 at 3:26 PM, ~*~VICKY~*~ 
wrote:

> Hi folks,
>
> My team is expanding and looking for strong devs with deep understanding
> of basics. If you think you can take up the challenge of redesigning and
> optimizing the cloud computing world, send me your resumes (preferably one
> page resume) to give a shot at this great opportunity.
>
> Some links about the team
> http://www.microsoft.com/about/technicalrecognition/Autopilot.aspx
> http://www.theregister.co.uk/2014/02/07/microsoft_autopilot_feature/
>
> --
> Cheers,
>
>   Vicky
>



-- 
Cheers,

  Vicky

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

[algogeeks] Re: Dynamic Programming - Series

[aksam]

what is square have -ve value then your solution gonna fail.

-- 
You received this message because you are 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]

Below is my code where s1 is larger and s2 is smaller

string paddedString(string s1, string s2){

  int min = INT32_MAX, t, star = 0, diff = int(s1.size() - s2.size());

  string result = "";

  for (int i = 0; i <= diff; i++) {

t = 0;

for (int j = i; j < s2.size(); j++) {

  if (s1[j] != s2[j]) {

t++;

  }

}

if (t < min) {

  min = t;

  star = i;

}

  }

  for (int i = 0; i < star; i++) {

result += "*";

  }

  result += s2;

  for (int i = 0; i < (diff - star); i++) {

result += "*";

  }

  return result;

}

Prateek Khandelwal
Software Engineer in Directi
+91-7042393719

On Wed, Oct 8, 2014 at 12:10 AM, Rishav Mishra 
wrote:

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

-- 
You received this message because you are 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 
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 
> 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 
>> 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: 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 
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  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]

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

[algogeeks] Re: Comparing string of unequal length

[vikas]

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.

[algogeeks] Re: Regarding approach to solve

[Dave]

Do a breadth-first search. From your starting position, find all of the 
positions you can reach in one move. From each of those, find all positions 
you can reach in one move. If you reach an already-reached position, just 
ignore that move; you either got to that position on an earlier move or via 
another path on this move. Continue this way until either you reach the 
solution state or you are not able to find any previously unreached 
positions. In the former case, you have determined the minimum number of 
moves to solve the puzzle. In the latter case, there is no solution.

Dave

On Sunday, September 28, 2014 10:07:56 AM UTC-5, Ravi Ranjan wrote:

> Yesterday I appeared for ACM USA Regionals, there I got the problem
>
> https://icpc-qual-14.kattis.com/problems/flipfive
>
> Can anyone help how to solve this kind of problem.
> Any links for similar problems ?
>
>

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

[algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[wtx...@gmail.com]

Odysseus,
What does char 'N' mean in chr22.dna? DNA has only 4 chars: A, C, G, T.

Other DNA/RNA has any other chars? I read from wiki that 'U' appears in 
tRNA.

Where is a tRNA file I can use?

Thank you.

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.

[algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[wtx...@gmail.com]

Odysseus,
Thank you very much!!! 

I can open it with Microsoft' Notepad to view it.

This is really what I want!!!

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.

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

[algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[wtx...@gmail.com]

*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  
 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!] 
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.

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

[algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

[wtx...@gmail.com]

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.

[algogeeks] Re: Given sequence A_k, k=[1,n] find min{A_k} k=[i,j] in O(logn) time with O(n) memory

[Gene]

On Wednesday, July 23, 2014 8:41:33 AM UTC-4, bujji wrote:
>
> Suppose that we are given a sequence of n values x1, x2, ..., xn and seek 
> to
> quickly answer repeated queries of the form: given i and j, find the 
> smallest value
> in xi, . . . , xj .
>
> Design a data structure that uses O(n) space and answers queries in O(log 
> n)
> time. For partial credit, your data structure can use O(n log n) space and 
> have
> O(log n) query time.
>  
>
You can use a segment tree representing the range 1..n.  Each tree node 
stores the sequence index of the minimum element in the represented 
segment. Querying this structure for a range i..j is just finding all 
the nodes that represent included subranges and taking the min. How 
many can that be?  It is easy to show that a recursive search from the root 
will have to look at most two nodes per tree level. Therefore the query is 
O(2  log n) = O(log n).  The tree is best represented in a simple array, 
since it is nearly complete like an array-based heap.  This array 
will elements 2n-1 elements if n is a power of 2 or at most another factor 
of 2 if n is arbitrary, so space is clearly O(n). 

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

[algogeeks] Re: What is the algorithm for this problem

[Don]

// This function returns the number of hints required to
// determine the order of the cards.
// Parameter int c[n] specifies n cards which are provided
// in an unknown order. Each card is represented as a 10-bit field
// with two bits set, one representing the color of the card and the
// other representing the value. The low 5 bits (value 1-16) indicate 
// the color, and the next 5 bits (value 32-512) indicate the value.
// The function requires an array int bits[1024] where bits[i] contains
// the number of bits set in the value i.
//
// This works on the principle that there must be at least one hint which
// distinguishes any pair of cards. If there is not, those two cards could
// be switched and the hints would not indicate a difference.

int minHints(int *c, int n)
{
   int pairs[300];
   int p = 0;
   int i, j;
   int min = 8;

   for(i = 1; i < n; ++i)
  for(j = 0; j < i; ++j)
 pairs[p++] = c[i] ^ c[j];

   for(i = 0; i < 1024; ++i)
  if (bits[i] < min)
  {
 for(j = 0; j < p; ++j)
if ((i & pairs[j]) == 0) break;
 if (j == p) min = bits[i];
  }

   return min;
}

On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:
>
> One of my friend posted this question to me and I am unable to get 
> anywhere. Could you guys please help 
>
> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
> possible. Player 1 will choose n cards and tell you exactly , what all 
> cards he has. Then he will spread cards in front of you with face downwards 
> in random fashion.
> So you know the card values but not the ordering. Player 1 will provide 
> you 2 types of hints , he can tell you what all cards have some color or he 
> can tell you what all cards have some value. you need to tell the ordering 
> of cards with the help of these hints.
> challenge is to find out minimum number of hints to be provided by player 
> 1 so that you are able to make it for all cards.
>
> e.g. say player chosen n=5 cards
> and tells you the values
>
> B1 Y1 W1 G1 R1
>
> he can either tell you that what all cards are 1 (in this case all cards)
> or can tell you different color like leftmost is color 'B" and next after 
> 'Y' and so on. So minimun hints in this case is 4
>
>  
> another example
> if n=4
> G4 R3 R4 B3
>
> Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 and 
> 3 are of color 'R'. This will be sufficient to infer the card values. so 
> answer is 2
>
>
> I am not interested in code , please suggest plain simple algorithms, if 
> possible with arguments that why it is correct ?
>
>

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

[algogeeks] Re: What is the algorithm for this problem

[Don]

Here is a fairly simple way to find a solution.

Make a list of each pair of the n cards which have been selected. This list 
can include up to 300 pairs. Represent each card as a 10-bit value where 
each bit represents one particular color or value. Thus, each card will 
have two bits set. Each pair is the bitwise XOR (^) of the values of the 
card, indicating which hints will distinguish those two cards. Now try all 
1024 possible combinations of hints by iterating i from 0 to 1023. If the 
bitwise AND (&) of i with any value in the pair list is zero, that 
combination of hints would not distinguish those cards. So a valid 
combination of hints has a non-zero bitwise AND with all values in the 
pairs list. Find the value of i with the fewest bits which meets this 
condition.

Don

On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:
>
> One of my friend posted this question to me and I am unable to get 
> anywhere. Could you guys please help 
>
> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
> possible. Player 1 will choose n cards and tell you exactly , what all 
> cards he has. Then he will spread cards in front of you with face downwards 
> in random fashion.
> So you know the card values but not the ordering. Player 1 will provide 
> you 2 types of hints , he can tell you what all cards have some color or he 
> can tell you what all cards have some value. you need to tell the ordering 
> of cards with the help of these hints.
> challenge is to find out minimum number of hints to be provided by player 
> 1 so that you are able to make it for all cards.
>
> e.g. say player chosen n=5 cards
> and tells you the values
>
> B1 Y1 W1 G1 R1
>
> he can either tell you that what all cards are 1 (in this case all cards)
> or can tell you different color like leftmost is color 'B" and next after 
> 'Y' and so on. So minimun hints in this case is 4
>
>  
> another example
> if n=4
> G4 R3 R4 B3
>
> Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 and 
> 3 are of color 'R'. This will be sufficient to infer the card values. so 
> answer is 2
>
>
> I am not interested in code , please suggest plain simple algorithms, if 
> possible with arguments that why it is correct ?
>
>

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

[algogeeks] Re: What is the algorithm for this problem

[Don]

There are a total of 10 hints which can be asked for.

If you ask for 4 colors and 4 values, you can deduce the remaining color or 
value by a process of elimination, so the most hints you will ever need is 
8.

You may not need all eight hints, if every card can be distinguished from 
every other card by one of the hints which you do request.

There are only 120 combinations of 7 hints. If you try each one of those to 
determine if it distinguishes each pair of cards selected, you can 
determine if only 7 hints will suffice. Keep trying with fewer hints until 
you find the lower limit.

Don

On Monday, July 7, 2014 12:06:51 PM UTC-4, Don wrote:
>
> As soon as you get one hint, the number of orders drops greatly. Your 
> first question should be to ask about the color or value which occurs 
> closest to n/2 times. When you ask about that, the number of possible 
> orders will be much smaller, and you can continue with just that list. The 
> problem was to find the minimum number of hints required, not to minimize 
> the computation time to find those hints. A faster algorithm is to ask for 
> hints randomly, but that will require more hints.
>
> Don
>
> On Wednesday, July 2, 2014 11:20:32 AM UTC-4, vikas wrote:
>>
>> Don, if you are talking about cards ordering then it will be n! which 
>> looks pretty high to compute ( consider even for n=10). and then for every 
>> count , you will need to compute every single color and values , i.e. worst 
>> case will be 25 n! ~ O(n!) . Can we do better ?
>>
>> On Wednesday, 2 July 2014 01:20:07 UTC+5:30, Don wrote:
>>>
>>> Initially there are 5! = 120 possible orders for the cards. You should 
>>> ask for the hint which will reduce that number by the largest amount. So in 
>>> your example above, asking which cards have value 1 would not reduce the 
>>> number at all. Asking which card is Green would reduce the possible orders 
>>> to 24. The algorithm is to make a list of the possible orders. Then for 
>>> each question, count the number of orders in the list would give each 
>>> possible answer. The largest count is the score for that question. Ask the 
>>> question with the smallest score. Then based on the answer, remove any 
>>> orders from the list which are not consistent with that answer. Repeat the 
>>> process until you have only one order remaining.
>>> Don
>>>
>>> On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:

 One of my friend posted this question to me and I am unable to get 
 anywhere. Could you guys please help 

 A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
 possible. Player 1 will choose n cards and tell you exactly , what all 
 cards he has. Then he will spread cards in front of you with face 
 downwards 
 in random fashion.
 So you know the card values but not the ordering. Player 1 will provide 
 you 2 types of hints , he can tell you what all cards have some color or 
 he 
 can tell you what all cards have some value. you need to tell the ordering 
 of cards with the help of these hints.
 challenge is to find out minimum number of hints to be provided by 
 player 1 so that you are able to make it for all cards.

 e.g. say player chosen n=5 cards
 and tells you the values

 B1 Y1 W1 G1 R1

 he can either tell you that what all cards are 1 (in this case all 
 cards)
 or can tell you different color like leftmost is color 'B" and next 
 after 'Y' and so on. So minimun hints in this case is 4

  
 another example
 if n=4
 G4 R3 R4 B3

 Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 
 and 3 are of color 'R'. This will be sufficient to infer the card values. 
 so answer is 2


 I am not interested in code , please suggest plain simple algorithms, 
 if possible with arguments that why it is correct ?



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

[algogeeks] Re: What is the algorithm for this problem

[Don]

As soon as you get one hint, the number of orders drops greatly. Your first 
question should be to ask about the color or value which occurs closest to 
n/2 times. When you ask about that, the number of possible orders will be 
much smaller, and you can continue with just that list. The problem was to 
find the minimum number of hints required, not to minimize the computation 
time to find those hints. A faster algorithm is to ask for hints randomly, 
but that will require more hints.

Don

On Wednesday, July 2, 2014 11:20:32 AM UTC-4, vikas wrote:
>
> Don, if you are talking about cards ordering then it will be n! which 
> looks pretty high to compute ( consider even for n=10). and then for every 
> count , you will need to compute every single color and values , i.e. worst 
> case will be 25 n! ~ O(n!) . Can we do better ?
>
> On Wednesday, 2 July 2014 01:20:07 UTC+5:30, Don wrote:
>>
>> Initially there are 5! = 120 possible orders for the cards. You should 
>> ask for the hint which will reduce that number by the largest amount. So in 
>> your example above, asking which cards have value 1 would not reduce the 
>> number at all. Asking which card is Green would reduce the possible orders 
>> to 24. The algorithm is to make a list of the possible orders. Then for 
>> each question, count the number of orders in the list would give each 
>> possible answer. The largest count is the score for that question. Ask the 
>> question with the smallest score. Then based on the answer, remove any 
>> orders from the list which are not consistent with that answer. Repeat the 
>> process until you have only one order remaining.
>> Don
>>
>> On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:
>>>
>>> One of my friend posted this question to me and I am unable to get 
>>> anywhere. Could you guys please help 
>>>
>>> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
>>> possible. Player 1 will choose n cards and tell you exactly , what all 
>>> cards he has. Then he will spread cards in front of you with face downwards 
>>> in random fashion.
>>> So you know the card values but not the ordering. Player 1 will provide 
>>> you 2 types of hints , he can tell you what all cards have some color or he 
>>> can tell you what all cards have some value. you need to tell the ordering 
>>> of cards with the help of these hints.
>>> challenge is to find out minimum number of hints to be provided by 
>>> player 1 so that you are able to make it for all cards.
>>>
>>> e.g. say player chosen n=5 cards
>>> and tells you the values
>>>
>>> B1 Y1 W1 G1 R1
>>>
>>> he can either tell you that what all cards are 1 (in this case all cards)
>>> or can tell you different color like leftmost is color 'B" and next 
>>> after 'Y' and so on. So minimun hints in this case is 4
>>>
>>>  
>>> another example
>>> if n=4
>>> G4 R3 R4 B3
>>>
>>> Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 
>>> and 3 are of color 'R'. This will be sufficient to infer the card values. 
>>> so answer is 2
>>>
>>>
>>> I am not interested in code , please suggest plain simple algorithms, if 
>>> possible with arguments that why it is correct ?
>>>
>>>

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

[algogeeks] Re: What is the algorithm for this problem

[vikas]

Don, if you are talking about cards ordering then it will be n! which looks 
pretty high to compute ( consider even for n=10). and then for every count 
, you will need to compute every single color and values , i.e. worst case 
will be 25 n! ~ O(n!) . Can we do better ?

On Wednesday, 2 July 2014 01:20:07 UTC+5:30, Don wrote:
>
> Initially there are 5! = 120 possible orders for the cards. You should ask 
> for the hint which will reduce that number by the largest amount. So in 
> your example above, asking which cards have value 1 would not reduce the 
> number at all. Asking which card is Green would reduce the possible orders 
> to 24. The algorithm is to make a list of the possible orders. Then for 
> each question, count the number of orders in the list would give each 
> possible answer. The largest count is the score for that question. Ask the 
> question with the smallest score. Then based on the answer, remove any 
> orders from the list which are not consistent with that answer. Repeat the 
> process until you have only one order remaining.
> Don
>
> On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:
>>
>> One of my friend posted this question to me and I am unable to get 
>> anywhere. Could you guys please help 
>>
>> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
>> possible. Player 1 will choose n cards and tell you exactly , what all 
>> cards he has. Then he will spread cards in front of you with face downwards 
>> in random fashion.
>> So you know the card values but not the ordering. Player 1 will provide 
>> you 2 types of hints , he can tell you what all cards have some color or he 
>> can tell you what all cards have some value. you need to tell the ordering 
>> of cards with the help of these hints.
>> challenge is to find out minimum number of hints to be provided by player 
>> 1 so that you are able to make it for all cards.
>>
>> e.g. say player chosen n=5 cards
>> and tells you the values
>>
>> B1 Y1 W1 G1 R1
>>
>> he can either tell you that what all cards are 1 (in this case all cards)
>> or can tell you different color like leftmost is color 'B" and next after 
>> 'Y' and so on. So minimun hints in this case is 4
>>
>>  
>> another example
>> if n=4
>> G4 R3 R4 B3
>>
>> Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 
>> and 3 are of color 'R'. This will be sufficient to infer the card values. 
>> so answer is 2
>>
>>
>> I am not interested in code , please suggest plain simple algorithms, if 
>> possible with arguments that why it is correct ?
>>
>>

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

[algogeeks] Re: What is the algorithm for this problem

[Don]

Initially there are 5! = 120 possible orders for the cards. You should ask 
for the hint which will reduce that number by the largest amount. So in 
your example above, asking which cards have value 1 would not reduce the 
number at all. Asking which card is Green would reduce the possible orders 
to 24. The algorithm is to make a list of the possible orders. Then for 
each question, count the number of orders in the list would give each 
possible answer. The largest count is the score for that question. Ask the 
question with the smallest score. Then based on the answer, remove any 
orders from the list which are not consistent with that answer. Repeat the 
process until you have only one order remaining.
Don

On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote:
>
> One of my friend posted this question to me and I am unable to get 
> anywhere. Could you guys please help 
>
> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are 
> possible. Player 1 will choose n cards and tell you exactly , what all 
> cards he has. Then he will spread cards in front of you with face downwards 
> in random fashion.
> So you know the card values but not the ordering. Player 1 will provide 
> you 2 types of hints , he can tell you what all cards have some color or he 
> can tell you what all cards have some value. you need to tell the ordering 
> of cards with the help of these hints.
> challenge is to find out minimum number of hints to be provided by player 
> 1 so that you are able to make it for all cards.
>
> e.g. say player chosen n=5 cards
> and tells you the values
>
> B1 Y1 W1 G1 R1
>
> he can either tell you that what all cards are 1 (in this case all cards)
> or can tell you different color like leftmost is color 'B" and next after 
> 'Y' and so on. So minimun hints in this case is 4
>
>  
> another example
> if n=4
> G4 R3 R4 B3
>
> Here he can tell you the card 1st and 3rd are of  values 4 and cards 2 and 
> 3 are of color 'R'. This will be sufficient to infer the card values. so 
> answer is 2
>
>
> I am not interested in code , please suggest plain simple algorithms, if 
> possible with arguments that why it is correct ?
>
>

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

[algogeeks] Re: Solving complicated Tree construction algorithm for Spatial Partioning

[nurabha]

Here is brief list of background concepts needed to understand the problem

- Space Filling Curves (SFC) : Morton codes are one particular kind of SFC 
implmeentation. Gray code and Hilber code are two more types of SFCs that 
can be generated
- Binary tree and traversal
- Prefix trees
- Basic sorting
- Conceptual understanding of Octree/Quadtree 

Regards
N.


On Tuesday, 10 June 2014 16:10:42 UTC+5:30, nurabha wrote:
>
> I am going to discuss a difficult problem related to geometrical 
> algorithms for space partitioning (2d, 3d, hyperspace).  
>
> The problem is concerning a special kind of tree called *Octree*(in 3d) 
> or *Quadtree*(2d). 
>
> The Octree/Quadtree structures are used to hierarchically partition 
> objects present inside 3d or 2d space.
>
> There was a recent paper from NVIDIA which proposes a fast algorithm for 
> constructing *Octree*. 
> Here is the link to the paper: 
> http://research.nvidia.com/sites/default/files/publications/karras2012hpg_paper.pdf
>
> The author proposes constructing the Octree using another primitive kind 
> of tree called* binary radix tree. *
> *The Octree construction as described in paper consists of of seven steps: 
> *
>
>> (1) calculate Morton codes for the points, 
>> (2) sort the Morton codes, 
>> (3) identify duplicates, i.e. points falling within the same leaf node, 
>> by comparing each pair of adjacent Morton codes, 
>> (4) remove the duplicates using parallel compaction, 
>> (5) construct a binary radix tree, 
>> *(6) perform parallel prefix sum to allocate the octree nodes, and *
>> *(7) find the parent of each node. *
>>
>
> I am working on implementing this algorithm and so far I have understood 
> and implementing steps (1-5) of the algorithm in the paper. 
>
> *However the final 2 steps i.e step 6 and 7  in the paper are not 
> described properly and I am having hard time understanding it*.
> *Below is the paragraph which offers some explanation about steps 6 and 7 
> (copy pasted verbatim from paper) but not in a clear way*
>
> *Octrees. To construct an octree for a set of points, we observe that each 
>> 3k-bit prefix of a given Morton code maps directly to an octree node at 
>> level k.*
>> *We can enumerate these prefixes by looking at the edges of a 
>> corresponding binary radix tree - an edge connecting a parent with a prefix 
>> of length Dparent *
>> *to a child with a prefix of length Dchild represents all subprefixes of 
>> length Dparent+1, Dchild. *
>> *Out of these, Floor( Dchild/3 ) - Floor( Dparent/3 ) are divisible by 3. 
>> *
>> *We evaluate these counts during radix tree construction, and then 
>> perform a parallel prefix sum to allocate the octree nodes. *
>> *The parents of the octree nodes can then be found by looking at the 
>> immediate ancestors of each radix tree node.*
>>
>
>
> I am trying to decipher the algorithm for final 2 steps but it is proving 
> a bit difficult as I am not an algorithm expert.
>
> If anyone is willing to spend time to with me to solve this problem, I 
> will be more than happy.  ;)
>
> Thanks
> N.
>

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

[algogeeks] Re: Solving coin change problem with limited coins.

[s khadar]

The main difference between the standard CC algo, and the one with limited 
coin supply is the maximum value that we can form with the given coins. 

For example :

In stranded CC

coins[] = {1,2,3}

then we can can form denominations to any value(assuming that coin with 1 
value will always be there). But in case the provided coins are limited 
then we can form the denominations only up to the partial sum:

Ex:

coins[] = {1,2,3}
count[] = {1,1,2}

then we can form the denominations only up to 1*1+2*1+3*2 = 9. But this 
value is only valid if we take all the coins into the consideration. But if 
you take only two coins {1,2} then we can form denominations only up to 3.

So the modified algorithm is

Pick the current coin
Use the coin to form denominations till it's partial sum.

Code Snippet:

public static void coinChange(int max_value, int coins[], int count[]) {
int coins_sz = coins.length;
int dp[] = new int[max_value + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int partial_sum = 0;
for (int i = 0; i < coins_sz; i++) {
partial_sum += coins[i] * count[i];
for (int j = coins[i]; j <= partial_sum && j <= max_value; j++) {
dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
}
}
for (int i = 1; i <= max_value; i++) {
System.out.println("Coin value = " + i
+ ", Minimum number of coins = " + dp[i]);
}
}

Let me know in case the above algorithm fails for any test cases. 

On Thursday, May 15, 2014 11:05:12 AM UTC+5:30, 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.

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

-- 
You received this message because you are 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: 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.

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

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

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

[algogeeks] Re: Solving coin change problem with limited coins.

[Don]

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.

Re: [algogeeks] Re: Shortest path in grid with dynamic programming.

[Don]

Good catch. A function called "markShortestPath" ought to mark the shortest 
path, huh?

Don

On Monday, April 21, 2014 4:38:32 PM UTC-4, bujji wrote:
>
>
>  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.
>
>
>
>
> On Mon, Apr 21, 2014 at 10:01 AM, Don >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 .
>>
>
>

-- 
You received this message because you are 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  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  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,
 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  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.

[algogeeks] Re: Shortest path in grid with dynamic programming.

[Don]

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.

[algogeeks] Re: Max difference of Monotonic Pair in An Array

[Don]

// The result will always include the smallest value of A[i] where i is 
less than j,
// so just keep track of that minimum value as you scan through the array.

int findPair(int *A, int N)
{   
   min = A[0];   
   max = 0;
   for(j = 1; j < N; ++j)
   {
  if ((A[j] - min) > max) max = A[j] - min;
  if (A[j] < min) A[j] = min;
   }

   return max;
}

On Friday, April 18, 2014 4:49:26 PM UTC-4, TUSHAR wrote:
>
> Hi All,
>
> Can anyone help me solving this problem ?
>
> Given a non-empty array A consisting of N integers.
>
> Find Max(j-i), s.t 0<=i<=j
> Here (i, j) is a Monotonic Pair, satisfying the above condition.
>
> Space Complexity : O(n)  Time Complexity: O(n)
>
> -- 
> Regards...
>  

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

[algogeeks] Re: Shortest path in grid with dynamic programming.

[Don]

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.

Re: [algogeeks] Re: Calculating C(n.r)

[kumar raja]

Thanks for the idea.


On 9 April 2014 10:25, Dave  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.

[algogeeks] Re: Calculating C(n.r)

[Don]

Very nice solution.
Don

On Wednesday, April 9, 2014 12:55:43 AM UTC-4, Dave 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.

[algogeeks] Re: Calculating C(n.r)

[Dave]

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.

[algogeeks] Re: Calculating C(n.r)

[Don]

Note that my example is for C(n,r), but you can use the same method for 
your second formula. Just add up the logs of whatever you multiply in the 
numerator and subtract the logs of the factors of the denominator. Then the 
result is exp of the resulting sum.

Don

On Tuesday, April 8, 2014 2:15:06 PM UTC-4, Don wrote:
>
> Use the fact that a*b*c*d = exp(log a + log b + log c + log d)
>
> double sum = 0.0;
> double x;
>
> for(x = n-r+1.0; x <= n; x += 1.0)
>sum += log(x);
>
> for(x = 2; x <= r; x += 1.0)
>sum -= log(x);
>
> result = exp(sum);
>
> Don
>
> On Tuesday, April 8, 2014 2:06:47 PM UTC-4, 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.

[algogeeks] Re: Calculating C(n.r)

[Don]

Use the fact that a*b*c*d = exp(log a + log b + log c + log d)

double sum = 0.0;
double x;

for(x = n-r+1.0; x <= n; x += 1.0)
   sum += log(x);

for(x = 2; x <= r; x += 1.0)
   sum -= log(x);

result = exp(sum);

Don

On Tuesday, April 8, 2014 2:06:47 PM UTC-4, 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.

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

[algogeeks] Re: Implement lastindexofastring(String s1,String s2)

[Dan]

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.

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 >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  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) && s>max) 
> { 
>bestI = i; bestJ = j; max = s; 
> } 
>   } 
>
> On 1/25/13, Don  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  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  
> 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  
> 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  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 rec

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  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  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) && s>max)
 {
bestI = i; bestJ = j; max = s;
 }
   }

 On 1/25/13, Don  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  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  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  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  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+

[algogeeks] Re: explanation of solution required.

[Don]

The sort is what makes this O(n*log n). The processing after the sort is 
O(N).

So to describe the algorithm, after sorting A, it steps through the sorted 
array, determining what the value of K would have to be at that point such 
that setting the remaining values to K would cause the sum to be S. S-sum 
is the required total of the rest of the array, and that total is divided 
among the len(A) - index remaining values. If solution is less than the 
previous value in A, then it is not a valid solution because that previous 
value would have been set to K as well. If solution is greater than the 
current value, the the current value would not be replaced. Thus, it is 
necessary that prev < solution <= value.

There are some unstated assumptions. For example, if the values in A can be 
negative, there could be problems. And if values in A must be integers, the 
value of solution might not give a result exactly equal to S. But if A 
contains positive real numbers I think that it will work.

Don

On Sunday, March 30, 2014 10:02:08 AM UTC-4, atul007 wrote:
>
> Hello,
>   i found this question online and its solution tooBut i am not able 
> to fully understand the solution.Need your help to proof correctness of the 
> algo.
>
> Question is as follows :-
>
> *Question:*
>
> *Given an array A and a number S', provide an efficient algorithm (nlogn) 
> to find a number K such that if all elements in A greater than K are 
> changed to K, the sum of all elements in the resulting array will be S'.*
>
> *Example, given A: [90,30,100,40,20] and S' = 210, K will be 60.*
>
> *Ans)*
>
> #!/usr/bin/env python
>
>  
>
> A = [90, 30, 100, 40, 20]
>
> S = 210
>
> K = 60
>
>  
>
> A= sorted(A)
>
> prev = 0
>
> sum  = 0
>
>  
>
> for index, value in enumerate(A):
>
> # What do we need to set all subsequent values to to get the desired sum?
>
> solution = (S - sum) / (len(A) - index)
>
>  
>
> # That answer can't be too big or too small.
>
> if prev < solution <= value:
>
> print solution
>
>  
>
> sum += value
>
> prev = value
>
>  

-- 
You received this message because you are 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 >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) && s>max) 
>>> { 
>>>bestI = i; bestJ = j; max = s; 
>>> } 
>>>   } 
>>>
>>> On 1/25/13, Don  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  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  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  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  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.

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  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) && s>max)
>> {
>>bestI = i; bestJ = j; max = s;
>> }
>>   }
>>
>> On 1/25/13, Don  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  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  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  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  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) && s>max) 
> { 
>bestI = i; bestJ = j; max = s; 
> } 
>   } 
>
> On 1/25/13, Don > 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  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  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  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  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) && s>max)
{
   bestI = i; bestJ = j; max = s;
}
  }

On 1/25/13, Don  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  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  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  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  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

[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  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;i if(max 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;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  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.
>> !---

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  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;i if(max 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;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  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
>> !--

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;ii) {
return false;
}
prev = max;
}
return true;
}
}

On Tue, Mar 25, 2014 at 10:14 AM, Dan  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   :: 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(*,*) '--'
>
> write(*,*)
> write(*,*) 'Test Case #2  array size = 8,  Easy to check'
> n = 8
> v(1:n) = (/8,12,7,15,10,20,12,16/)
> Call Solve_for_X()
> write(*,*) ''
>
> write(*,*)
> write(*,*) 'Test Case #3:  array size = 10

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

[Dan]

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   :: 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(*,*) '--'

write(*,*)
write(*,*) 'Test Case #2  array size = 8,  Easy to check'
n = 8
v(1:n) = (/8,12,7,15,10,20,12,16/)
Call Solve_for_X()
write(*,*) ''

write(*,*)
write(*,*) 'Test Case #3:  array size = 1  w/ random array values up to 
999'
n = 1
Call Random_Seed()
Call Random_Number( r(1:n) )
v(1:n) = 1 + Int(999*r(1:n))
Call Solve_for_X()
write(*,*) ''

call timer(it2)
write(*,*) 'Total time = ', Real(it2-it1)/100.0

Contains

   Subroutine Solve_for_X()
   !
   x = TransformArray( v(1:n) )
   write(*,'(a,i0)') ' X minimum = ', x

   Call Validate_X( v(1:n), x )

   ! Check to see if a smaller X value would have worked
   write(*,*)
   write(*,'(a,i0,a)') ' Check to see if x = ', x-1, '  will work:'
   Call Validate_X( v(1:n), x-1 )
   End Subrout

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
 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  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  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 (p>>{
>>>   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: 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  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  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 (p>{
>>   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.

[algogeeks] Re: Data structure question

[SVIX]

1- question seems to be a little too vague... if it's a mail server 
application, I'm guessing you would use some kind of persistent storage... 
maybe a no-sql solution like cassandra... u could use a tale with the user 
ID and mail status as key to store mails...

2- priority queues, maybe

3- a sorted tree so u can search by range... you could make it better by 
using a hash map that maps from a short date string (-MM-dd) to the 
sorted tree where events are stored and you could binary search based on ur 
range

On Saturday, March 8, 2014 8:28:35 AM UTC-8, atul007 wrote:
>
> 1) - When u login, it retrieves all the unread mails only. Which data 
> structure should you use ?
>
> 2)- If you get an event invitation then u have to be notified . eg if u 
> have two event invitations, one is in the next hour and other one 2 months 
> later, the one that is tomorrow will be given a higher priority and sent to 
> u before any other event or mail.What data structure should you use?
>
> 3) - If the events are added to your calendar on the server ,the server 
> should handle the query :
>
> Find if there is a time slot on a particular date in a particular time 
> range of the given duration. What data structure will you use ?eg - find a 
> free timeslot on 31st of august between 6 AM to 7 PM of 30 min duration.
>  

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

[algogeeks] Re: Integer partition problem - DP

[Dave]

See http://en.wikipedia.org/wiki/Partition_(number_theory).

On Saturday, March 1, 2014 10:25:57 AM UTC-6, kumar raja wrote:
>
> Given an integer how many number of ways u can partition the number?
>  
> e.g. 3  can be written as 3,1+2,1+1+1 
> and 4 can be written as  4, 1+1+1+1,2+2,1+3,1+1+2   
>
> So  for 3 --> 3
>   for 4 -->5.
>
> The order of the elements in the partition does not matter. 
> So how to calculate the number of ways to partition the given number?
>
> Can someone give idea on how to write the recurrence relation 
> for the problem? 
>

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

[algogeeks] Re: [Adobe]Generate all possible combinations (of r elements) inside an array of size N

[Ziklon]

1.- if you use bitmask can be easy solved
2.- second aproach is create un recursion

string func(int idx, int cnt){
   if(cnt==r)return "";;
   string ans = func(idx+1, cnt);
   if(cnt
>  Generate all possible combinations (of r elements) inside an array of 
> size N
> E.g. arr [] = {2,8,14} All possible combinations of r=2 will be {2,8}, 
> {8,14}, {14,2}
>
> Asked in adobe
>

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

[algogeeks] Re: Permuations with stack constraints

[Dave]

@Kumar: As a point of interest, the number of valid sequences of n pushes 
and n pops is C(3), the third Catalan Number. See, e.g., 
http://en.wikipedia.org/wiki/Catalan_number for details.

Dave

On Thursday, February 20, 2014 12:27:35 PM UTC-6, kumar raja wrote:

> Hi all,
>
> Here is a permuatation related question.
>
> Suppose the set is {a,b,c};
>
> At a given point of time either u can push an
> elemnt on to the stack or pop of the element.
> While pushing the elements u have to follow the 
> order a,b,c as given in the set.
>
> When u pop the element u will print it to the 
> output array.
>
> one possible sequence of operations is 
>
> push(a),push(b),pop(),push(c),pop(),pop()
>
> The permuation obtained by above combination is 
>
>  {b,c,a}.
>  
> But out of 6! permuations possible one invalid 
> permutation  is {c,a,b} (guess how?)
>
> So how to print all valid permuations with the 
> above constaraints?  
>

-- 
You received this message because you are 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  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  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();
>> List counts = new ArrayList();
>> List l = new ArrayList();
>>  l.add(2);
>> l.add(3);
>> l.add(5);
>> l.add(7);
>>  for(int i=0;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(List l) {
>>  List li = new ArrayList();
>> int temp=0;
>> for(int i=0;i>  int k = 0;
>> int j =0;
>> if(l.get(i)==0&&temp==1&&i==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==1&&k==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(List l) {
>> int num=0;
>>  for(int i=0;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.

[algogeeks] Re: Find 3 digit number.

[bhargav]

>
> 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();
> List counts = new ArrayList();
> List l = new ArrayList();
> l.add(2);
> l.add(3);
> l.add(5);
> l.add(7);
> for(int i=0;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(List l) {
> List li = new ArrayList();
> int temp=0;
> for(int i=0;i int k = 0;
> int j =0;
> if(l.get(i)==0&&temp==1&&i==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==1&&k==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(List l) {
> int num=0;
> for(int i=0;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.

[algogeeks] Re: Generate random number from 1 to 10.

[SVIX]

Thanks for the explanation Don! It looks like I need better math-foo to 
completely understand your explanation...

On Tuesday, February 11, 2014 10:07:05 AM UTC-8, Don wrote:
>
>
> It can be shown mathematically that if you use a multiplier A such that 
> A*2^15-1 and A*2^16-1 are both prime, you get a sequence with period 
> A*2^15. With A=63663 you get a sequence of nearly two billion. If A was 
> larger than 2^16, the multiplication would result in overflow in some 
> cases, so the value I used was near the limit. The generator uses only the 
> low 16 bits as output. The high 16 bits, however, are kept as state, 
> meaning that you can't tell from the current output what the next output 
> will be. The full cycle contains each possible output value an equal number 
> of times, so over a large sample, the outputs are all equally likely.
>
> Using mod 1000 is not a perfect way to get a uniform value in the range 
> 0-1000. Because the outputs are in the range 0..65536, there are 65 ways to 
> generate numbers <= 536 and 66 ways to generate numbers > 536. A better way 
> to generate a number in the range 0..n-1 is to divide the output by 
> 65535/n. Then check the result and if it is >= n, repeat the process until 
> you get a valid result.
>
> Don
>
> On Tuesday, February 11, 2014 1:18:26 AM UTC-5, SVIX wrote:
>>
>> :) true... that was silly of me.. I was too quick to post... anyway, the 
>> point I was trying to understand was why this specific combination of 
>> operations would produce good randomness... Running the original solution 
>> you posted a million times (with the max limit set to 1000), below is the 
>> frequency of the numbers generated (in the format  X  )
>>
>>
>> On Friday, February 7, 2014 11:42:03 AM UTC-8, Don wrote:
>>>
>>> Because if you put that in a loop you will get a series like:
>>>
>>> 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
>>>
>>> On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:

 Just curious... Why is this more random than 
 (getSystemTimeInMilliseconds() % 10)

 On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don 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 * (x&65535) + (x>>16);
>>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.

[algogeeks] Re: Generate random number from 1 to 10.

[Don]

It can be shown mathematically that if you use a multiplier A such that 
A*2^15-1 and A*2^16-1 are both prime, you get a sequence with period 
A*2^15. With A=63663 you get a sequence of nearly two billion. If A was 
larger than 2^16, the multiplication would result in overflow in some 
cases, so the value I used was near the limit. The generator uses only the 
low 16 bits as output. The high 16 bits, however, are kept as state, 
meaning that you can't tell from the current output what the next output 
will be. The full cycle contains each possible output value an equal number 
of times, so over a large sample, the outputs are all equally likely.

Using mod 1000 is not a perfect way to get a uniform value in the range 
0-1000. Because the outputs are in the range 0..65536, there are 65 ways to 
generate numbers <= 536 and 66 ways to generate numbers > 536. A better way 
to generate a number in the range 0..n-1 is to divide the output by 
65535/n. Then check the result and if it is >= n, repeat the process until 
you get a valid result.

Don

On Tuesday, February 11, 2014 1:18:26 AM UTC-5, SVIX wrote:
>
> :) true... that was silly of me.. I was too quick to post... anyway, the 
> point I was trying to understand was why this specific combination of 
> operations would produce good randomness... Running the original solution 
> you posted a million times (with the max limit set to 1000), below is the 
> frequency of the numbers generated (in the format  X  )
>
>
> On Friday, February 7, 2014 11:42:03 AM UTC-8, Don wrote:
>>
>> Because if you put that in a loop you will get a series like:
>>
>> 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
>>
>> On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:
>>>
>>> Just curious... Why is this more random than 
>>> (getSystemTimeInMilliseconds() % 10)
>>>
>>> On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don 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 * (x&65535) + (x>>16);
>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.

[algogeeks] Re: Generate random number from 1 to 10.

[SVIX]

:) true... that was silly of me.. I was too quick to post... anyway, the 
point I was trying to understand was why this specific combination of 
operations would produce good randomness... Running the original solution 
you posted a million times (with the max limit set to 1000), below is the 
frequency of the numbers generated (in the format  X  )

Hello World!
502 x 2061, 245 x 644, 396 x 1328, 537 x 1103, 639 x 1419, 621 x 1401, 298 
x 1372, 388 x 888, 668 x 519, 108 x 1621, 912 x 1829, 954 x 1077, 393 x 
1220, 959 x 788, 5
25 x 1331, 203 x 788, 769 x 1330, 275 x 1162, 425 x 756, 578 x 770, 84 x 
698, 761 x 1082, 698 x 1122, 375 x 1230, 805 x 1329, 483 x 1620, 573 x 936, 
377 x 1039, 54 x
 672, 858 x 523, 662 x 506, 752 x 1083, 430 x 1206, 472 x 1990, 38 x 1674, 
417 x 765, 43 x 1280, 787 x 2051, 227 x 1754, 329 x 913, 835 x 1182, 512 x 
652, 78 x 1001,
 882 x 1467, 559 x 1178, 602 x 1326, 168 x 1358, 845 x 755, 411 x 243, 977 
x 1129, 543 x 1844, 745 x 1661, 549 x 2088, 115 x 2151, 554 x 367, 358 x 
1359, 162 x 1021,
 839 x 391, 406 x 1916, 972 x 1416, 649 x 1009, 453 x 766, 19 x 961, 585 x 
1075, 24 x 833, 67 x 900, 395 x 1056, 310 x 1032, 638 x 1435, 788 x 1824, 
119 x 629, 924 x
 1136, 490 x 774, 167 x 834, 257 x 869, 61 x 1209, 865 x 996, 542 x 385, 
109 x 1942, 913 x 1837, 352 x 962, 156 x 780, 722 x 1892, 637 x 641, 144 x 
643, 354 x 1353,
209 x 936, 13 x 1072, 579 x 1277, 256 x 1423, 627 x 2101, 431 x 1234, 478 x 
1110, 619 x 667, 990 x 1026, 965 x 865, 233 x 1362, 335 x 1336, 774 x 1026, 
626 x 974, 14
5 x 1778, 286 x 1292, 656 x 781, 460 x 1057, 899 x 923, 704 x 1167, 270 x 
883, 947 x 1036, 751 x 1789, 139 x 824, 994 x 1263, 560 x 915, 365 x 944, 
864 x 720, 132 x
2159, 996 x 910, 477 x 815, 44 x 1124, 550 x 1120, 989 x 714, 555 x 1606, 
359 x 2573, 36 x 860, 186 x 1602, 407 x 1671, 758 x 995, 842 x 1142, 459 x 
1265, 25 x 764,
830 x 824, 269 x 2126, 657 x 683, 461 x 1406, 687 x 1212, 364 x 879, 930 x 
1001, 122 x 1437, 561 x 511, 127 x 1195, 932 x 847, 175 x 1161, 633 x 478, 
72 x 1760, 443
x 1657, 448 x 1159, 252 x 1454, 929 x 1254, 733 x 894, 501 x 1574, 305 x 
1442, 675 x 1698, 114 x 2041, 680 x 1355, 723 x 2015, 400 x 695, 204 x 
1332, 770 x 1118, 911
 x 1455, 715 x 1302, 281 x 1172, 823 x 962, 768 x 712, 334 x 684, 436 x 
1288, 3 x 2315, 246 x 1578, 336 x 1445, 251 x 1334, 55 x 1388, 299 x 1259, 
669 x 679, 716 x 1
201, 282 x 940, 526 x 1617, 92 x 1043, 37 x 839, 841 x 718, 341 x 1606, 847 
x 1842, 949 x 713, 90 x 1152, 192 x 1264, 137 x 1237, 942 x 1201, 568 x 
370, 74 x 718, 79
9 x 801, 169 x 1894, 608 x 1019, 174 x 878, 978 x 528, 655 x 271, 264 x 
899, 703 x 1344, 507 x 1001, 73 x 882, 877 x 294, 317 x 1220, 883 x 974, 
126 x 936, 496 x 104
2, 697 x 285, 544 x 1044, 983 x 1104, 353 x 1226, 919 x 912, 163 x 1950, 
205 x 2031, 14 x 1006, 258 x 1049, 62 x 1027, 157 x 2209, 401 x 1475, 9 x 
2093, 56 x 1367, 4
95 x 964, 300 x 1369, 104 x 1105, 151 x 1551, 394 x 825, 289 x 1655, 966 x 
1789, 514 x 1260, 953 x 1267, 520 x 1195, 86 x 949, 1 x 1123, 567 x 1450, 
371 x 1514, 48 x
 1630, 198 x 388, 241 x 1529, 807 x 2055, 50 x 2080, 556 x 970, 651 x 717, 
900 x 855, 508 x 1434, 318 x 734, 646 x 1478, 383 x 627, 889 x 2111, 693 x 
1925, 936 x 259
5, 741 x 933, 418 x 988, 984 x 1008, 31 x 727, 926 x 823, 603 x 1472, 211 x 
919, 888 x 1070, 692 x 1944, 259 x 1751, 68 x 1263, 311 x 1005, 793 x 998, 
925 x 753, 491
 x 1414, 210 x 1972, 301 x 1917, 306 x 2586, 348 x 1196, 724 x 1596, 967 x 
1326, 584 x 692, 686 x 1287, 776 x 1222, 581 x 939, 824 x 982, 866 x 1834, 
7 x 624, 51 x 1
719, 234 x 730, 337 x 1166, 848 x 1576, 479 x 1054, 199 x 474, 467 x 1034, 
442 x 1172, 8 x 802, 812 x 382, 379 x 825, 562 x 583, 128 x 1608, 133 x 
248, 937 x 1322, 1
81 x 393, 747 x 1187, 424 x 1491, 228 x 1040, 794 x 1013, 659 x 532, 800 x 
1139, 604 x 1651, 170 x 633, 413 x 719, 455 x 1060, 895 x 839, 521 x 647, 
265 x 641, 312 x
 1340, 450 x 915, 735 x 1005, 217 x 999, 783 x 939, 26 x 856, 878 x 1151, 
121 x 1068, 253 x 1323, 931 x 1169, 63 x 1370, 740 x 1414, 872 x 833, 158 x 
1165, 597 x 822
, 57 x 1880, 973 x 1380, 539 x 1034, 105 x 629, 20 x 871, 628 x 515, 634 x 
1153, 438 x 538, 681 x 1435, 247 x 1126, 99 x 634, 623 x 1613, 806 x 1417, 
372 x 805, 347
x 1659, 616 x 809, 420 x 2190, 859 x 917, 663 x 1401, 229 x 1455, 473 x 
1149, 427 x 1228, 342 x 1253, 908 x 1931, 474 x 1197, 718 x 1251, 938 x 
998, 615 x 860, 705 x
 1043, 795 x 1209, 414 x 1677, 218 x 1094, 27 x 863, 837 x 702, 80 x 1243, 
212 x 1005, 694 x 867, 498 x 1659, 545 x 683, 355 x 1006, 32 x 1153, 836 x 
1547, 974 x 100
3, 540 x 2549, 825 x 926, 873 x 809, 116 x 1164, 920 x 536, 449 x 1673, 254 
x 900, 582 x 1214, 497 x 1668, 629 x 970, 915 x 647, 729 x 924, 771 x 1138, 
777 x 633, 81
9 x 1177, 385 x 1430, 586 x 1163, 390 x 1430, 481 x 1044, 962 x 908, 766 x 
, 813 x 913, 193 x 1609, 235 x 1173, 801 x 1018, 288 x 1014, 914 x 
1583, 658 x 1016, 4
62 x 1278, 901 x 1296, 509 x 838, 515 x 537, 319 x 969, 146 x 1026, 950 x 
1632, 517 x 1029, 956 x 811,

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 >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 * (X&65535) + (X>>16);
>>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"  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 * (x&65535) + (x>>16);
>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 .
>>
>
>

-- 
You received this message because you are 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  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 * (X&65535) + (X>>16);
>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"  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 * (x&65535) + (x>>16);
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.

[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 * (X&65535) + (X>>16);
   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" > 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 * (x&65535) + (x>>16);
>>>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.