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.

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

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

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