Re: [algogeeks] SDE-1 openings in Amazon

[sourabh jain]

Location?

Thank You
Have a Nice Day :)

Regards
Sourabh Kumar Jain
Computer Science Corporation(CSC)
Hyderabad, Telangana.
MOB.-+91916049
  +919993878717

On 2 December 2014 at 15:44, Bhanu Kishore  wrote:

> Hi,
>   We have 4 SDE-1 openings in our team at Amazon Hyderabad. If any of you
> are interested, you can forward your resume to bhanukishor...@gmail.com
>
> --
> Thank & Regards,
>
> Bhanu Kishore Diddi.
> Software Development Engineer,
> Amazon India Development Center(Hyderabad).
> Mobile :- 9704253365
> Email:- kisho...@amazon.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] Find the max element of sets of size K

[sourabh jain]

@kumar raja : check the last approach in given link.


On Wed, Sep 11, 2013 at 4:44 PM, kumar raja wrote:

> I heard there exists a O(n) algorithm in DP? Does anyone has the idea
> about it?
>
>
> On 11 September 2013 03:21, Aaquib Javed  wrote:
>
>> http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
>>
>>
>> On Tue, Sep 10, 2013 at 11:46 PM, kumar raja wrote:
>>
>>> suppose we have n numbers and k <=n.
>>>
>>> Then a1,a2... ak is one set.
>>>
>>> then a2,a3 ak+1 is other set.
>>> ...
>>> so totally we can have n-k+1 sets.
>>>
>>> how to figure out the maximum elements of all these k size sets with
>>> least possible time complexity and space complexity?
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>>
>>
>> --
>> Aaquib Javed
>> B.Tech. Final Year
>> Electronics & Comm Engineering
>> MNNIT Allahabad.
>> +91-8953519834
>>
>> --
>> You received this message because you are subscribed to the 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,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[sourabh jain]

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

> Can anyone modify this solution so that it does not duplicate the memory
> at each level of recursion?
>
> (Here is my solution with the fix mentioned above)
>
> typedef std::vector btree;
>
> bool sameBstFormed(btree t1, btree t2)
> {
>bool result;
>if (t1.size() != t2.size()) result = false;
>else if (t1.size() == 0) result = true;
>else if (t1[0] != t2[0]) result = false;
>else if (t1.size() == 1) result = true;
>else
>{
>   btree left1, right1, left2, right2;
>   for(int i = 1; i < t1.size(); ++i)
>   {
>  if (t1[i] < t1[0]) left1.push_back(t1[i]);
>  else right1.push_back(t1[i]);
>  if (t2[i] < t2[0]) left2.push_back(t2[i]);
>  else right2.push_back(t2[i]);
>   }
>   result = sameBstFormed(left1, left2) && sameBstFormed(right1,
> right2);
>}
>return result;
> }
>
> On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:
>>
>> Yes, you are right. Good catch.
>>
>> On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:
>>>
>>> Amazing solution Don, thank you :)  You missed a small check in the
>>> code: if(t1[0] != t2[0]) return 0;
>>>
>>>
>>> On Tue, Jul 9, 2013 at 11:27 PM, Don  wrote:
>>>
 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

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

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

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

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:
>
> I came across this question on careercup: how do we go about finding
> whether the BSTs formed by the given input order would be identical or not
> without actually forming the tree?
>
> Link: 
> http://www.careercup.**com**/question?id=19016700
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To unsubscribe from this group and stop receiving emails from it, send
 an email to algogeeks+...@googlegroups.com**.



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

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

Re: [algogeeks] Re:

[sourabh jain]

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

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

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


On Fri, Jun 21, 2013 at 11:44 PM, Don  wrote:

> The n<3 condition is the base case. For n=0,1, or 2 the answer is n.
>
> x is floor(log2(n))
>
> This can be computed in constant time by the built in function provided.
> It is the same as the position of the highest bit set in n.
>
> Then the number of bits in 0..n is the number of times the xth bit is set
> plus the number of bits in 0..n-2^x. That is what the last line computes.
>
> Don
>
>
> On Friday, June 21, 2013 1:42:08 PM UTC-4, shubham saini wrote:
>
>> thanx Don for your algos, bt i m not able to understand your second
>> approach can you please explain it a liitle
>>
>>
>> On Fri, Jun 21, 2013 at 9:50 PM, Don  wrote:
>>
>>> int bitCount(int n)
>>> {
>>>if (n < 3) return n;
>>>int x=31-__builtin_clz(n);
>>>n -= 1<>>return x*(1<<(x-1)) + bitCount(n) + n + 1;
>>>
>>>  }
>>>
>>> On Thursday, June 20, 2013 11:03:35 PM UTC-4, shubham saini wrote:
>>>
>>>> How to count no of set bits for all numbers from 1 to n for a given n...
>>>>
>>>> i knew brute force any better solution ??
>>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+...@**googlegroups.com.
>>>
>>>
>>>
>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] kth smallest element in 2 sorted arrays

[sourabh jain]

its same as finding a median of two sorted arrays only.
http://www.geeksforgeeks.org/median-of-two-sorted-arrays/


On Sun, Jun 9, 2013 at 4:49 PM, rahul sharma wrote:

> Please suggest logm+logn aproach...
> can be easily done in o(k)
>
>
> How to do in logm +logn
>
> plz suggest algo
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] Re: t9 dictionary

[sourabh jain]

hi this is my java implementation of trie with 26 keys.

public class Trie {
public Trie [] childs;
char data;
 boolean isEnd;
TreeSet ts;
String possiblity;
 public Trie(){
childs=new Trie[26];
isEnd=false;
 ts=new TreeSet();
}
public void add(String s){
 char ar[]=s.toLowerCase().toCharArray();
 StringBuffer sb=new StringBuffer();
 for(int i=0;i=ar[i]){
sb.append(ar[i]);
 }else if('A'<=ar[i] && 'Z'>=ar[i]){
sb.append((char)('a'+ar[i]-'A'));
 }
}
ar=sb.toString().toCharArray();
if(ar.length<1) return;
 ts.add(sb.toString());
_add(this,ar,0);
 }
public void _add(Trie root,char ar[],int index){
if(root.childs[ar[index]-'a']==null){
 root.childs[ar[index]-'a']=new Trie();
root.childs[ar[index]-'a'].data=ar[index];
 }
 if(ar.length-1==index){
root.childs[ar[index]-'a'].isEnd=true;
 root.childs[ar[index]-'a'].possiblity=new String(ar);
return;
}
 _add(root.childs[ar[index]-'a'],ar,index+1);
}
public boolean search(String s){
 if(s.indexOf(" ")!=-1){ System.out.println(s); return;}
char ar[]=s.toLowerCase().toCharArray();
 if( _search(this,ar,0)){
return true;
}
return false;
 }
 public boolean _search(Trie root,char ar[],int index){
 if(index >= ar.length) return false;
if(root==null) return false;
return (index==ar.length-1 && root.childs[ar[index]-'a']!=null &&
root.childs[ar[index]-'a'].isEnd)? true:
_search(root.childs[ar[index]-'a'],ar,index+1);
 }
}


On Mon, Jun 3, 2013 at 11:22 PM, rahul sharma wrote:

> Can i implement by trie which is having structure as 9 pointers for 9
> digits..like if it comes 4663...i will make a path 4663 from root to leaf
> and in end i will have a linked list to store dataany more optimized
> solution anyone having???plz suggest
>
>
> On Thu, May 30, 2013 at 2:37 AM, rahul sharma wrote:
>
>> how to implement with trie.???is trie the best way..plz provide me raw
>> algo to start with,
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

Hi ravi ,
I think he is trying to find the longest possible increasing chain in
matrix .
he needs to start traversing from first row choosing columns one by one and
move in all direction. but he needs to maintain the already visited nodes.


On Thu, Jun 6, 2013 at 12:07 AM, sourabh jain  wrote:

> Round 1 :
> Q2: given BST is not correct.
> correct BST passing this condition will be 7
>  /
> 5
>   /
>  3
>\
> 4
> in this case the root element of given BST will be the largest if left
> child exist or will be the smallest if right child exist.
>
> so you just need to start checking the last value of given post order.
> eg: in this case
> post order will be  4 3 5 7
>  here last value is 7 so it is greatest among all so left nde exist.
> next is 5 which is largest of remaining  so left node exist for this
> next is 3 which is smallest of remaining so 4 will come on right node.
>
>
> On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan wrote:
>
>> Can u clear Round3 --- Qstn-3. the language is not cleared
>>
>>
>> On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain  wrote:
>>
>>> Round 1:
>>> 1.Design a Data Structure supporting 3 queries a)push b)pop c) find
>>> minimum
>>> Ans : Do it using Two Stacks . in first stack use it as normal stack.
>>> second stack use it to find minimun as the value inserted is greater than
>>> the top ignore it else push it. if pop operation happens and the value
>>> popped is equal to the top(s2)  then pop(s2).
>>>
>>> time complexity push : O(1) , pop O(1) , find Minimum O(1)
>>>
>>> 2.Given post order of a BST find whether each node of the tree(except
>>> leaf) has only 1 child or not.
>>>eg5
>>> \
>>>  7
>>> /
>>>3
>>>   /
>>>  2
>>> is correct as each node has only 1 child.
>>>
>>> Round 2:
>>> 1.Given a sorted array a and a sum k print all pairs of indexes i and
>>> j such that a[i]+a[j]=k.
>>>
>>> put one pointer at index 0 and 2nd at length(ar)-1.
>>>
>>> while (i>>  if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
>>>  else if(ar[i])+ar[j] >>  else if(ar[i])+ar[j] >k) j--;
>>> }
>>>
>>> 2.Given a matrix that is row and column wise sorted give an algo for
>>> finding count of the total no of -ve nos.
>>>
>>> start from (0,n) move towards right if found +ve and increment count of
>>> positive in row. else move down .
>>>
>>> Round 3:
>>> 1.Given a matrix consisting of nos you can print the max length of
>>> sequence possible where in a sequence each consecutive nos have a diff
>>> of +1 or -1.
>>>
>>> eg 3 5 7 3
>>>  4 5 8 1
>>>  6 4 5 2
>>>
>>> here sequence is 3
>>>   4 5
>>>  4 5
>>> *you can do it using recursion *
>>>
>>> 2.Give a data structure that supports following queries a)insert
>>> b)delete c)ispresent d)print all elements
>>> *BST's ... , if insertionorder needs to be maintained then linked list;*
>>>
>>>
>>> 3.Given a infinite supply of n cylinders where each cylinder is
>>> specified by weight of 02,weight of n2,total weight ,
>>> now u need some minimum quantity of o2 and n2 by selecting
>>> cylinders and your aim is make it so that u have min total weight.
>>> output the minimum total weight .
>>>
>>> Round 4:
>>> 1.Given 2 sorted arrays find there median
>>>  .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
>>>
>>> 2.Consider column of ms excel the start with A,BZ,AA
>>> Now u r given column no u need to print its name
>>>  *Ans : Same as number system problem with base 26*
>>>
>>> 3.Given 2 arrays.Imagine you are making bst from each array.u need to
>>> tell whether 2 bsts will be identical or not without actually
>>> constructing the tree.
>>> eg   1 2 3
>>>1 3 2
>>> will construct the same tree
>>>
>>>
>>

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

Round 1 :
Q2: given BST is not correct.
correct BST passing this condition will be 7
 /
5
  /
 3
   \
4
in this case the root element of given BST will be the largest if left
child exist or will be the smallest if right child exist.

so you just need to start checking the last value of given post order.
eg: in this case
post order will be  4 3 5 7
 here last value is 7 so it is greatest among all so left nde exist.
next is 5 which is largest of remaining  so left node exist for this
next is 3 which is smallest of remaining so 4 will come on right node.


On Wed, Jun 5, 2013 at 5:14 PM, Ravi Ranjan  wrote:

> Can u clear Round3 --- Qstn-3. the language is not cleared
>
>
> On Wed, Jun 5, 2013 at 1:52 PM, sourabh jain  wrote:
>
>> Round 1:
>> 1.Design a Data Structure supporting 3 queries a)push b)pop c) find
>> minimum
>> Ans : Do it using Two Stacks . in first stack use it as normal stack.
>> second stack use it to find minimun as the value inserted is greater than
>> the top ignore it else push it. if pop operation happens and the value
>> popped is equal to the top(s2)  then pop(s2).
>>
>> time complexity push : O(1) , pop O(1) , find Minimum O(1)
>>
>> 2.Given post order of a BST find whether each node of the tree(except
>> leaf) has only 1 child or not.
>>eg5
>> \
>>  7
>> /
>>3
>>   /
>>  2
>> is correct as each node has only 1 child.
>>
>> Round 2:
>> 1.Given a sorted array a and a sum k print all pairs of indexes i and
>> j such that a[i]+a[j]=k.
>>
>> put one pointer at index 0 and 2nd at length(ar)-1.
>>
>> while (i>  if(ar[i]+ar[j]==k) {printpairs; i++; j++;}
>>  else if(ar[i])+ar[j] >  else if(ar[i])+ar[j] >k) j--;
>> }
>>
>> 2.Given a matrix that is row and column wise sorted give an algo for
>> finding count of the total no of -ve nos.
>>
>> start from (0,n) move towards right if found +ve and increment count of
>> positive in row. else move down .
>>
>> Round 3:
>> 1.Given a matrix consisting of nos you can print the max length of
>> sequence possible where in a sequence each consecutive nos have a diff
>> of +1 or -1.
>>
>> eg 3 5 7 3
>>  4 5 8 1
>>  6 4 5 2
>>
>> here sequence is 3
>>   4 5
>>  4 5
>> *you can do it using recursion *
>>
>> 2.Give a data structure that supports following queries a)insert
>> b)delete c)ispresent d)print all elements
>> *BST's ... , if insertionorder needs to be maintained then linked list;*
>>
>>
>> 3.Given a infinite supply of n cylinders where each cylinder is
>> specified by weight of 02,weight of n2,total weight ,
>> now u need some minimum quantity of o2 and n2 by selecting
>> cylinders and your aim is make it so that u have min total weight.
>> output the minimum total weight .
>>
>> Round 4:
>> 1.Given 2 sorted arrays find there median
>>  .http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
>>
>> 2.Consider column of ms excel the start with A,BZ,AA
>> Now u r given column no u need to print its name
>>  *Ans : Same as number system problem with base 26*
>>
>> 3.Given 2 arrays.Imagine you are making bst from each array.u need to
>> tell whether 2 bsts will be identical or not without actually
>> constructing the tree.
>> eg   1 2 3
>>1 3 2
>> will construct the same tree
>>
>>
>> On Mon, Jun 3, 2013 at 10:52 PM, *$*  wrote:
>>
>>> these are for which position? and experience?
>>>
>>>
>>> On Thu, May 2, 2013 at 9:27 PM, Guneesh  wrote:
>>>
>>>> Round 1:
>>>> 1.Design a Data Structure supporting 3 queries a)push b)pop c) find
>>>> minimum
>>>> 2.Given post order of a BST find whether each node of the tree(except
>>>> leaf) has only 1 child or not.
>>>>eg5
>>>> \
>>>>  7
>>>> /
>>>>3
>>>>   /
>>>>  2
>>>> is correct as each

Re: [algogeeks] Minimum number of coins to SUM to S

[sourabh jain]

it is similar to knapsack problem.


On Thu, May 30, 2013 at 2:35 AM, rahul sharma wrote:

> yes clasic DP
>
>
> On Wed, May 29, 2013 at 8:54 PM, Ravi Ranjan wrote:
>
>> @DAve
>>
>> any proper reason or link to proof that at least twice can be solved
>> using greedy but others are not??
>>
>>
>> On Tue, May 28, 2013 at 12:41 PM, Shashwat Kumar <
>> shashwatkmr@gmail.com> wrote:
>>
>>> This seems to be Coin Change problem. Just google that.
>>>
>>>
>>> On Tue, May 28, 2013 at 12:42 AM, Adolfo Ccanto wrote:
>>>
>>>> Can you write the constraints for this problem?
>>>> thanks.
>>>> Adolfo
>>>>
>>>>
>>>> 2013/5/18 rahul sharma 
>>>>
>>>>> Minimum of coins to sum s
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the 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.
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Shashwat Kumar
>>> Third year Undergraduate student
>>> Department of Computer Science and Engineering
>>> IIT Kharagpur
>>>
>>>
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the 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.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] Amazon interview Questions

[sourabh jain]

Round 1:
1.Design a Data Structure supporting 3 queries a)push b)pop c) find
minimum
Ans : Do it using Two Stacks . in first stack use it as normal stack.
second stack use it to find minimun as the value inserted is greater than
the top ignore it else push it. if pop operation happens and the value
popped is equal to the top(s2)  then pop(s2).

time complexity push : O(1) , pop O(1) , find Minimum O(1)

2.Given post order of a BST find whether each node of the tree(except
leaf) has only 1 child or not.
   eg5
\
 7
/
   3
  /
 2
is correct as each node has only 1 child.

Round 2:
1.Given a sorted array a and a sum k print all pairs of indexes i and
j such that a[i]+a[j]=k.

put one pointer at index 0 and 2nd at length(ar)-1.

while (ik) j--;
}

2.Given a matrix that is row and column wise sorted give an algo for
finding count of the total no of -ve nos.

start from (0,n) move towards right if found +ve and increment count of
positive in row. else move down .

Round 3:
1.Given a matrix consisting of nos you can print the max length of
sequence possible where in a sequence each consecutive nos have a diff
of +1 or -1.

eg 3 5 7 3
 4 5 8 1
 6 4 5 2

here sequence is 3
  4 5
 4 5
*you can do it using recursion *

2.Give a data structure that supports following queries a)insert
b)delete c)ispresent d)print all elements
*BST's ... , if insertionorder needs to be maintained then linked list;*

3.Given a infinite supply of n cylinders where each cylinder is
specified by weight of 02,weight of n2,total weight ,
now u need some minimum quantity of o2 and n2 by selecting
cylinders and your aim is make it so that u have min total weight.
output the minimum total weight .

Round 4:
1.Given 2 sorted arrays find there median
.http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
2.Consider column of ms excel the start with A,BZ,AA
Now u r given column no u need to print its name
*Ans : Same as number system problem with base 26*
3.Given 2 arrays.Imagine you are making bst from each array.u need to
tell whether 2 bsts will be identical or not without actually
constructing the tree.
eg   1 2 3
   1 3 2
will construct the same tree


On Mon, Jun 3, 2013 at 10:52 PM, *$*  wrote:

> these are for which position? and experience?
>
>
> On Thu, May 2, 2013 at 9:27 PM, Guneesh  wrote:
>
>> Round 1:
>> 1.Design a Data Structure supporting 3 queries a)push b)pop c) find
>> minimum
>> 2.Given post order of a BST find whether each node of the tree(except
>> leaf) has only 1 child or not.
>>eg5
>> \
>>  7
>> /
>>3
>>   /
>>  2
>> is correct as each node has only 1 child.
>>
>> Round 2:
>> 1.Given a sorted array a and a sum k print all pairs of indexes i and
>> j such that a[i]+a[j]=k.
>> 2.Given a matrix that is row and column wise sorted give an algo for
>> finding count of the total no of -ve nos.
>>
>> Round 3:
>> 1.Given a matrix consisting of nos you can print the max length of
>> sequence possible where in a sequence each consecutive nos have a diff
>> of +1 or -1.
>>
>> eg 3 5 7 3
>>  4 5 8 1
>>  6 4 5 2
>>
>> here sequence is 3
>>   4 5
>>  4 5
>> 2.Give a data structure that supports following queries a)insert
>> b)delete c)ispresent d)print all elements
>>
>> 3.Given a infinite supply of n cylinders where each cylinder is
>> specified by weight of 02,weight of n2,total weight ,
>> now u need some minimum quantity of o2 and n2 by selecting
>> cylinders and your aim is make it so that u have min total weight.
>> output the minimum total weight .
>>
>> Round 4:
>> 1.Given 2 sorted arrays find there median.
>> 2.Consider column of ms excel the start with A,BZ,AA
>> Now u r given column no u need to print its name
>> 3.Given 2 arrays.Imagine you are making bst from each array.u need to
>> tell whether 2 bsts will be identical or not without actually
>> constructing the tree.
>> eg   1 2 3
>>1 3 2
>> will construct the same tree
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
> --
> Thx,
> --Gopi
>
> --
> You rece

Re: [algogeeks] Infinite stream , identify distinct k kintegers

[sourabh jain]

use a bit vector to mark the existence of the distinct Integer.

eg :
vector : 00
integer occured : 5 7 9 22 8
vector: 000111101


On Sun, Jun 2, 2013 at 12:57 PM, Avi Dullu  wrote:

> (For very large k case only)
>
> Keep as many elements in the hash_map as you can. Once the map capacity is
> exhausted, sort all the elements in the hash_map and write them to disk and
> build a bloom filter. Keep this bloom 
> filter<http://en.wikipedia.org/wiki/Bloom_filter>in memory, empty the 
> hash_map and now for every new number in the stream,
> check in the bloom filter, if it says does not exist, that means this is a
> new number, insert in the map. If it says the number does exist, then this
> can be a false positive, then first check in the map, if not found in it,
> it could be on disk. Use a binary search on the file (this will take
> O(logn) disk seeks) and verify if its present in the file or not. If
> present, ignore, else add in the map. Keep repeating the process of
> flushing the map to disk whenever the map is full. To flush, you could
> either use any external 
> sorting<http://en.wikipedia.org/wiki/External_sorting>method, or just write 
> out a new file each time. If separate files, you will
> need to binary search in all of them in case of false positive.
>
> Programmers should realize their critical importance and responsibility in
> a world gone digital. They are in many ways similar to the priests and
> monks of Europe's Dark Ages; they are the only ones with the training and
> insight to read and interpret the "scripture" of this age.
>
>
> On Sat, Jun 1, 2013 at 10:19 PM, MAC  wrote:
>
>> Given an infinite stream of integers with only k distinct integers, find
>> those distinct integers. How would you modify your solution if k is also
>> very large and cannot use hash table.
>>
>>
>>
>>
>>
>> thanks
>> --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

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

Re: [algogeeks] Infinite stream , identify distinct k kintegers

[sourabh singh]

for each num instream
inserting num to stl::set()
if size of set == k
 break

O(nlogk)


On Sun, Jun 2, 2013 at 10:49 AM, MAC  wrote:

> Given an infinite stream of integers with only k distinct integers, find
> those distinct integers. How would you modify your solution if k is also
> very large and cannot use hash table.
>
>
>
>
>
> thanks
> --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

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

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

@sandeep he is talking about constant space.

On Tue, Mar 19, 2013 at 5:31 PM, sandeep kumar
wrote:

> Hey what if while scanning through the array we create a BST n check
> simultaneously that :
>
> current node == current node's parent && current node == current node's
> left or right child
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Cyclic sorting problem

[sourabh jain]

Hi all ,

if an array is given in random order , you have to output the minimum
number of swaps required to convert into cyclic sorted array.

e.g. array given is 3 5 4 2 1

so the first swap will be 5<-->4   result : 3 4 5 2 1
second swap will be  2<-->1  result : 3 4 5 1 2 (final)

output : 2





-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Print tree node which sum

[sourabh jain]

take two stacks of O(logn) space use one to traverse as left - > root->
right (inorder) and other as right->root-> left(reverse inorder) like

while (true){

 a=top(s1);
b=top(s2);
if(a+b==sum ) break;
if(a+b  sum) pop(s2);
}

if(s1 && s2 are empty) no solution
else result = top(s1) and top(s2);

On Tue, Mar 5, 2013 at 1:24 PM, marti  wrote:

> Given a value , print two nodes that sum to the value in a BST and normal
> tree.. time:O(n), space O(logn).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] MS Question:WAP to print last n lines of a log file

[sourabh jain]

Read line by line . use doublylinkedlist(Queue)/ Circular Buffer of size N.
when EOF is achieved print the lines.


On Mon, Mar 4, 2013 at 9:10 AM, Ashish Goel  wrote:

> Q1. Given a log file, pirnt last n lines. Note that the Log file is being
> written into.
> Q2. Implement Circular Buffer.
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

you can solve this problem using bitvector/bitset.

first scan :
scan the array set the bit on odd occurrence and unset on even or
0 occurrence.

second scan :
shift all the odd occurring elements in beginning of array and even towards
end.

third scan : till end of odd occurring elements.
take another bit vector
on first occurence :if bit is set in bv1 then unset it and set it in bv2.
on second occurence : if bv1 is not set and bv2 is set then these are the
array elements occuring 3rd time.





On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh
wrote:

> Yes, thats a valid point Don.
> Thats what i meant when i wrote  "//is that correct?" in the comments on
> the array line in code.
>
>
>  int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>
>
> On Wed, Feb 13, 2013 at 9:09 PM, Don  wrote:
>
>> The xor approach only works if there are no values which occur only
>> once. But the problem statement indicates that some numbers occur
>> once, some occur twice, and one occurs three times. So you will end up
>> with prod equal to the xor of all of the values which occur once or
>> three times. Put that in your input array and you'll find that you
>> don't get the desired output.
>>
>> I don't know of a solution better than sorting and scanning the array.
>>
>> Don
>>
>> On Feb 12, 3:14 pm, prakhar singh  wrote:
>> > #include
>> >
>> > int main()
>> > {
>> >int a[] = {2,2,3,3,3,1,1,4,4};   // is this correct?
>> >int prod=a[0];int i;
>> >for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
>> >{
>> >   prod ^= a[i];
>> >}
>> >printf("%d\n",prod);   //outputs 3, algorithm works as Sachin
>> described
>> > it;
>> >
>> > }
>> >
>> > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > use ex-or operation for all array elements..
>> > > a^a=0
>> > > a^a^a=a
>> >
>> > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B <
>> mohanabala...@gmail.com>wrote:
>> >
>> > >> can use counting sort
>> >
>> > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota <
>> santoshthot...@gmail.com>wrote:
>> >
>> > >>> If we can retrieve ith prime efficiently, we can do the following...
>> > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th
>> prime
>> > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>> > >>>else prod=prod*ith_prime;
>> > >>> 3.repeat it till end
>> >
>> > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>> >
>> > >>>> Given an array of integers where some numbers repeat once, some
>> numbers
>> > >>>> repeat twice and only one number repeats thrice, how do you find
>> the number
>> > >>>> that gets repeated 3 times?
>> >
>> > >>>> Does this problem have an O(n) time and O(1) space solution?
>> > >>>> No hashmaps please!
>> >
>> > >>>  --
>> > >>> You received this message because you are subscribed to the Google
>> > >>> Groups "Algorithm Geeks" group.
>> > >>> To view this discussion on the web visit
>> > >>>https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ.
>> >
>> > >>> To post to this group, send email to algogeeks@googlegroups.com.
>> > >>> To unsubscribe 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 unsubscribe from this group and stop receiving emails from it,
>> send an
>> > >> email to algogeeks+unsubscr...@googlegroups.com.
>> > >> For more options, visithttps://groups.google.com/groups/opt_out.
>> >
>> > > --
>> > > Regards,
>> > > Sachin Chitale
>> > > Application Engineer SCJP, SCWCD
>> > > Contact# : +91 8086284349, 9892159511
>> > > Oracle Cor

Re: [algogeeks] Re: Amazon Interview Question

[sourabh jain]

Search for BitSet/BitVector in java .

On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
wrote:

> use ex-or operation for all array elements..
> a^a=0
> a^a^a=a
>
>
> On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B 
> wrote:
>
>> can use counting sort
>>
>>
>> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota 
>> wrote:
>>
>>> If we can retrieve ith prime efficiently, we can do the following...
>>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
>>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
>>>else prod=prod*ith_prime;
>>> 3.repeat it till end
>>>
>>>
>>>
>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>
>>>> Given an array of integers where some numbers repeat once, some numbers
>>>> repeat twice and only one number repeats thrice, how do you find the number
>>>> that gets repeated 3 times?
>>>>
>>>> Does this problem have an O(n) time and O(1) space solution?
>>>> No hashmaps please!
>>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/TSPSKlD0FDsJ.
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe 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 unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Amazon interview Question

[sourabh jain]

One solution for the 2nd question can be LinkedHashMap (linked list +
hashmap) .
Store the integer in linked list in the order of occurrence in stream and
make an entry in hashmap on first occurence. Delete the integer entry from
linked list on 2nd occurence and replace the reference with some special
value so for 3rd time no need to touch the linked list. while printing the
result print first k integers from linked list.

On Fri, Feb 8, 2013 at 9:46 AM, bharat b wrote:

> @sourabh : how do u find whether the element in stream gets repeated in
> heap.--> O(n) time...totally its O(nk) algo ..
>
> If we maintain max-heap with BST property on index, then it would be
> O(nlogk).
>
>
> On Wed, Feb 6, 2013 at 12:25 PM, sourabh jain  wrote:
>
>> for 2nd question you can make a heap with their index as a factor to
>> heapify them. whenever a integer in stream gets repeated you just nead to
>> remove it from heap and heapify it.
>>
>>
>> On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur <
>> navneet.singhg...@gmail.com> wrote:
>>
>>> nice algo ankit, so it will be nlogn using O (n) space only. What abt
>>> 2nd Q., which have a big online stream.
>>>
>>> On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit  wrote:
>>> > For 1:
>>> > i think you can use sorting, sort the array and keep the indices of the
>>> > numbers in the sorted list.
>>> > Now traverse the sorted list and  in the sorted list you need to find
>>> the
>>> > unique number with the
>>> > minimum index which is easy to find.
>>> >
>>> > Eg: Array:5 3 1 2 4 1 4
>>> >   Indices: 0 1 2 3 4 5 6
>>> >
>>> >
>>> > After sorting : Array:1 1 2 3 4 4 5
>>> > Indices:  2 5 3 1 4 6 1
>>> >
>>> > Now you can see the unique number with lowest index is 3(index=1). So
>>> , you
>>> > have your answer.
>>> >
>>> >
>>> > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur
>>> >  wrote:
>>> >>
>>> >> 1. Given a array,find a first unique integer.
>>> >> 2. Integers are coming as online stream,have to find a kth unique
>>> integer
>>> >> till now.
>>> >>
>>> >> For 1.
>>> >>
>>> >> Even we cannot use sorting for solving this as if we sort it than our
>>> >> first number which is non-repetitive changes.
>>> >>
>>> >> The best I am able to do is nlogn using a space of O( n ).
>>> >>
>>> >> For 2. No 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.
>>> >> For more options, visit https://groups.google.com/groups/opt_out.
>>> >>
>>> >>
>>> >
>>> >
>>> >
>>> >
>>> > --
>>> > Kumar Ankit
>>> > Senior Undergraduate
>>> > Department of Computer Engineering
>>> > Institute of Technology
>>> > Banaras Hindu University
>>> > Varanasi
>>> > Ph: +91 9473629892
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> Groups
>>> > "Algorithm Geeks" group.
>>> > To unsubscribe from this group and stop receiving emails from it, send
>>> an
>>> > email to algogeeks+unsubscr...@googlegroups.com.
>>> > For more options, visit https://groups.google.com/groups/opt_out.
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>> 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.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>> --
>> Regards,
>> Sourabh Kumar Jain
>> +91-8971547841
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>



-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Amazon interview Question

[sourabh jain]

for 2nd question you can make a heap with their index as a factor to
heapify them. whenever a integer in stream gets repeated you just nead to
remove it from heap and heapify it.


On Wed, Feb 6, 2013 at 10:00 AM, navneet singh gaur <
navneet.singhg...@gmail.com> wrote:

> nice algo ankit, so it will be nlogn using O (n) space only. What abt
> 2nd Q., which have a big online stream.
>
> On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit  wrote:
> > For 1:
> > i think you can use sorting, sort the array and keep the indices of the
> > numbers in the sorted list.
> > Now traverse the sorted list and  in the sorted list you need to find the
> > unique number with the
> > minimum index which is easy to find.
> >
> > Eg: Array:5 3 1 2 4 1 4
> >   Indices: 0 1 2 3 4 5 6
> >
> >
> > After sorting : Array:1 1 2 3 4 4 5
> > Indices:  2 5 3 1 4 6 1
> >
> > Now you can see the unique number with lowest index is 3(index=1). So ,
> you
> > have your answer.
> >
> >
> > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur
> >  wrote:
> >>
> >> 1. Given a array,find a first unique integer.
> >> 2. Integers are coming as online stream,have to find a kth unique
> integer
> >> till now.
> >>
> >> For 1.
> >>
> >> Even we cannot use sorting for solving this as if we sort it than our
> >> first number which is non-repetitive changes.
> >>
> >> The best I am able to do is nlogn using a space of O( n ).
> >>
> >> For 2. No 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.
> >> For more options, visit https://groups.google.com/groups/opt_out.
> >>
> >>
> >
> >
> >
> >
> > --
> > Kumar Ankit
> > Senior Undergraduate
> > Department of Computer Engineering
> > Institute of Technology
> > Banaras Hindu University
> > Varanasi
> > Ph: +91 9473629892
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
>
>
>
> --
> 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.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>


-- 
Regards,
Sourabh Kumar Jain
+91-8971547841

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] spoj problem EASYMATH

[Sourabh Singh]

please suggest something  :

Problem :
http://www.spoj.pl/problems/EASYMATH/

C++ code :
http://ideone.com/r2OSb
was getting wrong ans due to over flow i think in LCM() for big prime's i guess.
thin tried in python .

Now getting NZEC for python code which mean's high level or recurrsion
some where preventing
normal termination .
but where ??

Python code:
http://ideone.com/KDPPJ

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Find peak element in log(n)

[Sourabh Singh]

@Hassan Monfared

was reading that link only. it's strange how he assume's we can leave
half of element's ??

– If A[n/2-1]>A[n/2]  then search for a peak among A[1]… A[n/2-1] ?? why ??

eg. 12 12 12 11 1 2 5 3

m i missing something ??

On Sat, Jun 23, 2012 at 10:02 PM, Hassan Monfared  wrote:
> just found a good resource for 1d and 2D version :
> http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
>
>
> On Sun, Jun 24, 2012 at 3:31 AM, sengar.mahi  wrote:
>>
>> @adarsh :its nt dat easy as u see it..
>>
>>
>> On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh 
>> wrote:
>>>
>>> @adarsh kumar
>>>
>>> are u sure it's worst case will be O (log n) ??
>>> i think iff array is fully sorted O(n) will be required to say "NO
>>> such element present"
>>>
>>> On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar  wrote:
>>> > This is a variation of binary search, the difference being that we have
>>> > to
>>> > search for an element that is greater than its immediate left one and
>>> > lesser
>>> > than its immediate right one. Just implement binary search with these
>>> > additional constraints, thereby giving O(log n).
>>> > In case of any difficulty/error, let me know.
>>> >
>>> > On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared 
>>> > wrote:
>>> >>
>>> >> Given an array of integers find a peak element of array in log(n)
>>> >> time.
>>> >> for example if A={3,4,6,5,10} then peak element is 6  ( 6>5 & 6>4 ).
>>> >>
>>> >> Regards.
>>> >>
>>> >> --
>>> >> You received this message because you are subscribed to the Google
>>> >> Groups
>>> >> "Algorithm Geeks" group.
>>> >> To view this discussion on the web visit
>>> >> https://groups.google.com/d/msg/algogeeks/-/AQI6ahWgyOIJ.
>>> >> To post to this group, send email to algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> >> algogeeks+unsubscr...@googlegroups.com.
>>> >> For more options, visit this group at
>>> >> http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> > Groups
>>> > "Algorithm Geeks" group.
>>> > To post to this group, send email to algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> > algogeeks+unsubscr...@googlegroups.com.
>>> > For more options, visit this group at
>>> > http://groups.google.com/group/algogeeks?hl=en.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Regards
>> Mahendra Pratap Singh Sengar
>> B-tech 4/4
>> NIT Warangal.
>>
>> Facebook ID
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] 4Sum

[Sourabh Singh]

@ Amol Sharma

thanx got it..

yup, overlooked those case's :-) my bad..

On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma  wrote:

> @sourabh:
> for this particular question..
> in your code replace
>
> if(binary_search(c,c+size,-b[i]))
> count++;
>
> by
>
> count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]);
>
> you are actually missing some of the quadruplesas there can be more
> than one element with value -b[i] in the array c and you are actually
> ignoring them.
> --
>
>
> Amol Sharma
> Final Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>
> <http://gplus.to/amolsharma99> 
> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99>
>
>
>
>
>
>
> On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh 
> wrote:
>
>> @ALL
>>
>>  O(n^2 lg(n^2))
>>
>> http://www.spoj.pl/problems/SUMFOUR/
>>
>> my code :
>> http://ideone.com/kAPNB
>>
>> plz. suggest some test case's :
>>
>> On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma wrote:
>>
>>> @bhaskar,rammar:
>>>
>>> I don't think your algo willn not work for the following test case --
>>>
>>>
>>> test case :
>>> arr: 2 4 6 8
>>> arr^2 : 6 8 10 10 12 14(sum of each unique pair in
>>> arr[i])
>>>
>>> let's say target sum is 26
>>>
>>> your solution will return true as they 12+14=26 but in 12 and 14, 8 is
>>> common, infact 26  is not possible in the given array
>>>
>>> --
>>>
>>>
>>> Amol Sharma
>>> Final Year Student
>>> Computer Science and Engineering
>>> MNNIT Allahabad
>>>
>>> <http://gplus.to/amolsharma99> 
>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha <
>>> bhaskar.kushwaha2...@gmail.com> wrote:
>>>
>>>> We first compute the N^2 two sums, and sort the two sums. The for each
>>>> TwoSum t, we check whether there is another two sum t' such that t.value +
>>>> t'.value = target. The time complexity of this approach is O(N^2 logN)
>>>>
>>>>
>>>> On Wed, Jun 20, 2012 at 1:36 AM, rammar  wrote:
>>>>
>>>>> Lets see ur example... We can have two other arrays corresponding to
>>>>> our n^2 array.
>>>>> For every (target-arr[i]) which we search in our look up array, we can
>>>>> also search the components which were used to get that sum. This can be
>>>>> done in addition constant amount search.
>>>>> I hope we can still go with Hemesh's algo. Please let me know if it
>>>>> breaks somewhere...
>>>>>
>>>>> let's take a test case :
>>>>> arr: 2   4   68
>>>>> arr[0]: 6   8   10   10   12   14
>>>>> arr[1]: 2   22 4 46
>>>>> arr[2]: 4   68 6 88
>>>>>
>>>>>
>>>>> P.S. Can we do better?
>>>>>
>>>>> On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote:
>>>>>>
>>>>>> @rammar:
>>>>>> can you please explain the case...which i took in the earlier
>>>>>> post..with this method.
>>>>>>
>>>>>> --
>>>>>>
>>>>>>
>>>>>> Amol Sharma
>>>>>> Final Year Student
>>>>>> Computer Science and Engineering
>>>>>> MNNIT Allahabad
>>>>>>
>>>>>> <http://gplus.to/amolsharma99> 
>>>>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 19, 2012 at 11:27 PM, rammar  wrote:
>>>>>>
>>>>>>> @Hemesh +1
>>>>>>>
>>>>>>

Re: [algogeeks] Find peak element in log(n)

[Sourabh Singh]

@adarsh kumar

are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say "NO
such element present"

On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar  wrote:
> This is a variation of binary search, the difference being that we have to
> search for an element that is greater than its immediate left one and lesser
> than its immediate right one. Just implement binary search with these
> additional constraints, thereby giving O(log n).
> In case of any difficulty/error, let me know.
>
> On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared 
> wrote:
>>
>> Given an array of integers find a peak element of array in log(n) time.
>> for example if A={3,4,6,5,10} then peak element is 6  ( 6>5 & 6>4 ).
>>
>> Regards.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/AQI6ahWgyOIJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] 4Sum

[Sourabh Singh]

@ALL

 O(n^2 lg(n^2))

http://www.spoj.pl/problems/SUMFOUR/

my code :
http://ideone.com/kAPNB

plz. suggest some test case's :

On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma  wrote:

> @bhaskar,rammar:
>
> I don't think your algo willn not work for the following test case --
>
>
> test case :
> arr: 2 4 6 8
> arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i])
>
> let's say target sum is 26
>
> your solution will return true as they 12+14=26 but in 12 and 14, 8 is
> common, infact 26  is not possible in the given array
>
> --
>
>
> Amol Sharma
> Final Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>
>  
> 
>
>
>
>
>
>
> On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha <
> bhaskar.kushwaha2...@gmail.com> wrote:
>
>> We first compute the N^2 two sums, and sort the two sums. The for each
>> TwoSum t, we check whether there is another two sum t' such that t.value +
>> t'.value = target. The time complexity of this approach is O(N^2 logN)
>>
>>
>> On Wed, Jun 20, 2012 at 1:36 AM, rammar  wrote:
>>
>>> Lets see ur example... We can have two other arrays corresponding to our
>>> n^2 array.
>>> For every (target-arr[i]) which we search in our look up array, we can
>>> also search the components which were used to get that sum. This can be
>>> done in addition constant amount search.
>>> I hope we can still go with Hemesh's algo. Please let me know if it
>>> breaks somewhere...
>>>
>>> let's take a test case :
>>> arr: 2   4   68
>>> arr[0]: 6   8   10   10   12   14
>>> arr[1]: 2   22 4 46
>>> arr[2]: 4   68 6 88
>>>
>>>
>>> P.S. Can we do better?
>>>
>>> On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote:

 @rammar:
 can you please explain the case...which i took in the earlier
 post..with this method.

 --


 Amol Sharma
 Final Year Student
 Computer Science and Engineering
 MNNIT Allahabad

  
 






 On Tue, Jun 19, 2012 at 11:27 PM, rammar  wrote:

> @Hemesh +1
>
>   Please correct me if i am wrong.
>   Creation of our look up array a[n*n] -> sum of all the pairs will
> take O(n^2).
>   Search using binary sort or quick sort in O(n^2 log (n^2) )  ==
> O(n^2 log n)
>   We will traverse this array, and for every element we will find
> (target - a[i])  -> This traversal will again take O(n^2).
>   For every (target -a[i]) we will search it in our lookup
> array using binary search -> This will take O(log n^2) = O(2log n) = O(log
> n)
>   We will store all the matched for the target.
>
> Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n)   == O (n^2
> log n)
>   If the values of max of a[n] is not very high, we can go with a hash
> map. This will result in a quick look up. And we can get the answer in
> O(n^2).
>
>
> P.S. Can we do better?
>
>
> On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote:
>>
>> @KK and hemesh
>> target is not a constant value , it can be any element in array , so
>> you need to do binary search for all (array[i] - (a+b)) to find which
>> increases the complexity to n^3logn.
>> So, i think the n^3 approach which i gave before do it ??
>>
>> --   Correct me if m wrong
>>
>> On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma 
>> wrote:
>>
>>> @hemesh,kk:
>>>
>>> let's take a test case :
>>> arr: 2 4 6 8
>>> arr^2 : 6 8 10 10 12 14(sum of each unique pair in
>>> arr[i])
>>>
>>> let's say target sum is 26
>>>
>>> your solution will return true as they 12+14=26 but in 12 and 14, 8
>>> is common, infact 26  is not possible in the given array
>>>
>>> can u please elaborate how will you take care of such situation ?
>>>
>>> @jalaj:
>>> yes it's O( (n^3)*logn)
>>>
>>> @bhavesh:
>>> fyi..
>>> log(n^3)=3*log(n)=O(log(n))
>>> so it's same.. :P
>>>
>>>
>>>
>>>
>>>
>>> --
>>>
>>>
>>> Amol Sharma
>>> Final Year Student
>>> Computer Science and Engineering
>>> MNNIT Allahabad
>>>
>>>  
>>> 
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Mon, Jun 18, 2012 at 12:29 AM, KK wrote:
>>>
 @Hemesh

Re: [algogeeks] Re: Question asked in Amazon online test

[Sourabh Singh]

@deepika anand

solution given by me is  for getting number of swap's in O(n)

as far as sorting goes any O(n lgn) algo can be used .
if count sort is allowed then O(n) for sorting also.[constant extra space.. ]


On Sat, Jun 23, 2012 at 12:49 AM, ashish jain  wrote:
> @all
>
> yaa.. For getting number of swaps..  we have to calculate total number of
> zeroes on the right for each '1' and on adding them
> we will get the number of swaps. and in O(n) time.
>
>
> On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
>  wrote:
>>
>> It will work because we need to swap only adjacent elements. So we do a
>> sweep from left to right finding the number of ones encountered to the left
>> of a zero when we find a zero. We keep adding the number as we sweep the
>> entire length.
>>
>>
>> On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand 
>> wrote:
>>>
>>> @saurabh..wat array r u getting finallyis it all 1's or in sorted
>>> order for the input
>>>  int a[8]={1,1,1,0,1,0,1,1};
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Question asked in Amazon online test

[Sourabh Singh]

@ALL

see if this work's :

#include
using namespace std;

int a[8]={0,0,1,0,1,0,1,1};

int count_zero(int size)
{   int i,count =0;
for(i=0;i wrote:
> i think it can be done in O(n)
> for each 1, calculate no. of zeros in right
> and adding all no. of zeros in right of all 1's will give no. of swaps.
>
> correct me if i am wrong
>
>
> On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh 
> wrote:
>>
>> @deepika
>>
>> yes, it's giving number of swaps.
>> still Linear time solution would be better :-)
>>
>> On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand 
>> wrote:
>> >
>> > will bubble sort give number of swaps??
>> >
>> > I tried the (bubble sort) code of 1,0,0,1,1,0,1 >swapcount = 5
>> > and for the array  (0,0,1,0,1,0,1,1)>swapcount = 3
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> DARPAN BAWEJA
> 3rd year, I.T
> MNNIT Allahabad
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Question asked in Amazon online test

[Sourabh Singh]

@deepika

yes, it's giving number of swaps.
still Linear time solution would be better :-)

On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand  wrote:
>
> will bubble sort give number of swaps??
>
> I tried the (bubble sort) code of 1,0,0,1,1,0,1 >swapcount = 5
> and for the array  (0,0,1,0,1,0,1,1)>swapcount = 3
>
> --
> You received this message because you are subscribed to the Google Groups 
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to 
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at 
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Programming Question

[Sourabh Singh]

u can use stl::map(,vector)
idea is same bucket sort :-)

On Fri, Jun 22, 2012 at 3:02 AM, Eshwar  wrote:
> Bucket sort algortihm Linkedlist based
>
>
> On Fri, Jun 22, 2012 at 3:31 PM, Gobind Kumar Hembram 
> wrote:
>>
>> I was asked this question in one company Programming Round.Please help
>> me in solving this,I tried with array of pointers ,2-D array and by
>> buffering.
>>
>> You have a file with names of brands separated by comma. Write a
>> program (in language of your choice) to group them by their starting
>> letter.
>>
>> For example, if the input file is this:
>> Reebok, Puma, Adidas, Clarks, Catwalk, Converse, FILA, Lotto, Newfeel,
>> Nike, Numero Uno, New Balance, ASICS, Carlton London, Crocs
>>
>> The program should print the following:
>> A
>>  ASICS, Adidas
>>
>> C
>>  Carlton London, Catwalk, Clarks, Converse, Crocs
>>
>> F
>>  FILA
>>
>> L
>>  Lotto
>>
>> N
>>  New Balance, Newfeel, Nike, Numero Uno
>>
>> P
>>  Puma
>>
>> R
>>  Reebok
>>
>> --
>> 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,
> Eshwar
> +91-95350-86592
>
> This message (including any attachments) is intended only for the use of the
> individual or entity to which it is addressed and may contain information
> that is non-public, proprietary, privileged, confidential, and exempt from
> disclosure under applicable law or may constitute as attorney work product.
> If you are not the intended recipient, you are hereby notified that any use,
> dissemination, distribution, or copying of this communication is strictly
> prohibited. If you have received this communication in error, notify us
> immediately by telephone and (i) destroy this message if a facsimile or (ii)
> delete this message immediately if this is an electronic communication.
> Thank you.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Sorting using array of pointer

[Sourabh Singh]

Nice DCE vs NSIT


On Fri, Jun 22, 2012 at 3:12 AM, deepikaanand  wrote:
> @vindhya thanx ..
>
> --
> You received this message because you are subscribed to the Google Groups 
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to 
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at 
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Reverse Queue

[Sourabh Singh]

@ALL this shud work :-)

#include
#include
using namespace std;
queue Q;
void rev()
{   if(!Q.empty())
{ int x=Q.front(); Q.pop();
  rev();
  Q.push(x);
}

}
main()
{ for(int i=1;i<12;i++) Q.push(i);
  rev();
  while(!Q.empty())
  {   int x=Q.front(); Q.pop();
  printf("%d ",x);
  }
  system("pause");
}


On Thu, Jun 21, 2012 at 12:14 PM, sanjay pandey
 wrote:
> it seems @hassan sol is correctcan nybody knw d flaw in 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.

Re: [algogeeks]

[Sourabh Singh]

@ sohinee basak
it won't matter much . +1 or -1 will get u right range.. : ...

On Thu, Jun 21, 2012 at 9:54 PM, sohinee basak  wrote:
> i have a doubt ... is the range of rand7 from 0 to 6 or from 1 to 7
>
> On Fri, Jun 22, 2012 at 10:13 AM, Anant Sharma  wrote:
>>
>>
>> The reason why finding a solution to this question is difficult is because
>> the combinations of rand5() function which we use ( eg. rand5() + rand5()%2
>> ) leads to some numbers being generated more frequently than others. So the
>> problem would be solved if we could find a function which leads to each
>> output being generated an equal number of times ( once, or maybe more. )
>>
>> 5 * rand5() + rand5()
>>
>> Looking at this function, it is easy to see that each value from 0 to 24
>> will be generated only once for every respective value that first and second
>> rand5() returns.
>>
>> Suppose the first rand5() returns 0, then the second rand5() can return
>> any value from 0 - 4. Now see that no value from 0-4 could be generated by
>> any other combination. When the value returned by the second rand5() is 1,
>> corresponding to the value returned by second rand5(), we could get 5 - 9.
>>
>>
>> Now we have each number from 0-24 appearing once. But simply returning the
>> mod of this value with 7 wouldn't lead to equal probability distribution as
>> the values 0 - 3 would be returned more times than 4-6. So to fix this
>> inequality, we ignore when the value of the function is more than 20. Now
>> doing mod with 7 will result in every number 0 - 6 being returned with equal
>> probability.
>>
>> We could even have ignored the values above 6, or the values above 13, the
>> only difference being that it would take more number of calls to return a
>> rand7() result.
>>
>> This way is non-deterministic i.e. we cannot say how many times the
>> function will be called before we get the rand7()  result, but we can be
>> sure that whenever the function returns a value, it would have been as
>> probable as any other value from 0 - 6. Taking the mod of the result of the
>> function, there would be 3 ways in which each digit 0 through 6 can be
>> generated.
>>
>>
>> Implementation:
>>
>> int rand7 ( ) {
>> int num = 5 * rand5 ( ) + rand ( ) ;
>> if ( num > 20 )
>> return rand7 (  ) ;
>> else
>> retutrn num % 7 ;
>> }
>>
>> On Thu, Jun 21, 2012 at 12:44 PM, Abhishek Sharma 
>> wrote:
>>>
>>> @umer
>>> it's not random,but biased
>>>
>>>
>>> On Wed, Jun 20, 2012 at 11:16 AM, Umer Farooq 
>>> wrote:
>>>>
>>>> Hmmm, true. That's what I expected in this solution. Similarly, we can
>>>> get 3 by (3,3) (1,2)
>>>>
>>>> However, did you take a look at the other solution I proposed? I guess
>>>> that solves the problem to some extent.
>>>>
>>>>
>>>> On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh
>>>>  wrote:
>>>>>
>>>>> @Umer and Navin :
>>>>> 1 is generated by (1,3) only.
>>>>> 2 is generated by (1,1) and (2,3).
>>>>>
>>>>> so given solution is wrong
>>>>>
>>>>>
>>>>> On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh
>>>>>  wrote:
>>>>>>
>>>>>> @ ALL
>>>>>>
>>>>>>     please. post along with your method .
>>>>>>     proof than it make's equal distribution over the given range.
>>>>>>
>>>>>> On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar
>>>>>>  wrote:
>>>>>>>
>>>>>>> @Umer:
>>>>>>>
>>>>>>> rand(5) + (rand(5)%2): => it will never give 6 because for rand(7)
>>>>>>> range will be 0-6.
>>>>>>> So better try this: rand(5) + (rand(5)%3).
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq 
>>>>>>> wrote:
>>>>>>>>
>>>>>>>> rand(5) + (rand(5)%2);
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh
>>>>>>>>  wrote:
>>>>>>>>>
>>>>>>>>> @ sry
>>>>>>>>> condition should be:
>&g

Re: [algogeeks]

[Sourabh Singh]

@ Anant Sharma

Good one. it should work .

On Thu, Jun 21, 2012 at 9:43 PM, Anant Sharma  wrote:
>
> The reason why finding a solution to this question is difficult is because
> the combinations of rand5() function which we use ( eg. rand5() + rand5()%2
> ) leads to some numbers being generated more frequently than others. So the
> problem would be solved if we could find a function which leads to each
> output being generated an equal number of times ( once, or maybe more. )
>
> 5 * rand5() + rand5()
>
> Looking at this function, it is easy to see that each value from 0 to 24
> will be generated only once for every respective value that first and second
> rand5() returns.
>
> Suppose the first rand5() returns 0, then the second rand5() can return any
> value from 0 - 4. Now see that no value from 0-4 could be generated by any
> other combination. When the value returned by the second rand5() is 1,
> corresponding to the value returned by second rand5(), we could get 5 - 9.
>
>
> Now we have each number from 0-24 appearing once. But simply returning the
> mod of this value with 7 wouldn't lead to equal probability distribution as
> the values 0 - 3 would be returned more times than 4-6. So to fix this
> inequality, we ignore when the value of the function is more than 20. Now
> doing mod with 7 will result in every number 0 - 6 being returned with equal
> probability.
>
> We could even have ignored the values above 6, or the values above 13, the
> only difference being that it would take more number of calls to return a
> rand7() result.
>
> This way is non-deterministic i.e. we cannot say how many times the function
> will be called before we get the rand7()  result, but we can be sure that
> whenever the function returns a value, it would have been as probable as any
> other value from 0 - 6. Taking the mod of the result of the function, there
> would be 3 ways in which each digit 0 through 6 can be generated.
>
>
> Implementation:
>
> int rand7 ( ) {
> int num = 5 * rand5 ( ) + rand ( ) ;
> if ( num > 20 )
> return rand7 (  ) ;
> else
> retutrn num % 7 ;
> }
>
> On Thu, Jun 21, 2012 at 12:44 PM, Abhishek Sharma 
> wrote:
>>
>> @umer
>> it's not random,but biased
>>
>>
>> On Wed, Jun 20, 2012 at 11:16 AM, Umer Farooq  wrote:
>>>
>>> Hmmm, true. That's what I expected in this solution. Similarly, we can
>>> get 3 by (3,3) (1,2)
>>>
>>> However, did you take a look at the other solution I proposed? I guess
>>> that solves the problem to some extent.
>>>
>>>
>>> On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh 
>>> wrote:
>>>>
>>>> @Umer and Navin :
>>>> 1 is generated by (1,3) only.
>>>> 2 is generated by (1,1) and (2,3).
>>>>
>>>> so given solution is wrong
>>>>
>>>>
>>>> On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh
>>>>  wrote:
>>>>>
>>>>> @ ALL
>>>>>
>>>>>     please. post along with your method .
>>>>>     proof than it make's equal distribution over the given range.
>>>>>
>>>>> On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar 
>>>>> wrote:
>>>>>>
>>>>>> @Umer:
>>>>>>
>>>>>> rand(5) + (rand(5)%2): => it will never give 6 because for rand(7)
>>>>>> range will be 0-6.
>>>>>> So better try this: rand(5) + (rand(5)%3).
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq 
>>>>>> wrote:
>>>>>>>
>>>>>>> rand(5) + (rand(5)%2);
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh
>>>>>>>  wrote:
>>>>>>>>
>>>>>>>> @ sry
>>>>>>>> condition should be:
>>>>>>>>
>>>>>>>> if(20*prob <= 500/7) :-)
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh
>>>>>>>>  wrote:
>>>>>>>>>
>>>>>>>>> @ALL
>>>>>>>>>
>>>>>>>>> Given a random number generator say r(5) generates number between
>>>>>>>>> 1-5 uniformly at random , use it to in r(7) which should generate a 
>>>>>>>>&

Re: [algogeeks] Re: POSTAGE STAMP PROBLEM

[Sourabh Singh]

try this : similar problem

http://www.spoj.pl/problems/NOCHANGE/

On Tue, Jun 19, 2012 at 1:32 PM, aditya gupta  wrote:
> this can be solved in a manner similar to knapsack problem.
> u can take the weight of tha knapsack the be the the various amounts u need
> to make, 13 cents etc etc. we would need to find a first empty cell.
> instead of parameter "value", use your own parameter specifying the number
> of stamps used.
> and u would have to make a smal intuitive change to the manner in which the
> cells are populated so as to ensure that it picks a combination which
> reaches an exact amount/weight that u need as opposed to a <= amount/weight
> in regular knapsack.
>
>
>
> On Tue, Jun 19, 2012 at 10:41 PM, rammar  wrote:
>>
>> This can be done with DP.
>> Take an array with values 1 to n.
>> For every number i, try to make it using the stamps available and the 1 to
>> i-1 array. Anytime u find that the upper bound is reached, u return.
>>
>> sudo code.
>>
>> stamps[K];   -> Stamp denominations available.
>> a[N]             -> Array of number of stamps required.
>> a[0] = 0;
>> For i= 1 to n
>> {
>>    tempMin = 1000( some large number)
>>    For j = 0 to K   -> loop over the array storing the number of stamp
>> denominations.
>>    {
>>        if(stamps[j] <= i)
>>            if( tempMin > 1 + a[i-j])
>>                 tempMin := 1 + a[i-j];
>>    }
>>    if(tempMin > maxStampAllowed)
>>    {
>>         return i;
>>     }
>>     else
>>     {
>>          a[i] =tempMin
>>     }
>> }
>>
>> This will work with time complexity of O (n*k) . Use of vectors (in c++)
>> can be helpfule for dynamic arrays.
>>
>>
>> P.S.  Can we do better?
>>
>>
>> On Tuesday, June 19, 2012 9:25:42 PM UTC+5:30, suzi wrote:
>>>
>>> The postage stamp problem is a mathematical riddle that asks what is the
>>> smallest postage value which cannot be placed on an envelope, if the letter
>>> can hold only a limited number of stamps, and these may only have certain
>>> specified face values.
>>>
>>> For example, suppose the envelope can hold only three stamps, and the
>>> available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the
>>> solution is 13 cents; since any smaller value can be obtained with at most
>>> three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one
>>> must use at least four stamps.
>>>
>>> Is there an algorithm that given the maximum amount of stamps allowed and
>>> the face value of the stamps, one can find the smallest postage that cannot
>>> be placed on the envelope?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/a1ykZ8HaDjEJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe 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.
>
>
>
>
> --
> Aditya Gupta
> B.Tech III yr CSE
> IITR
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@Umer and Navin :
1 is generated by (1,3) only.
2 is generated by (1,1) and (2,3).

so given solution is wrong

On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh wrote:

> @ *ALL*
>
> please. post along with your method .
> proof than it make's equal distribution over the given range.
>
> On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar wrote:
>
>> @Umer:
>>
>> rand(5) + (rand(5)%2): => it will never give 6 because for rand(7) range
>> will be 0-6.
>> So better try this: rand(5) + (rand(5)%3).
>>
>>
>> On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq  wrote:
>>
>>> rand(5) + (rand(5)%2);
>>>
>>>
>>> On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh <
>>> singhsourab...@gmail.com> wrote:
>>>
>>>> @ sry
>>>> condition should be:
>>>>
>>>> if(20*prob <= 500/7) :-)
>>>>
>>>>
>>>> On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh <
>>>> singhsourab...@gmail.com> wrote:
>>>>
>>>>> @ALL
>>>>>
>>>>> Given a random number generator say r(5) generates number between 1-5
>>>>> uniformly at random , use it to in r(7) which should generate a random
>>>>> number between 1-7 uniformly at random
>>>>>
>>>>> i have seen this on many site's but not a single correct solution. all
>>>>> solution's posted got rejected by someone else.:
>>>>> plz.. suggest some algo :
>>>>>
>>>>> my aprroach:
>>>>>
>>>>> let's assume a rectangle :
>>>>>
>>>>> 100  |___
>>>>> |___|__
>>>>> 500/7   |  ||
>>>>> |  ||
>>>>> |___|__|
>>>>> 0 1  2  3 4  5 67
>>>>> now :
>>>>>
>>>>> let : num  = rand(5);
>>>>>prob = rand(5);
>>>>>
>>>>>if(prob <= rand(5))
>>>>> print  num
>>>>>else
>>>>> print  5 + num*(2/5)
>>>>>
>>>>>
>>>>>  --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>  --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Umer
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@ *ALL*

please. post along with your method .
proof than it make's equal distribution over the given range.

On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar wrote:

> @Umer:
>
> rand(5) + (rand(5)%2): => it will never give 6 because for rand(7) range
> will be 0-6.
> So better try this: rand(5) + (rand(5)%3).
>
>
> On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq  wrote:
>
>> rand(5) + (rand(5)%2);
>>
>>
>> On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh > > wrote:
>>
>>> @ sry
>>> condition should be:
>>>
>>> if(20*prob <= 500/7) :-)
>>>
>>>
>>> On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh <
>>> singhsourab...@gmail.com> wrote:
>>>
>>>> @ALL
>>>>
>>>> Given a random number generator say r(5) generates number between 1-5
>>>> uniformly at random , use it to in r(7) which should generate a random
>>>> number between 1-7 uniformly at random
>>>>
>>>> i have seen this on many site's but not a single correct solution. all
>>>> solution's posted got rejected by someone else.:
>>>> plz.. suggest some algo :
>>>>
>>>> my aprroach:
>>>>
>>>> let's assume a rectangle :
>>>>
>>>> 100  |___
>>>> |___|__
>>>> 500/7   |  ||
>>>> |  ||
>>>> |___|__|
>>>> 0 1  2  3 4  5 67
>>>> now :
>>>>
>>>> let : num  = rand(5);
>>>>prob = rand(5);
>>>>
>>>>if(prob <= rand(5))
>>>> print  num
>>>>else
>>>> print  5 + num*(2/5)
>>>>
>>>>
>>>>  --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Umer
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@ sry
condition should be:

if(20*prob <= 500/7) :-)

On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh wrote:

> @ALL
>
> Given a random number generator say r(5) generates number between 1-5
> uniformly at random , use it to in r(7) which should generate a random
> number between 1-7 uniformly at random
>
> i have seen this on many site's but not a single correct solution. all
> solution's posted got rejected by someone else.:
> plz.. suggest some algo :
>
> my aprroach:
>
> let's assume a rectangle :
>
> 100  |___
> |___|__
> 500/7   |  ||
> |  ||
> |___|__|
> 0 1  2  3 4  5 67
> now :
>
> let : num  = rand(5);
>prob = rand(5);
>
>if(prob <= rand(5))
> print  num
>else
> print  5 + num*(2/5)
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks]

[Sourabh Singh]

@ALL

Given a random number generator say r(5) generates number between 1-5
uniformly at random , use it to in r(7) which should generate a random
number between 1-7 uniformly at random

i have seen this on many site's but not a single correct solution. all
solution's posted got rejected by someone else.:
plz.. suggest some algo :

my aprroach:

let's assume a rectangle :

100  |___
|___|__
500/7   |  ||
|  ||
|___|__|
0 1  2  3 4  5 67
now :

let : num  = rand(5);
   prob = rand(5);

   if(prob <= rand(5))
print  num
   else
print  5 + num*(2/5)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Find the Max from each sub-array of size k

[Sourabh Singh]

@ALL can be solved using segment tree . :-)

On Fri, Sep 2, 2011 at 9:49 AM, Anup Ghatage  wrote:

> I just checked Shashank's blog post. The Deque solution is awesome :)
>
> --
> Anup Ghatage
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MS Question: Reverse stack using push, pop without any auxiliary data structure

[Sourabh Singh]

@ Navin Kumar

Nice . Solution.
But
your  function also make a stack only. so you are using a stack[internal]
here.
but may be this one is allowed:-)

On Thu, Jun 14, 2012 at 5:23 AM, Navin Kumar wrote:

> void Reverse(struct Stack *S) {
> int data;
> if(IsEmptyStack(S)) return;
> data=pop(s);
> ReverseStack(S);
> InsertAtBottom(S, data);
> }
>
> void InsertAtBottom(struct stack *S, int data)
> {
>int temp;
>if(!IsEmptyStack(S)){
>push(S,data);
>return;
> }
>temp=pop(S);
>InsertAtBottom(S,data);
> push(S, temp);
>
> }
>
>
> On Thu, Jun 14, 2012 at 2:44 PM, rahul patil <
> rahul.deshmukhpa...@gmail.com> wrote:
>
>> to store items in stack you will need some DS. Do they mean you cant use
>> any auxillary DS than stack ?
>>
>>
>> On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel  wrote:
>>
>>>
>>> Best Regards
>>> Ashish Goel
>>> "Think positive and find fuel in failure"
>>> +919985813081
>>> +919966006652
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Regards,
>> Rahul Patil
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: spoj problem

[Sourabh Singh]

@  saurabh singh :

 what algorithm can be used ??
 coz.. i did it by simple observation.

 1)  just take any sequence of numbers.
 2)  write it's first 5-6 xor round's.
 3)  now luk for some pattern.

 u'll get the answer  : )

On Wed, Jun 13, 2012 at 9:46 PM, saurabh singh  wrote:

> No this is fair enough.It directly involves algorithm.
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
>
>
> On Thu, Jun 14, 2012 at 4:28 AM, shiv narayan 
> wrote:
>
>> will be better if you post on spoj forums.!!
>>
>>
>> On Wednesday, 13 June 2012 01:40:36 UTC+5:30, gaurav yadav wrote:
>>>
>>> plz nyone explain how to approach this problem..
>>> http://www.spoj.pl/problems/**XORROUND/
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/lvClpFbMOwgJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Matrix Minimum Path Sum

[Sourabh Singh]

 Basic Dijikstra problem . :-)

On Wed, Jun 6, 2012 at 6:13 AM, Dheeraj Jain  wrote:

> http://www.geeksforgeeks.org/archives/14943
>
>
> On Mon, Jun 4, 2012 at 7:57 PM, Decipher  wrote:
>
>> @Victor - Someone had asked this question from me !! He told me its from
>> Project Euler Q-83.
>> @Hassan -  I think you are right. This question can be solved by
>> Dijikstra's algo, if we consider the matrix elements as weights.
>>
>>
>> On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote:
>>>
>>> moving must be done in A* style
>>>
>>> On Mon, Jun 4, 2012 at 1:17 PM, atul anand wrote:
>>>
 i dont think so dijistra will worh here..bcozz we cannot move
 diagonally ...but according to matrix this path can be considered.

 On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared wrote:

> for non-negative values Dijkstra will solve the problem in ( O(N^2) )
> and Floyd-Warshal is the solution for negative cells. ( O(N^3) )
>
>
>
> On Mon, Jun 4, 2012 at 11:20 AM, atul anand 
> wrote:
>
>> this recurrence wont work..ignore
>>
>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 
>> wrote:
>>
>>> find cumulative sum row[0]
>>> find cumulative sum of col[0]
>>>
>>> after this following recurrence will solve the problem.
>>>
>>> start from mat[1][1]
>>>
>>> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] )
>>>
>>>
>>> On Sun, Jun 3, 2012 at 7:30 PM, Decipher wrote:
>>>
 Q) In the 5 by 5 matrix below, the minimal path sum from the top
 left to the bottom right, by moving left, right, up, and down, is 
 indicated
 in bold red and is equal to 2297.


  *131*

 673

 *234*

 *103*

 *18*

 *201*

 *96*

 *342*

 965

 *150*

 630

 803

 746

 *422*

 *111*

 537

 699

 497

 *121*

 956

 805

 732

 524

 *37*

 *331*



 Write an algorithm to find the same. Also, write an algorithm if
 the same matrix contains negative numbers (maybe negative cycle) and
 compare the space and time complexity of both.

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To view this discussion on the web visit
 https://groups.google.com/d/**msg/algogeeks/-/3JeyGNqWbs8J
 .
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscribe@**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+unsubscribe@*
>> *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+unsubscribe@**
> 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+unsubscribe@**
 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 view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> F

Re: [algogeeks] Find the maximum boxes which can fit each other?

[sourabh datta]

@atul..
i think what u meant is longest decreasing sequence..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] GSOC help android app inventor

[Sourabh Chandak]

Google Group: app-inventor-open-source-...@googlegroups.com

On Fri, Mar 23, 2012 at 9:11 PM, Raghav Garg wrote:

> Thanks..
> I am trying to work with that code but there is no contact information
> for that organisation( like irc channel, mailing list or facebook
> page) so how could i contact them?
>
> On 3/23/12, Sourabh Chandak  wrote:
> > Hi Raghav,
> >
> > I dont have much idea about the organisation. I gave a look at the idea
> > page while searching for an organisation to work for, and this is what I
> > could figure out.
> >
> > The work you need to do for app inventor for GSoC is not android
> > application development. App inventor is for ones who dont know how to
> > code. The coding involved in it will not use the Android SDK rather it
> will
> > use Android NDK. As the idea page of the organization suggests, you need
> to
> > fill in the form they have provided. Checkout the code of app inventor
> and
> > try to see how things are implemented and try to figure out how you can
> > implement one of the ideas listed on the idea page.
> >
> > Hope that make things a bit clear.
> >
> > Regards,
> >
> > On Thu, Mar 22, 2012 at 7:41 PM, Raghav Garg  >wrote:
> >
> >> *Hello,
> >> I am very much interested in android development and also i have made
> few
> >> apps with eclipse and also with app inventor.
> >> I need to know what else i can do to contribute in app inventor to get
> >> selected in GSOC besides from just filling the application.
> >> *Thanking you
> >>
> >> *With regards-
> >> Raghav garg
> >> Contact no. 9013201944
> >> www.facebook.com/rock.raghavag
> >> B. tech (IT), 5th sem
> >> University School Of Information Technology
> >> Guru Govind Singh Indraprastha University
> >> Delhi*
> >>
> >>  --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> >
> >
> > --
> > Sourabh Chandak
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
>
> --
> Thanking you
>
> *With regards-
> Raghav garg
> Contact no. 9013201944
> www.facebook.com/rock.raghavag
> B. tech (IT), 5th sem
> University School Of Information Technology
> Guru Govind Singh Indraprastha University
> Delhi*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Sourabh Chandak

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] GSOC help android app inventor

[Sourabh Chandak]

Hi Raghav,

I dont have much idea about the organisation. I gave a look at the idea
page while searching for an organisation to work for, and this is what I
could figure out.

The work you need to do for app inventor for GSoC is not android
application development. App inventor is for ones who dont know how to
code. The coding involved in it will not use the Android SDK rather it will
use Android NDK. As the idea page of the organization suggests, you need to
fill in the form they have provided. Checkout the code of app inventor and
try to see how things are implemented and try to figure out how you can
implement one of the ideas listed on the idea page.

Hope that make things a bit clear.

Regards,

On Thu, Mar 22, 2012 at 7:41 PM, Raghav Garg wrote:

> *Hello,
> I am very much interested in android development and also i have made few
> apps with eclipse and also with app inventor.
> I need to know what else i can do to contribute in app inventor to get
> selected in GSOC besides from just filling the application.
> *Thanking you
>
> *With regards-
> Raghav garg
> Contact no. 9013201944
> www.facebook.com/rock.raghavag
> B. tech (IT), 5th sem
> University School Of Information Technology
> Guru Govind Singh Indraprastha University
> Delhi*
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Sourabh Chandak

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Google written test

[Sourabh Chandak]

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

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

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

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

> Hello!
>
> I got to know that Google visited several colleges in last week. They will
> be visiting my campus on 20th. Please let us know pattern & questions if
> you know.
>
> Thanks,
> - RD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Sourabh Chandak

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@ atul and saurabh

Here is my code of what m trying to implement .

here starting at bottom right corner we try to come up moving row by row .
in end  b matrix contain's dimention of rectangle which can be formed
from Aij in Bij (width,height)

plz.. post what u make of it...  can it be improved to work for all case's
??

#include
#include

using namespace std;
main()
{ int width=0,height=1;
  int a[6][6]={0,1,1,1,1,0,
   0,0,0,1,1,0,
   0,1,1,1,1,0,
   0,1,1,0,0,0,
   0,1,1,0,0,0,
   0,0,0,0,0,0 };

  int b[6][6][2]={0};

  int i,j;
  for(i=0;i<6;i++)
  {   b[5][i][width]=1;
  b[i][5][width]=1;

  b[5][i][height]=1;
  b[i][5][height]=1;
  }
  for(i=4;i>=0;i--)
  {
  for(j=4;j>=0;j--)
  {

   if(a[i][j]!=a[i+1][j] & a[i][j]!=a[i][j+1])
   {
 b[i][j][width]=1;
 b[i][j][height]=1;
   }
   else if(a[i][j]==a[i][j+1] &
a[i][j]!=a[i+1][j])
{
 b[i][j][width]=b[i][j+1][width]+1;
 b[i][j][height]=1;

//printf("widht\n");
}
else if(a[i][j]==a[i+1][j] &
a[i][j]!=a[i][j+1])
 {
 b[i][j][width]=1;

b[i][j][height]=b[i+1][j][height]+1;
// printf("height\n");
 }
 else
 {

b[i][j][width]=min(b[i+1][j][width],b[i][j+1][width]+1);

b[i][j][height]=min(b[i+1][j][height]+1,b[i][j+1][height]);
 }
  }
  }

  for(i=0;i<6;i++)
  {
  for(j=0;j<6;j++)
  {
 printf("%d,%d ",b[i][j][width],b[i][j][height]);
  }
  printf("\n");
  }
  getch();
}



On Wed, Mar 14, 2012 at 8:59 PM, atul anand  wrote:

> @Sourabh : here we are talking abt 2 different problems in this
> post..which are little bit similar.
>
> 1) original question says find max subset of matix contaning '1' and '0'
>
> we knw recurrence to solve this problem , as posted above.
>
> 2) now your question is to find max subset of matrix which contain +ve or
> -ve numbers , not necessarily only '1' or '0'
>
> so in my solution , you need to give some input to solve this problem 
> and that input is say matrix m[][].
> if you check my solution then in just modifies input matrix to find
> solution , its space complexity is O(1).
>
>
>
> On Thu, Mar 15, 2012 at 12:26 AM, Sourabh Singh 
> wrote:
>
>> @atul
>>
>> 1) it won't work for large dimention's coz their is a limit to size of
>> array we can declare on stack.
>>( which is typically 10^6 as far as i know :-)  ).
>>
>> 2) the algo i m trying to find would work in linear time. while this one
>> is more then O(n^2)
>> fo rvery very large input this algo would be very very slow.. making
>> it impractial..
>>
>> ( it's like if u can find substring's in linear time then why use an
>> O(n^2) algo ;-) )
>>
>> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit
>> short on time to check implemention of  your algo right now )
>>
>>
>>
>> On Wed, Mar 14, 2012 at 9:07 AM, atul anand wrote:
>>
>>> @rahul: i have alreday explained it in the provided link.
>>> @sourbh : why it would not work for large dimension
>>> On 14 Mar 2012 19:39, "rahul sharma"  wrote:
>>>
>>>> @atul..plz tell me an example for square matrix...actually i faced it
>>>> first tym...it executes...but explain plz..
>>>>
>>>> On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh <
>>>> singhsourab...@gmail.com> wrote:
>>>>
>>>>> @atul
>>>>>
>>>>> Also the histogram algo and algo given by you can't work on very very
>>>>> big dimentions. say 10^5 x 10^5 matrix.
>>>>>  but if we can find a DP then  we just need to keep 2 row's at a time.
>>>>> :-)
>>>>>
>>>>>
>>>>

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@rahul

may be this will help you..

/* Given a binary matrix, find out the maximum size square sub-matrix with
all 1s.
   1. O(n^3) sol is very obvious
   2. O(n^2) sol [ this file]
   3. O(n)   sol [ possible but we need to know tucker matrix, etc advanced
set theory's]
*/


#include
#include

int b[6][6];
using namespace std;
main()
{ int i,j,t;
  int a[6][6]=
  { 0,0,0,1,0,1,
0,1,1,1,0,0,
1,1,1,1,0,1,
0,1,1,1,1,0,
1,0,0,1,0,0,
0,1,0,1,1,0,};
  for(i=0;i<6;i++)
  for(j=0;j<6;j++)
  {   if(a[i][j]==1)
  {

b[i][j]=min(min(b[i-1][j],b[i][j-1]),b[j-1][i-1])+1;
  }
  else
b[i][j]=0;
  }
  for(i=0;i<6;i++)
  {   for(j=0;j<6;j++)
  {printf(" %d",a[i][j]);
  }
  printf("\n");
  }
  printf("\n\n\n\n\n");
  for(i=0;i<6;i++)
  {   for(j=0;j<6;j++)
  {printf(" %d",b[i][j]);
  }
  printf("\n");
  }
      getch();
  return 0;
}


On Wed, Mar 14, 2012 at 11:56 AM, Sourabh Singh wrote:

> @atul
>
> 1) it won't work for large dimention's coz their is a limit to size of
> array we can declare on stack.
>( which is typically 10^6 as far as i know :-)  ).
>
> 2) the algo i m trying to find would work in linear time. while this one
> is more then O(n^2)
> fo rvery very large input this algo would be very very slow.. making
> it impractial..
>
> ( it's like if u can find substring's in linear time then why use an
> O(n^2) algo ;-) )
>
> NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
> on time to check implemention of  your algo right now )
>
>
>
> On Wed, Mar 14, 2012 at 9:07 AM, atul anand wrote:
>
>> @rahul: i have alreday explained it in the provided link.
>> @sourbh : why it would not work for large dimension
>> On 14 Mar 2012 19:39, "rahul sharma"  wrote:
>>
>>> @atul..plz tell me an example for square matrix...actually i faced it
>>> first tym...it executes...but explain plz..
>>>
>>> On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh >> > wrote:
>>>
>>>> @atul
>>>>
>>>> Also the histogram algo and algo given by you can't work on very very
>>>> big dimentions. say 10^5 x 10^5 matrix.
>>>>  but if we can find a DP then  we just need to keep 2 row's at a time.
>>>> :-)
>>>>
>>>>
>>>>
>>>> On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh <
>>>> singhsourab...@gmail.com> wrote:
>>>>
>>>>> @atul
>>>>>
>>>>> read it ..
>>>>>
>>>>> it's good but more or less like the histogram algo.. i wanted a DP.
>>>>> approach..
>>>>>
>>>>> here is some of wat i heard from a senior in colg..
>>>>>
>>>>> 1. at every index we can keep 4 variable
>>>>>
>>>>> ht: height of max rectangle possible at index above current
>>>>>  wt width   "   "  " " "
>>>>> "   "
>>>>>  hl:height of max rectangle possible at index left of  current
>>>>> wl:   """   " "
>>>>> ""
>>>>>
>>>>>
>>>>> now problem is which one to take for current... index
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand 
>>>>> wrote:
>>>>>
>>>>>> @ Sourabh: check solution i have posted in below link
>>>>>>
>>>>>>
>>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh <
>>>>>> singhsourab...@gmail.com> wrote:
>>>>>>
>>>>>>> @ ALL
>>>>>>>
>>>>>>>  finding square matrix is quite a standard question and nw an easy
>>>>>>> one as everyone knows the reccussence atul has given.
>>>>>>>  but  i wanted to 

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@atul

1) it won't work for large dimention's coz their is a limit to size of
array we can declare on stack.
   ( which is typically 10^6 as far as i know :-)  ).

2) the algo i m trying to find would work in linear time. while this one is
more then O(n^2)
fo rvery very large input this algo would be very very slow.. making it
impractial..

( it's like if u can find substring's in linear time then why use an O(n^2)
algo ;-) )

NOTE: sry if m getting any fact's wrong m in mid of exam's (so a bit short
on time to check implemention of  your algo right now )



On Wed, Mar 14, 2012 at 9:07 AM, atul anand  wrote:

> @rahul: i have alreday explained it in the provided link.
> @sourbh : why it would not work for large dimension
> On 14 Mar 2012 19:39, "rahul sharma"  wrote:
>
>> @atul..plz tell me an example for square matrix...actually i faced it
>> first tym...it executes...but explain plz..
>>
>> On Wed, Mar 14, 2012 at 6:56 PM, Sourabh Singh 
>> wrote:
>>
>>> @atul
>>>
>>> Also the histogram algo and algo given by you can't work on very very
>>> big dimentions. say 10^5 x 10^5 matrix.
>>>  but if we can find a DP then  we just need to keep 2 row's at a time.
>>> :-)
>>>
>>>
>>>
>>> On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh >> > wrote:
>>>
>>>> @atul
>>>>
>>>> read it ..
>>>>
>>>> it's good but more or less like the histogram algo.. i wanted a DP.
>>>> approach..
>>>>
>>>> here is some of wat i heard from a senior in colg..
>>>>
>>>> 1. at every index we can keep 4 variable
>>>>
>>>> ht: height of max rectangle possible at index above current
>>>>  wt width   "   "  " " "
>>>> "   "
>>>>  hl:height of max rectangle possible at index left of  current
>>>> wl:   """   " "
>>>> ""
>>>>
>>>>
>>>> now problem is which one to take for current... index
>>>>
>>>>
>>>>
>>>> On Tue, Mar 13, 2012 at 10:52 AM, atul anand 
>>>> wrote:
>>>>
>>>>> @ Sourabh: check solution i have posted in below link
>>>>>
>>>>>
>>>>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh <
>>>>> singhsourab...@gmail.com> wrote:
>>>>>
>>>>>> @ ALL
>>>>>>
>>>>>>  finding square matrix is quite a standard question and nw an easy
>>>>>> one as everyone knows the reccussence atul has given.
>>>>>>  but  i wanted to find max rectangle..
>>>>>>
>>>>>> i know there is a DP for it. in O(n^2). for nxn matrix..don't know
>>>>>> the whole approach .but  here is what i remember..
>>>>>>
>>>>>> 1. aproach is simple to keep track of max rectangle which can be
>>>>>> formed from any point taking that point as top  left corner of max
>>>>>> rectangle and
>>>>>> proceed further down .
>>>>>>
>>>>>> can someone suggest how can be proceed further..
>>>>>>
>>>>>>
>>>>>> [ NOTE: problem occurs mainly when their are more than one rectangles
>>>>>> which can be formed from same point ]
>>>>>>
>>>>>> plz.. don't suggest the histogram method it's just a dirty way of
>>>>>> avoiding to work on getting this DP right. :-)
>>>>>>
>>>>>>
>>>>>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand >>>>> > wrote:
>>>>>>
>>>>>>> here is the recurrence for solving this
>>>>>>>
>>>>>>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1],
>>>>>>> R[i,,j-1] ) );
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma <
>>>>>>> rahul23111...@gmail.com> wrote:
>>>>>&

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@atul

Also the histogram algo and algo given by you can't work on very very big
dimentions. say 10^5 x 10^5 matrix.
 but if we can find a DP then  we just need to keep 2 row's at a time. :-)


On Tue, Mar 13, 2012 at 1:03 PM, Sourabh Singh wrote:

> @atul
>
> read it ..
>
> it's good but more or less like the histogram algo.. i wanted a DP.
> approach..
>
> here is some of wat i heard from a senior in colg..
>
> 1. at every index we can keep 4 variable
>
> ht: height of max rectangle possible at index above current
>  wt width   "   "  " " "
> "   "
>  hl:height of max rectangle possible at index left of  current
> wl:   """   " "
> "    "
>
>
> now problem is which one to take for current... index
>
>
>
> On Tue, Mar 13, 2012 at 10:52 AM, atul anand wrote:
>
>> @ Sourabh: check solution i have posted in below link
>>
>>
>> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>>
>>
>>
>> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh > > wrote:
>>
>>> @ ALL
>>>
>>>  finding square matrix is quite a standard question and nw an easy one
>>> as everyone knows the reccussence atul has given.
>>>  but  i wanted to find max rectangle..
>>>
>>> i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
>>> whole approach .but  here is what i remember..
>>>
>>> 1. aproach is simple to keep track of max rectangle which can be formed
>>> from any point taking that point as top  left corner of max rectangle and
>>> proceed further down .
>>>
>>> can someone suggest how can be proceed further..
>>>
>>>
>>> [ NOTE: problem occurs mainly when their are more than one rectangles
>>> which can be formed from same point ]
>>>
>>> plz.. don't suggest the histogram method it's just a dirty way of
>>> avoiding to work on getting this DP right. :-)
>>>
>>>
>>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote:
>>>
>>>> here is the recurrence for solving this
>>>>
>>>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1]
>>>> ) );
>>>>
>>>>
>>>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma >>> > wrote:
>>>>
>>>>>
>>>>>  April 4, 2010
>>>>>
>>>>> Given a binary matrix, find out the maximum size square sub-matrix
>>>>> with all 1s.
>>>>>
>>>>> For example, consider the below binary matrix.
>>>>>
>>>>>0  1  1  0  1
>>>>>1  1  0  1  0
>>>>>0  1  1  1  0
>>>>>1  1  1  1  0
>>>>>1  1  1  1  1
>>>>>0  0  0  0  0
>>>>>
>>>>> The maximum square sub-matrix with all set bits is
>>>>>
>>>>> 1  1  1
>>>>> 1  1  1
>>>>> 1  1  1
>>>>>
>>>>>  --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>  --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@atul

read it ..

it's good but more or less like the histogram algo.. i wanted a DP.
approach..

here is some of wat i heard from a senior in colg..

1. at every index we can keep 4 variable

ht: height of max rectangle possible at index above current
 wt width   "   "  " " "
"   "
 hl:height of max rectangle possible at index left of  current
wl:   """   " "
""


now problem is which one to take for current... index


On Tue, Mar 13, 2012 at 10:52 AM, atul anand wrote:

> @ Sourabh: check solution i have posted in below link
>
>
> http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0
>
>
>
> On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh 
> wrote:
>
>> @ ALL
>>
>>  finding square matrix is quite a standard question and nw an easy one as
>> everyone knows the reccussence atul has given.
>>  but  i wanted to find max rectangle..
>>
>> i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
>> whole approach .but  here is what i remember..
>>
>> 1. aproach is simple to keep track of max rectangle which can be formed
>> from any point taking that point as top  left corner of max rectangle and
>> proceed further down .
>>
>> can someone suggest how can be proceed further..
>>
>>
>> [ NOTE: problem occurs mainly when their are more than one rectangles
>> which can be formed from same point ]
>>
>> plz.. don't suggest the histogram method it's just a dirty way of
>> avoiding to work on getting this DP right. :-)
>>
>>
>> On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote:
>>
>>> here is the recurrence for solving this
>>>
>>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1]
>>> ) );
>>>
>>>
>>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma 
>>> wrote:
>>>
>>>>
>>>>  April 4, 2010
>>>>
>>>> Given a binary matrix, find out the maximum size square sub-matrix with
>>>> all 1s.
>>>>
>>>> For example, consider the below binary matrix.
>>>>
>>>>0  1  1  0  1
>>>>1  1  0  1  0
>>>>0  1  1  1  0
>>>>1  1  1  1  0
>>>>1  1  1  1  1
>>>>0  0  0  0  0
>>>>
>>>> The maximum square sub-matrix with all set bits is
>>>>
>>>> 1  1  1
>>>> 1  1  1
>>>> 1  1  1
>>>>
>>>>  --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Maximum size square sub-matrix with all 1s

[Sourabh Singh]

@ ALL

 finding square matrix is quite a standard question and nw an easy one as
everyone knows the reccussence atul has given.
 but  i wanted to find max rectangle..

i know there is a DP for it. in O(n^2). for nxn matrix..don't know the
whole approach .but  here is what i remember..

1. aproach is simple to keep track of max rectangle which can be formed
from any point taking that point as top  left corner of max rectangle and
proceed further down .

can someone suggest how can be proceed further..


[ NOTE: problem occurs mainly when their are more than one rectangles which
can be formed from same point ]

plz.. don't suggest the histogram method it's just a dirty way of avoiding
to work on getting this DP right. :-)


On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote:

> here is the recurrence for solving this
>
> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] )
> );
>
>
> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma wrote:
>
>>
>>  April 4, 2010
>>
>> Given a binary matrix, find out the maximum size square sub-matrix with
>> all 1s.
>>
>> For example, consider the below binary matrix.
>>
>>0  1  1  0  1
>>1  1  0  1  0
>>0  1  1  1  0
>>1  1  1  1  0
>>1  1  1  1  1
>>0  0  0  0  0
>>
>> The maximum square sub-matrix with all set bits is
>>
>> 1  1  1
>> 1  1  1
>> 1  1  1
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Amazon ques

[Sourabh Singh]

@all

plz.. tell if this thing would work..

assume 2 in place of every 0 in array. ie
1 1 0 0 0 1 0 1   be
1 1 2 2 2 1 2 1

then find max sub array wid sum length/2 * 3.

this can be done in O(n) but worst case would still be O(n lgn) .

On 1/26/12, Sanjay Rajpal  wrote:
> +1
> *
> Sanjay Kumar
> B.Tech Final Year
> Department of Computer Engineering
> National Institute of Technology Kurukshetra
> Kurukshetra - 136119
> Haryana, India
> Contact: +91-8053566286
> *
>
>
>
> On Thu, Jan 26, 2012 at 6:28 PM, Ashish Goel  wrote:
>
>> replace all 0s by -1
>> keep additional array to get the sumHere at every position of all -1s and
>> 1s.
>>
>> say you got
>>  0  1  0 1  0  0  0  0 1 1 1 1  0
>> -1 1 -1 1 -1 -1 -1 -1 1 1 1 1 -1
>> sum -1 0 -1 0 -1 -2 -3 -4 -3 -2 -1 0 -1
>>
>> all equal numbers in sum shows equal zeros and 1s between then including
>> the end( between two -2 or two -3 or 0 0r -1) so biggest one can be
>> figured
>> out easily use a hash to store these cum sum, store their first and
>> last occurrence, walk over to get max diff.
>>
>>
>>
>>
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>>
>> On Fri, Jan 27, 2012 at 1:48 AM, algoist  wrote:
>>
>>> Consider 2 temp arrays, B and C
>>>
>>> Where B gets updated for every find of 0 and C for every find of 1
>>>
>>> i.e if(a[i]==0)
>>>b[i]+=b[i-1]+1;
>>>c[i]=c[i-1];
>>> i.e if(a[i]==1)
>>>c[i]+=c[i-1]+1;
>>>b[i]=b[i-1];
>>>
>>> if(c[i]==b[i])
>>>   update max.
>>>
>>> return max.
>>>
>>> This is O(N) algo. Is it right or i am missing anything here?
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/YnKOgIEspAcJ.
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: sort 2D array

[Sourabh Singh]

@all

I have come across this question earlier. it's a young's tableaus (
cormen pg. 167 ) can be treated as min heap. solution can be found in
mit online study material.

i'll post the link here as soon as i remember it.

On 1/24/12, atul anand  wrote:
> @praveen : k way merge would require extra space right??question is to
> do it in place.
>
> On Tue, Jan 24, 2012 at 5:47 PM, praveen raj  wrote:
>
>> This can be done... k way merge...
>>
>> c- number of columns
>> r- number of rows
>>
>> In O(c*r*log(r))
>>
>> PRAVEEN RAJ
>> DELHI COLLEGE OF ENGINEERING
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks]

[Sourabh Singh]

@ALL
//Imagine that you write down all numbers between A and B in 2's
complement representation using 32 bits. How many 1's will you write
down in all ?

wat's wrong with this code

working fine for all cases i tested but

on

http://www.spoj.pl/problems/CODESPTA/

wrong answer..
plz.. point out cases where it might fail . thanku..
#include
int find(int a)
{   int ret=0;
if(a>0)
{
   while(a)
   {
   if(a&1)
  ret++;
   a=a>>1;
   }
}
else if(a==0)
 ret=0;
 else
 {
 a=~a;
 ret=32; //here ret is maximum bits in the representation
of number and it varies from machine to machine
 while(a>0)
 {
   if(a&1)
  ret--;
   a=a>>1;
 }
 }
   return ret;
}
uint64_t solve(uint64_t a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + find(a) ;
 return (a + 1) / 2 + 2 * solve(a / 2) ;
}

main()
{
int a,b,t;
uint64_t in_a,in_b;
scanf("%d",&t);
while(t--)
{   scanf("%d %d",&a,&b);
if(a==-2147483648 & b==2147483647)
  printf("18446744073709551616\n");
else
{
if(a<0)
{  a=-a;
   in_a=(32*a-solve(a-1));
   if(b<0)
   {   b=-b;
   in_b=(32*b-solve(b-1));

printf("%llu\n",in_a-in_b+(32-find(b-1)));
   }
   else
   {
   in_b=solve(b);
   printf("%llu\n",in_b+in_a);
   }
}
else
{
in_a=solve(a);
in_b=solve(b);
printf("%llu\n",in_b-in_a+find(a));
}
}
}
return 0;
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@all sorry .. 21 is prime :-)

 hw can above algo be well implemented to get mpow function...


On 1/18/12, Sourabh Singh  wrote:
> @All
>
> pow() mod is giving problem...
>
> found an algo .. is some1 intrested to discuss...
>
> Example:
> Take  3^21 (mod 7)
>
> 3^2= 9  = 2(mod 7),
> 3^4= (3^2)^2 = 2^2 = 4(mod 7)
> 3^8= (3^4)^2 = 4^2 = 16 = 2(mod 7)
> 3^16  = (3^8)^2 = 2^2 = 4(mod 7)
>
> So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).
>
> basically.. we can split the power and take individual a^d%n for each
> then multiply to get result..
>
> but my question is what if power is prime and big...
>
>
> On 1/18/12, Terence  wrote:
>> error in pow.
>> as long as n < 2^31, x*x fits into int64_t, since x>
>> On 2012-1-18 20:51, Sourabh Singh wrote:
>>> @ Terence
>>>
>>> I belive nw its giving wrong answer for n>41 onwards
>>> due to error's in pow and x*x over flow as u already stated...
>>>
>>> i guess algo is right nw.. ;-)
>>>
>>> thanx again..
>>>
>>>
>>> On 1/18/12, Sourabh Singh  wrote:
>>>> @ thanx got it.. silly mistakes ;-) . missed thought it ws + between s
>>>> and
>>>> d.
>>>>
>>>>
>>>> //suggested corrections made.. still not working..
>>>> #include
>>>> #include
>>>> #include
>>>> using namespace std;
>>>> int is_prime(int n)
>>>> {
>>>>  if(n==2 | n==3)
>>>>return 1;
>>>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>>>return 0;
>>>>  int j,s,d=n-1; while((d&1)==0) d>>=1;
>>>>
>>>>  s=n/d;for(j=0;1<>>>
>>>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>>  uint64_t x;
>>>>  for(i=0;i<6;i++)
>>>>  {if(primes[i]>=n)
>>>>   break;
>>>>   a=primes[i];
>>>>   x=uint64_t(pow(a,d))%n;
>>>>   if(x==1 || x==n-1)
>>>>   continue;
>>>>   int r;
>>>>   for(r=1;r>>>   {   x=(x*x)%n;
>>>>   if(x==1)
>>>>   return 0;
>>>>   if(x==n-1)
>>>> break;
>>>>   }
>>>>   if(x!=n-1)
>>>> return 0;
>>>>  }
>>>>  return 1;
>>>> }
>>>> main()
>>>> {for(int k=1;k<2000;k++)
>>>>   if(is_prime(k))
>>>>  printf("%d is %d\n",k,is_prime(k));
>>>>   getch();
>>>> }
>>>>
>>>>
>>>> On 1/18/12, Terence  wrote:
>>>>> @Sourabh
>>>>>
>>>>> m=2^s***d
>>>>> primes[i]*<*n
>>>>>
>>>>>
>>>>>
>>>>> On 2012-1-18 19:39, Sourabh Singh wrote:
>>>>>> @Terrence
>>>>>>
>>>>>> sry i didn't explain what s,d were they were also wrong i ws
>>>>>> calculating for n not n-1
>>>>>> earlier  n=2^s+d
>>>>>>
>>>>>> nw m=n-1;  for odd n
>>>>>>m=2^s+d;
>>>>>>
>>>>>> //suggested corrections made.. still not working..
>>>>>> #include
>>>>>> #include
>>>>>> #include
>>>>>> using namespace std;
>>>>>> int is_prime(int n)
>>>>>> {
>>>>>>   if(n==2 | n==3)
>>>>>> return 1;
>>>>>>   if(((n-1)%6!=0&   (n+1)%6!=0) || n<2)
>>>>>> return 0;
>>>>>>   int m=n-1;
>>>>>>   int s,d;
>>>>>>   for(s=0;1<>>>>>
>>>>>>   int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>>>>   uint64_t x;
>>>>>>   for(i=0;i<6;i++)
>>>>>>   {if(primes[i]>

Re: [algogeeks]

[Sourabh Singh]

@All

pow() mod is giving problem...

found an algo .. is some1 intrested to discuss...

Example:
Take  3^21 (mod 7)

3^2= 9  = 2(mod 7),
3^4= (3^2)^2 = 2^2 = 4(mod 7)
3^8= (3^4)^2 = 4^2 = 16 = 2(mod 7)
3^16  = (3^8)^2 = 2^2 = 4(mod 7)

So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).

basically.. we can split the power and take individual a^d%n for each
then multiply to get result..

but my question is what if power is prime and big...


On 1/18/12, Terence  wrote:
> error in pow.
> as long as n < 2^31, x*x fits into int64_t, since x
> On 2012-1-18 20:51, Sourabh Singh wrote:
>> @ Terence
>>
>> I belive nw its giving wrong answer for n>41 onwards
>> due to error's in pow and x*x over flow as u already stated...
>>
>> i guess algo is right nw.. ;-)
>>
>> thanx again..
>>
>>
>> On 1/18/12, Sourabh Singh  wrote:
>>> @ thanx got it.. silly mistakes ;-) . missed thought it ws + between s
>>> and
>>> d.
>>>
>>>
>>> //suggested corrections made.. still not working..
>>> #include
>>> #include
>>> #include
>>> using namespace std;
>>> int is_prime(int n)
>>> {
>>>  if(n==2 | n==3)
>>>return 1;
>>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>>return 0;
>>>  int j,s,d=n-1; while((d&1)==0) d>>=1;
>>>
>>>  s=n/d;for(j=0;1<>>
>>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>  uint64_t x;
>>>  for(i=0;i<6;i++)
>>>  {if(primes[i]>=n)
>>>   break;
>>>   a=primes[i];
>>>   x=uint64_t(pow(a,d))%n;
>>>   if(x==1 || x==n-1)
>>>   continue;
>>>   int r;
>>>   for(r=1;r>>   {   x=(x*x)%n;
>>>   if(x==1)
>>>   return 0;
>>>   if(x==n-1)
>>> break;
>>>   }
>>>   if(x!=n-1)
>>> return 0;
>>>  }
>>>  return 1;
>>> }
>>> main()
>>> {for(int k=1;k<2000;k++)
>>>   if(is_prime(k))
>>>  printf("%d is %d\n",k,is_prime(k));
>>>   getch();
>>> }
>>>
>>>
>>> On 1/18/12, Terence  wrote:
>>>> @Sourabh
>>>>
>>>> m=2^s***d
>>>> primes[i]*<*n
>>>>
>>>>
>>>>
>>>> On 2012-1-18 19:39, Sourabh Singh wrote:
>>>>> @Terrence
>>>>>
>>>>> sry i didn't explain what s,d were they were also wrong i ws
>>>>> calculating for n not n-1
>>>>> earlier  n=2^s+d
>>>>>
>>>>> nw m=n-1;  for odd n
>>>>>m=2^s+d;
>>>>>
>>>>> //suggested corrections made.. still not working..
>>>>> #include
>>>>> #include
>>>>> #include
>>>>> using namespace std;
>>>>> int is_prime(int n)
>>>>> {
>>>>>   if(n==2 | n==3)
>>>>> return 1;
>>>>>   if(((n-1)%6!=0&   (n+1)%6!=0) || n<2)
>>>>> return 0;
>>>>>   int m=n-1;
>>>>>   int s,d;
>>>>>   for(s=0;1<>>>>
>>>>>   int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>>>   uint64_t x;
>>>>>   for(i=0;i<6;i++)
>>>>>   {if(primes[i]>n)
>>>>>break;
>>>>>a=primes[i];
>>>>>x=uint64_t(pow(a,d))%n;
>>>>>if(x==1 || x==n-1)
>>>>>continue;
>>>>>
>>>>>for(int r=1;r>>>>{   x=(x*x)%n;
>>>>>if(x==1)
>>>>>return 0;
>>>>>if(x==n-1)
>>>>>  break;
>>>&g

Re: [algogeeks]

[Sourabh Singh]

@ Terence

I belive nw its giving wrong answer for n>41 onwards
due to error's in pow and x*x over flow as u already stated...

i guess algo is right nw.. ;-)

thanx again..


On 1/18/12, Sourabh Singh  wrote:
> @ thanx got it.. silly mistakes ;-) . missed thought it ws + between s and
> d.
>
>
> //suggested corrections made.. still not working..
> #include
> #include
> #include
> using namespace std;
> int is_prime(int n)
> {
> if(n==2 | n==3)
>   return 1;
> if(((n-1)%6!=0 & (n+1)%6!=0) || n<2)
>   return 0;
> int j,s,d=n-1; while((d&1)==0) d>>=1;
>
> s=n/d;for(j=0;1<
> int primes[6]={2,3,7,31,61,73},i,a,flag;
> uint64_t x;
> for(i=0;i<6;i++)
> {if(primes[i]>=n)
>  break;
>  a=primes[i];
>  x=uint64_t(pow(a,d))%n;
>  if(x==1 || x==n-1)
>  continue;
>  int r;
>  for(r=1;r  {   x=(x*x)%n;
>  if(x==1)
>  return 0;
>  if(x==n-1)
>break;
>  }
>  if(x!=n-1)
>return 0;
> }
> return 1;
> }
> main()
> {for(int k=1;k<2000;k++)
>  if(is_prime(k))
> printf("%d is %d\n",k,is_prime(k));
>  getch();
> }
>
>
> On 1/18/12, Terence  wrote:
>> @Sourabh
>>
>> m=2^s***d
>> primes[i]*<*n
>>
>>
>>
>> On 2012-1-18 19:39, Sourabh Singh wrote:
>>> @Terrence
>>>
>>> sry i didn't explain what s,d were they were also wrong i ws
>>> calculating for n not n-1
>>> earlier  n=2^s+d
>>>
>>> nw m=n-1;  for odd n
>>>   m=2^s+d;
>>>
>>> //suggested corrections made.. still not working..
>>> #include
>>> #include
>>> #include
>>> using namespace std;
>>> int is_prime(int n)
>>> {
>>>  if(n==2 | n==3)
>>>return 1;
>>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>>return 0;
>>>  int m=n-1;
>>>  int s,d;
>>>  for(s=0;1<>>
>>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>  uint64_t x;
>>>  for(i=0;i<6;i++)
>>>  {if(primes[i]>n)
>>>   break;
>>>   a=primes[i];
>>>   x=uint64_t(pow(a,d))%n;
>>>   if(x==1 || x==n-1)
>>>   continue;
>>>
>>>   for(int r=1;r>>   {   x=(x*x)%n;
>>>   if(x==1)
>>>   return 0;
>>>   if(x==n-1)
>>> break;
>>>   }
>>>   if(x!=n-1)
>>> return 0;
>>>  }
>>>  return 1;
>>> }
>>> main()
>>> {for(int k=1;k<20;k++) printf("%d is %d\n",k,is_prime(k)); getch();}
>>>
>>>
>>> On 1/18/12, Sourabh Singh  wrote:
>>>> @ sunny agrawal
>>>>
>>>> you are right. but i have used check a>n also . no improvement .
>>>> i think algo is wrong in later part.. somewhere..
>>>>
>>>> @ Terence
>>>>
>>>> 1) pow may not work for big n but , m just checking for n=1..200
>>>> just to check wether algo is right.. and it's not working even for
>>>> n=7,19...
>>>>
>>>> 2) d,s are also coming fine for small values.. of n
>>>>
>>>> 3) for x i have used... 64bit integer.. uint64_t in it's declaration.
>>>>
>>>> i just want to get algo right first then bother about big n ;-)
>>>>
>>>> On 1/18/12, Terence  wrote:
>>>>> 1. the computing of d is incorrect.
>>>>>   d = n-1;
>>>>>   while((d&1)==0) d>>=1;
>>>>>
>>>>> 2. the accuracy of pow is far from enough. you should implement your
>>>>> own
>>>>> pow-modulo-n method.
>>>>>
>>>>> 3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
>>>>> need to implement your own multi

Re: [algogeeks]

[Sourabh Singh]

@ thanx got it.. silly mistakes ;-) . missed thought it ws + between s and d.


//suggested corrections made.. still not working..
#include
#include
#include
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
  return 1;
if(((n-1)%6!=0 & (n+1)%6!=0) || n<2)
  return 0;
int j,s,d=n-1; while((d&1)==0) d>>=1;

s=n/d;for(j=0;1<=n)
 break;
 a=primes[i];
 x=uint64_t(pow(a,d))%n;
 if(x==1 || x==n-1)
 continue;
 int r;
 for(r=1;r wrote:
> @Sourabh
>
> m=2^s***d
> primes[i]*<*n
>
>
>
> On 2012-1-18 19:39, Sourabh Singh wrote:
>> @Terrence
>>
>> sry i didn't explain what s,d were they were also wrong i ws
>> calculating for n not n-1
>> earlier  n=2^s+d
>>
>> nw m=n-1;  for odd n
>>   m=2^s+d;
>>
>> //suggested corrections made.. still not working..
>> #include
>> #include
>> #include
>> using namespace std;
>> int is_prime(int n)
>> {
>>  if(n==2 | n==3)
>>return 1;
>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>return 0;
>>  int m=n-1;
>>  int s,d;
>>  for(s=0;1<>
>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>  uint64_t x;
>>  for(i=0;i<6;i++)
>>  {if(primes[i]>n)
>>   break;
>>   a=primes[i];
>>   x=uint64_t(pow(a,d))%n;
>>   if(x==1 || x==n-1)
>>   continue;
>>
>>   for(int r=1;r>   {   x=(x*x)%n;
>>   if(x==1)
>>   return 0;
>>   if(x==n-1)
>> break;
>>   }
>>   if(x!=n-1)
>> return 0;
>>  }
>>  return 1;
>> }
>> main()
>> {for(int k=1;k<20;k++) printf("%d is %d\n",k,is_prime(k)); getch();}
>>
>>
>> On 1/18/12, Sourabh Singh  wrote:
>>> @ sunny agrawal
>>>
>>> you are right. but i have used check a>n also . no improvement .
>>> i think algo is wrong in later part.. somewhere..
>>>
>>> @ Terence
>>>
>>> 1) pow may not work for big n but , m just checking for n=1..200
>>> just to check wether algo is right.. and it's not working even for
>>> n=7,19...
>>>
>>> 2) d,s are also coming fine for small values.. of n
>>>
>>> 3) for x i have used... 64bit integer.. uint64_t in it's declaration.
>>>
>>> i just want to get algo right first then bother about big n ;-)
>>>
>>> On 1/18/12, Terence  wrote:
>>>> 1. the computing of d is incorrect.
>>>>   d = n-1;
>>>>   while((d&1)==0) d>>=1;
>>>>
>>>> 2. the accuracy of pow is far from enough. you should implement your own
>>>> pow-modulo-n method.
>>>>
>>>> 3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
>>>> need to implement your own multiply method in this case.
>>>>
>>>>
>>>> On 2012-1-18 18:15, Sourabh Singh wrote:
>>>>> @all output's to above code are just random.. some prime's. found
>>>>> correctly while some are not
>>>>>
>>>>> why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
>>>>> n wiki for about 10^15 checking with these is enough..
>>>>>
>>>>> On 1/18/12, Sourabh Singh   wrote:
>>>>>> @ALL hi everyone m trying to make prime checker based on miller-rabin
>>>>>> test . can some1 point out . wat's wrong with the code. thank's alot
>>>>>> in advance...
>>>>>>
>>>>>> //prime checker based on miller-rabin test
>>>>>> #include
>>>>>> #include
>>>>>> #include
>>>>>> int is_prime(int n)
>>>>>> {
>>>>>>   if(n==2 | n==3)
>>>>>> return 1;
>>>>>>   if(((n-1)%6!=0&   (n+1)%6!=0) || n<2)
>>>>>> return 0;
>>>>>>   int s,d;
>>>>>>   for(s=0;1<>>>>>
&

Re: [algogeeks]

[Sourabh Singh]

@Terrence

sry i didn't explain what s,d were they were also wrong i ws
calculating for n not n-1
earlier  n=2^s+d

nw m=n-1;  for odd n
 m=2^s+d;

//suggested corrections made.. still not working..
#include
#include
#include
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
  return 1;
if(((n-1)%6!=0 & (n+1)%6!=0) || n<2)
  return 0;
int m=n-1;
int s,d;
for(s=0;1<n)
 break;
 a=primes[i];
 x=uint64_t(pow(a,d))%n;
 if(x==1 || x==n-1)
 continue;

 for(int r=1;r wrote:
> @ sunny agrawal
>
> you are right. but i have used check a>n also . no improvement .
> i think algo is wrong in later part.. somewhere..
>
> @ Terence
>
> 1) pow may not work for big n but , m just checking for n=1..200
>just to check wether algo is right.. and it's not working even for
> n=7,19...
>
> 2) d,s are also coming fine for small values.. of n
>
> 3) for x i have used... 64bit integer.. uint64_t in it's declaration.
>
> i just want to get algo right first then bother about big n ;-)
>
> On 1/18/12, Terence  wrote:
>> 1. the computing of d is incorrect.
>>  d = n-1;
>>  while((d&1)==0) d>>=1;
>>
>> 2. the accuracy of pow is far from enough. you should implement your own
>> pow-modulo-n method.
>>
>> 3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
>> need to implement your own multiply method in this case.
>>
>>
>> On 2012-1-18 18:15, Sourabh Singh wrote:
>>> @all output's to above code are just random.. some prime's. found
>>> correctly while some are not
>>>
>>> why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
>>> n wiki for about 10^15 checking with these is enough..
>>>
>>> On 1/18/12, Sourabh Singh  wrote:
>>>> @ALL hi everyone m trying to make prime checker based on miller-rabin
>>>> test . can some1 point out . wat's wrong with the code. thank's alot
>>>> in advance...
>>>>
>>>> //prime checker based on miller-rabin test
>>>> #include
>>>> #include
>>>> #include
>>>> int is_prime(int n)
>>>> {
>>>>  if(n==2 | n==3)
>>>>return 1;
>>>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>>>return 0;
>>>>  int s,d;
>>>>  for(s=0;1<>>>
>>>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>>  uint64_t x;
>>>>  for(i=0;i<6;i++)
>>>>  {flag=0;
>>>>
>>>>   a=primes[i];
>>>>   x=uint64_t(pow(a,d))%n;
>>>>   if(x==1 | x==n-1)
>>>>  continue;
>>>>   for(int r=1;r>>>   {   x=(x*x)%n;
>>>>   printf("x is %llu\n",x);
>>>>   if(x==1)
>>>>   return 0;
>>>>   else
>>>>   flag=1;
>>>>   }
>>>>   if(flag)
>>>>   continue;
>>>>   return 0;
>>>>  }
>>>>  return 1;
>>>> }
>>>> main()
>>>> {
>>>>for(int k=1;k<100;k++)
>>>>{
>>>>printf("%d is %d\n",k,is_prime(k));
>>>>}
>>>>getch();
>>>> }
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups
>>>> "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@ sunny agrawal

you are right. but i have used check a>n also . no improvement .
i think algo is wrong in later part.. somewhere..

@ Terence

1) pow may not work for big n but , m just checking for n=1..200
   just to check wether algo is right.. and it's not working even for n=7,19...

2) d,s are also coming fine for small values.. of n

3) for x i have used... 64bit integer.. uint64_t in it's declaration.

i just want to get algo right first then bother about big n ;-)

On 1/18/12, Terence  wrote:
> 1. the computing of d is incorrect.
>  d = n-1;
>  while((d&1)==0) d>>=1;
>
> 2. the accuracy of pow is far from enough. you should implement your own
> pow-modulo-n method.
>
> 3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
> need to implement your own multiply method in this case.
>
>
> On 2012-1-18 18:15, Sourabh Singh wrote:
>> @all output's to above code are just random.. some prime's. found
>> correctly while some are not
>>
>> why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
>> n wiki for about 10^15 checking with these is enough..
>>
>> On 1/18/12, Sourabh Singh  wrote:
>>> @ALL hi everyone m trying to make prime checker based on miller-rabin
>>> test . can some1 point out . wat's wrong with the code. thank's alot
>>> in advance...
>>>
>>> //prime checker based on miller-rabin test
>>> #include
>>> #include
>>> #include
>>> int is_prime(int n)
>>> {
>>>  if(n==2 | n==3)
>>>return 1;
>>>  if(((n-1)%6!=0&  (n+1)%6!=0) || n<2)
>>>return 0;
>>>  int s,d;
>>>  for(s=0;1<>>
>>>  int primes[6]={2,3,7,31,61,73},i,a,flag;
>>>  uint64_t x;
>>>  for(i=0;i<6;i++)
>>>  {flag=0;
>>>
>>>   a=primes[i];
>>>   x=uint64_t(pow(a,d))%n;
>>>   if(x==1 | x==n-1)
>>>  continue;
>>>   for(int r=1;r>>   {   x=(x*x)%n;
>>>   printf("x is %llu\n",x);
>>>   if(x==1)
>>>   return 0;
>>>   else
>>>   flag=1;
>>>   }
>>>   if(flag)
>>>   continue;
>>>   return 0;
>>>  }
>>>  return 1;
>>> }
>>> main()
>>> {
>>>for(int k=1;k<100;k++)
>>>{
>>>printf("%d is %d\n",k,is_prime(k));
>>>}
>>>getch();
>>> }
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[Sourabh Singh]

@all output's to above code are just random.. some prime's. found
correctly while some are not

why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
n wiki for about 10^15 checking with these is enough..

On 1/18/12, Sourabh Singh  wrote:
> @ALL hi everyone m trying to make prime checker based on miller-rabin
> test . can some1 point out . wat's wrong with the code. thank's alot
> in advance...
>
> //prime checker based on miller-rabin test
> #include
> #include
> #include
> int is_prime(int n)
> {
> if(n==2 | n==3)
>   return 1;
> if(((n-1)%6!=0 & (n+1)%6!=0) || n<2)
>   return 0;
> int s,d;
> for(s=0;1<
> int primes[6]={2,3,7,31,61,73},i,a,flag;
> uint64_t x;
> for(i=0;i<6;i++)
> {flag=0;
>
>  a=primes[i];
>  x=uint64_t(pow(a,d))%n;
>  if(x==1 | x==n-1)
> continue;
>  for(int r=1;r  {   x=(x*x)%n;
>  printf("x is %llu\n",x);
>  if(x==1)
>  return 0;
>  else
>  flag=1;
>  }
>  if(flag)
>  continue;
>  return 0;
> }
> return 1;
> }
> main()
> {
>   for(int k=1;k<100;k++)
>   {
>   printf("%d is %d\n",k,is_prime(k));
>   }
>   getch();
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks]

[Sourabh Singh]

@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...

//prime checker based on miller-rabin test
#include
#include
#include
int is_prime(int n)
{
if(n==2 | n==3)
  return 1;
if(((n-1)%6!=0 & (n+1)%6!=0) || n<2)
  return 0;
int s,d;
for(s=0;1

Re: [algogeeks] Re: DP problems in SPOJ

[sourabh singh]

@All are these output's correct ??

288230376151711744  20164264869698944
144115188075855872  5130634330054016
72057594037927936   5130634330054016
36028797018963968   1306288411057536
18014398509481984   1306288411057536
9007199254740992332818957147520
4503599627370496332818957147520
225179981368524884859707399552
112589990684262484859707399552
562949953421312 21654400343424
281474976710656 21654400343424
140737488355328 5530598972800
70368744177664   5530598972800
35184372088832   1413883960704
17592186044416   1413883960704


On Tue, Dec 27, 2011 at 11:20 PM, sourabh singh wrote:

> @all
>
> plz point out wat's wrong with this code. works for small numbers but
> fails for large number's
>
> #include
> #include
> using namespace std;
> unsigned int find_nCp(unsigned int n,unsigned int p)
> { unsigned int j=p;
>   unsigned int num=1,den=1;
>   for(;j;j--)
>num*=n--;
>   for(;p;p--)
>den*=p;
>   return (num/den);
> }
>
> unsigned int num(unsigned int n,unsigned int k)
> {
> if(n==1 || k==0)
> return 1;
> return  find_nCp(n,k) + num(n-2,(n-1)/2);
> }
> main()
> { uint64_t n,p,test=1;
>   unsigned int t,i,sum,j;
>   scanf("%u",&t);
>   while(t--)
>   { n=test< scanf("%llu",&n);
> if(n<4)
>cout<<0< else
> {   for(p=1,i=0;p<=n;p=p<<1,i++);
> i=i-2;
> if(i%2==0)
> {
>   i--;
> }
> cout< getch();
> }
>   }
>   return 0;
> }
>
>
> On Tue, Dec 27, 2011 at 10:33 AM, kumar rajat wrote:
>
>> *I am not able to follow..
>>
>> On Tue, Dec 27, 2011 at 11:47 PM, kumar rajat 
>> wrote:
>> > @Lucifier:
>> > Thanks a lot..
>> > But,I am able to follow the code that u posted for Non-Decreasing
>> Digits.
>> > Can u jus explain ur algo instead of givin the code directly?
>> > Thanks once again.
>> >
>> > On Tue, Dec 27, 2011 at 10:44 PM, Lucifer 
>> wrote:
>> >> @ Special Nos..
>> >> Well the actual logic would be :
>> >> int count = 0;for ( int i = 2; i <= LOGbase2(N) ; i+=2)  count+=
>> >> [ (i-1) C (i/2) ] ; // here xCy is nothing but the no. of ways y items
>> >> can be selected from a collection of x items.
>> >> Hence, the working code:
>> >> int totalCount = 0;
>> >> int interCnt = 1;
>> >>
>> >> if ( LOGbase2(N) > 1)
>> >> {
>> >>  totalCount = 1; // for LOGbase2(N) = 2...
>> >>
>> >>  for ( int i = 4; i <= LOGbase2(N) ; i+=2)
>> >>  {
>> >> interCnt = (i-1)*(i-2) * interCnt / ( i/2 * (i/2 -1));
>> >>  totalCount += interCnt;
>> >>
>> >>  }
>> >>  printf("%d", totalCount);
>> >> }
>> >> else
>> >>  printf("%d", 0);
>> >> On Dec 27, 7:38 pm, Tasvinder Singh  wrote:
>> >>> I think the first problem involves some mathematics...
>> >>> In this we fix the first bit and if the remaining no. of bits are odd
>> then
>> >>> we calculate the no. as follows
>> >>>
>> >>> If we have 2^4=16  then total bits 5 so we do not include this.
>> >>> Total no. of bits in one less than the given no. (in this eg. 15) is
>> 4.
>> >>> Fix first bit, no. of bits remaining = 3
>> >>> Now let 2 bits are 0 and one bit 1. We have total 3!/(2!*1!) = 3
>> >>> combinations.
>> >>>
>> >>> Now go for next even no which is 2 in this case again do the same
>> >>> Fix first bit, no. of bits remaining = 1
>> >>> Now let 1 bit is 0. We have total 1!/(0!*1!) = 1 combinations.
>> >>>
>> >>> Next even 0. stop here.
>> >>> You can go for this by starting from 2 till no. is less than given N
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> On Tue, Dec 27, 2011 at 7:28 PM, kumar rajat 
>> wrote:
>> >>> > Hi
>> >

Re: [algogeeks] Re: DP problems in SPOJ

[sourabh singh]

@all

plz point out wat's wrong with this code. works for small numbers but fails
for large number's

#include
#include
using namespace std;
unsigned int find_nCp(unsigned int n,unsigned int p)
{ unsigned int j=p;
  unsigned int num=1,den=1;
  for(;j;j--)
   num*=n--;
  for(;p;p--)
   den*=p;
  return (num/den);
}

unsigned int num(unsigned int n,unsigned int k)
{
if(n==1 || k==0)
return 1;
return  find_nCp(n,k) + num(n-2,(n-1)/2);
}
main()
{ uint64_t n,p,test=1;
  unsigned int t,i,sum,j;
  scanf("%u",&t);
  while(t--)
  { n=test *I am not able to follow..
>
> On Tue, Dec 27, 2011 at 11:47 PM, kumar rajat 
> wrote:
> > @Lucifier:
> > Thanks a lot..
> > But,I am able to follow the code that u posted for Non-Decreasing Digits.
> > Can u jus explain ur algo instead of givin the code directly?
> > Thanks once again.
> >
> > On Tue, Dec 27, 2011 at 10:44 PM, Lucifer 
> wrote:
> >> @ Special Nos..
> >> Well the actual logic would be :
> >> int count = 0;for ( int i = 2; i <= LOGbase2(N) ; i+=2)  count+=
> >> [ (i-1) C (i/2) ] ; // here xCy is nothing but the no. of ways y items
> >> can be selected from a collection of x items.
> >> Hence, the working code:
> >> int totalCount = 0;
> >> int interCnt = 1;
> >>
> >> if ( LOGbase2(N) > 1)
> >> {
> >>  totalCount = 1; // for LOGbase2(N) = 2...
> >>
> >>  for ( int i = 4; i <= LOGbase2(N) ; i+=2)
> >>  {
> >> interCnt = (i-1)*(i-2) * interCnt / ( i/2 * (i/2 -1));
> >>  totalCount += interCnt;
> >>
> >>  }
> >>  printf("%d", totalCount);
> >> }
> >> else
> >>  printf("%d", 0);
> >> On Dec 27, 7:38 pm, Tasvinder Singh  wrote:
> >>> I think the first problem involves some mathematics...
> >>> In this we fix the first bit and if the remaining no. of bits are odd
> then
> >>> we calculate the no. as follows
> >>>
> >>> If we have 2^4=16  then total bits 5 so we do not include this.
> >>> Total no. of bits in one less than the given no. (in this eg. 15) is 4.
> >>> Fix first bit, no. of bits remaining = 3
> >>> Now let 2 bits are 0 and one bit 1. We have total 3!/(2!*1!) = 3
> >>> combinations.
> >>>
> >>> Now go for next even no which is 2 in this case again do the same
> >>> Fix first bit, no. of bits remaining = 1
> >>> Now let 1 bit is 0. We have total 1!/(0!*1!) = 1 combinations.
> >>>
> >>> Next even 0. stop here.
> >>> You can go for this by starting from 2 till no. is less than given N
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> >>> On Tue, Dec 27, 2011 at 7:28 PM, kumar rajat 
> wrote:
> >>> > Hi
> >>> > I have jus started to learn DP and I have coded the standard
> >>> > algorithms(LCS,etc).
> >>> > I have been trying these problems in SPOJ:
> >>>
> >>> >http://www.spoj.pl/problems/NOVICE63/
> >>> >http://www.spoj.pl/problems/NY10E/
> >>>
> >>> > I understand these may be solved elegantly using DP,but I dont get to
> >>> > code the same.
> >>> > Can any1 help me how to solve these types of problems using DP?
> >>> > Any help regarding the same will be greatly appreciated.
> >>>
> >>> > --
> >>> > 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.
> >>>
> >>> --
> >>> Tasvinder Singh
> >>> B.Tech Final Year,
> >>> Department of Computer Engineering,
> >>> Malaviya National Institute Of Technology, Jaipur.
> >>> Contact: +91-9460627331
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
> >>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: DP problems in SPOJ

[sourabh singh]

@All

i was searching fr some better way for i/o . i came across this code and
many similar examples on net.
i think asm can provide a way to load .output directly nd take input
directly from i/o registers . but due to me being new to
asm these code's are giving me trouble.

It's an  AT&T type asm code.

#include 
#include 
int main() {
/* Add 10 and 20 and store result into register %eax */
__asm__ ( "movl $10, %eax;"
"movl $20, %ebx;"
"addl %ebx, %eax;"
);


Now, I don't knw.

1. wat input register is called ?
2. wat output register is called ?
3. how to do simple i/o using asm ?

[ NOTE : I have googled enough so plz no replies as "Google 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.

Re: [algogeeks] Re: doubt in spoj 8473 ways

[sourabh singh]

@anubhav  No,i can't post an AC code here . takes all fun out of spoj
problem solving thing.

i can just hint that i used the function posted earlier and u don't need to
make a function single for loop will do.
that's it try harder. buddy :-)

btw it got ac 111 later :-).

On Sat, Dec 17, 2011 at 5:43 AM, anubhav raj  wrote:

> @saurav: if you dnt mind cn i c ur code...like earlier your post was also
> related to f(n) bt it wz out f d limit
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: doubt in spoj 8473 ways

[sourabh singh]

@all got AC 114 still i think without some other way to input/output it
hard to get below 100. can some1 suggest some better (smaller ) way to i/o
integers 

On Sat, Dec 17, 2011 at 1:31 AM, sourabh singh wrote:

> @anubhav i too didn't find it on google bt may be it is:
>
> f(n)=  ((4n-2)/n)*f(n-1)n>1
>
>  2   n=1
>
>
> On Fri, Dec 16, 2011 at 8:07 AM, anubhav raj wrote:
>
>> @samm:i hv googled it several time bt by code no & path r ways as a tag
>> bt cudnt get ne link..cn u plz paste the link here.i
>> jst want 2 do ittnx in advnce
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: doubt in spoj 8473 ways

[sourabh singh]

@anubhav i too didn't find it on google bt may be it is:

f(n)=  ((4n-2)/n)*f(n-1)n>1

 2   n=1


On Fri, Dec 16, 2011 at 8:07 AM, anubhav raj  wrote:

> @samm:i hv googled it several time bt by code no & path r ways as a tag bt
> cudnt get ne link..cn u plz paste the link here.i jst
> want 2 do ittnx in advnce
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] doubt in spoj 8473 ways

[sourabh singh]

limit is just v.smll can ny1 help me with this code: [ c code ] get it
under 120 bytes .
is there any way to take inputs. without using scanf ???   in c .  m
thinking about inputs getting into
argc array directly.???

#define s(n) scanf("%d",&n);
f(int n){return n==1?1:(n*f(n-1));}
main()
{
  int t,n;
  s(t)
  while(t--)
  { s(n)
printf("%d",(f(2*n)/f(n))/f(n));
  }
}


On Thu, Dec 15, 2011 at 10:08 PM, anubhav raj  wrote:

> #include
> #define s(n) scanf("%d",&n)
> #define I int
> I a[14][14];
> I d(I m,I n)
> {
> I s=a[m][n];
> I k;
> if(!m||!n)
> k=1;
> else if(s)
> k=s;
> else
> {
> k=d(m-1,n)+d(m,n-1);
> s=k;
> }
> return k;
> }
> main()
> {
> I t,n,k;s(t);
> while(t--)
> {
> s(n);
> k=d(n,n);
> printf("%d\n",k);
> }
> }
>
> @saurav:this is the actual and very simple code...may be u cn
> reduce its no of bytesits simple dp approach...tnx
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] doubt in spoj 8473 ways

[sourabh singh]

yup it can be further reduced but i think u need a new approach. (m,m) is a
big hint . try some nCp type of solution.

#define s(n) scanf("%d",&n)
#define I int
I a[14][14],t,n;
I d(I m,I n)
{ I s=a[m][n],
  k=(!m||!n)?1:(s?s:d(m-1,n)+d(m,n-1));
  s=k;return k;
}
main()
{
  s(t);
  while(t--)
  {
s(n);
printf("%d\n",d(n,n));
}
  return 0;
}


On Thu, Dec 15, 2011 at 6:10 PM, saurabh singh  wrote:

> Post the formatted code too.(With proper indents)Then it would be easier
> for others to work on it,
>
>
> On Thu, Dec 15, 2011 at 11:47 PM, anubhav raj wrote:
>
>> we have to submit it in 120 byte cn ne 1 tl me dat whr z the chances of
>> further byte reduction in this code.
>> #include
>> #define s(n) scanf("%d",&n)
>> #define I int
>> I a[14][14];I d(I m,I n){I s=a[m][n];I k;if(!m||!n)k=1;else
>> if(s)k=s;else{k=d(m-1,n)+d(m,n-1);s=k;}return k;}main(){I
>> t,n,k;s(t);while(t--){s(n);k=d(n,n);printf("%d\n",k);}}
>>
>> tnx in advnce
>>
>> --
>> 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.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Sub-array problem

[sourabh singh]

@ giridhar IS  correction missed increment j in outer loop: sry :-)

assuming u wanted k=13 ( max sum <=13)

start : i,j points to 1st element
keep a track of sum between i to j

outer loop:   till j wrote:
> @ giridhar IS
>
> assuming u wanted k=13 ( max sum <=13)
>
> start : i,j points to 1st element
>  keep a track of sum between i to j
>
> outer loop:   till j sum=sum+a[j]
> inner loop  till sum exceeds k.
>increment i .sum=sum-a[i]
>keep track of max sum so far in max.
> end :   max will have max sum < k.
>
> values after each looping of outer loop:
>
> i j summax
> 0000
> 0122
> 0299
> 0312  12
> 24712
> 2512  12
> 4613  13
>
> On 12/7/11, Chunyuan Ge  wrote:
>> My implementation, can anyone offer my test cases that i can verify?
>>
>> struct Deal
>> {
>> unsigned int nStartIndex;
>> unsigned int nEndIndex;
>> unsigned int nSum;
>>
>> Deal()
>> {
>> nStartIndex = 0;
>> nEndIndex = 0;
>> nSum = 0;
>> }
>> };
>>
>> int findBestDeal( const std::vector& iHotelPrices, unsigned
>> int iLotteryPrice, Deal& bestDeal)
>> {
>> /* for loop to find a. best solution in history
>> b. best solution end with j-1
>> */
>>
>> Deal bestPotential;
>>
>> for (unsigned int i=0; i> {
>> unsigned int nTemp = bestPotential.nSum + iHotelPrices[i];
>>
>> if ( nTemp <= iLotteryPrice)
>> {
>> bestPotential.nSum = nTemp;
>> bestPotential.nEndIndex = i;
>> }
>> else
>> {
>> int nStepCount = 0;
>> unsigned int newTemp = nTemp;
>> do
>> {
>> newTemp -=
>> iHotelPrices[bestPotential.nStartIndex+nStepCount];
>> nStepCount ++;
>> }
>> while (newTemp > iLotteryPrice);
>>
>> // better solution
>>     bestPotential.nSum = newTemp;
>> bestPotential.nEndIndex = i;
>> bestPotential.nStartIndex += nStepCount;
>> }
>>
>> if (bestPotential.nSum > bestDeal.nSum)
>> {
>> bestDeal = bestPotential;
>> }
>> }
>>
>> return 0;
>> }
>>
>>
>>
>> On Wed, Dec 7, 2011 at 4:58 AM, GIRIDHAR IS  wrote:
>>
>>> @sourabh
>>>
>>> can you explain me how it will work for this example
>>> a[]={2,7,3,4,5,8,10}
>>>
>>>
>>> On Dec 7, 12:17 am, sourabh singh  wrote:
>>> > @ sourabh :-) yep, got your point... it wont work for all cases.
>>> > but
>>> > if we set initial max to a negative value . say max possible 64 bit
>>> > -ve number.then ?
>>> > point is though the code has limitations it will work fine mostly.
>>> >
>>> > On 12/5/11, sourabh  wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > @sourabh singh..
>>> >
>>> > > Hey u don't need an example... I see a check "sum > max" in ur code
>>> > > to
>>> > > calculate the max value, ryt ? Now ur initial value of max is set to
>>> > > 1. That means ur always assuming that the value whose closest is to
>>> > > be
>>> > > found is >= 1 , which is incorrect. What do you think ?
>>> >
>>> > > On Dec 6, 12:24 am, sourabh singh  wrote:
>>> > >> @ sourabh tried some cases its working on -ve as well. pls post
>>> > >> some
>>> > >> case in which it might not work.
>>> >
>>> > >> On 12/5/11, sourabh  wrote:
>>> >
>>> > >> > @sourabh..
>>> >
>>> > >> > I don't think it will work for all the cases.. did u consider
>>> negative
>>> > >> > integers as well... what i can understand from the above code is
>>> that
>>> > >> > u have taken 2 pointers of which one points to the beginning of
>>> > >> > the
>>> > >&

Re: [algogeeks] Re: Sub-array problem

[sourabh singh]

@ giridhar IS

assuming u wanted k=13 ( max sum <=13)

start : i,j points to 1st element
 keep a track of sum between i to j

outer loop:   till j wrote:
> My implementation, can anyone offer my test cases that i can verify?
>
> struct Deal
> {
> unsigned int nStartIndex;
> unsigned int nEndIndex;
> unsigned int nSum;
>
> Deal()
> {
> nStartIndex = 0;
> nEndIndex = 0;
> nSum = 0;
> }
> };
>
> int findBestDeal( const std::vector& iHotelPrices, unsigned
> int iLotteryPrice, Deal& bestDeal)
> {
> /* for loop to find a. best solution in history
> b. best solution end with j-1
> */
>
> Deal bestPotential;
>
> for (unsigned int i=0; i {
> unsigned int nTemp = bestPotential.nSum + iHotelPrices[i];
>
> if ( nTemp <= iLotteryPrice)
> {
> bestPotential.nSum = nTemp;
> bestPotential.nEndIndex = i;
> }
> else
> {
> int nStepCount = 0;
> unsigned int newTemp = nTemp;
> do
> {
> newTemp -=
> iHotelPrices[bestPotential.nStartIndex+nStepCount];
> nStepCount ++;
> }
> while (newTemp > iLotteryPrice);
>
> // better solution
> bestPotential.nSum = newTemp;
> bestPotential.nEndIndex = i;
> bestPotential.nStartIndex += nStepCount;
> }
>
> if (bestPotential.nSum > bestDeal.nSum)
> {
> bestDeal = bestPotential;
> }
> }
>
> return 0;
> }
>
>
>
> On Wed, Dec 7, 2011 at 4:58 AM, GIRIDHAR IS  wrote:
>
>> @sourabh
>>
>> can you explain me how it will work for this example
>> a[]={2,7,3,4,5,8,10}
>>
>>
>> On Dec 7, 12:17 am, sourabh singh  wrote:
>> > @ sourabh :-) yep, got your point... it wont work for all cases.
>> > but
>> > if we set initial max to a negative value . say max possible 64 bit
>> > -ve number.then ?
>> > point is though the code has limitations it will work fine mostly.
>> >
>> > On 12/5/11, sourabh  wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > @sourabh singh..
>> >
>> > > Hey u don't need an example... I see a check "sum > max" in ur code to
>> > > calculate the max value, ryt ? Now ur initial value of max is set to
>> > > 1. That means ur always assuming that the value whose closest is to be
>> > > found is >= 1 , which is incorrect. What do you think ?
>> >
>> > > On Dec 6, 12:24 am, sourabh singh  wrote:
>> > >> @ sourabh tried some cases its working on -ve as well. pls post some
>> > >> case in which it might not work.
>> >
>> > >> On 12/5/11, sourabh  wrote:
>> >
>> > >> > @sourabh..
>> >
>> > >> > I don't think it will work for all the cases.. did u consider
>> negative
>> > >> > integers as well... what i can understand from the above code is
>> that
>> > >> > u have taken 2 pointers of which one points to the beginning of the
>> > >> > subarray and other one at the end of the subarray and u r shifting
>> the
>> > >> > pointers based on the closest value.. this app is fine for non-
>> > >> > negative integers but will fail when the given input contains both
>> neg
>> > >> > and pos integers...
>> >
>> > >> > On Dec 5, 4:25 pm, sourabh singh  wrote:
>> > >> >> @ mohit my first post on here. this solution got ac  in spoj
>> >
>> > >> >> main()
>> > >> >> {
>> > >> >>unsigned int n,m,sum,max,i,j;
>> > >> >> sum=0;max=1;
>> > >> >> n=in.ReadNextUInt();
>> > >> >> m=in.ReadNextUInt();
>> > >> >> unsigned int *a = new unsigned int[n];
>> > >> >> unsigned int *p = a;
>> > >> >> for (i=0; i < n; i++)
>> > >> >> *(p++) = in.ReadNextUInt();
>> > >> >> i=0;
>> > >> >> j=0;
>> > >> >> while(j> >

Re: [algogeeks] Re: Sub-array problem

[sourabh singh]

@ sourabh :-) yep, got your point... it wont work for all cases.
but
if we set initial max to a negative value . say max possible 64 bit
-ve number.then ?
point is though the code has limitations it will work fine mostly.


On 12/5/11, sourabh  wrote:
> @sourabh singh..
>
> Hey u don't need an example... I see a check "sum > max" in ur code to
> calculate the max value, ryt ? Now ur initial value of max is set to
> 1. That means ur always assuming that the value whose closest is to be
> found is >= 1 , which is incorrect. What do you think ?
>
> On Dec 6, 12:24 am, sourabh singh  wrote:
>> @ sourabh tried some cases its working on -ve as well. pls post some
>> case in which it might not work.
>>
>> On 12/5/11, sourabh  wrote:
>>
>>
>>
>>
>>
>>
>>
>> > @sourabh..
>>
>> > I don't think it will work for all the cases.. did u consider negative
>> > integers as well... what i can understand from the above code is that
>> > u have taken 2 pointers of which one points to the beginning of the
>> > subarray and other one at the end of the subarray and u r shifting the
>> > pointers based on the closest value.. this app is fine for non-
>> > negative integers but will fail when the given input contains both neg
>> > and pos integers...
>>
>> > On Dec 5, 4:25 pm, sourabh singh  wrote:
>> >> @ mohit my first post on here. this solution got ac  in spoj
>>
>> >> main()
>> >> {
>> >>            unsigned int n,m,sum,max,i,j;
>> >>                 sum=0;max=1;
>> >>                 n=in.ReadNextUInt();
>> >>                 m=in.ReadNextUInt();
>> >>                 unsigned int *a = new unsigned int[n];
>> >>                     unsigned int *p = a;
>> >>                 for (i=0; i < n; i++)
>> >>                             *(p++) = in.ReadNextUInt();
>> >>                     i=0;
>> >>                 j=0;
>> >>                 while(j> >>                 {
>> >>                          sum+=a[j++];
>> >>                          while(sum>m)
>> >>                          {
>> >>                                      sum-=a[i++];
>> >>                          }
>> >>                          if(sum>max)
>> >>                                     max=sum;
>> >>                 }
>> >>                 out.WriteUInt(max,'\n');
>>
>> >>        out.Flush();
>> >>        return 0;
>>
>> >> }
>>
>> >> On 11/28/11, Mohit kumar lal  wrote:
>>
>> >> > Given a array of positive integers ,You have to find the largest sum
>> >> > possible from consecutive sub-array but sum should be less than or
>> >> > equal
>> >> > to
>> >> > K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
>> >> >  ans->12, sub-array={3,4,5}
>>
>> >> > Firstly i tried with brute-force and then i also tried to solve it by
>> >> > DP
>> >> > but complexity were same ( O(n^2)) so plz try to provide a
>> >> > solution
>> >> > for
>> >> > O(nlgn) or O(n).
>>
>> >> > --
>> >> > Mohit kumar lal
>>
>> >> > IIIT ALLAHABAD
>>
>> >> > --
>> >> > You received this message because you are subscribed to the Google
>> >> > Groups
>> >> > "Algorithm Geeks" group.
>> >> > To post to this group, send email to algogeeks@googlegroups.com.
>> >> > To unsubscribe from this group, send email to
>> >> > algogeeks+unsubscr...@googlegroups.com.
>> >> > For more options, visit this group at
>> >> >http://groups.google.com/group/algogeeks?hl=en.
>>
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

@sourabh singh..

Hey u don't need an example... I see a check "sum > max" in ur code to
calculate the max value, ryt ? Now ur initial value of max is set to
1. That means ur always assuming that the value whose closest is to be
found is >= 1 , which is incorrect. What do you think ?

On Dec 6, 12:24 am, sourabh singh  wrote:
> @ sourabh tried some cases its working on -ve as well. pls post some
> case in which it might not work.
>
> On 12/5/11, sourabh  wrote:
>
>
>
>
>
>
>
> > @sourabh..
>
> > I don't think it will work for all the cases.. did u consider negative
> > integers as well... what i can understand from the above code is that
> > u have taken 2 pointers of which one points to the beginning of the
> > subarray and other one at the end of the subarray and u r shifting the
> > pointers based on the closest value.. this app is fine for non-
> > negative integers but will fail when the given input contains both neg
> > and pos integers...
>
> > On Dec 5, 4:25 pm, sourabh singh  wrote:
> >> @ mohit my first post on here. this solution got ac  in spoj
>
> >> main()
> >> {
> >>            unsigned int n,m,sum,max,i,j;
> >>                 sum=0;max=1;
> >>                 n=in.ReadNextUInt();
> >>                 m=in.ReadNextUInt();
> >>                 unsigned int *a = new unsigned int[n];
> >>                     unsigned int *p = a;
> >>                 for (i=0; i < n; i++)
> >>                             *(p++) = in.ReadNextUInt();
> >>                     i=0;
> >>                 j=0;
> >>                 while(j >>                 {
> >>                          sum+=a[j++];
> >>                          while(sum>m)
> >>                          {
> >>                                      sum-=a[i++];
> >>                          }
> >>                          if(sum>max)
> >>                                     max=sum;
> >>                 }
> >>                 out.WriteUInt(max,'\n');
>
> >>        out.Flush();
> >>        return 0;
>
> >> }
>
> >> On 11/28/11, Mohit kumar lal  wrote:
>
> >> > Given a array of positive integers ,You have to find the largest sum
> >> > possible from consecutive sub-array but sum should be less than or equal
> >> > to
> >> > K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> >> >  ans->12, sub-array={3,4,5}
>
> >> > Firstly i tried with brute-force and then i also tried to solve it by DP
> >> > but complexity were same ( O(n^2)) so plz try to provide a solution
> >> > for
> >> > O(nlgn) or O(n).
>
> >> > --
> >> > Mohit kumar lal
>
> >> > IIIT ALLAHABAD
>
> >> > --
> >> > You received this message because you are subscribed to the Google
> >> > Groups
> >> > "Algorithm Geeks" group.
> >> > To post to this group, send email to algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com.
> >> > For more options, visit this group at
> >> >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks]

[sourabh]

This problem is a direct implication of "next_permutation" defined in C
++ STL algorithms.

1) From the end, keep decrementing till A[i] < A[i+1]..
2) Now, find the closest element , greater than equal, to A[i] in A[i
+1 ... n]. Say, the index of the found element is "j".
3) Swap (A[i], A[j])
4) Reverse array A[i+1 .. n]



On Dec 6, 12:37 am, Anup Ghatage  wrote:
> Hmm here is a thought.
>
> In the given number, check the second digit from the left.
>
> if it is the maximum, find the digit that is the next greater digit from
> the left most digit.
> append it to the start and append all the other numbers in sorted order.
>
> if the second from left isn't the largest, find the next digit that is
> greater than the last digit and swap places with it.
>
> On Mon, Dec 5, 2011 at 11:05 PM, raushan kumar 
> wrote:
>
> > Given a number,find the next higher number using the same digits in the
> > number.
> > eg: 15432  :: 21345
> >        14532
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Anup Ghatage

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Sub-array problem

[sourabh singh]

@ sourabh tried some cases its working on -ve as well. pls post some
case in which it might not work.

On 12/5/11, sourabh  wrote:
> @sourabh..
>
> I don't think it will work for all the cases.. did u consider negative
> integers as well... what i can understand from the above code is that
> u have taken 2 pointers of which one points to the beginning of the
> subarray and other one at the end of the subarray and u r shifting the
> pointers based on the closest value.. this app is fine for non-
> negative integers but will fail when the given input contains both neg
> and pos integers...
>
> On Dec 5, 4:25 pm, sourabh singh  wrote:
>> @ mohit my first post on here. this solution got ac  in spoj
>>
>> main()
>> {
>>            unsigned int n,m,sum,max,i,j;
>>                 sum=0;max=1;
>>                 n=in.ReadNextUInt();
>>                 m=in.ReadNextUInt();
>>                 unsigned int *a = new unsigned int[n];
>>                     unsigned int *p = a;
>>                 for (i=0; i < n; i++)
>>                             *(p++) = in.ReadNextUInt();
>>                     i=0;
>>                 j=0;
>>                 while(j>                 {
>>                          sum+=a[j++];
>>                          while(sum>m)
>>                          {
>>                                      sum-=a[i++];
>>                          }
>>                          if(sum>max)
>>                                     max=sum;
>>                 }
>>                 out.WriteUInt(max,'\n');
>>
>>        out.Flush();
>>        return 0;
>>
>> }
>>
>> On 11/28/11, Mohit kumar lal  wrote:
>>
>>
>>
>>
>>
>>
>>
>> > Given a array of positive integers ,You have to find the largest sum
>> > possible from consecutive sub-array but sum should be less than or equal
>> > to
>> > K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
>> >  ans->12, sub-array={3,4,5}
>>
>> > Firstly i tried with brute-force and then i also tried to solve it by DP
>> > but complexity were same ( O(n^2)) so plz try to provide a solution
>> > for
>> > O(nlgn) or O(n).
>>
>> > --
>> > Mohit kumar lal
>>
>> > IIIT ALLAHABAD
>>
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

@sourabh..

I don't think it will work for all the cases.. did u consider negative
integers as well... what i can understand from the above code is that
u have taken 2 pointers of which one points to the beginning of the
subarray and other one at the end of the subarray and u r shifting the
pointers based on the closest value.. this app is fine for non-
negative integers but will fail when the given input contains both neg
and pos integers...

On Dec 5, 4:25 pm, sourabh singh  wrote:
> @ mohit my first post on here. this solution got ac  in spoj
>
> main()
> {
>            unsigned int n,m,sum,max,i,j;
>                 sum=0;max=1;
>                 n=in.ReadNextUInt();
>                 m=in.ReadNextUInt();
>                 unsigned int *a = new unsigned int[n];
>                     unsigned int *p = a;
>                 for (i=0; i < n; i++)
>                             *(p++) = in.ReadNextUInt();
>                     i=0;
>                 j=0;
>                 while(j                 {
>                          sum+=a[j++];
>                          while(sum>m)
>                          {
>                                      sum-=a[i++];
>                          }
>                          if(sum>max)
>                                     max=sum;
>                 }
>                 out.WriteUInt(max,'\n');
>
>        out.Flush();
>        return 0;
>
> }
>
> On 11/28/11, Mohit kumar lal  wrote:
>
>
>
>
>
>
>
> > Given a array of positive integers ,You have to find the largest sum
> > possible from consecutive sub-array but sum should be less than or equal to
> > K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> >  ans->12, sub-array={3,4,5}
>
> > Firstly i tried with brute-force and then i also tried to solve it by DP
> > but complexity were same ( O(n^2)) so plz try to provide a solution for
> > O(nlgn) or O(n).
>
> > --
> > Mohit kumar lal
>
> > IIIT ALLAHABAD
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Sub-array problem

[sourabh singh]

@ mohit my first post on here. this solution got ac  in spoj

main()
{
   unsigned int n,m,sum,max,i,j;
sum=0;max=1;
n=in.ReadNextUInt();
m=in.ReadNextUInt();
unsigned int *a = new unsigned int[n];
unsigned int *p = a;
for (i=0; i < n; i++)
*(p++) = in.ReadNextUInt();
i=0;
j=0;
while(jm)
 {
 sum-=a[i++];
 }
 if(sum>max)
max=sum;
}
out.WriteUInt(max,'\n');

   out.Flush();
   return 0;
}


On 11/28/11, Mohit kumar lal  wrote:
> Given a array of positive integers ,You have to find the largest sum
> possible from consecutive sub-array but sum should be less than or equal to
> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
>  ans->12, sub-array={3,4,5}
>
> Firstly i tried with brute-force and then i also tried to solve it by DP
> but complexity were same ( O(n^2)) so plz try to provide a solution for
> O(nlgn) or O(n).
>
> --
> Mohit kumar lal
>
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Maximal possible subsets Algorithm

[sourabh]

@ Piyush..

I have a doubt... Is there any significance of the value Vi, if yes
then can u give an example.
If not, then is your question about finding all maximum subsets where
the addition of the weights results in maximum (each weight being
considered only once)...
Say for ex-
The max weight is X<=Wmax , then find all subsets which add up to X..


On Dec 5, 1:51 pm, Piyush Grover  wrote:
> Yeah but there's one more  condition where it says if subset x is a
> solution then all the subsets of x will not be part of the solution.
> It should make some difference, exponential time solution is an obvious one.
>
>
>
>
>
>
>
> On Mon, Dec 5, 2011 at 2:16 PM, saurabh singh  wrote:
> > The possibility is ruled out by your question itself.There are exponential
> > subsets of a set,so finding all subset is not possible in polynomail time.
>
> > A backtracking approach is what you should think on,
>
> > On Mon, Dec 5, 2011 at 12:51 PM, Piyush Grover 
> > wrote:
>
> >> Given a set S of objects having weights Wi and values Vi, and given a
> >> maximum weight Wmax.
> >>  Find *ALL* the maximal subsets of set S such that Sum(Wi) <= Wmax.
>
> >>  Maximal subset means if {a, b, c} is a solution (such that Wa+Wb+Wc <=
> >> Wmax) it means there doesn't exist any other object x in S such that
> >> Wa+Wb+Wc+Wx <= Wmax and all the subsets of {a, b, c} e.g. {a, b}, {b, c},
> >> {a, c}{c} are not the part of the solution set.
>
> >> P.S. Note that I am *not asking the knapsack problem* where we need to
> >> find the optimal set.
> >>  I am asking *ALL* the possible maximal subsets and looking for a good
> >> algo (polynomial if exists).
>
> >> Thanks
>
> >> Piyush
>
> >> --
> >> 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.
>
> > --
> > Saurabh Singh
> > B.Tech (Computer Science)
> > MNNIT ALLAHABAD
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

@ankit...
I don't think the algorithm is correct...
The check "max_ending_here < 0 && max_limit_here <=k" doesn't look
correct...
Also I am not able to figure out the importance of 0 in the check ..

Ankit, may be I am wrong. Hence, can you come up with the algorithm
explaining ( with a set of steps ) what you are doing here...

On Dec 1, 11:12 pm, atul anand  wrote:
> @ankit : sorry dude , its not working for given input
>
> {2,1,3,4,5} k=12,
>  ans=12, sub-array={3,4,5}
>
> your algo will give ans=10 sub-array{0 to 3}
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha  wrote:
> > A little variation of kadane's algo will do as written below: -
>
> > #include "stdafx.h"
> > #include "stdlib.h"
>
> > int _tmain(int argc, _TCHAR* argv[])
> > {
> >        int a[5] = {-1,3,1,2,-3};
> >        int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0
> > ,
> > endIndex = 0, itr = 0;
> >        int k=12;
> >        for (itr = 0; itr<5;itr++)
> >        {
> >                max_ending_here +=a[itr];
> >                if (max_ending_here < 0 && max_limit_here <=k)
> >                {
> >                        max_ending_here = 0;
> >                        startIndex++;
> >                }
> >                else if (max_so_far  >                {
> >                        if (max_ending_here <= k)
> >                        {
> >                                max_so_far = max_ending_here;
> >                                endIndex = itr;
> >                        }
> >                        else
> >                        {
> >                                max_limit_here = max_ending_here;
> >                                max_ending_here = 0;
>
> >                        }
> >                }
>
> >        }
>
> >        printf("%d%d%d", max_so_far, startIndex, endIndex);
> >        system("PAUSE");
> >        return 0;
> > }
> > Complexity O(n)
>
> > Cheers,
> > Ankit Sinha
> > On Thu, Dec 1, 2011 at 4:58 PM, sourabh  wrote:
> > > @atul...
> > > thanks dude for ur thorough screening of the algo and pointing out the
> > > mistakes... I think that's y its always said that until and unless we
> > > don't turn an algo to a working code we are never really sure whether
> > > its perfect and covers all the cases.
>
> > > On Dec 1, 4:23 pm, atul anand  wrote:
> > >> yup i made some calculation error
>
> > >> Now this algo works perfectly :) :)
>
> > >> Thanks for your help and explanation :) :)
>
> > >> On Thu, Dec 1, 2011 at 4:26 PM, sourabh  wrote:
> > >> > @atul ...
>
> > >> > Reply 1:
> > >> > Yes, you are correct.. i missed it... Correct statement is as follows:
>
> > >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> > >> > i = 3, j = 4
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > >> > =5 , i = 4, j = 4
>
> > >> > -
>
> > >> > Reply 2:
> > >> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
> > >> > not getting my point  even if 14 is the search element, still the
> > >> > element smaller than equal to 14 in array B is 10 and not 15...
>
> > >> > Hence, the above calculation that you have made are incorrect.
>
> > >> > If you look at the problem statement it says that we have to find the
> > >> > sum which is smaller than equal to X.
> > >> > Now, if you look ta ur calculations you will see that your 'closest to
> > >> > X' search space contains elements 13 which is invalid as it is greater
> > >> > than 12...
>
> > >> > Hence, i m re-calculating the values based on the above given
> > >> > algorithm...
>
> > >> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> > >> > 8   , i = 1, j = 3
>
> > >> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > >> > =12   , i = 2, j = 4
>
> > >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > >> > 9   , i = 3 , j = 4
>
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to

[algogeeks] Re: Sub-array problem

[sourabh]

@atul...
thanks dude for ur thorough screening of the algo and pointing out the
mistakes... I think that's y its always said that until and unless we
don't turn an algo to a working code we are never really sure whether
its perfect and covers all the cases.

On Dec 1, 4:23 pm, atul anand  wrote:
> yup i made some calculation error
>
> Now this algo works perfectly :) :)
>
> Thanks for your help and explanation :) :)
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 4:26 PM, sourabh  wrote:
> > @atul ...
>
> > Reply 1:
> > Yes, you are correct.. i missed it... Correct statement is as follows:
>
> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> > i = 3, j = 4
> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > =5 , i = 4, j = 4
>
> > -
>
> > Reply 2:
> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
> > not getting my point  even if 14 is the search element, still the
> > element smaller than equal to 14 in array B is 10 and not 15...
>
> > Hence, the above calculation that you have made are incorrect.
>
> > If you look at the problem statement it says that we have to find the
> > sum which is smaller than equal to X.
> > Now, if you look ta ur calculations you will see that your 'closest to
> > X' search space contains elements 13 which is invalid as it is greater
> > than 12...
>
> > Hence, i m re-calculating the values based on the above given
> > algorithm...
>
> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> > 8   , i = 1, j = 3
>
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > =12   , i = 2, j = 4
>
> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > 9   , i = 3 , j = 4
>
> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> > 5 , i = 4 , j = 4
>
> > Also, as calculated in the previous post the corner case gives 10 as
> > the closest to X.
>
> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> > 12.
>
> > On Dec 1, 2:52 pm, atul anand  wrote:
> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13   ,
> > i
> > > = 1, j = 4
> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12   ,
> > i
> > > = 2, j = 4
> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11
> > , i
> > > = 3 , j = 4
> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 ,
> > i
> > > = 4 , j = 4
>
> > >  out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> > > So basically among this we have to find element closest X ( where
> > element <
> > > = X )
> > > hence 12 is the answer.
>
> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand 
> > wrote:
> > > > @sourabh
>
> > > > i guess you need to modify this statement :-
>
> > > > 3) Now for each element B[i][0] , do a (modified) binary *search  for
> > > > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > > > +1... n][0] ,
> > > > Say the found index after binary search is j ( which is > i)...
>
> > > > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,
> >  i
> > > > = 1, j = 3
> > > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
> > i =
> > > > 2, j = 4
> > > > 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> > > > *Cumulative SUM*
>
> > > > *i*
>
> > > > 2
>
> > > > 0
>
> > > > 3
>
> > > >  1
>
> > > > 6
>
> > > >  2
>
> > > > 10
>
> > > >  3
>
> > > > *15*
>
> > > >  4
>
> > > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > > > ..right ??
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

@atul ...

Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:

12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
i = 3, j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
=5 , i = 4, j = 4

-

Reply 2:
I might be wrong in calculating 12 + 2 = 14 but i guess you are
not getting my point  even if 14 is the search element, still the
element smaller than equal to 14 in array B is 10 and not 15...

Hence, the above calculation that you have made are incorrect.

If you look at the problem statement it says that we have to find the
sum which is smaller than equal to X.
Now, if you look ta ur calculations you will see that your 'closest to
X' search space contains elements 13 which is invalid as it is greater
than 12...

Hence, i m re-calculating the values based on the above given
algorithm...

12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
8   , i = 1, j = 3

12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
=12   , i = 2, j = 4

12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
9   , i = 3 , j = 4

12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
5 , i = 4 , j = 4

Also, as calculated in the previous post the corner case gives 10 as
the closest to X.

Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
12.

On Dec 1, 2:52 pm, atul anand  wrote:
> and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13   , i
> = 1, j = 4
> 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12   , i
> = 2, j = 4
> 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11   , i
> = 3 , j = 4
> 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 , i
> = 4 , j = 4
>
>  out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> So basically among this we have to find element closest X ( where element <
> = X )
> hence 12 is the answer.
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 3:11 PM, atul anand  wrote:
> > @sourabh
>
> > i guess you need to modify this statement :-
>
> > 3) Now for each element B[i][0] , do a (modified) binary *search  for
> > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > +1... n][0] ,
> > Say the found index after binary search is j ( which is > i)...
>
> > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,  i
> > = 1, j = 3
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i =
> > 2, j = 4
> > 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> > *Cumulative SUM*
>
> > *i*
>
> > 2
>
> > 0
>
> > 3
>
> >  1
>
> > 6
>
> >  2
>
> > 10
>
> >  3
>
> > *15*
>
> >  4
>
> > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > ..right ??

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

@atul.. thanks for pointing out.. i m doing a small mistake in
calculating closest element found... and i have rectified it below...
Also i have missed a corner case in the above solution hence i m
putting it down here...

3a) Corner case: Do modified binary search for closest element smaller
than equal to X in the array B[][0]  If the index of the search
returned is 'j' then
   closest to X = B[j][0]
   subarray = A[ 0 ... B[j][1] ]

3) Now for each element B[i][0] , do a (modified) binary search  for
the closest value smaller than equal to (X + B[i][0]) in array B[i
+1... n][0] ,
Say the found index after binary search is j ( which is > i)...

4) If B[i][1] < B[j][1] ( if not, then go to step 3), then keep track
of the max no. closest to X ( that is B[j][0] - B[i][0] )...

/*
In case you want to return the indices of the subarray for the max
closest element to X ,
then have two variable maxi and maxj such that
maxi = B[i][1]+1
maxj = B[j][1]

whenever you get a new max. no closest to X in step 4.
*/
--

Your example:
let X=12;

Corner case:
closest to X = 10 ...  i=0, j = 3

Other cases:
12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 =
8 i = 1, j = 3
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =
12  i = 2, j = 4
12 + 6 = 18 , closest element found = no element found
12 + 10 = 22 , closest element found = no element found

Hence the max closest to X is 12...and the sub array is  A [ 2 .. 4 ]

On Dec 1, 10:21 am, atul anand  wrote:
>  @sourabh :
>
> *Cumulative SUM*
>
> *i*
>
> 2
>
> 0
>
> 3
>
>  1
>
> 6
>
>  2
>
> 10
>
>  3
>
> 15
>
>  4
>
> above will the array B[][] formed for array A[]={ 2,1,3,4,5 }
>
> let X=12;
> 12 - 2 = 10 , closest element found = 10 , *closest to X = 2 + 10 =12*
>  ,*i = 0 , j = 3
> *   // this is the answer , so i am calculating other
>
> max number found closest to X=12 is 12
>
> to return sub-array for this max sum
>
> *i = 0 and j=3
>
> *hence from given A[]={ 2,1,3,4,5 } we will get sub-array = {2,1,3,4} ( sum
> = 2 + 1 + 3 + 4 = 10 )
>
> sub-array should be from i = 2 to  j = 4 which is {3,4,5} (sum = 3 + 4 + 5
> = 12)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

I am rewriting the algo here in much more readable form :

Given array of integers A,

1) Create an 2-d array B[n][2] of size n*2 such that
a) B[i][0] = sum of all elements from A[0] to A[i],
b) B[i][1] = i

2) Sort array B based on B[i][0] i.e. sort array B[][0] and
correspondingly rearrange elements of array B[][1] 

3) Now for each element B[i][0] ( till its <= X / 2 ), do a (modified)
binary search  for the closest value smaller than equal to
(X - B[i][0]) in array B[i+1... n][0] ,
Say the found index after binary search is j ( which is > i)

4) If B[i][1] < B[j][1] ( if not, then go to step 3), then keep track
of the max no. closest to X ( that is B[i][0] + B[j][0])...

// In case you want to return the indices of the subarray for he max
closest element to X , the have to variable maxi and maxj holding
value B[i][1] and B[j][1] respectively whenever you get a new max. no
closest to X in step 4.

Complexity = N (to create array B) + N log N (to sort) + N log N ( to
solve the problem) = O(n log n)

On Nov 30, 11:21 pm, sourabh  wrote:
> First i would like to rectify a editing mistake that is as foolws :
> Say the found index after binary search is j ( which is > i)..
> Now if B[i][1] < B[j][1] then keep track of the max no. closest to X
> ( that is B[i][0] + B[j][0])... // earlier the last text was B[i][1] +
> B[j][1]
>
> Now to clarify your doubts...
>
> 3) Why are u assuming that the array contains positive integers. It
> can as well contain non-positive integers.. hence, array B won't be
> inherently sorted...
>
> 4) As mentioned above, closest element found is B[j][0] which smaller
> than equal to X - B[i][0] 
>    And the closest max value to X is B[i][0] + B[j][0]
>
>    Keeping the above 2 points in mind i m re-tracing your example :
>
> let X=12;
> 12 - 2 = 10 , closest element found = 10 , closest to X = 2 + 10 =12
> 12 - 3 = 9  closest element found = 6 , closest to X = 3 + 6 = 9
> 12 - 6 = 6  closest element found = no element found , closest to X =
> 6 + 0 =6
> 12 - 10 = 2  no need to execute this step as 10 > 12 / 2 , because
> 12-10 = 2 which is smaller than 12 and won't lie on the right half...
>
> Hence the max closest to X is 12...and the sub array is  A [ B[i]
> [1] ... B[j][1] ]
>
> On Nov 30, 9:39 pm, atul anand  wrote:
>
>
>
>
>
>
>
> > @sourabh : please let me know where i am making mistake in understanding
> > your algo:-
>
> > considering your 1st algo:-
>
> > 1) Given array of integers A[n], = {2,1,3,4,5}
>
> > 2) create an array B[n] such that B[i] = sum of all elements from A[1]
> > to A[i], //  i guess it should be A[0] to A[i]
>
> > Array B formed :-
>
> > B[]={2,3,6,10,15}
>
> > 3) Now sort array B,
>
> > why you need to sort array B ???, it contain only +ve elements and what you
> > are doing is just the cumulative addition so it will always be sorted.
>
> > 4) for each element B[i] ( smaller that equal to
> > X), do a (modified) binary search  for the closest value smaller than
> > equal to (X - B[i]) in array B[i+1... n]
>
> > let X=12;
>
> > 12 - 2 = 10  closest element found = 10
> > 12 - 3 = 9  closest element found = 10
> > 12 - 6 = 6  closest element found = 10
> > 12 - 10 = 2  closest element found = 15
>
> > Answer should be Ans->12, sub-array={3,4,5}
>
> > where i am getting it wrong ???
>
> > On Wed, Nov 30, 2011 at 4:01 PM, sourabh  wrote:
> > > Given array of integers A,  create an 2-d array B of size n*2 such
> > > that  B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
> > > sort array B based on B[i][0]..
> > > Now for each element B[i][0] ( till its smaller that equal to X), do a
> > > (modified) binary search  for the closest value smaller than equal to
> > > (X - B[i][0]) in array B[i+1... n][0] ,
> > > Say the found index after binary search is j ( which is > i).. Now if
> > > B[i][1] < B[j][1] then keep track of the max no. closest to X ( that
> > > is B[i][1] + B[j][1])... Complexity = N (to create array B) + N log N
> > > (to sort) + N log N ( to solve the problem) = O(n log n)
> > > On Nov 29, 7:13 pm, Mohit kumar lal  wrote:
> > > > here it is similar type of question i found on spoj ,it asks only for 
> > > > the
> > > > sum
>
> > > >http://www.spoj.pl/problems/HOTELS/
>
> > > > but it is giving TLE in O(n^2)..
>
> > > > On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg  > > >wrote:
>
> > > > > cant think of anything better than O(N^2). Are you sure there exists
> > > such
> > > > &

[algogeeks] Re: Sub-array problem

[sourabh]

First i would like to rectify a editing mistake that is as foolws :
Say the found index after binary search is j ( which is > i)..
Now if B[i][1] < B[j][1] then keep track of the max no. closest to X
( that is B[i][0] + B[j][0])... // earlier the last text was B[i][1] +
B[j][1]

Now to clarify your doubts...

3) Why are u assuming that the array contains positive integers. It
can as well contain non-positive integers.. hence, array B won't be
inherently sorted...

4) As mentioned above, closest element found is B[j][0] which smaller
than equal to X - B[i][0] 
   And the closest max value to X is B[i][0] + B[j][0]

   Keeping the above 2 points in mind i m re-tracing your example :

let X=12;
12 - 2 = 10 , closest element found = 10 , closest to X = 2 + 10 =12
12 - 3 = 9  closest element found = 6 , closest to X = 3 + 6 = 9
12 - 6 = 6  closest element found = no element found , closest to X =
6 + 0 =6
12 - 10 = 2  no need to execute this step as 10 > 12 / 2 , because
12-10 = 2 which is smaller than 12 and won't lie on the right half...

Hence the max closest to X is 12...and the sub array is  A [ B[i]
[1] ... B[j][1] ]



On Nov 30, 9:39 pm, atul anand  wrote:
> @sourabh : please let me know where i am making mistake in understanding
> your algo:-
>
> considering your 1st algo:-
>
> 1) Given array of integers A[n], = {2,1,3,4,5}
>
> 2) create an array B[n] such that B[i] = sum of all elements from A[1]
> to A[i], //  i guess it should be A[0] to A[i]
>
> Array B formed :-
>
> B[]={2,3,6,10,15}
>
> 3) Now sort array B,
>
> why you need to sort array B ???, it contain only +ve elements and what you
> are doing is just the cumulative addition so it will always be sorted.
>
> 4) for each element B[i] ( smaller that equal to
> X), do a (modified) binary search  for the closest value smaller than
> equal to (X - B[i]) in array B[i+1... n]
>
> let X=12;
>
> 12 - 2 = 10  closest element found = 10
> 12 - 3 = 9  closest element found = 10
> 12 - 6 = 6  closest element found = 10
> 12 - 10 = 2  closest element found = 15
>
> Answer should be Ans->12, sub-array={3,4,5}
>
> where i am getting it wrong ???
>
>
>
>
>
>
>
> On Wed, Nov 30, 2011 at 4:01 PM, sourabh  wrote:
> > Given array of integers A,  create an 2-d array B of size n*2 such
> > that  B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
> > sort array B based on B[i][0]..
> > Now for each element B[i][0] ( till its smaller that equal to X), do a
> > (modified) binary search  for the closest value smaller than equal to
> > (X - B[i][0]) in array B[i+1... n][0] ,
> > Say the found index after binary search is j ( which is > i).. Now if
> > B[i][1] < B[j][1] then keep track of the max no. closest to X ( that
> > is B[i][1] + B[j][1])... Complexity = N (to create array B) + N log N
> > (to sort) + N log N ( to solve the problem) = O(n log n)
> > On Nov 29, 7:13 pm, Mohit kumar lal  wrote:
> > > here it is similar type of question i found on spoj ,it asks only for the
> > > sum
>
> > >http://www.spoj.pl/problems/HOTELS/
>
> > > but it is giving TLE in O(n^2)..
>
> > > On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg  > >wrote:
>
> > > > cant think of anything better than O(N^2). Are you sure there exists
> > such
> > > > algo?
>
> > > > On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal <
> > kumarmohit...@gmail.com>wrote:
>
> > > >> Given a array of positive integers ,You have to find the largest sum
> > > >> possible from consecutive sub-array but sum should be less than or
> > equal to
> > > >> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> > > >>  ans->12, sub-array={3,4,5}
>
> > > >> Firstly i tried with brute-force and then i also tried to solve it by
> > DP
> > > >> but complexity were same ( O(n^2)) so plz try to provide a
> > solution for
> > > >> O(nlgn) or O(n).
>
> > > >> --
> > > >> Mohit kumar lal
>
> > > >> IIIT ALLAHABAD
>
> > > >> --
> > > >> You received this message because you are subscribed to the Google
> > Groups
> > > >> "Algorithm Geeks" group.
> > > >> To post to this group, send email to algogeeks@googlegroups.com.
> > > >> To unsubscribe from this group, send email to
> > > >> algogeeks+unsubscr...@googlegroups.com.
> > > >> For more options, visit this group at
> > > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > > --

[algogeeks] Re: Sub-array problem

[sourabh]

Given array of integers A,  create an 2-d array B of size n*2 such
that  B[i][0] = sum of all elements from A[0] to A[i], B[i][1] = i;Now
sort array B based on B[i][0]..
Now for each element B[i][0] ( till its smaller that equal to X), do a
(modified) binary search  for the closest value smaller than equal to
(X - B[i][0]) in array B[i+1... n][0] ,
Say the found index after binary search is j ( which is > i).. Now if
B[i][1] < B[j][1] then keep track of the max no. closest to X ( that
is B[i][1] + B[j][1])... Complexity = N (to create array B) + N log N
(to sort) + N log N ( to solve the problem) = O(n log n)
On Nov 29, 7:13 pm, Mohit kumar lal  wrote:
> here it is similar type of question i found on spoj ,it asks only for the
> sum
>
> http://www.spoj.pl/problems/HOTELS/
>
> but it is giving TLE in O(n^2)..
>
> On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg wrote:
>
>
>
>
>
>
>
>
>
> > cant think of anything better than O(N^2). Are you sure there exists such
> > algo?
>
> > On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal 
> > wrote:
>
> >> Given a array of positive integers ,You have to find the largest sum
> >> possible from consecutive sub-array but sum should be less than or equal to
> >> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> >>  ans->12, sub-array={3,4,5}
>
> >> Firstly i tried with brute-force and then i also tried to solve it by DP
> >> but complexity were same ( O(n^2)) so plz try to provide a solution for
> >> O(nlgn) or O(n).
>
> >> --
> >> Mohit kumar lal
>
> >> IIIT ALLAHABAD
>
> >> --
> >> 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.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Mohit kumar lal
> rit2009014
> IIIT ALLAHABAD
> contact@9454681805
> kumarmohit...@gmail.com
> mohitkumar...@yahoo.com
> rit2009...@iiita.ac.inhttp://profile.iiita.ac.in/rit2009014

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Sub-array problem

[sourabh]

Given array of integers A[n],
 create an array B[n] such that B[i] = sum of all elements from A[1]
to A[i],

Now sort array B, and for each element B[i] ( smaller that equal to
X), do a (modified) binary search  for the closest value smaller than
equal to (X - B[i]) in array B[i+1... n]

Keep track of the closest difference...

Complexity ( n log n + n log n) = O(n log n)

On Nov 29, 7:13 pm, Mohit kumar lal  wrote:
> here it is similar type of question i found on spoj ,it asks only for the
> sum
>
> http://www.spoj.pl/problems/HOTELS/
>
> but it is giving TLE in O(n^2)..
>
> On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg wrote:
>
>
>
>
>
>
>
>
>
> > cant think of anything better than O(N^2). Are you sure there exists such
> > algo?
>
> > On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal 
> > wrote:
>
> >> Given a array of positive integers ,You have to find the largest sum
> >> possible from consecutive sub-array but sum should be less than or equal to
> >> K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
> >>  ans->12, sub-array={3,4,5}
>
> >> Firstly i tried with brute-force and then i also tried to solve it by DP
> >> but complexity were same ( O(n^2)) so plz try to provide a solution for
> >> O(nlgn) or O(n).
>
> >> --
> >> Mohit kumar lal
>
> >> IIIT ALLAHABAD
>
> >> --
> >> 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.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Mohit kumar lal
> rit2009014
> IIIT ALLAHABAD
> contact@9454681805
> kumarmohit...@gmail.com
> mohitkumar...@yahoo.com
> rit2009...@iiita.ac.inhttp://profile.iiita.ac.in/rit2009014

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg  wrote:
> I don't think it is O(N*K)
> It is O(N^2)
> Just to confirm if i have understood correctly
>
> Lets say n and k are given and are global to all subproblems
> Subproblem Definition
> F[i,j] -> maximum expected sum that we can get by partitioning array from 0
> to i into j subarrays. Each subarray satisfies the size bound
> [ceiling(n/2k),floor(3n/2k)]
>
> F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
> subarray from i-r+1 to i}
>
> So to calculate every subsequent subproblem we need to check solutions to
> O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu  wrote:
> > Hi
>
> > I may not have understood your solution properly. But i think that
> > your solution is an implementation of brute force where you are
> > dealing with all cases valid in the range n/2k and 3n/2k without any
> > optimization with regard to DP. Am i right?
>
> > On Nov 28, 2:17 am, sourabh  wrote:
> > > Consider the example that you have given:
> > > [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> > > Now we need to partition the array into 3 contiguous sub arrays such
> > > that :
> > > a) The expected sum value is maximum
> > > b) and the size of each sub array should be between 2 and 6, both
> > > inclusive. In case, this constraint is not satisfied then its not a
> > > valid candidate for the solution even if the partition produces the
> > > max value.
>
> > >       2 = ceil (n / 2k) = ceil (12/6)
> > >       6 = floor (3n / 2k) = floor (36/6)
> > > -
> > >  As mentioned above the following equation :
> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > > k-1) }
>
> > > /**
> > > For understanding how partitioning of the array is represented by the
> > > above equation:
>
> > > Say there is an array denoted by A[i] and it needs to be divided into
> > > 3 contiguous parts, one of the ways to do so would be to take the
> > > following steps :
>
> > > Let K(partition no.) be initialized to 3.
> > > Let array size N be 12.
>
> > > a) If N is 0, the goto step 'f'
> > > b) If K == 1 then call it as partition K and goto step 'e'.
> > > c) Lets take X no. of elements from the end of array A of size N and
> > > call it partition K.
> > > d) Decrement K by 1 and N by X { --K; and N-=X;}
> > > d) Goto step 'a'
> > > e) Valid partition and End.
> > > f) Not a valid partition and End.
>
> > > Now if the above set of steps is run for all values of X such that
> > > 2<=X<=6 , then it will generate all possible candidates (partitions)
> > > as per the given problem statement. And for all the valid
> > > partitions(the ones that will hit step 'e') we need to calculate the
> > > expected sum value.
> > > **/
>
> > > can be translated into,
> > > // I am using 1-based array indexing for better clarity
> > > // A[x .. y] means all elements from A[y] to A[x]..
>
> > > F(12, 3) = MAX
> > >                        {
> > >                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
> > >                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
> > >                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
> > > this will yield the maximum sum..
> > >                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
> > >                           ExpVal (A[12 .. 7])    +  F(6, 2)
> > >                        }
>
> > > which is nothing but,
> > > F(12, 3) = MAX
> > >                        {
> > >                           1/2  +  F(10, 2) ,
> > >                           2/3  +  F(9, 2) ,
> > >                           2/4  +  F(8, 2) , // this will yield the
> > > maximum sum..
> > >                           3/5  +  F(7, 2) ,
> > >                           4/6  +  F(6, 2)
> > >                        }
>
> > > Trace the above equation and

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg  wrote:
> I don't think it is O(N*K)
> It is O(N^2)
> Just to confirm if i have understood correctly
>
> Lets say n and k are given and are global to all subproblems
> Subproblem Definition
> F[i,j] -> maximum expected sum that we can get by partitioning array from 0
> to i into j subarrays. Each subarray satisfies the size bound
> [ceiling(n/2k),floor(3n/2k)]
>
> F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
> subarray from i-r+1 to i}
>
> So to calculate every subsequent subproblem we need to check solutions to
> O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu  wrote:
> > Hi
>
> > I may not have understood your solution properly. But i think that
> > your solution is an implementation of brute force where you are
> > dealing with all cases valid in the range n/2k and 3n/2k without any
> > optimization with regard to DP. Am i right?
>
> > On Nov 28, 2:17 am, sourabh  wrote:
> > > Consider the example that you have given:
> > > [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> > > Now we need to partition the array into 3 contiguous sub arrays such
> > > that :
> > > a) The expected sum value is maximum
> > > b) and the size of each sub array should be between 2 and 6, both
> > > inclusive. In case, this constraint is not satisfied then its not a
> > > valid candidate for the solution even if the partition produces the
> > > max value.
>
> > >       2 = ceil (n / 2k) = ceil (12/6)
> > >       6 = floor (3n / 2k) = floor (36/6)
> > > -
> > >  As mentioned above the following equation :
> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > > k-1) }
>
> > > /**
> > > For understanding how partitioning of the array is represented by the
> > > above equation:
>
> > > Say there is an array denoted by A[i] and it needs to be divided into
> > > 3 contiguous parts, one of the ways to do so would be to take the
> > > following steps :
>
> > > Let K(partition no.) be initialized to 3.
> > > Let array size N be 12.
>
> > > a) If N is 0, the goto step 'f'
> > > b) If K == 1 then call it as partition K and goto step 'e'.
> > > c) Lets take X no. of elements from the end of array A of size N and
> > > call it partition K.
> > > d) Decrement K by 1 and N by X { --K; and N-=X;}
> > > d) Goto step 'a'
> > > e) Valid partition and End.
> > > f) Not a valid partition and End.
>
> > > Now if the above set of steps is run for all values of X such that
> > > 2<=X<=6 , then it will generate all possible candidates (partitions)
> > > as per the given problem statement. And for all the valid
> > > partitions(the ones that will hit step 'e') we need to calculate the
> > > expected sum value.
> > > **/
>
> > > can be translated into,
> > > // I am using 1-based array indexing for better clarity
> > > // A[x .. y] means all elements from A[y] to A[x]..
>
> > > F(12, 3) = MAX
> > >                        {
> > >                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
> > >                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
> > >                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
> > > this will yield the maximum sum..
> > >                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
> > >                           ExpVal (A[12 .. 7])    +  F(6, 2)
> > >                        }
>
> > > which is nothing but,
> > > F(12, 3) = MAX
> > >                        {
> > >                           1/2  +  F(10, 2) ,
> > >                           2/3  +  F(9, 2) ,
> > >                           2/4  +  F(8, 2) , // this will yield the
> > > maximum sum..
> > >                           3/5  +  F(7, 2) ,
> > >                           4/6  +  F(6, 2)
> > >                        }
>
> > > Trace the above equation and

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg  wrote:
> I don't think it is O(N*K)
> It is O(N^2)
> Just to confirm if i have understood correctly
>
> Lets say n and k are given and are global to all subproblems
> Subproblem Definition
> F[i,j] -> maximum expected sum that we can get by partitioning array from 0
> to i into j subarrays. Each subarray satisfies the size bound
> [ceiling(n/2k),floor(3n/2k)]
>
> F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
> subarray from i-r+1 to i}
>
> So to calculate every subsequent subproblem we need to check solutions to
> O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu  wrote:
> > Hi
>
> > I may not have understood your solution properly. But i think that
> > your solution is an implementation of brute force where you are
> > dealing with all cases valid in the range n/2k and 3n/2k without any
> > optimization with regard to DP. Am i right?
>
> > On Nov 28, 2:17 am, sourabh  wrote:
> > > Consider the example that you have given:
> > > [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> > > Now we need to partition the array into 3 contiguous sub arrays such
> > > that :
> > > a) The expected sum value is maximum
> > > b) and the size of each sub array should be between 2 and 6, both
> > > inclusive. In case, this constraint is not satisfied then its not a
> > > valid candidate for the solution even if the partition produces the
> > > max value.
>
> > >       2 = ceil (n / 2k) = ceil (12/6)
> > >       6 = floor (3n / 2k) = floor (36/6)
> > > -
> > >  As mentioned above the following equation :
> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > > k-1) }
>
> > > /**
> > > For understanding how partitioning of the array is represented by the
> > > above equation:
>
> > > Say there is an array denoted by A[i] and it needs to be divided into
> > > 3 contiguous parts, one of the ways to do so would be to take the
> > > following steps :
>
> > > Let K(partition no.) be initialized to 3.
> > > Let array size N be 12.
>
> > > a) If N is 0, the goto step 'f'
> > > b) If K == 1 then call it as partition K and goto step 'e'.
> > > c) Lets take X no. of elements from the end of array A of size N and
> > > call it partition K.
> > > d) Decrement K by 1 and N by X { --K; and N-=X;}
> > > d) Goto step 'a'
> > > e) Valid partition and End.
> > > f) Not a valid partition and End.
>
> > > Now if the above set of steps is run for all values of X such that
> > > 2<=X<=6 , then it will generate all possible candidates (partitions)
> > > as per the given problem statement. And for all the valid
> > > partitions(the ones that will hit step 'e') we need to calculate the
> > > expected sum value.
> > > **/
>
> > > can be translated into,
> > > // I am using 1-based array indexing for better clarity
> > > // A[x .. y] means all elements from A[y] to A[x]..
>
> > > F(12, 3) = MAX
> > >                        {
> > >                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
> > >                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
> > >                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
> > > this will yield the maximum sum..
> > >                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
> > >                           ExpVal (A[12 .. 7])    +  F(6, 2)
> > >                        }
>
> > > which is nothing but,
> > > F(12, 3) = MAX
> > >                        {
> > >                           1/2  +  F(10, 2) ,
> > >                           2/3  +  F(9, 2) ,
> > >                           2/4  +  F(8, 2) , // this will yield the
> > > maximum sum..
> > >                           3/5  +  F(7, 2) ,
> > >                           4/6  +  F(6, 2)
> > >                        }
>
> > > Trace the above equation and

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Yes nithin its O(n^2)..

The reasoning being say,
We store all the values in a 2-d array of size N * K.

Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...

On Nov 28, 6:42 pm, Nitin Garg  wrote:
> I don't think it is O(N*K)
> It is O(N^2)
> Just to confirm if i have understood correctly
>
> Lets say n and k are given and are global to all subproblems
> Subproblem Definition
> F[i,j] -> maximum expected sum that we can get by partitioning array from 0
> to i into j subarrays. Each subarray satisfies the size bound
> [ceiling(n/2k),floor(3n/2k)]
>
> F[i,j] = max over all r in our size bound {F[i-r,j-1] + expected sum of
> subarray from i-r+1 to i}
>
> So to calculate every subsequent subproblem we need to check solutions to
> O(N/k) previous subproblems. And there are N subproblems,  O((1/k)*N^2)
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 6:46 PM, Dumanshu  wrote:
> > Hi
>
> > I may not have understood your solution properly. But i think that
> > your solution is an implementation of brute force where you are
> > dealing with all cases valid in the range n/2k and 3n/2k without any
> > optimization with regard to DP. Am i right?
>
> > On Nov 28, 2:17 am, sourabh  wrote:
> > > Consider the example that you have given:
> > > [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> > > Now we need to partition the array into 3 contiguous sub arrays such
> > > that :
> > > a) The expected sum value is maximum
> > > b) and the size of each sub array should be between 2 and 6, both
> > > inclusive. In case, this constraint is not satisfied then its not a
> > > valid candidate for the solution even if the partition produces the
> > > max value.
>
> > >       2 = ceil (n / 2k) = ceil (12/6)
> > >       6 = floor (3n / 2k) = floor (36/6)
> > > -
> > >  As mentioned above the following equation :
> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > > k-1) }
>
> > > /**
> > > For understanding how partitioning of the array is represented by the
> > > above equation:
>
> > > Say there is an array denoted by A[i] and it needs to be divided into
> > > 3 contiguous parts, one of the ways to do so would be to take the
> > > following steps :
>
> > > Let K(partition no.) be initialized to 3.
> > > Let array size N be 12.
>
> > > a) If N is 0, the goto step 'f'
> > > b) If K == 1 then call it as partition K and goto step 'e'.
> > > c) Lets take X no. of elements from the end of array A of size N and
> > > call it partition K.
> > > d) Decrement K by 1 and N by X { --K; and N-=X;}
> > > d) Goto step 'a'
> > > e) Valid partition and End.
> > > f) Not a valid partition and End.
>
> > > Now if the above set of steps is run for all values of X such that
> > > 2<=X<=6 , then it will generate all possible candidates (partitions)
> > > as per the given problem statement. And for all the valid
> > > partitions(the ones that will hit step 'e') we need to calculate the
> > > expected sum value.
> > > **/
>
> > > can be translated into,
> > > // I am using 1-based array indexing for better clarity
> > > // A[x .. y] means all elements from A[y] to A[x]..
>
> > > F(12, 3) = MAX
> > >                        {
> > >                           ExpVal (A[12 .. 11])  +  F(10, 2) ,
> > >                           ExpVal (A[12 .. 10])  +  F(9, 2) ,
> > >                           ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
> > > this will yield the maximum sum..
> > >                           ExpVal (A[12 .. 8])    +  F(7, 2) ,
> > >                           ExpVal (A[12 .. 7])    +  F(6, 2)
> > >                        }
>
> > > which is nothing but,
> > > F(12, 3) = MAX
> > >                        {
> > >                           1/2  +  F(10, 2) ,
> > >                           2/3  +  F(9, 2) ,
> > >                           2/4  +  F(8, 2) , // this will yield the
> > > maximum sum..
> > >                           3/5  +  F(7, 2) ,
> > >                           4/6  +  F(6, 2)
> > >                        }
>
> > > Trace the above equation and

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

O(N*K)

On Nov 28, 1:04 pm, Nitin Garg  wrote:
> @Sourabh - whats the running time?
>
>
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg  wrote:
> > Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
>
> > Nice thinking man and thanks :)
>
> > On Mon, Nov 28, 2011 at 2:47 AM, sourabh  wrote:
>
> >> Consider the example that you have given:
> >> [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> >> Now we need to partition the array into 3 contiguous sub arrays such
> >> that :
> >> a) The expected sum value is maximum
> >> b) and the size of each sub array should be between 2 and 6, both
> >> inclusive. In case, this constraint is not satisfied then its not a
> >> valid candidate for the solution even if the partition produces the
> >> max value.
>
> >>      2 = ceil (n / 2k) = ceil (12/6)
> >>      6 = floor (3n / 2k) = floor (36/6)
> >> -
> >>  As mentioned above the following equation :
> >> F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> >> { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> >> k-1) }
>
> >> /**
> >> For understanding how partitioning of the array is represented by the
> >> above equation:
>
> >> Say there is an array denoted by A[i] and it needs to be divided into
> >> 3 contiguous parts, one of the ways to do so would be to take the
> >> following steps :
>
> >> Let K(partition no.) be initialized to 3.
> >> Let array size N be 12.
>
> >> a) If N is 0, the goto step 'f'
> >> b) If K == 1 then call it as partition K and goto step 'e'.
> >> c) Lets take X no. of elements from the end of array A of size N and
> >> call it partition K.
> >> d) Decrement K by 1 and N by X { --K; and N-=X;}
> >> d) Goto step 'a'
> >> e) Valid partition and End.
> >> f) Not a valid partition and End.
>
> >> Now if the above set of steps is run for all values of X such that
> >> 2<=X<=6 , then it will generate all possible candidates (partitions)
> >> as per the given problem statement. And for all the valid
> >> partitions(the ones that will hit step 'e') we need to calculate the
> >> expected sum value.
> >> **/
>
> >> can be translated into,
> >> // I am using 1-based array indexing for better clarity
> >> // A[x .. y] means all elements from A[y] to A[x]..
>
> >> F(12, 3) = MAX
> >>                       {
> >>                          ExpVal (A[12 .. 11])  +  F(10, 2) ,
> >>                          ExpVal (A[12 .. 10])  +  F(9, 2) ,
> >>                          ExpVal (A[12 .. 9])    +  F(8, 2) ,   //
> >> this will yield the maximum sum..
> >>                          ExpVal (A[12 .. 8])    +  F(7, 2) ,
> >>                          ExpVal (A[12 .. 7])    +  F(6, 2)
> >>                       }
>
> >> which is nothing but,
> >> F(12, 3) = MAX
> >>                       {
> >>                          1/2  +  F(10, 2) ,
> >>                          2/3  +  F(9, 2) ,
> >>                          2/4  +  F(8, 2) , // this will yield the
> >> maximum sum..
> >>                          3/5  +  F(7, 2) ,
> >>                          4/6  +  F(6, 2)
> >>                       }
>
> >> Trace the above equation and you should get it..
>
> >> On Nov 28, 12:57 am, Ankur Garg  wrote:
> >> > Hey Sourabh
>
> >> > Could you please explain the solution in a bit detail perhaps using an
> >> > example or so..It wud be really helpful ..Just logic not code
>
> >> > On Mon, Nov 28, 2011 at 1:03 AM, sourabh 
> >> wrote:
> >> > > Looks like a dynamic programming problem
>
> >> > > Say F(n,k) denotes the maximum expected sum value for an array of n
> >> > > elements and partition k , then
>
> >> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> >> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> >> > > k-1) }
>
> >> > > Base condition:
> >> > > 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) <= N
> >> > > <=  floor(3n/2k)
> >> > > 2) If any of the sub problems where the array size is not between
> &

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3

Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.

  2 = ceil (n / 2k) = ceil (12/6)
  6 = floor (3n / 2k) = floor (36/6)
-
 As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }

/**
For understanding how partitioning of the array is represented by the
above equation:

Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :

Let K(partition no.) be initialized to 3.
Let array size N be 12.

a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.

Now if the above set of steps is run for all values of X such that
2<=X<=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/

can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..

F(12, 3) = MAX
   {
  ExpVal (A[12 .. 11])  +  F(10, 2) ,
  ExpVal (A[12 .. 10])  +  F(9, 2) ,
  ExpVal (A[12 .. 9])+  F(8, 2) ,   //
this will yield the maximum sum..
  ExpVal (A[12 .. 8])+  F(7, 2) ,
  ExpVal (A[12 .. 7])+  F(6, 2)
   }

which is nothing but,
F(12, 3) = MAX
   {
  1/2  +  F(10, 2) ,
  2/3  +  F(9, 2) ,
  2/4  +  F(8, 2) , // this will yield the
maximum sum..
  3/5  +  F(7, 2) ,
  4/6  +  F(6, 2)
   }

Trace the above equation and you should get it..

On Nov 28, 12:57 am, Ankur Garg  wrote:
> Hey Sourabh
>
> Could you please explain the solution in a bit detail perhaps using an
> example or so..It wud be really helpful ..Just logic not code
>
>
>
>
>
>
>
> On Mon, Nov 28, 2011 at 1:03 AM, sourabh  wrote:
> > Looks like a dynamic programming problem
>
> > Say F(n,k) denotes the maximum expected sum value for an array of n
> > elements and partition k , then
>
> > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > k-1) }
>
> > Base condition:
> > 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) <= N
> > <=  floor(3n/2k)
> > 2) If any of the sub problems where the array size is not between
> > ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
> > candidate for the final solution. This is can be handled by giving
> > initial value to all such combination a value of -1.
>
> > To store that the intermediate computations take an array Max[N][K],
> > F(N,K) = Max[N][K]
>
> > On Nov 28, 12:17 am, sourabh  wrote:
> > > Because in the previous example k = 3.
>
> > > On Nov 27, 10:46 pm, Piyush Grover  wrote:
>
> > > > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> > > > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> > > > why this is not the optimal split???
>
> > > > On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg 
> > wrote:
> > > > > You have an array with *n* elements. The elements are either 0 or 1.
> > You
> > > > > want to *split the array into kcontiguous subarrays*. The size of
> > each
> > > > > subarray can vary between ceil(n/2k) and floor(3n/2k). You can
> > assume that
> > > > > k << n. After you split the array into k subarrays. One element of
> > each
> > > > > subarray will be randomly selected.
>
> > > > > Devise an algorithm for maximizing the sum of the randomly selected
> > > > > elements from the k subarrays. Basically means that we will want to
>

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Looks like a dynamic programming problem

Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then

F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }

Base condition:
1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) <= N
<=  floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.

To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]


On Nov 28, 12:17 am, sourabh  wrote:
> Because in the previous example k = 3.
>
> On Nov 27, 10:46 pm, Piyush Grover  wrote:
>
>
>
>
>
>
>
> > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> > why this is not the optimal split???
>
> > On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg  wrote:
> > > You have an array with *n* elements. The elements are either 0 or 1. You
> > > want to *split the array into kcontiguous subarrays*. The size of each
> > > subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
> > > k << n. After you split the array into k subarrays. One element of each
> > > subarray will be randomly selected.
>
> > > Devise an algorithm for maximizing the sum of the randomly selected
> > > elements from the k subarrays. Basically means that we will want to split
> > > the array in such way such that the sum of all the expected values for the
> > > elements selected from each subarray is maximum.
>
> > > You can assume that n is a power of 2.
>
> > > Example:
>
> > > Array: [0,0,1,1,0,0,1,1,0,1,1,0]
> > > n = 12
> > > k = 3
> > > Size of subarrays can be: 2,3,4,5,6
>
> > > Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
> > > Expected Value of the sum of the elements randomly selected from the 
> > > subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
>
> > > Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
> > > Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
>
> > > Source ->  
> > > http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
>
> > >  --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Google Question--Suggest Algo

[sourabh]

Because in the previous example k = 3.

On Nov 27, 10:46 pm, Piyush Grover  wrote:
> Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> why this is not the optimal split???
>
>
>
>
>
>
>
> On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg  wrote:
> > You have an array with *n* elements. The elements are either 0 or 1. You
> > want to *split the array into kcontiguous subarrays*. The size of each
> > subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
> > k << n. After you split the array into k subarrays. One element of each
> > subarray will be randomly selected.
>
> > Devise an algorithm for maximizing the sum of the randomly selected
> > elements from the k subarrays. Basically means that we will want to split
> > the array in such way such that the sum of all the expected values for the
> > elements selected from each subarray is maximum.
>
> > You can assume that n is a power of 2.
>
> > Example:
>
> > Array: [0,0,1,1,0,0,1,1,0,1,1,0]
> > n = 12
> > k = 3
> > Size of subarrays can be: 2,3,4,5,6
>
> > Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
> > Expected Value of the sum of the elements randomly selected from the 
> > subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
>
> > Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
> > Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
>
> > Source ->  
> > http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] COGNIZANT(CTS) HELP

[sourabh jain]

COGNIZANT(CTS) visited any clg?
Share all info.
Criteria, pkg etc
writtern exam patern, que/ans interview.
Thnx in adv.

-- 
Regards
SOURABH KUMAR JAIN
MCA,  NIT RAIPUR
MOB.-+919993878717

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Samsung campus visit

[sourabh jain]

in which clg???

when is coming?

On 2 October 2011 23:39, Anika Jain  wrote:

> package is 6lpa
>
> On Sep 28, 1:14 pm, sukran dhawan  wrote:
> > wats the package ?
> >
> >
> >
> >
> >
> >
> >
> > On Tue, Sep 27, 2011 at 9:08 PM, Nitin  wrote:
> > > C questions there are 12 -13 questions given on internet it will be
> same as
> > > it is given in the paper ,i dnt find a link right now otherwise do test
> ur c
> > > skills thoruoghly all c questions will be from that book
> >
> > > On Tue, Sep 27, 2011 at 7:47 PM, vartika aggarwal <
> > > vartika.aggarwa...@gmail.com> wrote:
> >
> > >> Thanks! :-)
> >
> > >> On Tue, Sep 27, 2011 at 7:45 PM, rahul sharma <
> rahul23111...@gmail.com>wrote:
> >
> > >>> test ur c skill for c..ds simple and os simpleno need to
> prepare
> > >>> if know basics...
> > >>> 25 dieasy.25 problem solving...
> > >>> interviews will b easy to crack...once u done with test u have done
> 90%
> > >>> all d best
> >
> > >>> On Tue, Sep 27, 2011 at 7:24 PM, sourabh jain <
> sourabhjain...@gmail.com>wrote:
> >
> > >>>> 1, writin 50 que.. (20 frm DI, 5 frm Quanta, 25 frm puzzel)
> > >>>> 2. technical written (20 frm c/c++, 5 frm DS, 5 frm OS)
> > >>>> 3. technical interview ( c/c++, DS, OS)
> > >>>> 4. HR interview (normal)
> >
> > >>>> --
> > >>>> Regards
> > >>>> SOURABH KUMAR JAIN
> > >>>> MCA,  NIT RAIPUR
> > >>>> MOB.-+919993878717
> >
> > >>>>  --
> > >>>> 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
> >
> > >> Vartika Aggarwal
> > >> Undergraduate Student
> > >> IT Department
> > >> NSIT, Dwarka
> >
> > >>  --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Regards
SOURABH KUMAR JAIN
MCA,  NIT RAIPUR
MOB.-+919993878717

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] cdoc

[sourabh jain]

cdoc visited anywhere?

tell me details?





Regards
SOURABH KUMAR JAIN
NIT RAIPUR

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Samsung campus visit

[sourabh jain]

1, writin 50 que.. (20 frm DI, 5 frm Quanta, 25 frm puzzel)
2. technical written (20 frm c/c++, 5 frm DS, 5 frm OS)
3. technical interview ( c/c++, DS, OS)
4. HR interview (normal)


-- 
Regards
SOURABH KUMAR JAIN
MCA,  NIT RAIPUR
MOB.-+919993878717

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