Re: [algogeeks] Urgent Need ITIL Service Management Operations Business/Process Analyst in Manhattan, NY for 6+ months

[Shashwat Anand]

Can we please get rid of this spammer ?

On Thu, Sep 10, 2015 at 1:53 AM, Shachindra A C 
wrote:

> ^^ +1
>
> On Wed, Sep 9, 2015 at 12:54 PM, Rahul Vatsa 
> wrote:
>
>> Please block this guy.
>>
>> On Thu, Sep 10, 2015 at 1:08 AM, Shaik Asif 
>> wrote:
>>
>>> Hi Partner,
>>>
>>>
>>>
>>> This is Shaik from Deegit Inc. Please find the below requirement for
>>> your review. If you are comfortable with the requirement please get back to
>>> me ASAP on sh...@deegit.com
>>>
>>>
>>>
>>> *Position: ITIL Service Management Operations Business/Process Analyst*
>>>
>>> Location: Manhattan, NY   10001
>>>
>>> Duration: 6+ Months
>>>
>>>
>>>
>>> ITIL v3 Foundations or higher certification required
>>>
>>> · Experience with BMC Remedy required
>>>
>>> · Experience with ServiceNow beneficial
>>>
>>> · Able to understand and document complex IT processes
>>>
>>> · Experience performing IT assessments and preparing gap
>>> analysis documents and recommendations
>>>
>>> · Experience working as an analyst in support of IT technical
>>> operations (e.g. - service desk, desktop support, server and application
>>> management)
>>>
>>> · Very strong communication: verbal and written required. Able
>>> to facilitate workshops and meetings: drive agendas, document findings and
>>> next steps
>>>
>>>
>>> Best Regards,
>>>
>>> ___
>>>
>>>
>>>
>>> Shaik | Deegit Inc |
>>>
>>> 1900 East Golf Rd., Suite 925 | Schaumburg, IL 60173 |
>>>
>>> Ph: 847.440.2436 ext - 358 | Fax: 847.330.1987
>>>
>>> sh...@deegit.com | www.deegit.com |
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>
>
>
> --
> Regards,
> Shachindra A C
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>

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

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

[atul anand]

Given a array with +ve and -ve integer , find the maximum sum such that you
are not allowed to skip 2 contiguous elements ( i.e you have to select
atleast one of them to move forward).

eg :-

10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3

Output : 10+20+30-10+40-1 = 89

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

Re: [algogeeks] Better data structure/Algorithm to handle the following porblem

[atul anand]

B+ tree is used by database... i guess same can be used here.
On 28 Dec 2014 16:13, kumar raja rajkumar.cs...@gmail.com wrote:

 which is like a table in database, and produces results for user queries.

 Data is: in txt file.

 ID, FIRSTNAME, LASTNAME, AGE, SALARY, TITLE
 1, venkatesh, kumar, 21, 3, reporter
 2, kiran, kannan, 45, 9000, chairman
 3, pradeep, mishra, 35, 15000, manager
 4, suman, raj, 35, 12000, manager

 user query will be like
 select firstName, lastName where age25 orderby salary dsc

 dsc - for descending
 you have to produce appropriate records.

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


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

[algogeeks] Distributed System problem

[atul anand]

It is a system design problem .

Suppose a http request  is sent to server . Now Server maintains cache for
fast retrieval . if link is present int the cache then it just takes a data
from cache and return it to user but if not , then user will fetch that
http address and then store it in its cache and return same to the user .

Problem is that there are many server and many global cache as expected in
distributed system. Now when request is received by a server then how can
we maintain global cache such that server can know which cache to query
instead of querying each global cache as it will be inefficient.

one approach can be.. maintain 26 global cache . Now when request is
received by server it check the web link say , www.*a*bc.com ... here
server will query cache-1 . Similarly cache-2 will take care of links with
starts from b...www.*b*bc.com and so on

above method will avoid duplicity in caches but will not be very efficient
as a cache may have higher query rate than others...


any other approach ??

-- 
You received this message because you are subscribed to the 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] Distributed System problem

[atul anand]

approach i have mentioned have flaws .  so what other approaches we can try
to solve this ?

On Sun, Dec 14, 2014 at 2:23 PM, SOMU somnath.nit...@gmail.com wrote:

 Then the Domain name is altered from abc to bbc .. That indirectly means
 that the nameserver will change.

 So in that case the Cache will point to the New NameServer ..

 Thanks,
 Somnath Singh

 On Sun, Dec 14, 2014 at 2:04 PM, atul anand atul.87fri...@gmail.com
 wrote:

 It is a system design problem .

 Suppose a http request  is sent to server . Now Server maintains cache
 for fast retrieval . if link is present int the cache then it just takes a
 data from cache and return it to user but if not , then user will fetch
 that http address and then store it in its cache and return same to the
 user .

 Problem is that there are many server and many global cache as expected
 in distributed system. Now when request is received by a server then how
 can we maintain global cache such that server can know which cache to query
 instead of querying each global cache as it will be inefficient.

 one approach can be.. maintain 26 global cache . Now when request is
 received by server it check the web link say , www.*a*bc.com ... here
 server will query cache-1 . Similarly cache-2 will take care of links with
 starts from b...www.*b*bc.com and so on

 above method will avoid duplicity in caches but will not be very
 efficient as a cache may have higher query rate than others...


 any other approach ??

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

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


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

Re: [algogeeks] Openings in Adobe India !!!

[Shashwat Anand]

People seems to confuse algogeeks with job board.
No idea, how can we get rid of these spam.

On Tue, Oct 14, 2014 at 2:25 PM, Ashish Mehta mehta.ashis...@gmail.com
wrote:

 There are multiple openings in Adobe India for Developer position. Send me
 your resume ASAP.

 Here is the list of urgent openings.


-

·   31639_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=fYIUCfXMqBAaj0T8JrUMKA

·31497_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=U5lgab7ocxgSbz0CjInfyw

·26279_ Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=hgTkxxHjX-jEcKNXOpxJBw

·30965_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=H7s2s7lpI3YK*RhWvOrU*Q

·31344_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=z6oIOM05vEdN6aZ76w1NXg

·30759_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=iYfB3oGLK*cP-GdYbRYqRA

·32543_Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=DQ-WKuGH8byLQ9Z5p8vWWQ

·27526_Security Czar
https://workspaces.acrobat.com/?d=2lXPky*D8qGxQbm9KDHdIw

·30262_Member of Technical Staff / Computer Scientist - MAC
Developer https://workspaces.acrobat.com/?d=8MDJ3-8PpjXLwSN8sZe2lQ

·30976 Member of Technical Staff / Computer Scientist
https://workspaces.acrobat.com/?d=AzpXN7cZ1Zh9l1usUsUMEQ


 Conditions for freshers:

- Candidate should be from a premier college i.e. IIT/IIIT/NIT/BITS or
equivalent.
- In case of any college from where Adobe does not hire developers. I
would recommend that you have something concrete in your resume so that I
can talk to HR with confidence. :)
Do mention this in the mail.

 Regards,
 Ashish

 --
 You received this message because you are subscribed to the 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] DP problems

[Shashwat Anand]

I am not too sure about your O (N^3) solution even.  Can you link the
working code ?


On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com wrote:

 This is a very good collection of DP problems.

 I want the answers for problem 2(e)
 and problem 14.

 for problem 14 the recurrence relation
 that i have is

 T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2  if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else

 But this is O(n^3) solution. Could not
 find out solution of order O(n^2).
 If someone knows please share the answers for them.


 --
 You received this message because you are subscribed to the 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] DP problems

[Shashwat Anand]

Code ?


On Thu, Jun 5, 2014 at 7:08 PM, kumar raja rajkumar.cs...@gmail.com wrote:

 U have two dimensions for the table ( has O(n^2) entries.) and to check
 whether string is palindrome or not it will take O(n) . So it is O(n^3)
 solution.

 I have checked it manually for some inputs, and it works.


 On 5 June 2014 18:53, Shashwat Anand m...@shashwat.me wrote:

 I am not too sure about your O (N^3) solution even.  Can you link the
 working code ?


 On Thu, Jun 5, 2014 at 6:48 PM, kumar raja rajkumar.cs...@gmail.com
 wrote:

 This is a very good collection of DP problems.

 I want the answers for problem 2(e)
 and problem 14.

 for problem 14 the recurrence relation
 that i have is

 T[i,j] = 0 if i=j
1 if j=i+1 and s[i]=s[j]
0 if j=i+1 and s[i]!=s[j]
j-i+1/2 if s[i..j] is even length palindrome
j-i/2  if s[i..j] is odd length palindrome
max{T[i+1,j],T[i,j-1]} else

 But this is O(n^3) solution. Could not
 find out solution of order O(n^2).
 If someone knows please share the answers for them.


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


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


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


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

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

[Shashwat Anand]

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

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

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

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

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

return 0;
}


@Atul
What is the issue in recursive approach ?

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


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

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

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

 How about this:

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

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

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

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

 Solving coin change problem with limited coins.

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

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

 input S = 6
 output = 2

 possible combination : 3+3 = 6

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

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

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

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

[atul anand]

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

 How about this:

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

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

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

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

 Solving coin change problem with limited coins.

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

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

 input S = 6
 output = 2

 possible combination : 3+3 = 6

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


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

[algogeeks] Solving coin change problem with limited coins.

[atul anand]

Solving coin change problem with limited coins.

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

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

input S = 6
output = 2

possible combination : 3+3 = 6

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

Re: [algogeeks] Remove minimum set of vertices to make the grap divided into more than one component

[atul anand]

find articulation point in graph
On 29 Apr 2014 16:56, shashi kant shashiski...@gmail.com wrote:

 Problem is as follows:

 1. Given a connected graph.
 2. Remove a vertex out of it and if graph is divided into two components
 return that vertex.
 3. else find a set of vertices to be removed that will divide graph into
 more than 1 component.



 Please Help me out here ..  probably min-cut problem
 http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ is suitable
 here.


 *Thanks  Regards,*
 *Shashi Kant *
 *Think positive and find fuel in failure*
 http://thinkndoawesome.blogspot.com/
 *Senior Software Engineer*
 *Samsung Research India Bangalore .*

 --
 You received this message because you are subscribed to the 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] Remove minimum set of vertices to make the grap divided into more than one component

[Shashwat Anand]

On Tue, Apr 29, 2014 at 10:33 PM, atul anand atul.87fri...@gmail.comwrote:

 find articulation point in graph


It won't work.

Say there are N nodes and every node is connected to every other node.
This graph does not have any articulation point.

You need to remove more than one vertex in this case.  You don't know which
vertex, you don't know what order.  I can't say for sure whether this
problem is NP-complete but I don't see how SCC works here.

On 29 Apr 2014 16:56, shashi kant shashiski...@gmail.com wrote:

 Problem is as follows:

 1. Given a connected graph.
 2. Remove a vertex out of it and if graph is divided into two components
 return that vertex.
 3. else find a set of vertices to be removed that will divide graph into
 more than 1 component.



 Please Help me out here ..  probably min-cut problem
 http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ is
 suitable here.


 *Thanks  Regards,*
 *Shashi Kant *
 *Think positive and find fuel in failure*
 http://thinkndoawesome.blogspot.com/
 *Senior Software Engineer*
 *Samsung Research India Bangalore .*

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

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


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

Re: [algogeeks] Remove minimum set of vertices to make the grap divided into more than one component

[Shashwat Anand]

On Tue, Apr 29, 2014 at 4:56 PM, shashi kant shashiski...@gmail.com wrote:

 Problem is as follows:


You have given a terrible description of problem.



 1. Given a connected graph.


Connected, how ?  Is the graph directed or undirected ?


 2. Remove a vertex out of it and if graph is divided into two components
 return that vertex.


Are you sure about two component part ?
What if graph is a star graph, you can take out the nucleus and it will be
divided into N - 1 connected component.  Will that not be ok ?  Does it
have to be *only* two components.


 3. else find a set of vertices to be removed that will divide graph into
 more than 1 component.


Does that set has to be minimum ?  If not why not simply remove N - 2
vertices and make is into two connected components.
What if graph only have one node ? The question loses its meaning here.





 Please Help me out here ..  probably min-cut problem
 http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ is suitable
 here.


Can you please explain, how is flow suitable here ?

FWIW, I see this question as broken and unclear.



 *Thanks  Regards,*
 *Shashi Kant *
 *Think positive and find fuel in failure*
 http://thinkndoawesome.blogspot.com/
 *Senior Software Engineer*
 *Samsung Research India Bangalore .*

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


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

Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black

[atul anand]

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


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

 00
 00
 010100
 011100
 01
 00

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

 Don


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

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



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

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


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

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

 It can be reduced to this :-

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

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

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


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


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

Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black

[atul anand]

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



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

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


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

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

 It can be reduced to this :-

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

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

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


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

[algogeeks] explanation of solution required.

[atul anand]

Hello,
  i found this question online and its solution tooBut i am not able to
fully understand the solution.Need your help to proof correctness of the
algo.

Question is as follows :-

*Question:*

*Given an array A and a number S', provide an efficient algorithm (nlogn)
to find a number K such that if all elements in A greater than K are
changed to K, the sum of all elements in the resulting array will be S'.*

*Example, given A: [90,30,100,40,20] and S' = 210, K will be 60.*

*Ans)*

#!/usr/bin/env python



A = [90, 30, 100, 40, 20]

S = 210

K = 60



A= sorted(A)

prev = 0

sum  = 0



for index, value in enumerate(A):

# What do we need to set all subsequent values to to get the desired sum?

solution = (S - sum) / (len(A) - index)



# That answer can't be too big or too small.

if prev  solution = value:

print solution



sum += value

prev = value

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

Re: [algogeeks] Re: maximum subsquare such that all four borders are filled black

[atul anand]

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

It can be reduced to this :-

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

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

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

 Don

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







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

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

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

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

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

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

   --

 --




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

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

[atul anand]

@bhargav : could you please explain your algorithmn

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

 public class Hill {

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

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


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

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

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

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

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

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

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

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

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

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

 Dan:-)

 Module Transform

   Contains

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


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

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

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

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

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

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

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

End Subroutine Validate_X

 End Module Transform



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

 Allocate( v(nmax), 

[algogeeks] Data structure question

[atul anand]

1) - When u login, it retrieves all the unread mails only. Which data
structure should you use ?

2)- If you get an event invitation then u have to be notified . eg if u
have two event invitations, one is in the next hour and other one 2 months
later, the one that is tomorrow will be given a higher priority and sent to
u before any other event or mail.What data structure should you use?

3) - If the events are added to your calendar on the server ,the server
should handle the query :

Find if there is a time slot on a particular date in a particular time
range of the given duration. What data structure will you use ?eg - find a
free timeslot on 31st of august between 6 AM to 7 PM of 30 min duration.

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

Re: [algogeeks] Integer partition problem - DP

[atul anand]

Problem is similar to coin change problem(i.e given an array of coins
denomination , Find number of ways to create N Rupees).So given input
K...fill up array from 1 to K.and use this array and a input to coin change
problem


On Sat, Mar 1, 2014 at 9:55 PM, kumar raja rajkumar.cs...@gmail.com wrote:

 Given an integer how many number of ways u can partition the number?

 e.g. 3  can be written as 3,1+2,1+1+1
 and 4 can be written as  4, 1+1+1+1,2+2,1+3,1+1+2

 So  for 3 -- 3
   for 4 --5.

 The order of the elements in the partition does not matter.
 So how to calculate the number of ways to partition the given number?

 Can someone give idea on how to write the recurrence relation
 for the problem?

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


-- 
You received this message because you are subscribed to the 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] Integer partition problem - DP

[Shashwat Anand]

Let us assume you have sum S.  The possible numbers it is made up are { 1,
2, .., S }.
Now, for every number belonging to the set, you have two options.
1. Subtract currently chosen number from the given set to sum.
2. Choose next number.

The state will be defined as (num, sum), where num is the number you are
using and sum is current sum.

 Recurrence will be,
f (num, sum) = f (num - 1, sum) + f (num, sum - num)
f (num, 0) = 1
f (0, sum) = 0

The translation to code is fairly obvious, which reduces to O (N^2) time
and O (N^2) space dp.

// Code.
int memo [55][505];

int
solve (int num, int sum) {
// f (num, sum) = f (num - 1, sum) + f (num, sum - num)
if (sum == 0) return 1;
if (sum  0 || num = 0) return 0;
if (memo [num][sum] != -1) return memo [num][sum];
return memo [num][sum] = solve (num - 1, sum) + solve (num, sum - num);
}

int
main () {
memset (memo, -1, sizeof (memo));
for (int i = 0; i = 10; i++) printf (%d %d\n, i, solve (i, i));

return 0;
}

Output:
0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42

Assuming, order matter, [i.e. 1 + 2 != 2 + 1], it reduces to simple
take-it or leave-it knapsack.  Though this is tangential to your question.




On Sat, Mar 1, 2014 at 9:55 PM, kumar raja rajkumar.cs...@gmail.com wrote:

 Given an integer how many number of ways u can partition the number?

 e.g. 3  can be written as 3,1+2,1+1+1
 and 4 can be written as  4, 1+1+1+1,2+2,1+3,1+1+2

 So  for 3 -- 3
   for 4 --5.

 The order of the elements in the partition does not matter.
 So how to calculate the number of ways to partition the given number?

 Can someone give idea on how to write the recurrence relation
 for the problem?

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


-- 
You received this message because you are subscribed to the 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] Permuations with stack constraints

[Shashwat Anand]

Think in binaries.
'1' = push, '0' = pop.
So a sequence of operations will consist of 0's and 1s.

Say N = length of set.

Property 1: count of 0 = count of 1 = N.
There will be N push and N pop.
Property 2: At any point count of 1s = count of 0s.
1100 is valid. [2 push, 2 pop.]
1001 is invalid. [1 push, 2 pop]  At index 3, number of 0s increased
that of 1s.
 Hence invalid.

Now just simulate the process by generating valid binaries.
Time complexity: O (N * (2 ^ N)), Space complexity: O (N)

Code follows,


int
main () {

string s = abc;
int N = s.size ();
for (int mask = 0; mask  (1  (2 * N)); mask++) {
bool ok = true;
if (__builtin_popcount (mask) != N) continue;
for (int i = 0, x = mask, c0 = 0, c1 = 0; i  2 * N; i++, x /= 2) {
(x  1) ? c1++ : c0++;
ok = (c0 = c1);
}
if (! ok) continue;  // Invalid mask.
stack char st;
string t = ;
for (int i = 0, x = mask, idx = 0; i  2 * N; i++, x /= 2)
if (x  1)
st.push (s [idx++]);
else
t += st.top (), st.pop ();

printf (%s\n, t.c_str ());
}

return 0;
}

For s = ab,

ba
ab

For s = abc,

cba
bca
acb
bac
abc

For s = abcd,

dcba
cdba
bdca
adcb
cbda
bcda
acdb
badc
abdc
cbad
bcad
acbd
bacd
abcd


Alternatively, you can simply simulate the whole process and do a validity
check after generation of string.  The check being, stack should be empty
and at any point during simulation, you should not try to pop from empty
stack.

On Thu, Feb 20, 2014 at 11:57 PM, kumar raja rajkumar.cs...@gmail.comwrote:

 Hi all,

 Here is a permuatation related question.

 Suppose the set is {a,b,c};

 At a given point of time either u can push an
 elemnt on to the stack or pop of the element.
 While pushing the elements u have to follow the
 order a,b,c as given in the set.

 When u pop the element u will print it to the
 output array.

 one possible sequence of operations is

 push(a),push(b),pop(),push(c),pop(),pop()

 The permuation obtained by above combination is

  {b,c,a}.

 But out of 6! permuations possible one invalid
 permutation  is {c,a,b} (guess how?)

 So how to print all valid permuations with the
 above constaraints?

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


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

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

[Shashwat Anand]

@Don, amazing solution.

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


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

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

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

return 0;
}

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


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

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


 public class PrimeFactors {

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


 btw was this from interviewstreet interview ?? :P

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


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

[algogeeks] Find 3 digit number.

[atul anand]

Given a number N, find the smallest 3 digits number  such that product of
its digits is equal to N.

For Eg:-

for input 24 , output :138 (1*3*8 = 24)
for input 36 , output :149 (1*4*9 = 36)
for input 100 , output : 455 (4*5*5 = 100)

-- 
You received this message because you are subscribed to the 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 3 digit number.

[Shashwat Anand]

Since the limit is so small, won't a simple bruteforce do ?
Just run a loop from [100, 1000) and return the minimum.

Here is a quick python code I wrote.

  N = 24
 min (i for i in range (100, 1001) if int (str (i) [0]) * int (str (i)
[1]) * int (str (i) [2]) == N)
138
 N = 36
 min (i for i in range (100, 1001) if int (str (i) [0]) * int (str (i)
[1]) * int (str (i) [2]) == N)
149
 N = 100
 min (i for i in range (100, 1001) if int (str (i) [0]) * int (str (i)
[1]) * int (str (i) [2]) == N)
455


On Wed, Feb 12, 2014 at 8:45 PM, atul anand atul.87fri...@gmail.com wrote:

 Given a number N, find the smallest 3 digits number  such that product of
 its digits is equal to N.

 For Eg:-

 for input 24 , output :138 (1*3*8 = 24)
 for input 36 , output :149 (1*4*9 = 36)
 for input 100 , output : 455 (4*5*5 = 100)

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


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

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

[atul anand]

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



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

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

 Here is a way to generate a permutation without swapping:

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

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


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

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

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

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

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

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

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

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

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

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


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

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

[atul anand]

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

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

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

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

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

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

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

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


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

[algogeeks] Generate random number from 1 to 10.

[atul anand]

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

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

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

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

[Shashwat Anand]

How about a normal binary search ?

We know that X can be [0, 2^31 - 1].
Also if X is a valid configuration, all the values above X will too.
 Monotonicity is all we need here.
So, take lo = 0 and hi = 2 ^ 31 - 1.
Now check, if your mid is a valid X.
If yes, X can lie between [0, mid].  If not, X will lie between [mid + 1,
2^31 -  1].

Here is an untested code.

typedef long long int64;

// If true, x is a valid configuration for v.
int
valid (int x, int N, vector int64 v) {
vector int64 u = v;
u [0] -= x;
for (int i = 1; i  N; i++)
if (u [i] + x = u [i - 1] + 1  u [i] - x = u [i - 1] + 1)
u [i] = u [i - 1] + 1;
else return false;
return true;
}

// A binary search over v for X [0, 2 ^ 31 - 1]
int
solve (int N, vector int64 v) {
int64 lo = 0, hi = 2147483647;
int ret = 0;
while (lo = hi) {
int64 mid = lo + (hi - lo) / 2;
if (valid (mid, N, v)) {
ret = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
return ret;
}

int
main () {
vector int64 v;
v.push_back (5);
v.push_back (4);
v.push_back (3);
v.push_back (2);
v.push_back (8);
printf (%d\n, solve (v.size (), v));

return 0;
}



On Wed, Jan 29, 2014 at 10:26 PM, bhargav ybbkris...@gmail.com wrote:

 Given an array of integer elements

 *Your task is to*

 · write a function that finds the minimum value X that makes
 possible the following: generate a new array that is sorted in strictly
 ascending order by increasing or decreasing each of the elements of the
 initial array with integer values in the [0, X] range.

 oExample: Having the initial array [5, 4, 3, 2, 8] the minimum value
 for X is 3. Decrease the first element (5) by 3, decrease the second one
 (4) by 1, increase the third one (3) by 1, increase the forth one (2) by 3
 and do nothing to the last one (8). In the end we obtain the array [2, 3,
 4, 5, 8] which is sorted in strictly ascending order.

 · print the result X to the standard output (stdout)

 Note that your function will receive the following arguments:

 · *v*

 owhich is the array of integers

 *Data constraints*

 · numbers are in ascending order when arranged from the smallest
 to the largest number

 · strictly ascending order means that each element is greater
 than the preceding one (e.g. [1, 2, 2, 3] is NOT strictly ascending order)

 · the length of the array will not exceed 5000

 · the elements of any of the arrays are integer numbers in the
 [1, 231 -1] range

 *Efficiency constraints*

 · your function is expected to print the result in less than 2
 seconds

 *Example*

 *Input*

 *Output*

 v: 5, 4, 3, 2, 8

 3

 any clues for the 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.


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

[algogeeks] changing structure of binary tree based on gravity and node selected.

[atul anand]

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

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

[algogeeks] Solving equation

[atul anand]

Hello,

How to solve an equation with one unknown variable ?
operator allowed are : + , -

for eg .  input could be :-
x + ( 5 + 4 ) = 6
(x - 7) + 7 = (x + 1) - 5

If operator also allows  *  (multiply) , then what change in algorithm is
required.

-- 
You received this message because you are subscribed to the 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] Job Openings at Adobe India

[Shashwat Anand]

We need active moderators who can ban these guys spamming the list.

This group deals with algorithm problems, we don't need salesmen and
brokers here.


On Wed, Jan 8, 2014 at 1:42 PM, RM rmath...@gmail.com wrote:

 Job postings to this mailing list should be marked as spam, and the
 senders blocked.

 This is not a India-specific chatroom, this not a place to exchange
 books and PDFs, this is not a forum for jokes and forwards, and
 certainly not the list to be posting job offers to.

 Ignoring the idiot who was peddling Macbook Pros last week was a
 mistake, since it has encouraged the moron from Adobe to send this
 mail now.

 I had mailed the list-owner via the Google-Groups interface last week,
 but I don't think he/she has done anything about it.  Does anyone know
 the list-owner?  IIRC, it was someone from the 2004-2006 batch of CEG.

 -- rm

 On Wed, Jan 8, 2014 at 12:16 AM, Gaurav Gupta gauravnit...@gmail.com
 wrote:
  Hello Lalit ,
 
  Please find my attached CV.
  Present Company : Samsung Research India , bangalore
  Experience : 1 year 6 months
  Time Frame To Join : 2 Months
 
 
  Thanks  Regards,
  Gaurav kumar gupta
 
 
  On 7 January 2014 22:49, Lalit Sharma lks.ru...@gmail.com wrote:
 
  Hi all,
 
  Adobe Hiring drive in Hyderabad, Noida and Bangalore
  Dates: 18th/25th Jan 2014
  Profile: Developer (C++/Java).
  Colleges Eligible: Premiere Institutes
  (IITs/NITs/IISc/BITS/IIITs/NSIT/Thapar/DCE/Jadavpur etc.)
  Experience Reqd : 1 – 5 Yrs experience in a good Product Company.
 
 
  Please share your resumes with me.
 
  --
  Lalit Sharma | Member of Technical Staff | Adobe Systems ,Noida , India
 |
  Contact No : +91-8130-321-181 .
 
 
 
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send
 an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
  --
  Thanks  Regards,
  Gaurav kumar gupta
  Software Engineer
  Samsung Research India,Bangalore
  Contact No:+91-9538147434
  Email id: gauravnit...@gmail.com
 
  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send an
  email to algogeeks+unsubscr...@googlegroups.com.

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


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

Re: [algogeeks] Re: Median Finding in Sorted Arrays

[atul anand]

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

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

 Dave

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

 Hi guys,

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


 Thanks,
 Sanjay

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


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

Re: [algogeeks] coloring problem Dynamic programming

[atul anand]

@saurabh : i did not get your algo for modified ques i.e No 3 adjacent
houses should get same color

according to your recurrence

answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + colorvalue[j] for
all t from 1 to k except j.


now suppose in some case *answer[i-1][t][0] *is found minimum in
above recurrence .
*answer[i-1][t][0] *means that i - 2 and i - 1 are of same color say for eg
color green.

answer[i][j][1] is not colored same as i-1 house (green in this case)
...now say it is colored with color yellow.

hence,
answer[i][j][1] is sum of house with color green+green+yellow.

i am not able to understand , how it is taking care that 3 adjacent are
colored
different.

could you please clarify my doubt.



On Thu, Dec 26, 2013 at 5:25 PM, Saurabh Paliwal 
saurabh.paliwa...@gmail.com wrote:

 @atul anand :- no, we need not use all the colors.

 @kumar raja :- sorry dude for replying this late. Continuing with the
 previous idea, I extend the solution for the modified problem as

 1. let answer[i][j][0] represent minimum cost of coloring i houses when
 ith house is colored with jth color and so is the (i-1)th house.

 2. let answer[i][j][1] represent minimum cost of coloring i houses when
 ith house is colored with jth color and (i-1)th is not.

 The recurrence will be

 3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]*

 4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) +
 colorvalue[j]* for all t from 1 to k except j.

 // In the first problem, I mistakenly wrote colorvalue[t] here. It will be
 colorvalue[j] there. ( sorry for the confusion )

 5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all
 j from 1 to k.

 6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j].


 Also now that I read the problem, I guess colorvalue is not fixed for
 every color, so that will be a 2-D matrix as well.

 *replace every colorvalue[j] with colorvalue[i][j] in the above
 recurrences*. ( i is the house number, j is the color number )


 On Wed, Dec 18, 2013 at 10:16 PM, atul anand atul.87fri...@gmail.comwrote:

 @kumar :  i have one doubt regarding this question.Do we have to use all
 K colors[K] to color all building.

 for example :-

 color[3]={1,2,10};

  now if we have to color 6 building then i can use only 1st 2 color to
 color all building and never 10 ...is this allowed ???
 building[N]={1,2,1,2,1,2}


  On Sun, Dec 15, 2013 at 12:44 AM, kumar raja 
 rajkumar.cs...@gmail.comwrote:

 You have 'n' houses and 'k' colors. The cost of coloring a house with
 one of the 'k' colors is different from coloring another house with same
 color.  The cost of coloring the house with different colors are different.
 So now how to colour the 'n' houses such that no two adjcent houses will
 get the same color and the total coloring cost for 'n' houses is minimized.



 Regards,
 Kumar Raja.

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


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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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


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

[Shashwat Anand]

Yes, we know now that you are a proud owner of Apple iPod.


On Fri, Jan 2, 1970 at 9:32 AM, Chitra chitradevi.ramachand...@gmail.comwrote:



 Sent from my iPod

 --
 You received this message because you are subscribed to the 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] coloring problem Dynamic programming

[atul anand]

@kumar :  i have one doubt regarding this question.Do we have to use all K
colors[K] to color all building.

for example :-

color[3]={1,2,10};

now if we have to color 6 building then i can use only 1st 2 color to color
all building and never 10 ...is this allowed ???
building[N]={1,2,1,2,1,2}


On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote:

 You have 'n' houses and 'k' colors. The cost of coloring a house with one
 of the 'k' colors is different from coloring another house with same color.
  The cost of coloring the house with different colors are different. So now
 how to colour the 'n' houses such that no two adjcent houses will get the
 same color and the total coloring cost for 'n' houses is minimized.



 Regards,
 Kumar Raja.

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


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

Re: [algogeeks] coloring problem Dynamic programming

[atul anand]

@saurabh :

answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to
k except j.

how this DP is taking care of the case where no adjacent house if of same
color.

what i understand from the DP is the following :-

find minimum cost of coloring previous house with color t (
min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum cost
of coloring answer[i][j].
where t varies from 1 to k except j. - is taking care that ignore coloring
house if it of same as colorvalue[t].

I dont see the above restriction of taken care of ... please explain and
correct me if i am wrong.


On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal 
saurabh.paliwa...@gmail.com wrote:

 what is the issue with the usual recurrence :-

 Let answer[i][j] represent minimum cost of coloring i houses with ith
 house colored with jth color.

 answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1
 to k except j.

 initial setting :-  answer[1][j] = colorvalue[j]

 final answer is min(answer[n][j]) for all j from 1 to k.

 Time complexity = O(n*k*k)
 Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are
 required ).


 On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote:

 You have 'n' houses and 'k' colors. The cost of coloring a house with one
 of the 'k' colors is different from coloring another house with same color.
  The cost of coloring the house with different colors are different. So now
 how to colour the 'n' houses such that no two adjcent houses will get the
 same color and the total coloring cost for 'n' houses is minimized.



 Regards,
 Kumar Raja.

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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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


-- 
You received this message because you are subscribed to the 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] coloring problem Dynamic programming

[atul anand]

ohh shoots...my bad.got this condition wrong t varies from 1 to k
except j.

 now got it :)..ignore my previous comment :) :)


On Tue, Dec 17, 2013 at 11:47 PM, atul anand atul.87fri...@gmail.comwrote:

 @saurabh :

 answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1
 to k except j.

 how this DP is taking care of the case where no adjacent house if of same
 color.

 what i understand from the DP is the following :-

 find minimum cost of coloring previous house with color t (
 min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum
 cost of coloring answer[i][j].
 where t varies from 1 to k except j. - is taking care that ignore
 coloring house if it of same as colorvalue[t].

 I dont see the above restriction of taken care of ... please explain and
 correct me if i am wrong.


 On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal 
 saurabh.paliwa...@gmail.com wrote:

 what is the issue with the usual recurrence :-

 Let answer[i][j] represent minimum cost of coloring i houses with ith
 house colored with jth color.

 answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1
 to k except j.

 initial setting :-  answer[1][j] = colorvalue[j]

 final answer is min(answer[n][j]) for all j from 1 to k.

 Time complexity = O(n*k*k)
 Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are
 required ).


 On Sun, Dec 15, 2013 at 12:44 AM, kumar raja rajkumar.cs...@gmail.comwrote:

 You have 'n' houses and 'k' colors. The cost of coloring a house with
 one of the 'k' colors is different from coloring another house with same
 color.  The cost of coloring the house with different colors are different.
 So now how to colour the 'n' houses such that no two adjcent houses will
 get the same color and the total coloring cost for 'n' houses is minimized.



 Regards,
 Kumar Raja.

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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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




-- 
You received this message because you are subscribed to the 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] [Algogeeks] Longest increasing sub sequence length in linear time

[atul anand]

can be done with nlogn i dont think so O(n) is possible...
On 17 Dec 2013 01:30, bujji jajala jajalabu...@gmail.com wrote:

 Given an Array of integers (A1,A2,...,An) of length n, Find the maximum
 possible  length of increasing sub sequence formed from A1, A2,,An.


 I read that it is possible to compute in linear time as mentioned in
 algorithm design manual bySkiena.

 -Thanks
 Bujji

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


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

Re: [algogeeks] [Algogeeks] Longest increasing sub sequence length in linear time

[Shashwat Anand]

On Tue, Dec 17, 2013 at 1:30 AM, bujji jajala jajalabu...@gmail.com wrote:

 Given an Array of integers (A1,A2,...,An) of length n, Find the maximum
 possible  length of increasing sub sequence formed from A1, A2,,An.


 I read that it is possible to compute in linear time as mentioned in
 algorithm design manual bySkiena.


Interesting.  I think I am getting older, I don't recall or probably missed
it.
Can you point the page number where it was mentioned, computing LIS in O
(N) that is.



 -Thanks
 Bujji

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


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

Re: [algogeeks] Re: Saving and restoring Binary trees in files

[atul anand]

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


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

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

 Dave

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

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

 Don

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

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


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

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

 Then rebuild like this:

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

 }

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

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

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

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

 write in file :-

 a b c d e # c b e a d

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

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

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

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

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

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

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

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


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


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

Re: [algogeeks] Re: Saving and restoring Binary trees in files

[atul anand]

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


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

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

 Then rebuild like this:

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

 }

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

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

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

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

 write in file :-

 a b c d e # c b e a d

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

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

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

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

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

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

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

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


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

Re: [algogeeks] Re: Saving and restoring Binary trees in files

[atul anand]

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

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

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

write in file :-

a b c d e # c b e a d

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

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

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

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

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

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

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

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


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

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


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

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













 Regards,
 Kumar Raja.

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




 --
 Thanks,
 Vishnu

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


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

Re: [algogeeks] Message distribution through rooted tree dynamic programming

[atul anand]

we can first count number of nodes in a subtree below each node.Now
transfer message to max(count(root-left),count-root-right);

On 11/1/13, kumar raja rajkumar.cs...@gmail.com wrote:
 Suppose we need to distribute a message to all the nodes in a rooted tree.
 Initially, only the root
 node knows the message. In a single round, any node that knows the message
 can forward it
 to at most one of its children. Design an algorithm to compute the minimum
 number of rounds
 required for the message to be delivered to all nodes.

 --
 You received this message because you are subscribed to the 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] variation of LIS problem

[atul anand]

using idea mentioned in below link , we can solve this similar problem
in O(n^2*k).

http://stackoverflow.com/questions/12862077/number-of-increasing-strings-of-length-k

On 10/26/13, atul anand atul.87fri...@gmail.com wrote:
 @saurabh : i did not get ur algo...can you please explain with an example
 On 26 Oct 2013 08:21, Saurabh Paliwal saurabh.paliwa...@gmail.com
 wrote:

 if all the elements are positive then we can reverse the array and
 multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since
 it
 gives the answer for all k=n with the minimum sum, this will be the
 answer
 multiplied by -1.


 On Sat, Oct 26, 2013 at 12:12 AM, kumar raja
 rajkumar.cs...@gmail.comwrote:

 I think O(nlogn) solution is possible for this problem.  First  find the
 largest increasing subsequence in O(nlogn) time.

 http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

 From this one u have LIS array M and parent array P. Now traverse
 through
 the array M and for all the length values = k , u can print the k
 elements using Parent array P. I guess the step of printing the array
 elements wont be greater than O(n logn).

 So it is bounded by O(nlogn) .  In the worst case it might go up to
 O(n^2). But i am not sure of this.


 On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote:

 OK, i got now why you were using min-heap.

 now consider this example :-

 200,12,33,1,55,100

 K=3

 insert 200
 12  200...cannot insert
 33  200...cannot insert
 .
 .
 .
 100200 cannot insert

 output : 200 (not lenght of k)
 output should be : 33,55,100


 On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
  Max-heap should not used in this case,
  why min heap? -- this is because program has to decide the smallest
 element
  in k-group.
  in your example if i consider k =3 than
 
  insert 1
  insert 2
  insert 5
  insert 10
  size of heap ==4 so delete root of min- heap (which is 1),
  insert 100
  30 cant insert because temp = 100 and 30temp
  insert 8 cant insert temp = 100 and 8temp
  (500temp)size of heap ==4 so delete root of min-heap(which is 2)
  insert 555
 
  now if i check the heap elements
  {5, 10, 100 , 555}
 
 
 
  On Thu, Oct 24, 2013 at 11:25 PM, atul anand
  atul.87fri...@gmail.comwrote:
 
  in your updated algo , you should be using max-heap not min-heap.
 
  check your algo for :-
 
  1,2,5,10,100,30,8,555
 
  let me know if it work fine.If it is working fine then i need more
  clarity of your algo
 
  On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
   @Saurabh:
   As per the question the elements of sub-sequence  should be
 increasing,
   so the solution will be {5} and as per the program.
   * but as written longest sub-sequence of k =2, so it should be
   {2,3}
   for
   this case. (there should be backtrack in this case.)
  
   @atul: increasing sub sequence is checked by condition, not by
   Min-heap,
   but min heap is used for storing the largest elements.
   So it is preferable DS,
  
  
   On Thu, Oct 24, 2013 at 8:35 PM, atul anand 
 atul.87fri...@gmail.com
   wrote:
  
   @pankaj : how can you maintain increasing sub-sequence using
   heapyour soln is for finding finding K largest element in the
   array...so it wont work.
  
   On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
   
   
   
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi 
 joshi10...@gmail.com
   wrote:
   
@ Saurabh,
   
I have done a correction on algo
   
temp =0
loop n to a[]
 if a[i]temp
   if min-heap(root)  a[i]
 if min-heap(count)==k
delete root in min- heap
 inseart a[i] in min - heap
   
As i have made the condition: min-heap, (condition size should
 be
always
k) for this particular case.
   
And in the example {5,2,1,10,9,30,8,55} if K =3
   
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as
count
 of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
   
and if k is 4
than
{5, 10, 30 , 55)
   
   
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal 
saurabh.paliwa...@gmail.com wrote:
   
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
   
   
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
   
   
hi all,
   
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
   
temp =0
loop n to a[]
 if a[i]temp
   if min-heap(root)  a[i]
 delete root in min- heap
 inseart a[i] in min - heap
   
at the end of main loop the min-heap will contain the final
sequence.
   
On Thu, Oct 24, 2013 at 8

Re: [algogeeks] variation of LIS problem

[atul anand]

@saurabh : i did not get ur algo...can you please explain with an example
On 26 Oct 2013 08:21, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:

 if all the elements are positive then we can reverse the array and
 multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it
 gives the answer for all k=n with the minimum sum, this will be the answer
 multiplied by -1.


 On Sat, Oct 26, 2013 at 12:12 AM, kumar raja rajkumar.cs...@gmail.comwrote:

 I think O(nlogn) solution is possible for this problem.  First  find the
 largest increasing subsequence in O(nlogn) time.

 http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

 From this one u have LIS array M and parent array P. Now traverse through
 the array M and for all the length values = k , u can print the k
 elements using Parent array P. I guess the step of printing the array
 elements wont be greater than O(n logn).

 So it is bounded by O(nlogn) .  In the worst case it might go up to
 O(n^2). But i am not sure of this.


 On 25 October 2013 00:17, atul anand atul.87fri...@gmail.com wrote:

 OK, i got now why you were using min-heap.

 now consider this example :-

 200,12,33,1,55,100

 K=3

 insert 200
 12  200...cannot insert
 33  200...cannot insert
 .
 .
 .
 100200 cannot insert

 output : 200 (not lenght of k)
 output should be : 33,55,100


 On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
  Max-heap should not used in this case,
  why min heap? -- this is because program has to decide the smallest
 element
  in k-group.
  in your example if i consider k =3 than
 
  insert 1
  insert 2
  insert 5
  insert 10
  size of heap ==4 so delete root of min- heap (which is 1),
  insert 100
  30 cant insert because temp = 100 and 30temp
  insert 8 cant insert temp = 100 and 8temp
  (500temp)size of heap ==4 so delete root of min-heap(which is 2)
  insert 555
 
  now if i check the heap elements
  {5, 10, 100 , 555}
 
 
 
  On Thu, Oct 24, 2013 at 11:25 PM, atul anand
  atul.87fri...@gmail.comwrote:
 
  in your updated algo , you should be using max-heap not min-heap.
 
  check your algo for :-
 
  1,2,5,10,100,30,8,555
 
  let me know if it work fine.If it is working fine then i need more
  clarity of your algo
 
  On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
   @Saurabh:
   As per the question the elements of sub-sequence  should be
 increasing,
   so the solution will be {5} and as per the program.
   * but as written longest sub-sequence of k =2, so it should be {2,3}
   for
   this case. (there should be backtrack in this case.)
  
   @atul: increasing sub sequence is checked by condition, not by
   Min-heap,
   but min heap is used for storing the largest elements.
   So it is preferable DS,
  
  
   On Thu, Oct 24, 2013 at 8:35 PM, atul anand 
 atul.87fri...@gmail.com
   wrote:
  
   @pankaj : how can you maintain increasing sub-sequence using
   heapyour soln is for finding finding K largest element in the
   array...so it wont work.
  
   On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
check for {5,2,3} and K = 2.
   
   
   
On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi 
 joshi10...@gmail.com
   wrote:
   
@ Saurabh,
   
I have done a correction on algo
   
temp =0
loop n to a[]
 if a[i]temp
   if min-heap(root)  a[i]
 if min-heap(count)==k
delete root in min- heap
 inseart a[i] in min - heap
   
As i have made the condition: min-heap, (condition size should
 be
always
k) for this particular case.
   
And in the example {5,2,1,10,9,30,8,55} if K =3
   
insert 5
2 is less so do nothing
1 is less so do nothing
insert 10
9 is less so do nothing
insert 30
8 is less so do nothing
insert 55 (before inserting 50 delete the root of heap as count
 of
heap
==
3), deleted root was - 5
so the output will be
{10,30,55}
   
and if k is 4
than
{5, 10, 30 , 55)
   
   
On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal 
saurabh.paliwa...@gmail.com wrote:
   
You must be mistaken in the definition of heaps, or maybe the
question,
look at the updated question I put up there.
   
   
On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
joshi10...@gmail.comwrote:
   
   
hi all,
   
nlog(k) is the solution i think.
can anyone suggest more optimal?
solution:
create a min-heap, (condition size should be always k)
   
temp =0
loop n to a[]
 if a[i]temp
   if min-heap(root)  a[i]
 delete root in min- heap
 inseart a[i] in min - heap
   
at the end of main loop the min-heap will contain the final
sequence.
   
On Thu, Oct 24, 2013 at 8:50 AM, atul anand
atul.87fri...@gmail.comwrote:
   
@Saurabh Paliwal : yes
   
On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com
wrote:
 Do you mean
 *of all the increasing subsequences of length k

Re: [algogeeks] variation of LIS problem

[atul anand]

@pankaj : how can you maintain increasing sub-sequence using
heapyour soln is for finding finding K largest element in the
array...so it wont work.

On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
 check for {5,2,3} and K = 2.



 On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com wrote:

 @ Saurabh,

 I have done a correction on algo

 temp =0
 loop n to a[]
  if a[i]temp
if min-heap(root)  a[i]
  if min-heap(count)==k
 delete root in min- heap
  inseart a[i] in min - heap

 As i have made the condition: min-heap, (condition size should be always
 k) for this particular case.

 And in the example {5,2,1,10,9,30,8,55} if K =3

 insert 5
 2 is less so do nothing
 1 is less so do nothing
 insert 10
 9 is less so do nothing
 insert 30
 8 is less so do nothing
 insert 55 (before inserting 50 delete the root of heap as count of heap
 ==
 3), deleted root was - 5
 so the output will be
 {10,30,55}

 and if k is 4
 than
 {5, 10, 30 , 55)


 On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal 
 saurabh.paliwa...@gmail.com wrote:

 You must be mistaken in the definition of heaps, or maybe the question,
 look at the updated question I put up there.


 On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
 joshi10...@gmail.comwrote:


 hi all,

 nlog(k) is the solution i think.
 can anyone suggest more optimal?
 solution:
 create a min-heap, (condition size should be always k)

 temp =0
 loop n to a[]
  if a[i]temp
if min-heap(root)  a[i]
  delete root in min- heap
  inseart a[i] in min - heap

 at the end of main loop the min-heap will contain the final sequence.

 On Thu, Oct 24, 2013 at 8:50 AM, atul anand
 atul.87fri...@gmail.comwrote:

 @Saurabh Paliwal : yes

 On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
  Do you mean
  *of all the increasing subsequences of length k in this array, find
 the one
  with maximum sum ?*
  
 
 
  On Wed, Oct 23, 2013 at 10:52 PM, atul anand
  atul.87fri...@gmail.comwrote:
 
  Given an array with N elements and integer K . Find sum of longest
  increasing sub-sequence of length  K elements such that
  sub-sequence
  found
  is maximum among all K max su-sequence.
 
  Eg arr[]={5,2,1,10,9,30,8,55}
 
  K = 3
  output : 10,30,55sum = 10+30+55 = 95
 
  if K=4
  output : 5,10,30,55   sum = 5+10+30+55 =100
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
 send an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
  --
   -Saurabh Paliwal
 
 B-Tech. Comp. Science and Engg.
 
 IIT ROORKEE
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
 send an
  email to algogeeks+unsubscr...@googlegroups.com.
 

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

 Pankaj Kumar Joshi

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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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




 --
  Regards,

 Pankaj Kumar Joshi

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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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


-- 
You received this message because you are subscribed to the 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] variation of LIS problem

[atul anand]

in your updated algo , you should be using max-heap not min-heap.

check your algo for :-

1,2,5,10,100,30,8,555

let me know if it work fine.If it is working fine then i need more
clarity of your algo

On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
 @Saurabh:
 As per the question the elements of sub-sequence  should be increasing,
 so the solution will be {5} and as per the program.
 * but as written longest sub-sequence of k =2, so it should be {2,3} for
 this case. (there should be backtrack in this case.)

 @atul: increasing sub sequence is checked by condition, not by Min-heap,
 but min heap is used for storing the largest elements.
 So it is preferable DS,


 On Thu, Oct 24, 2013 at 8:35 PM, atul anand atul.87fri...@gmail.com
 wrote:

 @pankaj : how can you maintain increasing sub-sequence using
 heapyour soln is for finding finding K largest element in the
 array...so it wont work.

 On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
  check for {5,2,3} and K = 2.
 
 
 
  On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com
 wrote:
 
  @ Saurabh,
 
  I have done a correction on algo
 
  temp =0
  loop n to a[]
   if a[i]temp
 if min-heap(root)  a[i]
   if min-heap(count)==k
  delete root in min- heap
   inseart a[i] in min - heap
 
  As i have made the condition: min-heap, (condition size should be
  always
  k) for this particular case.
 
  And in the example {5,2,1,10,9,30,8,55} if K =3
 
  insert 5
  2 is less so do nothing
  1 is less so do nothing
  insert 10
  9 is less so do nothing
  insert 30
  8 is less so do nothing
  insert 55 (before inserting 50 delete the root of heap as count of
  heap
  ==
  3), deleted root was - 5
  so the output will be
  {10,30,55}
 
  and if k is 4
  than
  {5, 10, 30 , 55)
 
 
  On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal 
  saurabh.paliwa...@gmail.com wrote:
 
  You must be mistaken in the definition of heaps, or maybe the
  question,
  look at the updated question I put up there.
 
 
  On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
  joshi10...@gmail.comwrote:
 
 
  hi all,
 
  nlog(k) is the solution i think.
  can anyone suggest more optimal?
  solution:
  create a min-heap, (condition size should be always k)
 
  temp =0
  loop n to a[]
   if a[i]temp
 if min-heap(root)  a[i]
   delete root in min- heap
   inseart a[i] in min - heap
 
  at the end of main loop the min-heap will contain the final
  sequence.
 
  On Thu, Oct 24, 2013 at 8:50 AM, atul anand
  atul.87fri...@gmail.comwrote:
 
  @Saurabh Paliwal : yes
 
  On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
   Do you mean
   *of all the increasing subsequences of length k in this array,
   find
  the one
   with maximum sum ?*
   
  
  
   On Wed, Oct 23, 2013 at 10:52 PM, atul anand
   atul.87fri...@gmail.comwrote:
  
   Given an array with N elements and integer K . Find sum of
   longest
   increasing sub-sequence of length  K elements such that
   sub-sequence
   found
   is maximum among all K max su-sequence.
  
   Eg arr[]={5,2,1,10,9,30,8,55}
  
   K = 3
   output : 10,30,55sum = 10+30+55 = 95
  
   if K=4
   output : 5,10,30,55   sum = 5+10+30+55 =100
  
   --
   You received this message because you are subscribed to the
   Google
  Groups
   Algorithm Geeks group.
   To unsubscribe from this group and stop receiving emails from
   it,
  send an
   email to algogeeks+unsubscr...@googlegroups.com.
  
  
  
  
   --
-Saurabh Paliwal
  
  B-Tech. Comp. Science and Engg.
  
  IIT ROORKEE
  
   --
   You received this message because you are subscribed to the
   Google
  Groups
   Algorithm Geeks group.
   To unsubscribe from this group and stop receiving emails from it,
  send an
   email to algogeeks+unsubscr...@googlegroups.com.
  
 
  --
  You received this message because you are subscribed to the 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,
 
  Pankaj Kumar Joshi
 
  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
  send
  an email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
  --
   -Saurabh Paliwal
 
 B-Tech. Comp. Science and Engg.
 
 IIT ROORKEE
 
  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
  send
  an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
  --
   Regards,
 
  Pankaj Kumar Joshi
 
  --
  You received this message because you are subscribed to the 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] variation of LIS problem

[atul anand]

OK, i got now why you were using min-heap.

now consider this example :-

200,12,33,1,55,100

K=3

insert 200
12  200...cannot insert
33  200...cannot insert
.
.
.
100200 cannot insert

output : 200 (not lenght of k)
output should be : 33,55,100


On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
 Max-heap should not used in this case,
 why min heap? -- this is because program has to decide the smallest element
 in k-group.
 in your example if i consider k =3 than

 insert 1
 insert 2
 insert 5
 insert 10
 size of heap ==4 so delete root of min- heap (which is 1),
 insert 100
 30 cant insert because temp = 100 and 30temp
 insert 8 cant insert temp = 100 and 8temp
 (500temp)size of heap ==4 so delete root of min-heap(which is 2)
 insert 555

 now if i check the heap elements
 {5, 10, 100 , 555}



 On Thu, Oct 24, 2013 at 11:25 PM, atul anand
 atul.87fri...@gmail.comwrote:

 in your updated algo , you should be using max-heap not min-heap.

 check your algo for :-

 1,2,5,10,100,30,8,555

 let me know if it work fine.If it is working fine then i need more
 clarity of your algo

 On 10/24/13, pankaj joshi joshi10...@gmail.com wrote:
  @Saurabh:
  As per the question the elements of sub-sequence  should be increasing,
  so the solution will be {5} and as per the program.
  * but as written longest sub-sequence of k =2, so it should be {2,3}
  for
  this case. (there should be backtrack in this case.)
 
  @atul: increasing sub sequence is checked by condition, not by
  Min-heap,
  but min heap is used for storing the largest elements.
  So it is preferable DS,
 
 
  On Thu, Oct 24, 2013 at 8:35 PM, atul anand atul.87fri...@gmail.com
  wrote:
 
  @pankaj : how can you maintain increasing sub-sequence using
  heapyour soln is for finding finding K largest element in the
  array...so it wont work.
 
  On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
   check for {5,2,3} and K = 2.
  
  
  
   On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi joshi10...@gmail.com
  wrote:
  
   @ Saurabh,
  
   I have done a correction on algo
  
   temp =0
   loop n to a[]
if a[i]temp
  if min-heap(root)  a[i]
if min-heap(count)==k
   delete root in min- heap
inseart a[i] in min - heap
  
   As i have made the condition: min-heap, (condition size should be
   always
   k) for this particular case.
  
   And in the example {5,2,1,10,9,30,8,55} if K =3
  
   insert 5
   2 is less so do nothing
   1 is less so do nothing
   insert 10
   9 is less so do nothing
   insert 30
   8 is less so do nothing
   insert 55 (before inserting 50 delete the root of heap as count of
   heap
   ==
   3), deleted root was - 5
   so the output will be
   {10,30,55}
  
   and if k is 4
   than
   {5, 10, 30 , 55)
  
  
   On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal 
   saurabh.paliwa...@gmail.com wrote:
  
   You must be mistaken in the definition of heaps, or maybe the
   question,
   look at the updated question I put up there.
  
  
   On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi
   joshi10...@gmail.comwrote:
  
  
   hi all,
  
   nlog(k) is the solution i think.
   can anyone suggest more optimal?
   solution:
   create a min-heap, (condition size should be always k)
  
   temp =0
   loop n to a[]
if a[i]temp
  if min-heap(root)  a[i]
delete root in min- heap
inseart a[i] in min - heap
  
   at the end of main loop the min-heap will contain the final
   sequence.
  
   On Thu, Oct 24, 2013 at 8:50 AM, atul anand
   atul.87fri...@gmail.comwrote:
  
   @Saurabh Paliwal : yes
  
   On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com
   wrote:
Do you mean
*of all the increasing subsequences of length k in this array,
find
   the one
with maximum sum ?*

   
   
On Wed, Oct 23, 2013 at 10:52 PM, atul anand
atul.87fri...@gmail.comwrote:
   
Given an array with N elements and integer K . Find sum of
longest
increasing sub-sequence of length  K elements such that
sub-sequence
found
is maximum among all K max su-sequence.
   
Eg arr[]={5,2,1,10,9,30,8,55}
   
K = 3
output : 10,30,55sum = 10+30+55 = 95
   
if K=4
output : 5,10,30,55   sum = 5+10+30+55 =100
   
--
You received this message because you are subscribed to the
Google
   Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
it,
   send an
email to algogeeks+unsubscr...@googlegroups.com.
   
   
   
   
--
 -Saurabh Paliwal
   
   B-Tech. Comp. Science and Engg.
   
   IIT ROORKEE
   
--
You received this message because you are subscribed to the
Google
   Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
 it,
   send an
email to algogeeks+unsubscr...@googlegroups.com.
   
  
   --
   You received this message because you are subscribed to the
   Google
   Groups Algorithm Geeks

[algogeeks] variation of LIS problem

[atul anand]

Given an array with N elements and integer K . Find sum of longest
increasing sub-sequence of length  K elements such that sub-sequence found
is maximum among all K max su-sequence.

Eg arr[]={5,2,1,10,9,30,8,55}

K = 3
output : 10,30,55sum = 10+30+55 = 95

if K=4
output : 5,10,30,55   sum = 5+10+30+55 =100

-- 
You received this message because you are subscribed to the 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] variation of LIS problem

[atul anand]

@Saurabh Paliwal : yes

On 10/24/13, Saurabh Paliwal saurabh.paliwa...@gmail.com wrote:
 Do you mean
 *of all the increasing subsequences of length k in this array, find the one
 with maximum sum ?*



 On Wed, Oct 23, 2013 at 10:52 PM, atul anand
 atul.87fri...@gmail.comwrote:

 Given an array with N elements and integer K . Find sum of longest
 increasing sub-sequence of length  K elements such that sub-sequence
 found
 is maximum among all K max su-sequence.

 Eg arr[]={5,2,1,10,9,30,8,55}

 K = 3
 output : 10,30,55sum = 10+30+55 = 95

 if K=4
 output : 5,10,30,55   sum = 5+10+30+55 =100

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




 --
  -Saurabh Paliwal

B-Tech. Comp. Science and Engg.

IIT ROORKEE

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


-- 
You received this message because you are subscribed to the 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] Breaking a string problem (Dynamic programming)

[atul anand]

Question seems similar to matrix chain multiplication problemhere you
need to find min cost..
Recurrence for this could be the following , please validate it.

DP(i,j) = j + (j - i) *  min( DP(i , k) , DP(k, j) ) for all i  k  j  i
 j


On Sat, Oct 12, 2013 at 12:54 PM, kumar raja rajkumar.cs...@gmail.comwrote:

 I was not able to figure out  the solution to the problem in CLRS book.

 A certain string-processing language offers a primitive operation which
 splits a string into two pieces. Since this operation involves copying the
 original string, it takes n units of time for a string of length n,
 regardless of the location of the cut. Suppose, now, that you want to break
 a string into many pieces. The order in which the breaks are made can
 affect the total running time. For example, if you want to cut a
 20-character string at positions 3 and 10 (say size of this set is k), then
 making the first cut at position 3 incurs a total cost of 20+17=37, while
 doing position 10 first has a better cost of 20+10=30. So the task is to
 find out which sequence gives the minimum cost and what is that sequence
 out of k! possible sequences.

 I have seen the solutions in stack overflow using divide and conquer, but
 i would like to know how to solve this problem using DP. Someother
 solutions in the web shows it can be solved in O(n^3) or O(n^2) but no
 where i have seen the sub  problem(Optimal substructure) defined.

 I was not able to identify sub problems and make a recurrence relation out
 of it.Can someone please throw light on this? I just want to develop
 approach to solve the DP problems.

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


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

[algogeeks] Generating random number without using rand()

[atul anand]

Hello,
   Given integer N , How to generate random number from 0 to N without
using rand() function.

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

[atul anand]

question is different...here we have to find max of k elements in the
window..not max subarry of size kfoe eg input is say ... 1 4 5 66 7 9
and k=3
then output should be
(1,4,5) = 5
(4,5,66) = 66
(5,66,7)=66
(66,7,9)=66
output - 5,66,66,66
On 19 Sep 2013 19:00, igor.b...@gmail.com igor.b...@gmail.com wrote:

 Hey, isn't it as simple as:

 1. Start at sum of the first K elements.
 2. Move the window of size K by one element to the right at each step.
 Subtract the left, add the right = get the new sum.  Keep the maximum.
 This executes in O(n) steps, requires O(1) memory. The code in C++ seems
to be trivial:

 pairint, int max_k(int a[], int n) {
   int sum_k = accumulate(a, a+k, 0);
   int max_sum = sum_k, max_id = 0;

   for (int i = k; i  n; ++i) {
 sum_k = sum_k - a[i - k] + a[i];
 if (sum_k  max_sum) {
   max_sum = sum_k;
   max_id = i - k + 1;
 }
   }
   return make_pair(max_id, max_sum);
 }
 ... or do I miss something?


 On Wednesday, September 11, 2013 7:14:24 AM UTC-4, 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 aaqui...@gmail.com wrote:

 http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/


 On Tue, Sep 10, 2013 at 11:46 PM, kumar raja rajkuma...@gmail.com
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+...@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+...@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] determine if 2 BSTs will be identical or not based on input order of its keys

[atul anand]

http://www.geeksforgeeks.org/check-for-identical-bsts-without-building-the-trees/


On Thu, Jun 6, 2013 at 11:27 AM, Sambhavna Singh coolsambha...@gmail.comwrote:

 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+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] Spoj FARIDA

[Shashwat Anand]

On Wed, May 22, 2013 at 9:45 AM, emmy foramlakh...@gmail.com wrote:

 problem : http://www.spoj.com/problems/FARIDA/

 what is wrong with this code? The algorithm is pretty straight forward


Is it ?

1000 1 1 1000
Your code gives 1001 as output.  Desired output should be 2000.

  --
 You received this message because you are subscribed to the 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] amazon f2f round question ..

[atul anand]

@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above

On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
 Since it is an acyclic graph, find the appropriate node that can be the
 root of this tree.

 Now apply the logic to find the diameter of the tree here, which finds the
 longest path in the graph as follows:

 int diameter(Tree * t) { if (t == 0) return 0; int lheight =
 height(tree-left); int rheight = height(tree-right); int ldiameter =
 diameter(tree-left); int rdiameter = diameter(tree-right); return
 max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
 int height(Tree * t)
 {
   if (t == 0)
 { return 0; } else { return 1 + max(height(t-left),height(t-right)); } }


 On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com wrote:

 In a connected and acyclic graph,that is a tree, we can apply this
 approach
 1. apply *dfs *on any random node and find the longest distant node from
 this node.Let us say this node i*s u*.
 2. from this no*de u*, again apply* dfs* to find longest distant node
 from this node.Let us say that node is v.
 (u,v) is the required pair of nodes.



 On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:

 Given an acyclic graph. Give an algorithm to find the pair of nodes
 which
 has the maximum distance between them, i.e. the maximum number of edges
 in
 between them


 any suggestion ?


 thanks
 --mac

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




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




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




-- 
You received this message because you are subscribed to the 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 f2f round question ..

[atul anand]

@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo to form a tree , you can
never guarantee that each node will have only 2 child , it can have
more than 2 children.So your terminology of using t-.left and t-right
wont work here.nevertheless it will fail for simple cases mentioned
below :-

given graph :-

(a)-(b)
(a)-(c)
(b)-(c)

output should be (a) - (b) -(c)

now to convert into tree as you have mentioned above you have to
remove edge (b)-(c).

so output will  be (a)-(b) or (a)-(c)
which is wrong.

On 5/12/13, Karthikeyan V.B kartmu...@gmail.com wrote:
 @atul anand : acyclic graph can be converted to a tree using prim/kruskal
 or by finding an appropriate node that can act like the root of a tree


 On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com
 wrote:

 @karthikeyan : It is an acyclic graph not a binary tree. your solution
 will work if given graph is a binary tree.
 problem can be solved using dfs as suggested above

 On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
  Since it is an acyclic graph, find the appropriate node that can be the
  root of this tree.
 
  Now apply the logic to find the diameter of the tree here, which finds
 the
  longest path in the graph as follows:
 
  int diameter(Tree * t) { if (t == 0) return 0; int lheight =
  height(tree-left); int rheight = height(tree-right); int ldiameter =
  diameter(tree-left); int rdiameter = diameter(tree-right); return
  max(lheight + rheight + 1, max(ldiameter,rdiameter)); }
  int height(Tree * t)
  {
if (t == 0)
  { return 0; } else { return 1 + max(height(t-left),height(t-right));
  }
 }
 
 
  On Sat, May 11, 2013 at 10:59 PM, Aman Jain pureama...@gmail.com
 wrote:
 
  In a connected and acyclic graph,that is a tree, we can apply this
  approach
  1. apply *dfs *on any random node and find the longest distant node
  from
  this node.Let us say this node i*s u*.
  2. from this no*de u*, again apply* dfs* to find longest distant node
  from this node.Let us say that node is v.
  (u,v) is the required pair of nodes.
 
 
 
  On Sat, May 11, 2013 at 7:16 PM, MAC macatad...@gmail.com wrote:
 
  Given an acyclic graph. Give an algorithm to find the pair of nodes
  which
  has the maximum distance between them, i.e. the maximum number of
  edges
  in
  between them
 
 
  any suggestion ?
 
 
  thanks
  --mac
 
  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it,
  send
  an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
   --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send
 an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 
 
  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To unsubscribe from this group and stop receiving emails from it, send
  an
  email to algogeeks+unsubscr...@googlegroups.com.
 
 
 

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




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




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

Re: [algogeeks] Re: Find the number of islands/connected components

[atul anand]

{*1*,* 1*, 0, 0, 0},
{0, *1*, 0, 0, *1*},
{*1*, 0, 0, *1*, *1*},
{0, 0, 0, 0, 0},
{*1*, 0, *1*, 0, *1*}

above different set of color represent different island.Simple DFS is
used to find all the island



On Fri, Apr 26, 2013 at 3:11 AM, Don dondod...@gmail.com wrote:

 The complexity is still O(ROWS*COLS) because each location in the
 matrix will be visited once by the loop and once by DFS. Once a
 location has been visited by DFS, it is marked as visited and can't be
 visited again.
 Don

 On Apr 25, 5:11 pm, rahul sharma rahul23111...@gmail.com wrote:
  What will be complexity if all elements in matrix are 1..
 
  when first dfs will call then all matrix will be scanned setting each
  element to visited...
  then again loop contiues to scan all the elements..plz explain
 
  On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma rahul23111...@gmail.com
 wrote:
 
 
 
 
 
 
 
   {*1*,* 1*, 0, 0, 0},
   {0, *1*, 0, 0, *1*},
   {*1*, 0, 0, *1*, *1*},
   {0, 0, 0, 0, 0},
   {*1*, 0, *1*, 0, *1*}
 
   Can anybody eplain how there are 5 islands in above matrix..thnx in
 advance
 
   source:-http://www.geeksforgeeks.org/find-number-of-islands/

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

Re: [algogeeks]

[atul anand]

//code sketch

row_len=R;
col_len=C;
r_start=0,col_start=0;

while (x  R*C)
{
for i=r_start to col_len
   keep extracting value from 1D and add it to mat[r_start][i]=arr[p++];

r_start++;

for i=r_start to row_len
   keep extracting value from 1D and add it to mat[i][col_len]=arr[p++];

col_len--;

for( i=col_len;i=col_start;i--)
   keep extracting value from 1D and add it to mat[row_len][i]=arr[p++];

row_len--;

for( i=row_len ; i =r_start;i--)
   keep extracting value from 1D and add it to
mat[i][col_start]=arr[p++];
col_start++;
}

keep on running above 4 loops till R*C times .
note : take care of 1D array bound , if all values are consumed then fill
with zero , add this checking in every loop.



On Thu, Apr 18, 2013 at 12:34 PM, w.s miller wentworth.miller6...@gmail.com
 wrote:

 given a 1D array.The task is to convert it in to a 2D array and values
 should be filled spirally while filling from 1D array

 the size of 1D array is multiple of a constant say n.
 the number of rows and columns of 2D array will be given.

 say number of rows =R
 say number of columns  = C

 k*n = R*C. where k*n =number of elements in 1D array
 if (R*C  number of elements in 1D array)
 then rest of the values will be zeros.
 e.g.

 n=5; k=3
 R= 6
 C= 3

 input 1D array=[1,0,0,0,1,0,0,0,0,0,1,1,1,1,0]

 output 2D array

 1 0 0 0 1 0
 1 0 0 0 0 0
 1 1 1 0 0 0

 here as 5*36*3 so ..18 -15 = 3

 i.e 3 remaining values are filled as zeros.


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

Re: [algogeeks] Re: Amazon interview question

[Shashwat Anand]

On 4/13/13 10:05 PM, pankaj joshi wrote:

in this Problem if the array is
A[n] = {a0,a1,a(n-1),a(n)}

after the second iteration,
the value will be
{a0 -2*a2+a3, a2 -2*a3 + a4, a3-2*a4+a5,, a(n-2)-2a(n-1)+a(n)}

if we add all these terms then
all the middle elements will be canceled out so the remaining will be.

{a0-a2  - a(n-1)+a(n)}
which can be written as a general form
solution: - {a(n)-a(n-1)} - {a2-a0}
this will solve the problem in time complexity in O(1).

example:  A = {5, 3, 8, 9, 16}
solution : - {16-9}-{3-5}
  {7} - {-2}
   9


No.

Your assertion is valid only for first two iteration.
Iteration 1: { a1 - a0, a2 - a1, ... an - an-1 } = an - a0
Iteration 2: { a2 - 2a1 + a0,  an - 2an-1 + an-2 } = (an - an-1) - 
(a1 - a0)
Iteration 3: an - 2an-1 +an-1 - a2 + 2a1 - a0, thereby nullifying the 
above observation.


At any state T, we need to find f (n, T) where coefficient of T is 0, to 
make it O(1) solution.

That does not seems to be the case here.

Say, for 4th iteration, what will be your answer ?  I don't see any 
closed form here.




On Wed, Apr 10, 2013 at 7:03 AM, Shashwat Anand m...@shashwat.me 
mailto:m...@shashwat.me wrote:


On 4/10/13 12:13 AM, rahul sharma wrote:

If you have any other solution ..please post that...i thnik
recursion is ok with base case...we need to scan again after
first iteration...??

First of all, the array size and number of iteration both won't be
N or else the answer will always be 0.
I take the following assumption, array have K elements and number
of iteration is N.
Now, if N = K, the return value will always be 0.
For rest, we can decompose the array following the rule of
adjacent element difference.

Solution with O(NK) time complexity follows:

int
doit (vector int v, int N) {
int k = (int) v.size () - 1;
if (N  k) return 0;
int c = 1;
while (N--) {
for (int i = k; i = c; i--)
v [i] -= v [i - 1];
for (int i = 0; i  c; i++)
v [i] = 0;
c++;
}
return accumulate (v.begin (), v.end (), 0);
}

int
main ()

int a [] = { 5, 3, 8, 9, 16 };
vector int v (a, a + sizeof (a) / sizeof (a [0]));
assert (doit (v, 0) == 41);
assert (doit (v, 1) == 11);
assert (doit (v, 2) == 9);
assert (doit (v, 3) == -1);
assert (doit (v, 4) == 21);
assert (doit (v, 5) == 0);

return 0;
}

However, I /strongly believe/ the solution can be done in *linear
time*.  To code this with quadratic time complexity is a no-brainer.

So, I took the array with K = 6 elements and decomposed.

N = 0: [a1, a2, a3, a4, a5, a6]  = a1 + a2 + a3 + a4 + a4 + a6
N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] = a6 - a1
N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 -
2a5 + a4] = a6 - a5 - a2 + a1 = (a6 - a5) - (a2 - a1)
N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5
+ 3a4 - a3] = a6 - 2a5 +a4 - a3 + 2a2 - a1
N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 -
4a3 + a2] = a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] = a6 -
5a5 + 10a4 - 10a3 + 5a2 - a1
N = 6: [0, 0, 0, 0, 0, 0] = 0

The resulting solution does show some property of Binomial
coefficient as pointed out by @Don in his hint (Pascal triangle). 
I suppose this shall be the way to attack this problem.



On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma
rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote:

i forgot to add base case..can add wen 2 elemnts are there
then there sum is stored and we reurn from there...i m in
hurry,,,sry for that,,


On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com
mailto:dondod...@gmail.com wrote:

It is O(N^2) because the inner loop takes N steps to
execute and that
loop will be executed N times.

However, I would suggest not using recursion. There is no
reason to
not do it iteratively. Your recursive solution has no
base case so it
will recurse until your computer runs out of stack space,
at which
point it will crash.

Don

On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com
mailto:rahul23111...@gmail.com wrote:
  A = {5, 3, 8, 9, 16}
 After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
 After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
 Given an array, return sum after n iterations

 my sol/
 void abc(int arr[],n)
 {
 for(i=0;in;i++)
 arr[i]=arr[i+1]-arr[i];
 abc(arr,n-1

Re: [algogeeks] Re: Amazon interview question

[Shashwat Anand]

On 4/10/13 12:13 AM, rahul sharma wrote:
If you have any other solution ..please post that...i thnik recursion 
is ok with base case...we need to scan again after first iteration...??
First of all, the array size and number of iteration both won't be N or 
else the answer will always be 0.
I take the following assumption, array have K elements and number of 
iteration is N.

Now, if N = K, the return value will always be 0.
For rest, we can decompose the array following the rule of adjacent 
element difference.


Solution with O(NK) time complexity follows:

int
doit (vector int v, int N) {
int k = (int) v.size () - 1;
if (N  k) return 0;
int c = 1;
while (N--) {
for (int i = k; i = c; i--)
v [i] -= v [i - 1];
for (int i = 0; i  c; i++)
v [i] = 0;
c++;
}
return accumulate (v.begin (), v.end (), 0);
}

int
main ()

int a [] = { 5, 3, 8, 9, 16 };
vector int v (a, a + sizeof (a) / sizeof (a [0]));
assert (doit (v, 0) == 41);
assert (doit (v, 1) == 11);
assert (doit (v, 2) == 9);
assert (doit (v, 3) == -1);
assert (doit (v, 4) == 21);
assert (doit (v, 5) == 0);

return 0;
}

However, I /strongly believe/ the solution can be done in *linear 
time*.  To code this with quadratic time complexity is a no-brainer.


So, I took the array with K = 6 elements and decomposed.

N = 0: [a1, a2, a3, a4, a5, a6]  = a1 + a2 + a3 + a4 + a4 + a6
N = 1: [0, a2 - a1, a3 - a2, a4 - a3, a5 - a4, a6 - a5] = a6 - a1
N = 2: [0, 0, a3 - 2a2 + a1, a4 - 2a3 + a2, a5 - 2a4 + a3, a6 - 2a5 + 
a4] = a6 - a5 - a2 + a1 = (a6 - a5) - (a2 - a1)
N = 3: [0, 0, 0, a4 - 3a3 +3a2 - a1, a5 - 3a4 + 3a3 - a2, a6 - 3a5 + 3a4 
- a3] = a6 - 2a5 +a4 - a3 + 2a2 - a1
N = 4: [0, 0, 0, 0, a5 - 4a4 + 6a3 - 4a2 + a1, a6 - 4a5 + 6a4 - 4a3 + 
a2] = a6 - 3a5 + 2a4 + 2a3 - 3a2 + a1
N = 5: [0, 0, 0, 0, 0, a6 - 5a5 + 10a4 - 10a3 + 5a2 - a1] = a6 - 5a5 + 
10a4 - 10a3 + 5a2 - a1

N = 6: [0, 0, 0, 0, 0, 0] = 0

The resulting solution does show some property of Binomial coefficient 
as pointed out by @Don in his hint (Pascal triangle).  I suppose this 
shall be the way to attack this problem.



On Wed, Apr 10, 2013 at 12:12 AM, rahul sharma 
rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote:


i forgot to add base case..can add wen 2 elemnts are there then
there sum is stored and we reurn from there...i m in hurry,,,sry
for that,,


On Wed, Apr 10, 2013 at 12:11 AM, Don dondod...@gmail.com
mailto:dondod...@gmail.com wrote:

It is O(N^2) because the inner loop takes N steps to execute
and that
loop will be executed N times.

However, I would suggest not using recursion. There is no
reason to
not do it iteratively. Your recursive solution has no base
case so it
will recurse until your computer runs out of stack space, at which
point it will crash.

Don

On Apr 9, 2:29 pm, rahul sharma rahul23111...@gmail.com
mailto:rahul23111...@gmail.com wrote:
  A = {5, 3, 8, 9, 16}
 After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
 After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
 Given an array, return sum after n iterations

 my sol/
 void abc(int arr[],n)
 {
 for(i=0;in;i++)
 arr[i]=arr[i+1]-arr[i];
 abc(arr,n-1);

 }

 I wana ask that the complexity is o(n) or o(n)2..as loop
is executed n
 times..say n is 10...so fxn is called 10 timesi.e  10
n..and ignoring n
 it comes out to be...n..but if we implemeted with 2
loops then
 complexity is n2 ...and both sol are taking same no of
iterations...please
 tell whether complexity is n or n2 for above codeif it
is n2 then how???

--
You received this message because you are subscribed to the
Google Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from
it, send an email to algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@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.




--
You received this message because you are subscribed to the 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] [Algorithm] Get Target

[atul anand]

are we allowed to use operation only once or multilpe times?


On Fri, Mar 22, 2013 at 6:27 AM, prankur gupta duke.lnm...@gmail.comwrote:

 Hi All,

 Could you help me this question.
 This was asked at Yelp Interview.

 Given 6 integers and 1 target value, write a function to get the target
 value using 6 integers with any on these operations +,*,-,/

 Thanks

 --
 PRANKUR GUPTA

 Masters Student (CSE)
 State University of New York
 Stony Brook University
 prgu...@cs.stonybrook.edu

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

Re: [algogeeks] Re: how to solve this?

[Shashwat Anand]

@Dave solution is perfect.  I prefer it over mind.

However, here is an alternate solution.
We know that this is an equation in 'x' with a degree of 1.  It means it is
a straight line and root is guaranteed unless of course the equation is of
the form y = c.  That is not the case here as it would make the equation
with a degree of 0..

Now, say if root is 't' and 'delta1' and 'delta2' being positive values, we
know f(t - delta1) * f (t - delta2)  0.
Why ?
f (t) = 0
All f (t - delta1) will share a common sign (either positive or negative).
 Same for all f (t - delta2), however the sign here will be reverse.  It
depends upon m (slope) but the product of both is guaranteed to be negative.

The graph will be strictly increasing or decreasing.  This provides an
ideal use case for *binary search. *
*
*
We take two extreme values assuming root should lie between them, and do a
binary search over it.
To do that, first of all we bring both side of expression to one side.
 This is not hard even programmatically, can be done in one line of code.

In [1]: s = 2*x+5-(4*x-7+(4-2))=10*x-9

In [2]: s.split ('=')[0] + -1*( + s.split ('=')[-1] + )
Out[2]: '2*x+5-(4*x-7+(4-2))-1*(10*x-9)'

Now, we do a binary search over the expression.

Below is the python code and codepad link [1] since some mail client don't
like indentations.

#!/usr/bin/env python
#-*- coding: utf-8 -*-

def bsearch (exp, lo, hi):
EPS = 0.01
ret = lo + (hi - lo) / 2
while (lo  hi):
mid = lo + (hi - lo) / 2.0
val_mid = eval (exp.replace ('x', str (mid)))
val_lo = eval (exp.replace ('x', str (lo)))
val_hi = eval (exp.replace ('x', str (hi)))
if (val_mid == 0):
return mid
elif (val_lo * val_mid  0):  // Root lies in between lo and mid.
ret = mid
hi = mid - EPS
else:// Root lies in between mid
and hi.
ret = mid
lo = mid + EPS
return ret


s = 2*x+5-(4*x-7+(4-2))-10*x+9
print bsearch (s, -100, 100)

The output,
% python solve.py
1.5886935

Just like Newton bisection method used to calculate roots, we can use
Epsilon to take care of the fact that root does not vary by Epsilon.  The
caveat here however is if we want the answer in the form of
numerator/denominator as in 19/12, it is tough (unless of course we use
fraction module and try some clever optimization, none of which strikes me
so far).

[1] http://codepad.org/85HJj0Eg


On Fri, Apr 5, 2013 at 2:51 AM, Don dondod...@gmail.com wrote:

 I like that solution better than the one I suggested.
 Don

 On Apr 4, 4:45 pm, Dave dave_and_da...@juno.com wrote:
  @Kumar0746: Technically, you can't solve an _expression_; you can solve
 an
  _equation_, which is a statement of the form expression = expression,
 which
  is what you have.
 
  Don's suggestion is a good one. Another way is to call the expression on
  the left side of the equation f(x) and the expression on the right side
 of
  the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then
 
  x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1))
 
  In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and
 g(1)
  = 1, so x = 19/12. Presuming that you want the exact answer, leave it in
  fractional form, and if the denominator is negative, then negate both
  numerator and denominator. Then divide both numerator and denominator by
  their gcd. Finally, if the denominator is 1, report the numerator as the
  answer; otherwise report the fraction numerator/denominator as the
 answer.
 
  Dave
 
 
 
 
 
 
 
  On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote:
   Simplify the expression by evaluating expressions inside parenthesis
   first. Follow the order of evaluation, doing multiplications first and
   then addition and subtraction. It should be possible to reduce any
   expression to the form
   ax+b=0. Then x=-b/a.
   Don
 
   On Apr 4, 11:18 am, arun kumar kumar0...@gmail.com wrote:
Given an expression in the form of a string, solve for x. The highest
   power
of x in the expression will be equal to 1. Operators allowed are +, *
   and
-. These are all binary operators. So, 2x would be written as 2*x.
 Every
operator will be followed by a single term or a constant.
 
For example, consider the following equation:
 
2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a
solution to x

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

Re: [algogeeks] Re: Median in stream of running integers

[atul anand]

@rahul : yes

On 3/24/13, rahul sharma rahul23111...@gmail.com wrote:
 So we need to implement prelocate down for deletion?

 On Sunday, March 24, 2013, atul anand atul.87fri...@gmail.com wrote:
 yeah implementation is wrong.

 On 3/24/13, tec technic@gmail.com wrote:
 The heap implementation is wrong to only prelocate up on deletion top.
 15
   /\
   14  13
  /  \/  \
1211109
/\/\/\/\
   8  7  6  5  4  3  2  1
 For example, for the above heap, when deleteTop is called, 1 is moved to
 top, and heaplify is called on node 9, which does nothing and leave the
 heap in an invalid state.

 Comapring l and r child to find maximum/minimum is only needed in
 prelocate
 down, not in prelocate up.


 2013/3/24 rahul sharma rahul23111...@gmail.com

 And also in heapify y we r not comapring l and r chid to find maximum?


 On Sun, Mar 24, 2013 at 6:07 PM, rahul sharma
 rahul23111...@gmail.comwrote:

 I was goin thorugh question on this link

 http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
 My doubt is y we uses prelocate up in case of deletion also.In
 deletion
 we use pre locate down.But y here we used pre locate up..plz
 xplain.thnx
 in
 advance

 // Heapification
  // Note that, for the current median tracing problem
  // we need to heapify only towards root, always
  void heapify(int i)
  {
  int p = parent(i);

 // comp - differentiate MaxHeap and MinHeap
  // percolates up
  if( p = 0  comp(A[i], A[p]) )
  {
  Exch(A[i], A[p]);
  heapify(p);
  }
  }

  int deleteTop()
  {
  int del = -1;

 if( heapSize  -1)
  {
  del = A[0];

 Exch(A[0], A[heapSize]);
  heapSize--;
  heapify(parent(heapSize+1));
  }

 return del;
  }


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

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

Re: [algogeeks] Least Common Ancestor in STL MAP

[Shashwat Anand]

On 3/21/13 5:02 PM, Avinash wrote:
Given a STL map, say mapint, bool m1. Given two value a  b that may 
or may not exists in m1. Find the Least Common Ancestor in STL MAP. 
Remember you don't have access to root, so you need to iterate using 
iterator. Use the methods/function of MAP forex begin, end, find etc. 
Solution should be efficient in terms of time complexity (forex if we 
use method find, we get it in O(logN) internally) --
You received this message because you are subscribed to the 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.


STP Map is a sorted associative container.  It stores key-value pair, in 
sorted order.
For more information on the above read about map [1] and about sorted 
associative containers. [2]


Map stores key-value pair and use iterators for traversal.
The iterators will either give you next value (forward iterator) or 
previous value (reverse iterator).

The container does *NOT* know, how it is implemented underneath the hood.
Given that you have the knowledge that map is implemented as Red-Black 
tree (a form of balance tree)

in libstd++ you can not abuse the container to tweak the internals.

I can write my own sorted associative container, use whatever data 
structure I want underneath and release it

and it would still be correct.
SGI gives specifications.  Each compiler is free to implement its own 
/internal/ implementation.
The STL does not expose the internals as it would violate OOP 
principles, i.e. exposing the underlying

data structures as it may lead to undesirable behavior.

Think of it like this, say N values are inserted in a map.  You don't 
know where is root, what is the tree structure ?
Hell, you don't even know if that is a tree.  The point is you are not 
supposed to know.
You basically don't know anything apart from two facts: (a) You can get 
``value'' from a given ``key''. (b) You can traverse in sorted or 
reverse-sorted manner.


This /nullifies/ your question.  In case you are interested in LCA, 
create your own Tree structure instead of trying to abuse the de facto 
sorted associative container of the Standard Template Library.



[1] http://www.sgi.com/tech/stl/Map.html
[2] http://www.sgi.com/tech/stl/SortedAssociativeContainer.html

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

Re: [algogeeks] Leaf nodes from inorder traversal

[Shashwat Anand]

Ambiguity lies in the heart of this question.

If you are given a tree and you want to look for leaf nodes  you can 
simply do an inorder traversa,

and check for leaf nodes.
Time complexity will be O(N) and space complexity will be O(log N).

void
getLeafNodes (node *root) {
if (! root) return;
getLeafNodes (root-left);
if (! root-left  ! root-right)  printf (%d , root-data);
getLeafNodes (root-right);
return;
}

However, as @Saurabh told - if you are simply given an array of values 
which would result from inorder traversal,
and not the tree itself, you can *not* create a unique tree.  It follows 
that you can not identify leaf nodes.
In fact with a given number of nodes (say N), there are (1 / (n + 1)) 
*2nCn (catalan number) possibility to form a tree  which annihilates any 
possibility even remote to search for the uniqueness.


Perhaps OP could be lucid.


On 3/16/13 9:48 PM, Saurabh Paliwal wrote:
I don't think so. If I understand your problem well, I have a 
counter-example

take for example - 
Inorder Traversal - 1-2-3
this could mean a binary tree rooted at 2 with 2 leaf nodes 1 and 3
but this could also mean a binary tree rooted at 3 with 2 as its left 
child which in-turn has 1 as its left child (the only leaf node).


On Sat, Mar 16, 2013 at 7:44 PM, Megha Agrawal megha1...@iiitd.ac.in 
mailto:megha1...@iiitd.ac.in wrote:


Hello all,

Is it possible to get leaf nodes from inorder traversal of a
binary tree(not BST)?

-- 
Thank you


-- 
You received this message because you are subscribed to the Google

Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an email to algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.





--
 -Saurabh Paliwal

   B-Tech. Comp. Science and Engg.

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

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.

Re: [algogeeks] FInd unique element.

[atul anand]

use hashmap

On Fri, Feb 22, 2013 at 12:58 AM, marti amritsa...@gmail.com wrote:

 How do I Find the Unique Element that Appears exactly k Times in an Array?
  the problem is given an integer array, only one integer appears* k* times,
 all the other integers appears *m* times in the array (*k**m*). Find out
 that integer.

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

Re: [algogeeks] Question

[atul anand]

related to this problem, link given below :-

http://groups.google.com/group/algogeeks/browse_thread/thread/7cfb0a6f7d121d92/0adc692fad1bab40?hl=enlnk=gstq=DP+equation+for+interval+problem#0adc692fad1bab40

-- 
You received this message because you are subscribed to the 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] Pointers Usage

[atul anand]

@shady : It allows us to allocate m/m dynamically ..which in itself is
very big advantage.
m/m consumption can be ignored , if you compare with the flexibility
it provides.
eg:-

int *arr=(int *)malloc(sizeof(int) * 100);

now  m/m consumption here is 100*4+8;// extra 8 wont hurt if you
compare with the advantage.

another advantage:-
suppose dere are 1000 integer value stored in
m/m...a1,a2,a3,a4a100...now among all these only one is active at
a particular time T.
now to make it more interesting,suppose multiple threads want to find
which one is active at a particular time T.

it would be better if we have int *active pointer.
now anyone among a1,a2,a3a100 becomes active then we store its
address to *active.All threads now just need to synchronize and check
*active pointer to find which one is active at a particular time T
among a1,a2,a3...a10 instead of checking each variable which is
time consuming and may corrupt at some time.
I hope it helps.


now suppose mutiple threads are accessing sam

-- 

Re: [algogeeks] Trie Implementaion Issues

[atul anand]

executed your code..working fine by commenting cmnt2 and un-commenting  cmnt1

-- 

Re: [algogeeks] Re: Coin denomination

[atul anand]

It can be solved using DP

here is the  recurrence eqn:-


coin[ i ] = 1+coin[ i - denom( j ) ] if i =1 and 1 j ArrayLen(denom)
base cases :- c[ i ]= inf  if j  0
c[ i ] = 0   if j==0

On 12/23/12, Dave dave_and_da...@juno.com wrote:
 @Shady. That still didn't answer my question. Maybe I didn't frame it very
 well, so let me try again. Are you naming coins that you have one of or an
 infinite supply of? I.e., if you want to use two of a coin to make a
 certain sum, does it count in the N as one coin or two? More specifically,
 if I want to make 7 as (5,1,1), do I list the coins as (1,5), which is N=2,

 or (1,1,5), which is N=3?

 Dave

 On Saturday, December 22, 2012 4:34:24 AM UTC-6, shady wrote:

 We have *all kinds of denominations (1, 2, 3, R)*... therefore to
 cover this range, we generally select coins like this 1, 2, 4, 8, 16...
 but
 in this case... we can select* any N coins from R*, such that it
 *minimizes
 the average coins used for all values in the range R*... like .

 6 can be represented by 2, 4
 15 - (1, 2, 4, 8)
 10 - (2, 8)



 On Sat, Dec 22, 2012 at 1:59 PM, Dave dave_an...@juno.com
 javascript:wrote:

 @Shady: I'm not sure what you mean by output N coins. With U.S. coins,

 you can need up to 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1
 half-dollar (or 4 pennies, 1 nickel, 2 dimes, and 3 quarters, if you
 don't
 use half-dollars, which are uncommon) to make any amount from 1 to 99
 cents. So should you output distinct coins (1,5,10,25,50), or repeat the

 coins the required number of times (1,1,1,1,5,10,10,25,50)?

 Dave

 On Friday, December 21, 2012 4:01:52 PM UTC-6, shady wrote:

 Given R and N, output N coins in the range from 1 to R such that average

 number of coins needed to represent all the number in the range is
 minimized.

 Any idea ? hints ?

  --






 --




-- 

Re: [algogeeks] Re: Coin denomination

[atul anand]

correction above :-

It can be solved using DP

here is the  recurrence eqn:-


coin[ i ] = 1+ min{ coin[ i - denom( j ) ] } if i =1 and 1 j ArrayLen(denom)
base cases :- c[ i ]= inf  if i  0
c[ i ] = 0   if i==0

-- 

Re: [algogeeks] Sieve

[atul anand]

i had implemented Sieve of Eratosthenes long time back...
what i did was the following :-
say N is the range and we want to find all prime number within this range.
take size of temp array[] to half = N/2...as we only care of odd
numbers.Prime number  2 can be handled explicitly.
run outer loop for
for(i=3 ; i(sqrt(N))/2;i=i+2) // consider only odd i
{
 for(j=i^2; (j/2) N/2 ; j+= i*2) // here I am excluding even multiple
of j by incrementing it by 2*i
set(j,false);
}

when i ran this algo for N=200 , it took 45.302 ms

On Sat, Dec 8, 2012 at 2:44 AM, Don dondod...@gmail.com wrote:

 I know that the Sieve of Eratosthenes is a fast way to find all prime
 numbers in a given range.
 I noticed that one implementation of a sieve spends a lot of time
 marking multiples of small primes as composite. For example, it takes
 1000 times as long to mark off all of the multiples of five as it
 takes to mark off the multiples of 5003. In addition, when it is
 marking off the multiples of larger primes, most of them are multiples
 of small primes. In fact, if it could skip over multiples of 2,3,5,7,
 and 11, the sieve would be about 5 times faster.

 Can someone describe a way to make a sieve faster by not having to
 deal with multiples of the first few prime numbers?

 Don

 --




-- 

Re: [algogeeks] reverse a string efficiently

[atul anand]

considering '+' , here will take Cn time . Here '+' is for concatenate ,
now this concatenation taking place in constant time?? , i dont think
so..internally it will be adding elements to new m/m space and for that it
need to traverse each character...so it will take cn time.
so T(n) =T(n/2) + cn =  nlogn

On Tue, Nov 27, 2012 at 11:17 AM, shady sinv...@gmail.com wrote:

 what is the time complexity of this?

 str_reverse(str){
 if(isempty(str)) return str;
 else if(length(str) = even) then split str into str_1 and str_2; (of
 equal length)
return str_reverse(str_2)+str_reverse(str_1);
 else split str into str_1, str_2, str_3; //if str is odd length, e.g.
 len = 7, split by 1-3 | 4 | 5-7
   return str_reverse(str_3)+str_2+str_reverse(str_1);
 }

 --




-- 

Re: [algogeeks] fastest sequential access

[atul anand]

@shady : as subject says fastest sequential access  , then if i am not
getting it wrong.we only care of sequential access a value not modifying
the linked list.
so i guess double linked list would be helpful
1) bcozz it can move in both the direction , so if linked list is sorted
then it would be a great help
2) if you want to insert element at the end of linked list then if will be
better than vector
so i guess it required 1-2 more parameter to decide ,which one to use.

On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote:

 which data structure among the follow has fastest sequential access ?
 i)   vector
 ii)  Singly linked list
 iii) Doubly linked list

 it won't be doubly linked list as it involves more pointer manipulations
 than singly linked list...

 --




-- 

Re: [algogeeks] Repeating element with constraints

[atul anand]

yes correct...missed that :( , But we can use method given in the above
geekforgeeks link to find those 2 elements :

set_bit_no = xor  ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i  size; i++)
  {
if(arr[i]  set_bit_no)
  x = x ^ arr[i]; /*XOR of first set in arr[] */
else
  y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i = n; i++)
  {
if(i  set_bit_no)
  x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
else
  y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }

  printf(\n The two repeating elements are %d  %d , x, y);

now we just need to check if any of these two elements found is present in
the given array , if yes then other element in the missing one.

On Mon, Nov 19, 2012 at 12:07 PM, Rushiraj Patel rushi4...@gmail.comwrote:

 @atul : In the second for loop...temp will also contain one which is
 being missing along with the one which is being repeated.
 kindly check it once again.


 On Mon, Nov 19, 2012 at 11:44 AM, atul anand atul.87fri...@gmail.comwrote:

  array has all distinct elements ans lie b/w 1 to n , now bcozz they are
 all distinct except 1 element means it should have all element with range 1
 to n...except 1 element ,  which can be any element b/w 1 to n.
 temp=arr[0]
 *for i=1 to n
temp=temp^arr[i]; *
 //now temp will contain all distinct elements except one which is
 repeated(they cancel out)
 *for i=1 to n
 temp=temp ^ i; *
 // now this will cancel out distinct elements excluding one which is
 repeated.
 temp will contain that repeated element

 On Sun, Nov 18, 2012 at 7:31 PM, shady sinv...@gmail.com wrote:

 Given an array of size n, which has all distinct elements between 1 to n
 with one element repeating, which also implies that one element is missing.
 How to find the repeating element without using extra space and linear
 time complexity ?

 Any way to do it with exor ? :P

 --




  --




  --




-- 

Re: [algogeeks] Repeating element with constraints

[atul anand]

array has all distinct elements ans lie b/w 1 to n , now bcozz they are all
distinct except 1 element means it should have all element with range 1 to
n...except 1 element ,  which can be any element b/w 1 to n.
temp=arr[0]
*for i=1 to n
   temp=temp^arr[i]; *
//now temp will contain all distinct elements except one which is
repeated(they cancel out)
*for i=1 to n
temp=temp ^ i; *
// now this will cancel out distinct elements excluding one which is
repeated.
temp will contain that repeated element

On Sun, Nov 18, 2012 at 7:31 PM, shady sinv...@gmail.com wrote:

 Given an array of size n, which has all distinct elements between 1 to n
 with one element repeating, which also implies that one element is missing.
 How to find the repeating element without using extra space and linear
 time complexity ?

 Any way to do it with exor ? :P

 --




-- 

Re: [algogeeks] Tree - sum problem

[atul anand]

from each node , make 4 recursive call
1) you consider this node as part of the solution i.e left=target -
currentNode-data is passed , and consider current-left for next
recursion
2)you consider this node as part of the solution i.e left=target -
currentNode-data is passed , and consider current-right for next
recursion
3) do not consider this node as part of the solution i.e target is
passed  and consider current-left for next
3) do not consider this node as part of the solution i.e target is
passed  and consider current-right for next recursion

keep track of path in an arr[] as you move on.

On 11/15/12, Amitesh Singh singh.amit...@gmail.com wrote:
 Given a binary search tree and a target value, find all the paths (if there
 exists more than one) which sum up to the target value. It can be any path
 in the tree. It doesn't have to be from the root.
 --
 Amitesh

 --




-- 

Re: [algogeeks] Advice needed

[atul anand]

use enum

On Sat, Oct 27, 2012 at 3:21 AM, rahul sharma rahul23111...@gmail.comwrote:

 There is question asked like
 O/p of following in C(32 bit OS)
 #include iostream
  #includestdio.h
 using namespace std;


 bool IsEqual(char * a)
 {
 printf(abc);
 return true;
 }

 int main()
 {
 char str[30];
 printf(%d,sizeof(sizeof(IsEqual(str;
 getchar();
 return 0;
 }
 I run with .cppi know o/p and all in c++...but c doesn't support
 bool.so what should i write in answer as it is asked in written..so wat
 should be writen

 4 i.e the answer in c++ or should i write that c doesn't support bool

 plez comment

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] Check if a binary tree is Binary Search Tree or not.

[atul anand]

@vishal : as discussed in previous post , your solution wont work for
certain test cases...and i dont think so , checking tree in inorder way is
complex .It is simple to implement , you just need to call tree recursively
in Inorder way and  keep track of prev node and compare prev node with
current node if prev node  current then fine move ahead or report fail.

On Tue, Nov 6, 2012 at 12:39 PM, vishal chaudhary
vishal.cs.b...@gmail.comwrote:

 hi all,
 yes you can do it that way, but the thing is why are you increasing the
 complexity of the problem by again checking the inorder traversal output to
 be checked for increasing order.
 just traverse through the ones recursively(as we do it in the inoder
 traversal) through all the nodes and check whether the left child is less
 than the root and root is smaller than the right node.


 Warm Regards
 Vishal Chaudhary
 BE(Hons) Computer Science and Engineering
 BITS Pilani






 On Tue, Nov 6, 2012 at 12:34 AM, shady sinv...@gmail.com wrote:

 Hi,
 Can we check this by just doing an inorder traversal, and then checking
 if it is in increasing order or not ?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] Check if a binary tree is Binary Search Tree or not.

[atul anand]

@vaibhav : by not using extra space...i guess you mean that you were not
allowed to use one extra pointer.bcozz space complexity will remain
constant for inorder approch.

On Tue, Nov 6, 2012 at 1:07 AM, vaibhav shukla vaibhav200...@gmail.comwrote:

 yes ofcourse... dats the easiest i suppose...
 but in one of my interviews, i told this approach, but was then asked not
 to use space (which i was ,to store inorder)
 So for such cases, you must try other approaches as well. (DO inorder,keep
 track of previously visited node and compare it with current node for value
 greater,or less accordingly.)


 On Tue, Nov 6, 2012 at 12:34 AM, shady sinv...@gmail.com wrote:

 Hi,
 Can we check this by just doing an inorder traversal, and then checking
 if it is in increasing order or not ?

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




 --
 best wishes!!
  Vaibhav

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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: Check if a binary tree is Binary Search Tree or not.

[atul anand]

@Don : your algo wont work for following tree :-

   30
  /  \
 20   31
   /  \
  9   41

above tree is not a BST bcozz here 41 should lie on the right side of the
30but it is not.
so we need to keep track of max and min as we move left or right part of
the tree.and each node should lie b/w that min and max range.
for more details : http://www.geeksforgeeks.org/archives/3042

@shady : yes correct..you can do in that way.

On Tue, Nov 6, 2012 at 1:18 AM, Don dondod...@gmail.com wrote:

 That would work. But a simpler approach is:

 bool isBinTree(root *t)
 {
return (!t) || ((!t-left || (t-value  t-left-value)) 
(!t-right || (t-value  t-right-value)) 
isBinTree(t-left)  isBinTree(t-right));
 }

 On Nov 5, 2:04 pm, shady sinv...@gmail.com wrote:
  Hi,
  Can we check this by just doing an inorder traversal, and then checking
 if
  it is in increasing order or not ?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] Time Complexity Analysis

[atul anand]

building tree will take O(n) time but for each node we need to find max i.e
  i = max (inorder, start, end);

so complexity in worst case will we O(n^2).

On Tue, Nov 6, 2012 at 12:26 AM, shady sinv...@gmail.com wrote:

 Sorting takes linear time, but it doesnt get repeated n times,

 it is like - T(n) = 2*T(n/2) + O(n)

 worst case solution is O(n^2)

 it is similar to quick sort


 On Mon, Nov 5, 2012 at 9:15 PM, rahul sharma rahul23111...@gmail.comwrote:

 dude n for build tree and n in this for finding maximun??so n*(n/2)=o(n^2)

 On Mon, Nov 5, 2012 at 8:54 PM, shady sinv...@gmail.com wrote:

 Here the time complexity of the solution should be O(n * log(n))
 http://www.geeksforgeeks.org/archives/21781

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] swap objects without temp variable

[atul anand]

a=a^b;
b=a^b;
a=a^b;

need to check if a and b are equal or not , bcozz a^a =0

On Mon, Nov 5, 2012 at 2:02 AM, manish narayan.shiv...@gmail.com wrote:

 Swapping two objects (not integers/chars),without using temp...?
 my solution is using xor operation..is that right and ny other solutions ?

 --
 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/-/OxVSnZ1QjzMJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] You are given two 32-bit numbers, N and M, and two bit positions, i and j.

[atul anand]

check out my comment ...i had posted it log time back on
geekforgeeks...search for atull007 int the below link.
let me know it does not work
http://www.geeksforgeeks.org/forum/topic/adobe-interview-question-for-software-engineerdeveloper-fresher-about-bit-magic-1

On Thu, Nov 1, 2012 at 4:00 AM, rahul sharma rahul23111...@gmail.comwrote:

 You are given two 32-bit numbers, N and M, and two bit positions, i and j.
 Write a method to set all bits between i and j in N equal to M (e.g., M
 becomes a substring of N located at i and starting at j).
 EXAMPLE:
 Input: N = 100, M = 10101, i = 2, j = 6
 Output: N = 10001010100

 Following is code...guys i think that in line no. 5  (1j) this should
 be replaced with (1j+1).means we have to shift 1 left by j+1 bits..Line
 no. 5 should be
  int left = max - ((1  j+1) - 1);
 plz comment ???

 public static int updateBits(int n, int m, int i, int j) {
 2 int max = ~0; /* All 1’s */
 3
 4 // 1’s through position j, then 0’s
 5 int left = max - ((1  j) - 1);
 6
 7 // 1’s after position i
 8 int right = ((1  i) - 1);
 9
 10 // 1’s, with 0s between i and j
 11 int mask = left | right;
 12
 13 // Clear i through j, then put m in there
 14 return (n  mask) | (m  i);
 15 }

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] Informatica written que : C output

[atul anand]

its seem to me that output buffer is not flushing ..to do so you need
to add \n while printing hello i.e
 printf(Hello\n);

it was working for you when the else {} part was un-commented  because you
are using \n in this statement
//printf( %d - %d \n , tmp[i], count); -- if you remove \n from here
then same problem will be reproduced


On Mon, Oct 29, 2012 at 12:47 PM, Rahul Kumar Patle 
patlerahulku...@gmail.com wrote:

 can anyone explain the reason for weird output producing by this code..
 it is giving output hello many time 30 but as code's logic it should
 print only 9 time
 it runs correctly when i comment out statements inside else{}
 thanks in advance

 #includestdio.h
 #includestdlib.h
 int count = 0;
 main()
 {
 int tmp[10] , i;
 int n = 0;
 for(i=0;i9;i++)
 {
 tmp[i]=fork();
 if(tmp[i]0)
 break;
 else
 {
 //count++;
 printf(Hello);
 //printf( %d - %d \n , tmp[i], count);
 }
 }
 }

 --
 Thanks and Regards:
 Rahul Kumar Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 Indiahttp://www.iitkgp.ac.in/
 Mobile No: +91-8798049298, +91-9424738542
 Alternate Email: rahulkumarpa...@hotmail.com
 [image: 
 Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
 [image: Twitter] https://twitter.com/rahulkumarpatle
 https://www.facebook.com/rkpatle

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] C Macro

[atul anand]

if you think the your expanded version is incorrect.You are wrong ,
because int * will hold pointer but you are not allocating address of
x ..instead you are allocating x value as an address of x to *t.This
wont work.
so to make it work you need to save the address of x and y in temp pointers i.e

   int *p.*q;
p=x;
q=y;
int t;
t=*p;
*p=*q;
*q=t;
now you can convert it into macro.

On 10/29/12, rahul sharma rahul23111...@gmail.com wrote:
 @atul...mistakenly  i have put w at place of t in my last post...i wana say



 On Mon, Oct 29, 2012 at 10:07 AM, dCoder bansal@gmail.com wrote:

 Just replace your macro with its definition and you will understand.

 its not doing swapping of pointers...plz explain



 @dCode i expanded..but its fine...please tell

 #includestdio.h
 #define swap(a,b,c) c t;t=a,a=b,b=t

 int main
 int x=10,y=20;
 int *p,*q;
 swap(x,y,int*);

 int * t;
 t=x;
 x=y;
 y=t;


 There is int* at the end..there is som problem with my
 keyborad...:(.acc to me axpanded version is above..but not swapping
 two pointerssplz comment




 On Sun, Oct 28, 2012 at 9:16 PM, rahul sharma
 rahul23111...@gmail.comwrote:

 its now doing swapping of pointers...plz explain


 On Sun, Oct 28, 2012 at 8:08 PM, atul anand
 atul.87fri...@gmail.comwrote:

 it should swap

 On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
  Why the following code is not able to swap two macros???although it
  is
  easily swapping 2 variables
 
  #includestdio.h
  #define swap(a,b,c) c t;t=a,a=b,b=t
 
 
  int main
 
 
  int x=10,y=20;
  int *p,*q;
 
  swap(x,y,int);
 
  --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 

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


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


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


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



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

Re: [algogeeks] C Macro

[atul anand]

well they should not , if you see it closely  pointer p and q
contain contain address of a and x.
and swap() macro will swap value these pointers are holding i.e adress
of a and xbut will it reflect address of a and x ???...NO
so if you print the address p and q ...before and after the swap then
you should see that after swap p will be holding address of x and
q will be holding address of a..that it

On 10/29/12, rahul sharma rahul23111...@gmail.com wrote:
 I have taken form book...i am writing exact code

 #includestdio.h
 #define swap(a,b,c) c t;t=a,a=b,b=t;


 int main()
 {
 float a,x;
 a=20.0;
 x=30.0;
 float *p,*q;
 p=a,q=x;
 swap(p,q,float*);
 printf(%f %f,a,x);
 getchar();
 }

 o/p=20.000 30.000


 why not swapped???
 On Mon, Oct 29, 2012 at 11:01 PM, atul anand
 atul.87fri...@gmail.comwrote:

 if you think the your expanded version is incorrect.You are wrong ,
 because int * will hold pointer but you are not allocating address of
 x ..instead you are allocating x value as an address of x to *t.This
 wont work.
 so to make it work you need to save the address of x and y in temp
 pointers i.e

int *p.*q;
 p=x;
 q=y;
 int t;
 t=*p;
 *p=*q;
 *q=t;
 now you can convert it into macro.

 On 10/29/12, rahul sharma rahul23111...@gmail.com wrote:
  @atul...mistakenly  i have put w at place of t in my last post...i wana
 say
 
 
 
  On Mon, Oct 29, 2012 at 10:07 AM, dCoder bansal@gmail.com wrote:
 
  Just replace your macro with its definition and you will understand.
 
  its not doing swapping of pointers...plz explain
 
 
 
  @dCode i expanded..but its fine...please tell
 
  #includestdio.h
  #define swap(a,b,c) c t;t=a,a=b,b=t
 
  int main
  int x=10,y=20;
  int *p,*q;
  swap(x,y,int*);
 
  int * t;
  t=x;
  x=y;
  y=t;
 
 
  There is int* at the end..there is som problem with my
  keyborad...:(.acc to me axpanded version is above..but not
 swapping
  two pointerssplz comment
 
 
 
 
  On Sun, Oct 28, 2012 at 9:16 PM, rahul sharma
  rahul23111...@gmail.comwrote:
 
  its now doing swapping of pointers...plz explain
 
 
  On Sun, Oct 28, 2012 at 8:08 PM, atul anand
  atul.87fri...@gmail.comwrote:
 
  it should swap
 
  On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
   Why the following code is not able to swap two macros???although
   it
   is
   easily swapping 2 variables
  
   #includestdio.h
   #define swap(a,b,c) c t;t=a,a=b,b=t
  
  
   int main
  
  
   int x=10,y=20;
   int *p,*q;
  
   swap(x,y,int);
  
   --
   You received this message because you are subscribed to the Google
  Groups
   Algorithm Geeks group.
   To post to this group, send email to algogeeks@googlegroups.com.
   To unsubscribe from this group, send email to
   algogeeks+unsubscr...@googlegroups.com.
   For more options, visit this group at
   http://groups.google.com/group/algogeeks?hl=en.
  
  
 
  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
   --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
   --
  You received this message because you are subscribed to the Google
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 
  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 

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



 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit

Re: [algogeeks] four umbers sum to given value

[atul anand]

becoz you are sorting the aux[] , it seems to fine by replacing it with i  j

On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
 I wana ask that ccan i replcae while condiion with the condition as follow
 while(ij)

 code reference :http://www.geeksforgeeks.org/archives/23338
 void findFourElements (int arr[], int n, int X)
 {
 int i, j;

 // Create an auxiliary array to store all pair sums
 int size = (n*(n-1))/2;
 struct pairSum aux[size];

 /* Generate all possible pairs from A[] and store sums
of all possible pairs in aux[] */
 int k = 0;
 for (i = 0; i  n-1; i++)
 {
 for (j = i+1; j  n; j++)
 {
 aux[k].sum = arr[i] + arr[j];
 aux[k].first = i;
 aux[k].sec = j;
 k++;
 }
 }

 // Sort the aux[] array using library function for sorting
 qsort (aux, size, sizeof(aux[0]), compare);

 // Now start two index variables from two corners of array
 // and move them toward each other.
 i = 0;
 j = size-1;
 while (i  size  j =0 )
 {
 if ((aux[i].sum + aux[j].sum == X)  noCommon(aux[i], aux[j]))
 {
 printf (%d, %d, %d, %d\n, arr[aux[i].first], arr[aux[i].sec],
  arr[aux[j].first], arr[aux[j].sec]);
 return;
 }
 else if (aux[i].sum + aux[j].sum  X)
 i++;
 else
 j--;
 }
 }

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] C Macro

[atul anand]

it should swap

On 10/28/12, rahul sharma rahul23111...@gmail.com wrote:
 Why the following code is not able to swap two macros???although it is
 easily swapping 2 variables

 #includestdio.h
 #define swap(a,b,c) c t;t=a,a=b,b=t


 int main


 int x=10,y=20;
 int *p,*q;

 swap(x,y,int);

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] C Macro

[atul anand]

didnt get you... first it was now working , now its working...!!!
 please write clearly about your doubts.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Design a method to find the frequency of occurrences of any given word in a book.

[atul anand]

Trie or hash map can b used

On 10/24/12, rahul sharma rahul23111...@gmail.com wrote:


 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] adobe questions

[atul anand]

use hash map...with key as original node and value as duplicate of this
node duplicate node next and random pointer is set to NULL initially.
now traverse whole linked list keep on adding node.
after this do another traversal of orig linked list taking key as orig
node ..duplicate=fetch value at this key(orig)
make duplicate node next and random ptr to
duplicate-next=fetch_value_from_hash(orig-next)
duplicate-random=fetch_value_from_hash(orig-random)

On Tue, Oct 23, 2012 at 2:06 PM, saket narayan.shiv...@gmail.com wrote:

 There is one linked list having two pointer one as usual next and other is
 random pointer pointing to any random node in list.
 write algo to make a duplicate of it.
 Note:- Original list is const, Can't be modified.
 i know O(n) solution when list can be modified , and o(n^2) when list can
 be modified.
 any one with O(n) solution when list couldnt be modified .

 --
 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/-/5RLLbA5iod0J.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] fibonicci recursive help

[atul anand]

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

On 10/21/12, rahul sharma rahul23111...@gmail.com wrote:
 Guys i have read an article somewhere regarding optimization of recursive
 fibonicci so that we donot need to calculate the sum that we have already
 calculated...

 In case if factorial,we donot need to find factorial that we have already
 calculated...

 I just forgot where i read from..may br from coreman ..but i am not able to
 find this again in coreman..may be i have read online..anybody please shar
 link from whr i can read these..it would be of great help..thnx in advance

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] Longest increasing subsequence

[atul anand]

@rahul : nope it wont work ..check for this input :-

input = 1, 2,3,6,4 ,101, 6

by removing  msis[i]  msis[j] + arr[i] condition then you are
excluding the max sub-sequence found from j=0 to i.


On 10/21/12, rahul sharma rahul23111...@gmail.com wrote:
 but if there are -ve numbers then arr[i]arr[j] only is sufficeient as it
 become falsecomment if wrng

 On Sat, Oct 20, 2012 at 11:59 PM, Saurabh Kumar
 srbh.ku...@gmail.comwrote:

 If your inputs are only positive numbers then that condition you pointed
 out is indeed redundant. But if you want your program to work for
 negative
 numbers as well, you need that condition.
 Also, you should initialize max = msis[0]; before running the loop for
 calculating 'max' :


 /* Pick maximum of all msis values */
  max = msis[0];for ( i = 0; i  n; i++ )
if ( max  msis[i] )
   max = msis[i];


 On 20 October 2012 22:58, rahul sharma rahul23111...@gmail.com wrote:

 http://www.geeksforgeeks.org/archives/19248
   /* Dynamic Programming implementation of Maximum Sum Increasing
 Subsequence (MSIS) problem */
  #includestdio.h

 /* maxSumIS() returns the maximum sum of increasing subsequence in arr[]
 of
 size n */
  int maxSumIS( int arr[], int n )
  {
 int *msis, i, j, max = 0;
 msis = (int*) malloc ( sizeof( int ) * n );

/* Initialize msis values for all indexes */
 for ( i = 0; i  n; i++ )
msis[i] = arr[i];

/* Compute maximum sum values in bottom up manner */
 for ( i = 1; i  n; i++ )
for ( j = 0; j  i; j++ )
   if ( arr[i]  arr[j]  msis[i]  msis[j] + arr[i])
  msis[i] = msis[j] + arr[i];

/* Pick maximum of all msis values */
 for ( i = 0; i  n; i++ )
if ( max  msis[i] )
   max = msis[i];

/* Free memory to avoid memory leak */
 free( msis );

return max;
  }

 /* Driver program to test above function */
  int main()
  {
int arr[] = {1, 101, 2, 3, 100, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
printf(Sum of maximum sum increasing subsequence is %d\n,
   maxSumIS( arr, n ) );

   getchar();
return 0;
  }
  I wana ask inner for loop has two conditons ...cant we remove condition
 onryt of  operator.
  As miss[j] would containg arr[j]or arr[j]+somethngif arr[i]arr[j]
 then miss[i] is always miss[j]+arrp[i]
  so cant we remove second condtion of  operator plz correct if m
 wrng

 --
 You received this message because you are subscribed to the Google
 Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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] fibonicci recursive help

[atul anand]

google searched it : geeksforgeeks + Fibonacci  number ;) ;)

On 10/21/12, rahul sharma rahul23111...@gmail.com wrote:
 thnx a lot atul...was looking for that only...can u plz tell me under which
 section u get this post
 On Sun, Oct 21, 2012 at 4:03 PM, atul anand atul.87fri...@gmail.com
 wrote:

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

 On 10/21/12, rahul sharma rahul23111...@gmail.com wrote:
  Guys i have read an article somewhere regarding optimization of
  recursive
  fibonicci so that we donot need to calculate the sum that we have
  already
  calculated...
 
  In case if factorial,we donot need to find factorial that we have
  already
  calculated...
 
  I just forgot where i read from..may br from coreman ..but i am not
  able
 to
  find this again in coreman..may be i have read online..anybody please
 shar
  link from whr i can read these..it would be of great help..thnx in
 advance
 
  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from 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] Microsoft Interview Question

[atul anand]

@Rahul : yes i know and actually i posted this query on geeksforgeeks.
you can find my solution in comments , search for atul007 in the provided
link.It will work for all cases. now to find all path you need to do small
modification on the same code.

On Tue, Oct 16, 2012 at 9:31 AM, Rahul Kumar Patle 
patlerahulku...@gmail.com wrote:

 @atul: in your solution object only can move down or right direction. but
 in my problem object is free to move in any direction and hence there are
 chances of cycle.. how to memoize cycle.
 if there is cycle then your approach will give infinite solution.

 consider this maze
 1  1  0  0  0
 1  1  0  0  0
 0  1  1  0  0
 0  1  1  0  0
 0  0  1  1  1

 you can see that object can take path
 M[0][0] - M[0][1] - M[1][1]- M[1][2]- M[][]- M[][]
 OR
 M[0][0] - M[1][0] - M[1][1]- M[1][2]- M[][]- M[][]
 But simple approach will also take path
 M[0][0] - M[0][1] - M[1][1]- M[1][0]- M[0][0]- M[0][1]  -- CYCLE

 how you will avoid these cycles...

 On Tue, Oct 16, 2012 at 8:58 AM, atul anand atul.87fri...@gmail.comwrote:

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


 On Tue, Oct 16, 2012 at 8:56 AM, atul anand atul.87fri...@gmail.comwrote:

 can be done simply by backtracking .

 On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle 
 patlerahulku...@gmail.com wrote:

 Pls help to solve this que.. does any one have DP solution for following
 que.

 http://www.geeksforgeeks.org/archives/24488
 section 5/question 2

 Write a program to find all the possible paths from a starting point to
 dest point in a maze(2-D array).

 ex:1 0 1 0
1 1 1 1
0 1 0 1
0 0 1 1

 If there is a block it’s represented by 0.
 If there is a path it’s represented by 1.



 --
 Thanks and Regards:
 Rahul Kumar Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 Indiahttp://www.iitkgp.ac.in/
 Mobile No: +91-8798049298, +91-9424738542
 Alternate Email: rahulkumarpa...@hotmail.com
 [image: 
 Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
 [image: Twitter] https://twitter.com/rahulkumarpatle
 https://www.facebook.com/rkpatle

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



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




 --
 Thanks and Regards:
 Rahul Kumar Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 Indiahttp://www.iitkgp.ac.in/
 Mobile No: +91-8798049298, +91-9424738542
 Alternate Email: rahulkumarpa...@hotmail.com
 [image: 
 Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
 [image: Twitter] https://twitter.com/rahulkumarpatle
 https://www.facebook.com/rkpatle

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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: Microsoft Interview Question

[atul anand]

@jaspreet : i dont find much difference between using BFS or
backtracking...which is doing similar to DFS.

On Tue, Oct 16, 2012 at 4:28 AM, Jaspreet Singh
jassajjassaj...@gmail.comwrote:

 BFS


 On Sun, Oct 14, 2012 at 4:21 PM, Rahul Kumar Patle 
 patlerahulku...@gmail.com wrote:

 response awaited!!!
 anyone??

 On Sat, Oct 13, 2012 at 12:31 AM, Rahul Kumar Patle 
 patlerahulku...@gmail.com wrote:

 Pls help to solve this que.. does any one have DP solution for following
 que.

 http://www.geeksforgeeks.org/archives/24488
 section 5/question 2

 Write a program to find all the possible paths from a starting point to
 dest point in a maze(2-D array).

 ex: 1 0 1 0
 1 1 1 1
 0 1 0 1
 0 0 1 1

 If there is a block it’s represented by 0.
 If there is a path it’s represented by 1.



 --
 Thanks and Regards:
 Rahul Kumar Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 Indiahttp://www.iitkgp.ac.in/
 Mobile No: +91-8798049298, +91-9424738542
 Alternate Email: rahulkumarpa...@hotmail.com
 [image: 
 Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
 [image: Twitter] https://twitter.com/rahulkumarpatle
 https://www.facebook.com/rkpatle




 --
 Thanks and Regards:
 Rahul Kumar Patle
 M.Tech, School of Information Technology
 Indian Institute of Technology, Kharagpur-721302, 
 Indiahttp://www.iitkgp.ac.in/
 Mobile No: +91-8798049298, +91-9424738542
 Alternate Email: rahulkumarpa...@hotmail.com
 [image: 
 Linkedin]http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
 [image: Twitter] https://twitter.com/rahulkumarpatle
 https://www.facebook.com/rkpatle

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.