Re: [algogeeks] Re: GOOGLE Q1

[Vandana Bachani]

In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.

public void longestAP(int[] a, int n) {
 int[] diff = new int[n-1];
 for(int i = 0; i < n-1; i++) {
  diff[i] = a[i+1]-a[i];
 }
 int maxDiff = diff[0], maxi = 0, maxCount = 1;
 int currentDiff = -1, currentCount = 0, currenti = -1;
 for(int i = 1; i < n-1; i++) {
  if(diff[i] == maxDiff) { maxCount++; }
  else {
   if(diff[i] == currentDiff) { currentCount++; if (currentCount >
maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi =
currenti;}}
   else {
currentDiff = diff[i]; currenti = i; currentCount = 1;
   }
  }
 }
 System.out.print("Elements of the AP: ") ;
 for(int i = maxi; i <= maxi+maxCount; i++) {
  System.out.print(a[i]+" ");
 }
 System.out.println();
}

On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt  wrote:

>
>
> On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:
>
>
>> Given an array of integers A, give an algorithm to find the longest
>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
>> such that
>>
>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
>> largest possible.
>>
>> The sequence S1, S2, …, Sk is called an arithmetic progression if
>>
>> Sj+1 – Sj is a constant.
>>
> Click on the following links or copy and paste them  into your browser.
> Many interesting possibilities.
>
> https://www.google.com.au/search?client=ubuntu&channel=fs&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1&ie=utf-8&oe=utf-8&redir_esc=&ei=GpQRUZXnJKaeiAen7oDYAw
>
>
> http://scholar.google.com/scholar?hl=en&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.&btnG=&as_sdt=1%2C5&as_sdtp=
>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/**profile.php?id=10655377926<https://www.facebook.com/profile.php?id=10655377926>*
>>
>>  --
> You received this message because you are subscribed to the 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.
>
>
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the 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] Need Help with PHP/HTML

[Vandana Bachani]

Hi,
You need to correct ur form tag. Try:


Thanks,
Vandana

On Mon, Jul 16, 2012 at 12:42 PM, Nandita Raman
wrote:

> Hello,
>
> I am working on PHP/HTML/ XML-RPC.
>
> I have a website, where one link shows the list of files as checkboxes and
> a submit button below that.
>
> I am stuck at point where when submit button is clicked, it has to go to
> another .php page and execute whatever is there in that .php file.
>
>
>  => I have tried and does not seem
> like its working.
>
> I would really appreciate any thoughts/inputs/help with this!
>
> Thanks!
>
> --
>
> Regards,
> Nandita
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] how to approach this kinda problmls

[Vandana Bachani]

A bunch of optimizations are possible like caching via hashing PDS numbers
as u find for prior inputs so that some of those can be used for next
inputs, etc. But first try to develop a simple algorithm.

-Vandana

On Fri, Apr 20, 2012 at 2:48 PM, Vandana Bachani wrote:

> hi Amrit,
> First you should try to write a module (function) which identifies if a
> number is a PDS number, basically given a number it checks whether the
> product of its digits is divisible by the sum of its digits.
> Then you should start an infinite loop and keep counting the PDS number u
> encounter starting from 1, until the count is N (as given in the input).
> You need to repeat this until the input is exhausted (i.e. the input is
> zero).
> Gather the inputs in an array first and then run the whole process on the
> array.
>
> Thanks,
> Vandana
>
> On Fri, Apr 20, 2012 at 1:19 PM, amrit harry wrote:
>
>> http://www.codechef.com/APRIL12/problems/PDSNUM
>>
>> --
>> 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/-/6NhjBLnaw0AJ.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Vandana Bachani
> Graduate Student, MSCE
> Computer Science & Engineering Department
> Texas A&M University, College Station
>
>


-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] how to approach this kinda problmls

[Vandana Bachani]

hi Amrit,
First you should try to write a module (function) which identifies if a
number is a PDS number, basically given a number it checks whether the
product of its digits is divisible by the sum of its digits.
Then you should start an infinite loop and keep counting the PDS number u
encounter starting from 1, until the count is N (as given in the input).
You need to repeat this until the input is exhausted (i.e. the input is
zero).
Gather the inputs in an array first and then run the whole process on the
array.

Thanks,
Vandana

On Fri, Apr 20, 2012 at 1:19 PM, amrit harry wrote:

> http://www.codechef.com/APRIL12/problems/PDSNUM
>
> --
> 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/-/6NhjBLnaw0AJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] program to convert roman to integer.........

[Vandana Bachani]

/Convert roman to decimal
#include

int convert(char *s, int len)
{
  int i = 0, d = 0, prev = 0;
  for(;i < len; i++)
  {
switch(*(s+i))
{
  case 'i': d += 1;
break;
  case 'v': if(i!=0 && *(s+prev) == 'i')
{
  d = d + 5 - 2;
}
else
  d += 5;
  break;
  case 'x': if(i!=0 && *(s+prev) == 'i')
{
  d = d + 10 - 2;
}
else
  d += 10;
break;
}
prev = i;
  }
  return d;
}
main()
{
  char s[] = "xix";
  int len = 0, d;
  while(s[len] != '\0')
len++;
  len++;
  d = convert((char *)s,len);
  printf("%d\n", d);
}


On Sun, Nov 6, 2011 at 11:15 AM, rahul sharma wrote:

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



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Dp solution for this problem?

[Vandana Bachani]

Hi Mohit,
Bellman-Ford algorithm is a dynamic programming algorithm but u need it
only if dijkstra's SP wont solve the problem... and Dijkstra's algo works
only for +ve weights. So if u r sure that there maybe negative weights then
you will need to use bellmann ford which is a DP algo.

On Mon, Oct 31, 2011 at 7:40 AM, mohit verma  wrote:

> I knew this could be done using Min Path finding algo. But what about DP
> for this problem , guys?
>
> On Mon, Oct 31, 2011 at 3:49 AM, SAMM  wrote:
>
>> This can be done using the Dijkstra's algorithm , Start frm the source
>> frm the Destination (In this example from (2 2)) . You need to
>> consider the index of the array as the the vertices and the weigjht as
>> the the value for the movement from the present vertex to it's
>> connecting neighbour ..
>>
>> On 10/31/11, mohit verma  wrote:
>> > Given a matrix you have to find the shortest path from one point to
>> another
>> > within the matrix. The cost of path is all the matrix entries on the
>> way.
>> > You can move in any direction (up, down, left, right, diagonally)
>> >
>> > e.g.
>> >
>> > 5 9 10 1
>> > 3 7 4 4
>> > 8 2 1 9
>> >
>> > So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost
>> -
>> > 5+3+2+1=11
>> >
>> > I dont think some DP solution exist for this problem.Can it be?
>> >
>> >
>> > --
>> > Mohit
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>>
>> --
>> Somnath Singh
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Mohit
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Dp solution for this problem?

[Vandana Bachani]

Consider each element of the matrix as a node of a graph. Connect the nodes
to the adjacent nodes (up, down, left, right or diagonal) using directed
edges having weight equal to the weight of the node it is incident on, eg.
any edge coming into (0,0) with have weight 5. Given the starting point to
find the shortest path, create a source node with an edge from that going
to the start node with the weight equal to the value of that node.
Find shortest path distance from the new source node to required
destination node.
If the matrix always has +ve values then dijkstra's shortest path algorithm
(greedy) will also do, else Bellman Ford should be able to help (DP).
G = (V, E), V = {source, (0,0), (0,1), etc.}, |V| = m*n+1, |E| = ((2) or
(3) or (5))*m*n + 1

-Vandana

On Sun, Oct 30, 2011 at 2:22 PM, mohit verma  wrote:

> Given a matrix you have to find the shortest path from one point to
> another within the matrix. The cost of path is all the matrix entries on
> the way. You can move in any direction (up, down, left, right, diagonally)
>
> e.g.
>
> 5 9 10 1
> 3 7 4 4
> 8 2 1 9
>
> So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost -
> 5+3+2+1=11
>
> I dont think some DP solution exist for this problem.Can it be?
>
>
> --
> Mohit
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] FACEBOOK ONLINE CODING ROUND

[Vandana Bachani]

Completing it... Got sent before I completed

On Wed, Oct 19, 2011 at 12:31 PM, Vandana Bachani wrote:

> Better logic:
> create a list array of lists 'arr' (like a hash table with lists). Array
> size is N represents 1 to N bits and lists that will increase as we add more
> elements to it. a.
> for(i = 1; i <= 2^N; i++)
> {
>c = count no. of 1s. in i
>add i to list arr[c-1].
>
}
>
   for (i = 0; i <  N; i++)
   {
  print list arr[i]
   }

>
> On Wed, Oct 19, 2011 at 12:16 PM, Vandana Bachani 
> wrote:
>
>> Hi,
>> logic:
>> We can work on this problem from the way we construct the sequence.
>> First we generate a binary tree such that each leafnode corresponds to one
>> of the 2^N nodes. We start we an empty root, creating 0, 1 nodes assigning
>> one bit at a time upto N levels (there would be 2^N - leafnodes) but while
>> doing that we can assign weights and values to each node as we construct the
>> tree. (In a breadth first fashion). node.weight = node.parent.weight + 0/1
>> (based on whether it lies on the 0th edge (left edge) of the parent or the
>> 1th edge (right edge) of the parent, we can say 0 ad 1 are respective edge
>> weights) and node.value = node.parent.value*2 + 0/1.
>> We will add the leaf nodes to an array(sequence) as they get created when
>> we reach "nth" level in the tree. Sort the array of nodes by weight and by
>> value in case of tie.
>>
>> -Vandana
>>
>> On Wed, Oct 19, 2011 at 10:33 AM, aritra kundu 
>> wrote:
>>
>>> *Question 1 / 1*
>>> Given an integer *N*, there are *2^N* binary codewords of length N. All
>>> of them are taken and sorted to create a sequence: Sort by the number of
>>> 1-bits in the codeword bit-string. If there is a tie, break tie so that the
>>> smaller number comes first in the output sequence
>>>
>>> *Testcases format:*
>>> You would be given 2 integers *N* (<=10) and *K* (1 <= K <= 2^N)
>>> Output the codeword with index K into this sequence
>>> The input is from stdin and output to stdout
>>>
>>> *Sample Testcases:*
>>> *Input #00:*
>>> 3 5
>>> *Output #00:*
>>> 011
>>> *Explanation:*
>>> For N = 3, the sequence consists of {000,001,010,100,011,101,110,
>>> 111}. The 5th indexed number would be 011
>>>
>>> *Input #01:*
>>> 7 127
>>> *Output #01:*
>>> 110
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] FACEBOOK ONLINE CODING ROUND

[Vandana Bachani]

Better logic:
create a list array of lists (like a hash table with lists). Array size is N
represents 1 to N bits and lists that will increase as we add more elements
to it.
for(i = 1; i < 2^N; i++)
{
   c = count no. of 1s. in i


}

On Wed, Oct 19, 2011 at 12:16 PM, Vandana Bachani wrote:

> Hi,
> logic:
> We can work on this problem from the way we construct the sequence.
> First we generate a binary tree such that each leafnode corresponds to one
> of the 2^N nodes. We start we an empty root, creating 0, 1 nodes assigning
> one bit at a time upto N levels (there would be 2^N - leafnodes) but while
> doing that we can assign weights and values to each node as we construct the
> tree. (In a breadth first fashion). node.weight = node.parent.weight + 0/1
> (based on whether it lies on the 0th edge (left edge) of the parent or the
> 1th edge (right edge) of the parent, we can say 0 ad 1 are respective edge
> weights) and node.value = node.parent.value*2 + 0/1.
> We will add the leaf nodes to an array(sequence) as they get created when
> we reach "nth" level in the tree. Sort the array of nodes by weight and by
> value in case of tie.
>
> -Vandana
>
> On Wed, Oct 19, 2011 at 10:33 AM, aritra kundu wrote:
>
>> *Question 1 / 1*
>> Given an integer *N*, there are *2^N* binary codewords of length N. All
>> of them are taken and sorted to create a sequence: Sort by the number of
>> 1-bits in the codeword bit-string. If there is a tie, break tie so that the
>> smaller number comes first in the output sequence
>>
>> *Testcases format:*
>> You would be given 2 integers *N* (<=10) and *K* (1 <= K <= 2^N)
>> Output the codeword with index K into this sequence
>> The input is from stdin and output to stdout
>>
>> *Sample Testcases:*
>> *Input #00:*
>> 3 5
>> *Output #00:*
>> 011
>> *Explanation:*
>> For N = 3, the sequence consists of {000,001,010,100,011,101,110,
>> 111}. The 5th indexed number would be 011
>>
>> *Input #01:*
>> 7 127
>> *Output #01:*
>> 110
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] FACEBOOK ONLINE CODING ROUND

[Vandana Bachani]

Hi,
logic:
We can work on this problem from the way we construct the sequence.
First we generate a binary tree such that each leafnode corresponds to one
of the 2^N nodes. We start we an empty root, creating 0, 1 nodes assigning
one bit at a time upto N levels (there would be 2^N - leafnodes) but while
doing that we can assign weights and values to each node as we construct the
tree. (In a breadth first fashion). node.weight = node.parent.weight + 0/1
(based on whether it lies on the 0th edge (left edge) of the parent or the
1th edge (right edge) of the parent, we can say 0 ad 1 are respective edge
weights) and node.value = node.parent.value*2 + 0/1.
We will add the leaf nodes to an array(sequence) as they get created when we
reach "nth" level in the tree. Sort the array of nodes by weight and by
value in case of tie.

-Vandana

On Wed, Oct 19, 2011 at 10:33 AM, aritra kundu wrote:

> *Question 1 / 1*
> Given an integer *N*, there are *2^N* binary codewords of length N. All of
> them are taken and sorted to create a sequence: Sort by the number of 1-bits
> in the codeword bit-string. If there is a tie, break tie so that the smaller
> number comes first in the output sequence
>
> *Testcases format:*
> You would be given 2 integers *N* (<=10) and *K* (1 <= K <= 2^N)
> Output the codeword with index K into this sequence
> The input is from stdin and output to stdout
>
> *Sample Testcases:*
> *Input #00:*
> 3 5
> *Output #00:*
> 011
> *Explanation:*
> For N = 3, the sequence consists of {000,001,010,100,011,101,110,
> 111}. The 5th indexed number would be 011
>
> *Input #01:*
> 7 127
> *Output #01:*
> 110
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Memorization

[Vandana Bachani]

Hi Arvind,
For the fibonacci series, we need to memoize only the the last 2 fibonacci
numbers.
We can even avoid recursion... So our regular fibonacci algorithm is the
simplest example of a dynamic programming algorithm with memoization.

To find nth fibonacci number:

int p = 0, q = 1, f;
for (int i  = 1; i <= n; i++)
{
  f = p + q;
  p = q;
  q = f;
}

But as gene mentioned, in complex programs involving dynamic programming we
might need to access more than 1 or 2 previously obtained values. To reduce
the burden of recalculating old values, we preserve them in a
hash/table/array, as the case might be and access them directly from there.
One of the most important properties of dynamic programming is that the
solutions to sub-problems are reused, which can be achieved with
memoization.

-Vandana

On Tue, Oct 11, 2011 at 3:17 AM, arvind kumar  wrote:

> ya ya,realy sorry..typo!its MEMOIZATION.
>
> On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg  wrote:
>
>> Memoization ?
>>
>>
>> On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar wrote:
>>
>>> Can anyone tell me how to go about with the memorization technique to
>>> retrieve values from already stored values,in case of eveluating
>>> sequences(fibonacci series,etc).?
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] Efficient Algo for Merging 2 Binary Search Trees

[Vandana Bachani]

Inorder traversal of one tree insert into another?

On Sat, Oct 8, 2011 at 4:33 PM, Ankur Garg  wrote:

> Hi ,
>
> Can anyone think of any better for doing this other than converting into
> List and then converting back again to BST ..
>
> Regards
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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 ques

[Vandana Bachani]

You have the right braces missing, it would result in a 0 depth for all
cases. (Precedence of != is greater than =)

On Tue, Jul 12, 2011 at 5:41 PM, nicks  wrote:

> i thought of this code..i think it should work.correct me if i am
> wrong
>
>
> depth=0;max=0;
> while(*(*c=getchar()*)*!=EOF)
> {
>  if(c== '{' )
>  {
>   depth+=1
>   if(depth>max)
>max=depth;
>  }
> else if(c== '}' )
> {
>   depth-=1;
> }
> }
>
>
> On Tue, Jul 12, 2011 at 4:55 PM, Sandeep Jain wrote:
>
>> If we just have to give the depth as in count then, I believe we can use
>> stack to push/pop curly braces. While maintaining the maximum depth observed
>> And if we have to display/print line numbers or code itself, then
>> converting the code in a tree structure should help.
>> Each node can contain the line/col position of starting/closing braces.
>> Each node will have its nested braces as child nodes.
>>
>> PS: In either case make sure you ignore comments and strings literals
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>> On Tue, Jul 12, 2011 at 4:43 PM, shilpa gupta 
>> wrote:
>>
>>> Write down the c code for finding out the maximum scope depth in a c
>>> code. A scope
>>> depth is increased by one with every '{' and decreases by one with
>>> every '}'
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>>
>
>
> On Tue, Jul 12, 2011 at 4:55 PM, Sandeep Jain wrote:
>
>> If we just have to give the depth as in count then, I believe we can use
>> stack to push/pop curly braces. While maintaining the maximum depth observed
>> And if we have to display/print line numbers or code itself, then
>> converting the code in a tree structure should help.
>> Each node can contain the line/col position of starting/closing braces.
>> Each node will have its nested braces as child nodes.
>>
>> PS: In either case make sure you ignore comments and strings literals
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>> On Tue, Jul 12, 2011 at 4:43 PM, shilpa gupta 
>> wrote:
>>
>>> Write down the c code for finding out the maximum scope depth in a c
>>> code. A scope
>>> depth is increased by one with every '{' and decreases by one with
>>> every '}'
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] finding vlaue of nCr

[Vandana Bachani]

Why cant we first cancel the higher denominator first?
Eg: For 10C3, 10!/(7!*3!) can be written as (10*9*8)/3!. This will be a
little more performing if the difference in n/2 and r is significant.

On Tue, Jun 21, 2011 at 1:09 PM, uttam tiwari  wrote:

> i think it can be done by look ups..i.e. we start wid the smallest
> no..evaluate the factorial of dat n den using dis we can get the
> factorial of a bigger no..
> ex.
> to calculate 10c3 we shud hav 3!, 7!, 10!, now firstly we evaluate 3!,
> den using dis evaluate 7! as 7!=7*6*5*4*3!
> n again  10!=10*9*8*7!...
>  i think d order can be minimized apprecialby...correct me if m wrong...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] [brain teaser] Aeroplane Hijack puzzle 30 may

[Vandana Bachani]

The hijacker was the "pilot".

On Mon, May 30, 2011 at 12:34 PM, Lavesh Rawat wrote:

> *Aeroplane Hijack puzzle SOLUTION
>  *
> *
> *
> **
> *A man hijacks an aeroplane transporting both passengers(8 of them) and
> valuable cargo. After taking the cargo, the man demands nine parachutes,
> puts one of them on, and jumps, leaving the other eight behind. Why did he
> want eight?
> **
> *
>
> *Update Your Answers at* : Click 
> Here
>
> Solution:
>
> Will be updated after 1 day
>
>
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] [brain teaser] MATHS TRICK TEASER 9 may

[Vandana Bachani]

1 from 19 makes 20
11 + 9 = 20 (take the one away from 19 and attach it to the other one and
put a + between the 2)

-Vandana

On Tue, May 10, 2011 at 12:39 PM, Lavesh Rawat wrote:

> *MATHS TRICK TEASER
>  *
> *
> *
> **
> *Prove that taking away 1 from 19 makes 20.
> *
>
> *Update Your Answers at* : Click 
> Here
>
>
> Solution:
> Will be updated after 1 day
>
>
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] [brain teaser ] NUMBER SEQUENCE PUZZLE 9 may

[Vandana Bachani]

Corrected.

On Mon, May 9, 2011 at 5:57 PM, Vandana Bachani wrote:

> The answer is 3.
>
> Its a sequence of the number of characters in the word form of the index.
>
> "one", "two", "three", "four", "five", "six", "seven"
> 3, 3, 5, 4, 4, 3, 5
>
>
> On Mon, May 9, 2011 at 12:52 PM, Lavesh Rawat wrote:
>
>>   NUMBER SEQUENCE PUZZLE
>> **
>> *
>> *
>> **
>> *Fill in the blanks:
>> 3 3 5 4 4 ? 5
>> **
>> *
>>
>> *Update Your Answers at* : Click 
>> Here<http://dailybrainteaser.blogspot.com/2011/05/number-sequence-puzzle-9-may.html?lavesh=lavesh>
>>
>>
>> Solution:
>> Will be updated after 1 day
>>
>>
>>
>>
>> --
>>
>> "Never explain yourself. Your friends don’t need it
>> and your enemies won’t believe it" .
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

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

Re: [algogeeks] [brain teaser ] NUMBER SEQUENCE PUZZLE 9 may

[Vandana Bachani]

The answer is 3.

Its a sequence of the number of digits in the word form of the index.

"one", "two", "three", "four", "five", "six", "seven"
3, 3, 5, 4, 4, 3, 5

On Mon, May 9, 2011 at 12:52 PM, Lavesh Rawat wrote:

>  NUMBER SEQUENCE PUZZLE
> **
> *
> *
> **
> *Fill in the blanks:
> 3 3 5 4 4 ? 5
> **
> *
>
> *Update Your Answers at* : Click 
> Here
>
>
> Solution:
> Will be updated after 1 day
>
>
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] [brain teaser ] sequence number puzzle 18april

[Vandana Bachani]

A funny one... until I figure out...
It contains all numbers from 0 to 10 :P

On Mon, Apr 18, 2011 at 1:58 PM, Lavesh Rawat wrote:

> * sequence number puzzle
>
> What is special about the following sequence of numbers?
> 8 5 4 9 1 7 6 10 3 2 0
> *
> *Update Your Answers at* : Click 
> Here
>
> Solution:
> Will be updated after 1 day
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] please explain the output

[Vandana Bachani]

Hi Arvind,
These are preprocessor specific operators. Check out
http://msdn.microsoft.com/en-us/library/wy090hkc(v=vs.80).aspx

-Vandana

On Tue, Apr 5, 2011 at 12:45 PM, Arvind  wrote:

> #include
>
> #define f(a,b) a##b
> #define g(a) #a
> #define h(a) g(a)
>
> int main()
> {
> printf("%s",g(f(1,2)));
> printf("\t%s",h(f(1,2)));
> return 0;
> }
>
>
>
> i have run this program in gcc compiler and getting : f(1,2) 12 as
> output.
> can anyone explain the reason for getting this output?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] [brain teaser ] 2april

[Vandana Bachani]

Letter 'e'

On Mon, Apr 4, 2011 at 1:14 PM, Lavesh Rawat  wrote:

> *WHAT AM I Problem Solution*
> *
> *The beginning of eternity. The end of time and space. The beginning of
> every end and the end of every place. What am I?
>
> *Update Your Answers at *: Click 
> Here
>
> Solution:
> Will be updated after 1 day
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] [brain teaser ] 31march

[Vandana Bachani]

1, 2, 3

On Thu, Mar 31, 2011 at 2:21 PM, Lavesh Rawat wrote:

> *Find Numbers Problem *
> *
> *Find three whole, positive numbers that have the same answer when
> multiplied together as when added together.
>
> Update Your Answers at : Click 
> Here
>
> Solution:
> Will be updated after 1 day
>
>
> --
>
> "Never explain yourself. Your friends don’t need it and
> your enemies won’t believe it" .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] [brain teaser ] 29march

[Vandana Bachani]

T(5) = 41 + 3^4 = 122.

On Thu, Mar 31, 2011 at 2:16 PM, Vandana Bachani wrote:

> T(n) = T(n-1) + 3^(n-1), T(0) = 1
>
> On Thu, Mar 31, 2011 at 11:20 AM, rahul  wrote:
>
>> 1+1+0, 2+2+1, 5+5+4, 14+14+13, 41+41+40
>>
>> On Tue, Mar 29, 2011 at 1:05 PM, Lavesh Rawat wrote:
>>
>>> *Series Problem Solution*
>>>
>>> 1, 2, 5, 14, 41, x
>>> Whats x ??
>>>
>>> Update Your Answers at : Click 
>>> Here<http://dailybrainteaser.blogspot.com/2011/03/29march.html?lavesh=lavesh>
>>>
>>> Solution:
>>> Will be updated after 1 day
>>>
>>>
>>> --
>>>
>>> "Never explain yourself. Your friends don’t need it
>>> and your enemies won’t believe it" .
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] [brain teaser ] 29march

[Vandana Bachani]

T(n) = T(n-1) + 3^(n-1), T(0) = 1

On Thu, Mar 31, 2011 at 11:20 AM, rahul  wrote:

> 1+1+0, 2+2+1, 5+5+4, 14+14+13, 41+41+40
>
> On Tue, Mar 29, 2011 at 1:05 PM, Lavesh Rawat wrote:
>
>> *Series Problem Solution*
>>
>> 1, 2, 5, 14, 41, x
>> Whats x ??
>>
>> Update Your Answers at : Click 
>> Here
>>
>> Solution:
>> Will be updated after 1 day
>>
>>
>> --
>>
>> "Never explain yourself. Your friends don’t need it
>> and your enemies won’t believe it" .
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: puzzle

[Vandana Bachani]

The ant needs to cover: 9.403 units. It will need to pass the diagonal of
the side (4 by 5) and go up or down the side 3 units.
3+ sqrt(16+25)

On Fri, Dec 31, 2010 at 4:16 PM, bittu  wrote:

>
> 2nd puzzle
>
> An ant has to crawl from one corner of a room to the diametrically
> opposite corner as quickly as possible. If the dimensions of the room
> are 3 x 4 x 5, what distance does the ant cover?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MS

[Vandana Bachani]

Hi Harshal,
The question is a bit unclear, especially given the *win and *def* pattern.
Does it mean anything before "win" is acceptable or anything before and
after "def" is acceptable? or is it like 'a' repeated any number of times
followed by 'b' repeated any number of times... in a*b*cd*?
I am assuming the pattern match has to looking for any character wherever
'*' is given. Thats the first one I mentioned above.
The solution to the second kind will be a little more involved.

This is how I would think of implementing it:

we should have a list of wildcards we support, suppose for now we support
only '*'
1. The search string can be called our query.
2. the query can be splitted into substrings whereever a wild card appears.
special cases include it appears in beginning and end.
3. we need to find the splitted strings, if they appear in the same order in
the as they appear in the query
for doing this we could have an array of the substrings and the indexes
at which they appear in the text,
if the indexes of appearances are in ascending order we know the
substrings exist.
the index of appearance of first and last substring might be needed in
the final response if we need to tell where exactly the string appears. For
now this will be able to handle only one occurrence of the pattern and can
be reformed to include more than one occurrences.
4. our next step includes matching to see if they fit as per our wild cards.
for * in beginning the of query the start index of the response could be the
beginning of the text similarly for end it could be the end of text given
step 3 returned a positive response, i.e substrings exist in order. if other
wildcards are involved we can think of checking the behaviour differently.

If we assume '*' means repetition of the previous char given:
1. we will have to start the parse the text along with the query.
2. looking for the first char (having a * in beginning doesnt make sense in
this case) in the query in the text. if there is a wild card, we look for
the wild card behavior in the text, repetition, etc.wherever the behavior
seems to end we look ahead in the query to see which is the character after
the wild card in the query if it matches with the character in text we move
further on the query and text or reset the query parse pointer to point to
beginning of query string. if the second character is not a wild card, we
just do a match and move forward if we find it in text or reset query
parsing pointer.
3. in the end if the query matches the text at any place we can fill the
response start and end pointers. for multiple occurrences if we havent
reached end of file we can reset query pointer and start finding the
complete match again.
** cases like a*ab*c may not be handled by this.

-V

On Sat, Oct 16, 2010 at 6:21 PM, Harshal  wrote:

> Given a text file, implement a solution to find out if a pattern
> similar to wild cards can be detected.
> for example find if a*b*cd*, or *win or *def* exists in the text.
>
> how to take care of wild cards?
>
> --
> Harshal Choudhary
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.