Re: [algogeeks] Sorting a very large number of intergers

[Avi Dullu]

Hint 1: If taken the assumption that you have ~6GB RAM (out of this 3.7GB
is for the input itself) you do not need any external sorting to do this.

Hint 2: 1,000,000,000 < (2 << 30)

Hint 3: Read this  up

On Thu, Jun 13, 2013 at 2:06 AM, MAC  wrote:

> How would one sort 1 billion integers.  .. I gave external sorting answer
> but he waned more .. What should i say ?
>



Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.

-- 
You received this message because you are subscribed to the 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: Google Interview Question: In how many intervals does a number exists

[Avi Dullu]

Can you tell the 'size' of your array 'f' if the intervals are [0, 10],
[10, 9223372036854775808] ?

Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.


On Mon, Jun 10, 2013 at 10:12 PM, sunny  wrote:

> yeah interval tree and binary indexed tree is a one solution which will
> give you answer in log(n) time for each query ,but if i got all the
> interval at the beigning of time i can get solution in O(1) time by O(n
> ) preprocessing take array f initialize with zero,now for each
> interval(l,r) do f[l]++ and f[r+1]--  once you are done wi all queries take
> prefix sum value of each index will tell you in how many interval it was
>
>
> On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>>
>> There are n Intervals. Given a set of m numbers, tell in how many
>> intervals does each number exists.
>> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
>> For 2 -> 1 as 2 lies only in 1 interval [2,3]
>> For 4 -> 3 as 4 lies in 3 intervals
>> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>>
>> It can be easily done in O(m*n) by traversing n intervals for each number
>> in the given set of m numbers. How would improve this?
>>
>> Note: I could not fully recall, but I have seen very similar question in
>> codechef but could not find the same.
>>
>  --
> You received this message because you are subscribed to the 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] Google Interview Question: In how many intervals does a number exists

[Avi Dullu]

Read up on Interval trees .

Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.


On Sun, Jun 9, 2013 at 12:20 AM, Monish Gupta wrote:

> There are n Intervals. Given a set of m numbers, tell in how many
> intervals does each number exists.
> Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
> For 2 -> 1 as 2 lies only in 1 interval [2,3]
> For 4 -> 3 as 4 lies in 3 intervals
> For 11 -> 0 as 11 lies in none of the given 4 intervals.
>
> It can be easily done in O(m*n) by traversing n intervals for each number
> in the given set of m numbers. How would improve this?
>
> Note: I could not fully recall, but I have seen very similar question in
> codechef but could not find the same.
>
> --
> You received this message because you are subscribed to the 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] Infinite stream , identify distinct k kintegers

[Avi Dullu]

(For very large k case only)

Keep as many elements in the hash_map as you can. Once the map capacity is
exhausted, sort all the elements in the hash_map and write them to disk and
build a bloom filter. Keep this bloom
filterin memory, empty the
hash_map and now for every new number in the stream,
check in the bloom filter, if it says does not exist, that means this is a
new number, insert in the map. If it says the number does exist, then this
can be a false positive, then first check in the map, if not found in it,
it could be on disk. Use a binary search on the file (this will take
O(logn) disk seeks) and verify if its present in the file or not. If
present, ignore, else add in the map. Keep repeating the process of
flushing the map to disk whenever the map is full. To flush, you could
either use any external
sortingmethod, or just
write out a new file each time. If separate files, you will
need to binary search in all of them in case of false positive.

Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the "scripture" of this age.


On Sat, Jun 1, 2013 at 10:19 PM, MAC  wrote:

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

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

Re: [algogeeks] amazon f2f round question ..

[Avi Dullu]

My bad, I wrote "out degree" where I should have written "in degree".
My proposal:
Topological Sort <http://en.wikipedia.org/wiki/Topological_sorting> the
graph and keep removing the nodes from vertices which have "in degree" of 0
(given the DAG, there will always be at least one such vertex).
For a BST, since just root has an in degree of 0, start by removing the 2
out nodes from it. Now you will have 2 vertices with in degree as 0, repeat
this for each of them. The last vertex which will be left i.e. the one
without any out degree will be one end of your solution and the root will
be the other. Essentially, for a BST this problem is equal to finding the
depth of the tree.

 Also I made a blunder by assuming the graph is directed (DAG). The
question does not say graph is directed or undirected. This approach will
work for DAG. For undirected, convert the graph in to a directed graph
first and then start with the vertices whose in degree is 1.


Veni Vedi Slumber !


On Fri, May 24, 2013 at 6:19 AM, MAC  wrote:

> kindly explain  visualizing a balanced BST as a graph   and unable to
> underdstand your point
>
>
> thanks
> --mac
>
>
> On Fri, May 24, 2013 at 6:04 AM, Avi Dullu  wrote:
>
>>
>> On Sat, May 11, 2013 at 10:29 AM, Aman Jain  wrote:
>>
>>> 2. from this no*de u*, again apply* dfs* to find longest distant node
>>> from this node.Let us say that node is v.
>>>
>>
>> Small doubt about the solution. Consider this graph a -> b -> c -> d
>>
>> You randomly choose vertex 'b' and do a DFS. Your "u" will be vertex 'd'.
>> Then you do DFS from d, but its out degree is 0.
>> So your DFS ends at 'd' itself and you report the solution as b->c->d.
>> But the solution is a->b->c->d. What did I miss?
>>
>> My proposal:
>> Topological Sort <http://en.wikipedia.org/wiki/Topological_sorting> the
>> graph and keep removing the nodes from vertices which have out degree of 0
>> (given the DAG, there will always be atleast one such vertex). Rest is self
>> explanatory :)
>>
>>
>> Veni Vedi Slumber !
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

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

Re: [algogeeks] amazon f2f round question ..

[Avi Dullu]

On Sat, May 11, 2013 at 10:29 AM, Aman Jain  wrote:

> 2. from this no*de u*, again apply* dfs* to find longest distant node
> from this node.Let us say that node is v.
>

Small doubt about the solution. Consider this graph a -> b -> c -> d

You randomly choose vertex 'b' and do a DFS. Your "u" will be vertex 'd'.
Then you do DFS from d, but its out degree is 0.
So your DFS ends at 'd' itself and you report the solution as b->c->d. But
the solution is a->b->c->d. What did I miss?

My proposal:
Topological Sort  the
graph and keep removing the nodes from vertices which have out degree of 0
(given the DAG, there will always be atleast one such vertex). Rest is self
explanatory :)


Veni Vedi Slumber !

-- 
You received this message because you are subscribed to the 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] stack. Mid element in o(1)

[Avi Dullu]

Code is here . Logic is made clear by the
variable names. Idea is similar to the one which is used to build a queue
using 2 stacks.


On Wed, May 22, 2013 at 8:45 AM, MAC  wrote:

> I think this is only possible if you make sure that at push you store the
> middle element with the top element as well .. this would mean push would
> cease to be o(1)   & become o(n) .. . or is there some other trick ?
>



Veni Vedi Slumber !

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

[Avi Dullu]

Another alternative soln.

int rec_cut(int l, int k) {
  if (l == k) return 0;
  int tmp = k - (l>>1);
  return 1 + rec_cut(l>>1, tmp <= 0 ? k : tmp);
}

int main() {
  int l, k;
  scanf("%d%d", &l, &k);
  printf("%d\n", rec_cut(l, k));
  return 0;
}

Veni Vedi Slumber !


On Sat, Jul 2, 2011 at 9:47 PM, varun pahwa wrote:

> @sunny thnx for the correction.
>
>
> On Sat, Jul 2, 2011 at 9:16 AM, varun pahwa wrote:
>
>> @sunny ya  i wanted to write the while(k % m == 0)
>>
>>
>> On Sat, Jul 2, 2011 at 3:47 AM, sameer.mut...@gmail.com <
>> sameer.mut...@gmail.com> wrote:
>>
>>> n&n-1  is the expression to find out if n is a power of 2...If n&n-1
>>> returns 0 its a power of 2 else its not.
>>> And what sunny said is also ryt
>>>
>>>
>>> On Sat, Jul 2, 2011 at 3:47 PM, sunny agrawal 
>>> wrote:
>>>
 @cegprakash
 Expression resets the least significant set bit


  On Sat, Jul 2, 2011 at 3:20 PM, mohit goel 
 wrote:

> May be this can work.give any counter example...
> int count;
> main()
> {
>   int l,rope,cuts;
>   scanf("%d%d",&l,&rope);
>   count =0;
>
>find_cuts(l,rope);
>printf("cuts needed is %d",count);
>getch();
>return 0;
>}
>
>  int find_cuts(int l,int rope)
>
>  {
>
> if(l==rope)
> return count;
>  count++;
>  printf("%d",count);
>  l=l/2;
>  if(l==rope)
>  return count;
>  if(rope>l)
>  rope =rope-l;
>
>  find_cuts(l,rope);
>
>
>  }
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



 --
 Sunny Aggrawal
 B-Tech IV year,CSI
 Indian Institute Of Technology,Roorkee

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.
>>>
>>
>>
>>
>> --
>> Varun Pahwa
>> B.Tech (IT)
>> 7th Sem.
>> Indian Institute of Information Technology Allahabad.
>> Ph : 09793899112 ,08011820777
>> Official Email :: rit2008...@iiita.ac.in
>> Another Email :: varunpahwa.ii...@gmail.com
>>
>> People who fail to plan are those who plan to fail.
>>
>>
>
>
> --
> Varun Pahwa
> B.Tech (IT)
> 7th Sem.
> Indian Institute of Information Technology Allahabad.
> Ph : 09793899112 ,08011820777
> Official Email :: rit2008...@iiita.ac.in
> Another Email :: varunpahwa.ii...@gmail.com
>
> People who fail to plan are those who plan to fail.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] null macro

[Avi Dullu]

#include 

#define NULL1 (void *)0
#define NULL2 0

int main() {
  int* p = NULL1;  // void* being assigned to a int*, C++ complains.
  int* q = NULL2;
  return 0;
}

Veni Vedi Slumber !


On Sat, Jul 2, 2011 at 10:28 PM, Decipher  wrote:

> Hey I was asked this question in Broadcom's interview. I thought its worth
> to share it here since its related to null pointer  :
>
> What's the dif b/w #define NULL (void*)0 and #define NULL 0 ?
>
>  --
> 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/-/mtyvsP4WoGIJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Taking Input

[Avi Dullu]

#include 
#include 
#include 

int main() {
  int n, num, i;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
char ch = '#';
printf("scanned from %d line: ", i + 1);
while (ch != '\n') {
  scanf("%d%c", &num, &ch);
  printf("%d ", num);
}
printf("\n");
  }
  return 0;
}

Better?

Veni Vedi Slumber !


On Sun, Jul 3, 2011 at 2:47 AM, anonymous procrastination <
opamp1...@gmail.com> wrote:

> Hey Thanks,,
> I got it.. when I press enter after entering the number it takes that
> as an empty string.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] Re: Microsoft - DP problem

[Avi Dullu]

@^ Just check ur solution for boundary case ( n = 2) .. M$ is *generally*
very strict about such mistakes :)


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Thu, Jan 20, 2011 at 11:05 PM, Davin  wrote:

> static int MaxLoot(int[] A, int n)
>{
>int[] S = new int[n];
>S[0] = A[0];
>S[1] = A[1];
>S[2] = S[0] + A[2];
>
>
>int maxloot = Math.Max(S[1], S[2]);
>
>
>
>for (int i = 3; i < n; i++)
>{
>S[i] = Math.Max(S[i - 2], S[i - 3]) + A[i];
>maxloot = Math.Max(maxloot, S[i]);
>}
>
>
>
>return maxloot;
> }
>
> On Jan 20, 7:30 pm, Manmeet Singh  wrote:
> > It can be done in O(n) space too using DP :) :).
> > U dont need that flag, but that solution u said is absolutely correct.
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Jan 20, 2011 at 7:27 PM, Decipher 
> wrote:
> > > There is a row of houses in which each house contains some amount of
> money.
> > > Write an algorithm that loots the maximum amount of money from these
> houses.
> > > The only restriction is that you cannot loot two houses that are
> directly
> > > next to each other.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
> 
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] C++ Doubt

[Avi Dullu]

extending the above example

Base B;

DerivedClasses D1, D2;

B's content   -> {content_of_B }
D1's content -> { content_of_B, }
D2's content -> { content_of_B, }

Can you see the reason now? The above is a very simplified example, think of
virtual classes too :).


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Thu, Jan 20, 2011 at 10:21 PM, yq Zhang  wrote:

> The reason is simple. The same thing happen in other language such as JAVA.
> You can convert Derived class to Base class but you can't convert Derived[]
> to Base[]. The reason is, if your Base class has two derived classes D1, D2.
> They can exist in Base[] because D1, D2 are valid Base instances. While you
> doing converting from Base[] to D1[], it's not possible, because in Base
> there are other D2 instances. To avoid these common mistakes, converting
> from Derived[] to Base[] it not allowed.
>
> Yq
>
>
> On Thu, Jan 20, 2011 at 5:54 AM, Decipher  wrote:
>
>> When we can convert Derived* to Base* then why can't we convert Derived**
>> to Base** ??
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

Sry I misunderstood your comment. I don't "feel" the greedy solution which
you gave will work in all the cases. Will update the thread when I next
sleep over it.

Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Mon, Jan 17, 2011 at 9:39 AM, SVIX wrote:

> @avi... i didn't quite fully understand the intent of the comment... u
> had initially said greedy would make wrong choices 3->5->4 and hence
> give wrong minimum number of jumps while DP would give 3->4... hence i
> responded saying that if we go greedy on a different function, greedy
> will yield the right result as well... and in a shorter time
>
> On Jan 16, 12:28 pm, Avi Dullu  wrote:
> > @svix that is precisely the reason why i gave my greedy approach first
> and
> > then the pseudo code and then the example, also I mentioned that greedy
> can
> > be be of different *locally optimal policies* so they *may* have a higher
> > running time than the corresponding DP solution.
> >
> > regarding "your algorithm should be greedy on" .. it depends solely on me
> as
> > to what I want to be greedy upon, given that I can provide a proof that
> the
> > approach will always work. Like in interval scheduling problem there are
> > numerous different greedy scheduling policies, but just one can be proved
> to
> > work for all the cases.
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> > On Mon, Jan 17, 2011 at 1:52 AM, SVIX  >wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @avi
> >
> > > regarding ur statement...
> >
> > > "
> > > 3, 5, 3, 4, 1, 3, 4, 5
> >
> > > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > > whereas DP would take 3, 4 ( 2 steps)
> > > "
> >
> > > it depends on what you are greedy about... as i had mentioned earlier,
> > > your algorithm should be greedy on how far the value you choose will
> > > let you jump and not just on the size of the value... i.e, get the
> > > local maximum for (currentIndex + array[currentIndex])
> >
> > > that is,
> >
> > > input: 3, 5, 3, 4, 1, 3, 4, 5
> > > index 0  1  2  3  4  5  6  7
> >
> > > when index = 0, u can choose items at index 1, 2 and 3... go greedy on
> > > f(index) = index + array[index]
> >
> > > so f(1) = 1 + 5 = 6
> > >f(2) = 2 + 3 = 5
> > >f(3) = 3 + 4 = 7
> >
> > > plainly, if u define ur greedy criteria right, u go for index 3...
> >
> > > On Jan 15, 11:15 pm, Avi Dullu  wrote:
> > > > The greedy will always chose the maximum, so iff a 0 is chosen, that
> > > implies
> > > > one cannot reach the end of the array.
> >
> > > > Programmers should realize their critical importance and
> responsibility
> > > in a
> > > > world gone digital. They are in many ways similar to the priests and
> > > monks
> > > > of Europe's Dark Ages; they are the only ones with the training and
> > > insight
> > > > to read and interpret the "scripture" of this age.
> >
> > > > On Sun, Jan 16, 2011 at 12:16 PM, SVIX <
> saivivekh.swaminat...@gmail.com
> > > >wrote:
> >
> > > > > thinkin abt this again, there may be a slight problem with
> > > > > straightforward greedy...
> > > > > note that reaching 0 doesn't let u move forward...
> >
> > > > > On Jan 15, 12:54 pm, Avi Dullu  wrote:
> > > > > > @jammy Thanx for the elongated description :)
> >
> > > > > > Yes, I feel I probably gave a DP solution wrongly to the Greedy
> > > approach.
> > > > > > But just to clarify, Greedy does not solve any subproblems, it
> just
> > > makes
> > > > > a
> > > > > > locally optimal choice and proceedes towards a global optimal
> > > strategy.
> > > > > And
> > > > > > your point that greedy usually takes lesser time tha

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

@svix that is precisely the reason why i gave my greedy approach first and
then the pseudo code and then the example, also I mentioned that greedy can
be be of different *locally optimal policies* so they *may* have a higher
running time than the corresponding DP solution.

regarding "your algorithm should be greedy on" .. it depends solely on me as
to what I want to be greedy upon, given that I can provide a proof that the
approach will always work. Like in interval scheduling problem there are
numerous different greedy scheduling policies, but just one can be proved to
work for all the cases.


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Mon, Jan 17, 2011 at 1:52 AM, SVIX wrote:

> @avi
>
> regarding ur statement...
>
> "
> 3, 5, 3, 4, 1, 3, 4, 5
>
> in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> whereas DP would take 3, 4 ( 2 steps)
> "
>
> it depends on what you are greedy about... as i had mentioned earlier,
> your algorithm should be greedy on how far the value you choose will
> let you jump and not just on the size of the value... i.e, get the
> local maximum for (currentIndex + array[currentIndex])
>
> that is,
>
> input: 3, 5, 3, 4, 1, 3, 4, 5
> index 0  1  2  3  4  5  6  7
>
> when index = 0, u can choose items at index 1, 2 and 3... go greedy on
> f(index) = index + array[index]
>
> so f(1) = 1 + 5 = 6
>f(2) = 2 + 3 = 5
>f(3) = 3 + 4 = 7
>
> plainly, if u define ur greedy criteria right, u go for index 3...
>
> On Jan 15, 11:15 pm, Avi Dullu  wrote:
> > The greedy will always chose the maximum, so iff a 0 is chosen, that
> implies
> > one cannot reach the end of the array.
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> > On Sun, Jan 16, 2011 at 12:16 PM, SVIX  >wrote:
> >
> > > thinkin abt this again, there may be a slight problem with
> > > straightforward greedy...
> > > note that reaching 0 doesn't let u move forward...
> >
> > > On Jan 15, 12:54 pm, Avi Dullu  wrote:
> > > > @jammy Thanx for the elongated description :)
> >
> > > > Yes, I feel I probably gave a DP solution wrongly to the Greedy
> approach.
> > > > But just to clarify, Greedy does not solve any subproblems, it just
> makes
> > > a
> > > > locally optimal choice and proceedes towards a global optimal
> strategy.
> > > And
> > > > your point that greedy usually takes lesser time than DP also stands
> > > > correct, but there are a lot of exceptions wherein the choice of
> local
> > > > optimal strategy may be of very high order, and thus perform worse
> than
> > > DP.
> >
> > > > Just to rest (and clarify) my argument, the following is the greedy
> > > approach
> > > > I feel, *will* fail:
> >
> > > > for i = 1; i < n; i++
> > > >   next_jump_will_be_from_index = index of max(input[  i ... i +
> input[i]
> > >  ])
> >
> > > > i.e. after each jump, greedy strategy is to choose the next jumping
> point
> > > as
> > > > the one which has maximum value
> >
> > > > 3, 5, 3, 4, 1, 3, 4, 5
> >
> > > > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > > > whereas DP would take 3, 4 ( 2 steps)
> >
> > > > and if you notice, the implementation of this greedy (without using
> fancy
> > > > RMQ/segment trees) would still be O(n^2) or O(nlogn) (using
> RMQ/segment
> > > > trees)
> >
> > > > Programmers should realize their critical importance and
> responsibility
> > > in a
> > > > world gone digital. They are in many ways similar to the priests and
> > > monks
> > > > of Europe's Dark Ages; they are the only ones with the training and
> > > insight
> > > > to read and interpret the "scripture" of this age.
> >
> > > > On Sun, Jan 16, 2011 at 1:39 AM, Jammy 
> wrote:
> > > > > @svix, I think pacific means takes i+v, But it still won't

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

The greedy will always chose the maximum, so iff a 0 is chosen, that implies
one cannot reach the end of the array.


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sun, Jan 16, 2011 at 12:16 PM, SVIX wrote:

> thinkin abt this again, there may be a slight problem with
> straightforward greedy...
> note that reaching 0 doesn't let u move forward...
>
> On Jan 15, 12:54 pm, Avi Dullu  wrote:
> > @jammy Thanx for the elongated description :)
> >
> > Yes, I feel I probably gave a DP solution wrongly to the Greedy approach.
> > But just to clarify, Greedy does not solve any subproblems, it just makes
> a
> > locally optimal choice and proceedes towards a global optimal strategy.
> And
> > your point that greedy usually takes lesser time than DP also stands
> > correct, but there are a lot of exceptions wherein the choice of local
> > optimal strategy may be of very high order, and thus perform worse than
> DP.
> >
> > Just to rest (and clarify) my argument, the following is the greedy
> approach
> > I feel, *will* fail:
> >
> > for i = 1; i < n; i++
> >   next_jump_will_be_from_index = index of max(input[  i ... i + input[i]
>  ])
> >
> > i.e. after each jump, greedy strategy is to choose the next jumping point
> as
> > the one which has maximum value
> >
> > 3, 5, 3, 4, 1, 3, 4, 5
> >
> > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > whereas DP would take 3, 4 ( 2 steps)
> >
> > and if you notice, the implementation of this greedy (without using fancy
> > RMQ/segment trees) would still be O(n^2) or O(nlogn) (using RMQ/segment
> > trees)
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> > On Sun, Jan 16, 2011 at 1:39 AM, Jammy  wrote:
> > > @svix, I think pacific means takes i+v, But it still won't give the
> > > global optimal
> >
> > > @Avi, I am not an expert on greedy algorithm and some problems may be
> > > solved by using greedy. But as far as I understand, the difference
> > > between DP and Greedy is DP makes use of the solution of the
> > > subproblems while greedy doesn't. DP solves current problem by solving
> > > subproblems first and then making the choice. Greedy solves current
> > > problem by making a choice and solving subproblems. (see CLRS).That's
> > > why greedy gives me this idea that it usually takes less time then
> > > DP.
> >
> > > In your latest post, it appears to me you are using DP instead greedy
> > > because your solution to current problem is built upon the solution of
> > > subproblems.
> >
> > > Please give me your input.
> >
> > > On Jan 15, 12:59 pm, SVIX  wrote:
> > > > actually, there is a way t do this in greedy... instead of taking the
> > > > local maximum value v for an index i, take the local maximum f(v) = i
> > > > + v... this will get you the right answer...more efficient than DP?
> > > > that i'm not sure... but average case will be close to linear
> >
> > > > On Jan 14, 9:29 pm, SVIX  wrote:
> >
> > > > > @pacific..
> > > > > the approach needs a little bit of tuning...
> >
> > > > > for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
> > > > > will pick 9, 8, 7, 6 etc...
> >
> > > > > minimum jumps in reality is from 9 to 1 to 2.
> >
> > > > > On Jan 14, 8:19 pm, pacific pacific  wrote:
> >
> > > > > > At each location if the value is k  ,
> > > > > > find the largest value in the next k elements and jump there.
> >
> > > > > > This greedy approach works in 0(n^2) and i believe it works. If
> not
> > > can
> > > > > > someone give me a counter example ?
> >
> > > > > > On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu 
> > > wrote:
> > > > > > > @jammy Even I felt the same, but the greedy 'algo' u suggest is
> > > actually
> > > &g

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

@jammy Thanx for the elongated description :)

Yes, I feel I probably gave a DP solution wrongly to the Greedy approach.
But just to clarify, Greedy does not solve any subproblems, it just makes a
locally optimal choice and proceedes towards a global optimal strategy. And
your point that greedy usually takes lesser time than DP also stands
correct, but there are a lot of exceptions wherein the choice of local
optimal strategy may be of very high order, and thus perform worse than DP.

Just to rest (and clarify) my argument, the following is the greedy approach
I feel, *will* fail:

for i = 1; i < n; i++
  next_jump_will_be_from_index = index of max(input[  i ... i + input[i]  ])

i.e. after each jump, greedy strategy is to choose the next jumping point as
the one which has maximum value

3, 5, 3, 4, 1, 3, 4, 5

in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
whereas DP would take 3, 4 ( 2 steps)

and if you notice, the implementation of this greedy (without using fancy
RMQ/segment trees) would still be O(n^2) or O(nlogn) (using RMQ/segment
trees)

Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sun, Jan 16, 2011 at 1:39 AM, Jammy  wrote:

> @svix, I think pacific means takes i+v, But it still won't give the
> global optimal
>
> @Avi, I am not an expert on greedy algorithm and some problems may be
> solved by using greedy. But as far as I understand, the difference
> between DP and Greedy is DP makes use of the solution of the
> subproblems while greedy doesn't. DP solves current problem by solving
> subproblems first and then making the choice. Greedy solves current
> problem by making a choice and solving subproblems. (see CLRS).That's
> why greedy gives me this idea that it usually takes less time then
> DP.
>
> In your latest post, it appears to me you are using DP instead greedy
> because your solution to current problem is built upon the solution of
> subproblems.
>
> Please give me your input.
>
> On Jan 15, 12:59 pm, SVIX  wrote:
> > actually, there is a way t do this in greedy... instead of taking the
> > local maximum value v for an index i, take the local maximum f(v) = i
> > + v... this will get you the right answer...more efficient than DP?
> > that i'm not sure... but average case will be close to linear
> >
> > On Jan 14, 9:29 pm, SVIX  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @pacific..
> > > the approach needs a little bit of tuning...
> >
> > > for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
> > > will pick 9, 8, 7, 6 etc...
> >
> > > minimum jumps in reality is from 9 to 1 to 2.
> >
> > > On Jan 14, 8:19 pm, pacific pacific  wrote:
> >
> > > > At each location if the value is k  ,
> > > > find the largest value in the next k elements and jump there.
> >
> > > > This greedy approach works in 0(n^2) and i believe it works. If not
> can
> > > > someone give me a counter example ?
> >
> > > > On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu 
> wrote:
> > > > > @jammy Even I felt the same, but the greedy 'algo' u suggest is
> actually
> > > > > IMHO not a greedy approach. You just take each arr[i] and jump
> *without
> > > > > deciding a locally optimal policy* . SO, if u were to *see* arr[i]
> and
> > > > > *decide* on the optimal policy I feel one would follow d same steps
> as in a
> > > > > DP solution. Its only just that the implementation would be O(n^2).
> Just to
> > > > > add, this is the greedy approach I feel:
> >
> > > > > greedy_min_steps[n]
> > > > > for i = 0; i < n; i++:
> > > > >   for (j = 0; j < input[i]; j++)
> > > > > greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ],
> > > > > greedy_min_steps[ i ] + 1)
> >
> > > > > this is the greedy approach I build and I see this being exactly
> similar to
> > > > > my DP approach. There are instances of greedy approach based
> algorithms
> > > > > which have *optimized* DP counter parts. I feel this problem is one
> of them.
> > > > > More ideas ?
> >
> > > > > Programmers should realize their critical importance and
> responsibility in
> > > > > a world gone digital. They are in many ways similar to the priests
> and m

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

@jammy Even I felt the same, but the greedy 'algo' u suggest is actually
IMHO not a greedy approach. You just take each arr[i] and jump *without
deciding a locally optimal policy* . SO, if u were to *see* arr[i] and
*decide* on the optimal policy I feel one would follow d same steps as in a
DP solution. Its only just that the implementation would be O(n^2). Just to
add, this is the greedy approach I feel:

greedy_min_steps[n]
for i = 0; i < n; i++:
  for (j = 0; j < input[i]; j++)
greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j ],
greedy_min_steps[ i ] + 1)

this is the greedy approach I build and I see this being exactly similar to
my DP approach. There are instances of greedy approach based algorithms
which have *optimized* DP counter parts. I feel this problem is one of them.
More ideas ?



Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sat, Jan 15, 2011 at 2:14 AM, Jammy  wrote:

> @Avi Greedy approach doesn't work since you can't ensure the choice is
> locally optimum. Consider 3,9,2,1,8,3.  Using greedy alg. would give
> you 3,1,8,3 while otherwise DP would give you 3,9,3.
>
> On Jan 14, 6:11 am, Avi Dullu  wrote:
> > I guess u got confused with the comment I wrote, I have added 2 print
> > statements and now I guess it should be clear to you as to why the code
> is
> > O(n). The comment means that each element of the min_steps_dp will be
> > ACCESSED only ONCE over the execution of the entire program. Hence the
> outer
> > loop still remains O(n). The next_vacat variable if u notice is always
> > incremental, never reset to a previous value.
> >
> > #include
> > #include
> >
> > #define MAX 0x7fff
> >
> > inline int min(int a, int b) {
> >   return a >= b ? b : a;
> >
> > }
> >
> > int find_min_steps(int const * const input, const int n) {
> >   int min_steps_dp[n], i, temp, next_vacant;
> >   for (i = 0; i < n; min_steps_dp[i++] = MAX);
> >
> >   min_steps_dp[0] = 0;
> >   next_vacant = 1; // Is the index in the array whose min_steps needs to
> be
> > updated
> >// in the next iteration.
> >   for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
> > temp = i + input[i];
> > if (temp >= n) {
> >   min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] +
> 1);
> >   temp = n - 1;
> > } else {
> >   printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] +
> > 1);
> >   min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
> > }
> > if (temp > next_vacant) {
> >   printf("i: %d \n", i);
> >   for (; next_vacant < temp; next_vacant++) {
> >   printf("next_vacant: %d \n", next_vacant);
> > min_steps_dp[next_vacant]
> >   = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
> >   }
> > }
> >   }
> >   for (i=0;i >   return min_steps_dp[n-1];
> >
> > }
> >
> > int main() {
> >   int n, *input, i;
> >   scanf("%d",&n);
> >   if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
> > return -1;
> >   }
> >   for (i = 0;i < n; scanf("%d",&input[i++]));
> >   printf("Minimum steps: %d\n",find_min_steps(input, n));
> >   return 0;
> >
> > }
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> > On Fri, Jan 14, 2011 at 1:49 PM, Decipher 
> wrote:
> > > I don't think the inner loop is executing only once . Kindly check it
> for
> > > this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner
> loop
> > > you will find that for same values of i(Outer index) inner loop is
> called.
> > > Its an O(n2) solution .
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogee

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

I guess u got confused with the comment I wrote, I have added 2 print
statements and now I guess it should be clear to you as to why the code is
O(n). The comment means that each element of the min_steps_dp will be
ACCESSED only ONCE over the execution of the entire program. Hence the outer
loop still remains O(n). The next_vacat variable if u notice is always
incremental, never reset to a previous value.

#include
#include

#define MAX 0x7fff

inline int min(int a, int b) {
  return a >= b ? b : a;
}

int find_min_steps(int const * const input, const int n) {
  int min_steps_dp[n], i, temp, next_vacant;
  for (i = 0; i < n; min_steps_dp[i++] = MAX);

  min_steps_dp[0] = 0;
  next_vacant = 1; // Is the index in the array whose min_steps needs to be
updated
   // in the next iteration.
  for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
temp = i + input[i];
if (temp >= n) {
  min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
  temp = n - 1;
} else {
  printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] +
1);
  min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
}
if (temp > next_vacant) {
  printf("i: %d \n", i);
  for (; next_vacant < temp; next_vacant++) {
  printf("next_vacant: %d \n", next_vacant);
min_steps_dp[next_vacant]
  = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
  }
}
  }
  for (i=0;i wrote:

> I don't think the inner loop is executing only once . Kindly check it for
> this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop
> you will find that for same values of i(Outer index) inner loop is called.
> Its an O(n2) solution .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Symmetric matrix

[Avi Dullu]

if the matrix is n x n and n is not huge > 5k
Use int arr[((n * n) - n ) / 2 + n];

One approach:

arr[0] = n;
c = 1;
for (i=n; i >= 0; i--)
  for (j=0; j < i ; j++)
arr[c++] = get_element_at(n-i, j);

And u can access any element in O(1).



Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Thu, Jan 13, 2011 at 3:37 PM, juver++  wrote:

> One-dimensional array.
> 1 2 4
> 2 3 5
> 4 5 6
> => [1, 2, 3, 4, 5, 6]
> Is your matrix summetric on a diagonal?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Amazon Interview - Algorithms

[Avi Dullu]

@juver++ : what is the greedy approach one could take here? I know it would
be wrong, but I tried to come up with a test case for greedy failure, but
realized the greedy policy here will be equivalent to the dp.

@Decipher: your's seems to be a O(n^2) solution. Here in the O(n) version of
it.

#include
#include

#define MAX 0x7fff

inline int min(int a, int b) {
  return a >= b ? b : a;
}

int find_min_steps(int const * const input, const int n) {
  int min_steps_dp[n], i, temp, next_vacant;
  for (i = 0; i < n; min_steps_dp[i++] = MAX);

  min_steps_dp[0] = 0;
  next_vacant = 1; // Is the index in the array whose min_steps needs to be
updated
   // in the next iteration.
  for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
temp = i + input[i];
if (temp >= n) {
  min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
  temp = n - 1;
} else {
  min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
}
if (temp > next_vacant) {
  // this loop executes only ONCE for each element in the array, so over
the
  // course of execution, is an O(n) loop only. The order of the outer
loop still
  // remains O(n).
  for (; next_vacant < temp; next_vacant++) {
min_steps_dp[next_vacant]
  = min(min_steps_dp[temp], min_steps_dp[next_vacant]);
  }
}
  }
  for (i=0;i wrote:

> No, there is a counterexample fot the greedy.
>
> --
> 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] Re: MICROSOFT IDC

[Avi Dullu]

Sure, I raised concern about 'sorting'.


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Thu, Jan 13, 2011 at 1:05 AM, juver++  wrote:

> Merging lists can be done using O(1) extra space, inplace.
>
> --
> 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] Re: MICROSOFT IDC

[Avi Dullu]

SO .. u guys propose that 'sorting' is an O(1) space ? Won't the sorting
algo swap elements of the list so making it a O(n) space algo ? (Just
proposing :) )


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Wed, Jan 12, 2011 at 11:16 PM, aniket chatterjee wrote:

> Hi all Its about set intersection.
> @Davin predicted the problem wrongly.
> So,sorting gives the best performance.
>
> --
> 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] Re: Adobe - Algorithm

[Avi Dullu]

Hey guys .. saw this discussion and wanted to add something .. I wrote the
below program in college .. and I kindof have forgotten wat was the logic
(see the problem with badly written code :P ), It works on a pattern which I
found in this problem, I checked it and feel it works in order O(n) as each
element is accessed only twice, if you guys find any problem do post it.

#include 

int main() {
  int n, i, j , k, t1, l;
  scanf("%d",&n);
  int arr[n<<1 + 1];
  for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ ) {
if ( i <= n )
  arr[i] = k+=2; // 1 3 5 7
else
  arr[i] = l+=2;
  }
  arr[0]=0;

  printf("\n\nBefore Shuffling ..\n");
  for (i = 0;i <= n<<1; i++) printf("%d ", arr[i]);
  printf("\n\nShuffling Now ..\n");

  // Shuffleing starts
  i = 1;
  int chk[j+1]; // To check if each element was visited only once
  for (i=0;i<=j;i++) chk[i]=0;
  i = 1;
  while (i <= j) {
while (i<=j && arr[i] == i) {
  chk[i]++;
  i++;
}
if (i >j)
  break;
t1 = arr[i];   // swap with temp
k = i; // note the curr. loc in array
l = i;
printf("%d   : Value of i entering loop\n",i);
while (1) {
  k = k & 1 ? (k + 1) / 2 : n + k / 2;
  chk[k]++;
  if (k == i) break;
  arr[l] = arr[k];
  l = k;
}
arr[l] = t1;
  }
  for (i = 0;i <= j;i++) printf("%d ",arr[i]);
  printf("\n Checking which element was processed how many times.\n");
  for (i = 0; i <= j; i++)
printf("%d  %d\n",i,chk[i]);
  return 0;
}



Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sun, Jan 9, 2011 at 7:11 PM, Decipher  wrote:

> No its a single array . You have to convert first array into second in
> O(n) time and O(1) space .
>
> --
> 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] BT

[Avi Dullu]

One approach would be to convert both the trees to well formed flat-tree
representation and then reduce the problem to a substring matching one (can
use KMP/Boyer-Moore/Rabin-Karp for it).

eg.
1
  2  3
4  5

is flattened to (using postorder traversal) (1 (2 4 .) (3 . 5))

Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sun, Jan 9, 2011 at 12:10 PM, nishaanth  wrote:

> Do an inorder walk on T1 till you get the root of T2.
>
> Then do a simultaneous walks on both the trees till T2(smaller tree) is
> fully explored.
>
> If at any point you discover dissimilar nodes. print 'no'
> else print 'yes'
>
> One more issue is if duplicates are allowed, then we cant print 'no' with
> just one failure, repeat till you explore the bigger tree fully.
> Correct me if i am wrong.
>
>
> On Sat, Jan 8, 2011 at 9:31 PM, Harshal  wrote:
>
>> Given two binary trees T1 and T2 which store character data, duplicates
>> allowed. You have to devise an algorithm to decide whether the T2 is a
>> subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
>>
>> --
>> Harshal Choudhary,
>> III Year B.Tech Undergraduate,
>> Computer Science and Engineering,
>> National Institute of Technology Surathkal, Karnataka
>> India.
>>
>>  --
>> 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.
>>
>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
>  --
> 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] Re: floating point

[Avi Dullu]

to add to @Dave's reply. He explained it elaborately in
thisthread


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sun, Jan 9, 2011 at 9:56 AM, Dave  wrote:

> @Priya: Most modern processors have arithmetic that conforms to the
> IEEE Floating Point Standard. Double constants have 53 bits of
> precision, while floats have 24 bits. Rounding depends on the bit to
> the right of the 24th bit from the left. If that bit is a 1, the
> number is rounded up, while 0 rounds down.
>
> I should point out that with many language implementations, there is a
> mechanism to control the rounding. While "round to nearest" is the
> default, it also may be possible to "round up," "round down," or
> "round to zero."
>
> Dave
>
> On Jan 8, 10:01 pm, priya mehta  wrote:
> > why is 1 double rounded down and the other double rounded up
> > is it compiler dependent?
> >
> >
> >
> > On Sun, Jan 9, 2011 at 9:29 AM, Dave  wrote:
> > > The 275.7 and 75.7 are doubles. The assignment statements round the
> > > double constant to float precision. Then you compare the unrounded
> > > double to the rounded float. If you had used 275.7e0 and 75.7e0 in the
> > > if statements, the results would have been "Hello" in both cases.
> >
> > > Or to put it differently, 275.7 != 275.7e0 (not surprising) and 75.7 !
> > > = 75.7e0 (ditto), but one double is greater than the float because the
> > > double is rounded down to form the float and the other is less than
> > > the float because the double is rounded up to form the float.
> >
> > > Dave
> >
> > > On Jan 8, 8:24 pm, priya mehta  wrote:
> > >  > #include
> > > > int main()
> > > > {
> > > > float a=275.7;
> > > > if(275.7>a)
> > > > printf("Hi");
> > > > else
> > > > printf("Hello");
> > > > return 0;
> >
> > > > }
> >
> > > > #include
> > > > int main()
> > > > {
> > > > float a=75.7;
> > > > if(75.7>a)
> > > > printf("Hi");
> > > > else
> > > > printf("Hello");
> > > > return 0;
> >
> > > > }
> >
> > > > why the above two programs give different output?
> >
> > > --
> > >  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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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] Re: Adobe - Coding

[Avi Dullu]

@Decipher

As far as I understand the problem it says "returns the 5 most common
occuring strings in a list", and the example u give is of a character array,
when u go to a list of strings with len_of_each_string > 1, u wil have to
*hash* them, which is when u will run into problems with count sort. So
count sort wil not work.

As juver++ said sorting is one option.
Going for hashing of each string and using a hashtable is another possible
solution.
Also building a compressed Trie out of the list and a traversal of it, will
give the top 5 counts (but this will be too much work for this task :) )


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sat, Jan 8, 2011 at 1:59 AM, Decipher  wrote:

> We can apply count sort here also and take the range of numbers as
> 256 . Example take an array c[256] , where c[i] gives the number of
> times i_th ASCII value is repeated . Then after you have obtained
> c[256] . Check for maximum 5 nos. in this array (which can be done in
> O(n) time and space).
>
> --
> 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] Re: double and int

[Avi Dullu]

I referred to the accuracy of result *acceptable to one*, if there are cases
that 0.2 and 0.29 may occur, and u still want to go with a 1.0e-5
value as a zero equality check, its your code, screw it up. If one knows
that such corner cases might come and he decides to discard them, fine, else
raise the bar. The problem is always to decide the thresholds and then
sticking to them. Also, I chose the value of 1.0e-5 to check equality with
0.... and when I say so, I stand by the point that 0.01999 *is*
0.0 for me, *whatever* may be the %age difference,
because values lesser than *1.0e-3* do *not* interest me hence I chose the
bar as 1.0e-5 and *not* 1.0e-3. Its an engineering decision, not a
programming contest solution to get through an online judge.


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Sat, Jan 8, 2011 at 1:35 AM, Dave  wrote:

> @Avi: Whether this is a safe implementation depends in part on whether
> you want to say that 0.2 == 0.29 because they differ by less
> than 1.0e-5, even though they differ by 45%. Applying your
> philosophical boilerplate, you have to use some intelligence even in
> this type of thing.
>
> Dave
>
> On Jan 7, 12:51 pm, Avi Dullu  wrote:
> > Thanx for the precise information.
> >
> > I was coming from a perspective of safe implementation, when dealing with
> > variables, you might not always know whether the values to be compared
> will
> > fall under the exact floating point representation, so the safe way to go
> > might always be to use the < 1.0e-5 method or go with library functions.
> You
> > see any problem with this too ?
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> >
> >
> > On Fri, Jan 7, 2011 at 4:15 AM, Dave  wrote:
> > > I don't think your example with == would ever fail. According to the
> > > IEEE floating point standard, integers within the dynamic range of the
> > > number type must be represented exactly and must compare as equal.
> >
> > > Furthermore, the four basic operations on integers within the dynamic
> > > range of the floating point number type that have integer results
> > > within that dynamic range must be exact. Thus, 25.0 - 5.0, 13.0 + 7.0,
> > > 4.0 * 5.0, and 60.0 / 3.0 all must equal 20.0 exactly.
> >
> > > Where you run into trouble is when the numbers in question cannot be
> > > represented exactly in the finite precision floating point format --
> > > something like this:
> >
> > > double d1 = 6.1;
> > > double d2 = 11.6;
> > > double d3 = 17.7;
> >
> > > assert(d1 + d2 == d3); // might fail, and Wrong way to do it !!
> >
> > > And your "correct and recommended way" is missing an absolute value:
> >
> > > assert(abs(d1 + d2 - d3) < 1.0e-5); // given you assume precision of
> > > 1e-5 is the correct and recommended way.
> >
> > > Dave
> >
> > > On Jan 6, 4:19 pm, Avi Dullu  wrote:
> > > > Just to mention, floating point numbers r always compared *for
> equality*
> > > > like
> >
> > > > double d1 = 90.0;
> > > > double d2 = 90.0;
> >
> > > > assert(d1 == d2); // might fail, and Wrong way to do !!
> >
> > > > assert(d1 - d2 < 1e-5); // given u assume precision of 1e-5, is the
> > > correct
> > > > and recommended way.
> >
> > > > Programmers should realize their critical importance and
> responsibility
> > > in a
> > > > world gone digital. They are in many ways similar to the priests and
> > > monks
> > > > of Europe's Dark Ages; they are the only ones with the training and
> > > insight
> > > > to read and interpret the "scripture" of this age.
> >
> > > > On Fri, Jan 7, 2011 at 1:47 AM, juver++ 
> wrote:
> > > > > Numbers without fractional parts are represented exactly (in a
> range
> > > > > supported by double).
> >
> > > > > --
> > > > > You received this message because

Re: [algogeeks] Re: double and int

[Avi Dullu]

Thanx for the precise information.

I was coming from a perspective of safe implementation, when dealing with
variables, you might not always know whether the values to be compared will
fall under the exact floating point representation, so the safe way to go
might always be to use the < 1.0e-5 method or go with library functions. You
see any problem with this too ?


Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Fri, Jan 7, 2011 at 4:15 AM, Dave  wrote:

> I don't think your example with == would ever fail. According to the
> IEEE floating point standard, integers within the dynamic range of the
> number type must be represented exactly and must compare as equal.
>
> Furthermore, the four basic operations on integers within the dynamic
> range of the floating point number type that have integer results
> within that dynamic range must be exact. Thus, 25.0 - 5.0, 13.0 + 7.0,
> 4.0 * 5.0, and 60.0 / 3.0 all must equal 20.0 exactly.
>
> Where you run into trouble is when the numbers in question cannot be
> represented exactly in the finite precision floating point format --
> something like this:
>
> double d1 = 6.1;
> double d2 = 11.6;
> double d3 = 17.7;
>
> assert(d1 + d2 == d3); // might fail, and Wrong way to do it !!
>
> And your "correct and recommended way" is missing an absolute value:
>
> assert(abs(d1 + d2 - d3) < 1.0e-5); // given you assume precision of
> 1e-5 is the correct and recommended way.
>
> Dave
>
> On Jan 6, 4:19 pm, Avi Dullu  wrote:
> > Just to mention, floating point numbers r always compared *for equality*
> > like
> >
> > double d1 = 90.0;
> > double d2 = 90.0;
> >
> > assert(d1 == d2); // might fail, and Wrong way to do !!
> >
> > assert(d1 - d2 < 1e-5); // given u assume precision of 1e-5, is the
> correct
> > and recommended way.
> >
> > Programmers should realize their critical importance and responsibility
> in a
> > world gone digital. They are in many ways similar to the priests and
> monks
> > of Europe's Dark Ages; they are the only ones with the training and
> insight
> > to read and interpret the "scripture" of this age.
> >
> >
> >
> > On Fri, Jan 7, 2011 at 1:47 AM, juver++  wrote:
> > > Numbers without fractional parts are represented exactly (in a range
> > > supported by double).
> >
> > > --
> > > 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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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] Re: double and int

[Avi Dullu]

Just to mention, floating point numbers r always compared *for equality*
like

double d1 = 90.0;
double d2 = 90.0;

assert(d1 == d2); // might fail, and Wrong way to do !!

assert(d1 - d2 < 1e-5); // given u assume precision of 1e-5, is the correct
and recommended way.



Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Fri, Jan 7, 2011 at 1:47 AM, juver++  wrote:

> Numbers without fractional parts are represented exactly (in a range
> supported by double).
>
> --
> 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] How to search for the presence of a file in Linux?

[Avi Dullu]

Hey,

Remembered of my OS assignment and wanted to fix it :). Though do not
appreciate the design of the program :D, and not having the enthu to
redesign it, I have fixed the program with minimal possible changes. Please
reply in case of any issues. Thnx for posting :)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define FOUND 1
#define MAX_DIR_PATH 1000
using namespace std;
int f =0;
class Search {
  // data members
  private :
DIR* dptr;
struct dirent* dir;
string dirname;
int count;

// instance methods
  public :
Search() {
  count =0;
}
char * scan_dir(string file, string str) {
  struct stat sfile;
  DIR * dptr = opendir(str.c_str());
  if( dptr == NULL) {
cout << "Error(" << errno << ") opening " << str << endl;
return "Error";
  }
  while(f != FOUND && ((dir = readdir(dptr)) != NULL)) {
if (dir->d_name[0] == '.') { // hidden files and all
  continue;
}
char path_[MAX_DIR_PATH];path_[0]=0;
strcpy(path_, str.c_str());
strcat(path_, "/");
strcat(path_, dir->d_name);
cout << "Abs Name :" << path_ << endl;
if ((lstat(path_, &sfile)) == 0) {
  if(S_ISDIR(sfile.st_mode)) {
if ((strcmp(dir->d_name,".")==0)
|| (strcmp(dir->d_name, "..") == 0) )
  continue;
char cwdir[MAX_DIR_PATH];cwdir[0]=0;
strcpy(cwdir, path_);
char * result = scan_dir(file, cwdir);
if (f == FOUND) return result;
chdir(path_);
  } else if ((S_ISREG(sfile.st_mode)) &&
!strcmp(dir->d_name,file.c_str())) {
cout << endl<< "::: FOUND FILE :::";
f = FOUND;
return path_;
  }
}
  }// eow
  char temp[MAX_DIR_PATH];temp[0]=0;
  strcmp(temp, str.c_str());
  return temp;
}//scan_dir
};// end of class decln
int main() {
  string file, directory;
  cout << "Name of file:";
  cin >> file;
  cout << " Name of root directory: ";
  cin >> directory;
  Search *S = new Search();
  cout << "SEARCHING for " << file << "  from root dir: " << directory <<
"\n";
  string name = S->scan_dir(file, directory);
  if (f != FOUND)
cout << "FILE NOT FOUND";
  else
cout << "Found at: " << name << "\n";
  return 0;
}



Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.


On Thu, Jan 6, 2011 at 6:33 PM, janani thiru  wrote:

>
>
> I have written a program to search for a file in C in UNIX.
> But it doesn't loop recursively if the starting path is "/"
> Could it be because of permissions? But I am the root while executing the
> program and I have also changed the permissions of all the files in the
> folder correspondingly.
>
> Please help.
>
> #include 
> #include 
> #include 
> #include 
> #include 
> #include 
> #include 
> #define FOUND 1
> #define MAX_DIR_PATH 1000
> using namespace std;
> int f =0;
> class Search
> {
>
> // data members
> private :
> DIR* dptr; DIR* prior;
> struct dirent* dir;
> string dirname;
> struct stat sfile;
> int count;
>
> // instance methods
> public :
> Search()
> {
> count =0;
> }
>
> ~Search()
> {
> closedir(dptr);
> }
>
> void setdname(string str)
> {
> dirname = str;
> }
>
>
> int scan_dir(string file, string str)
> {
> cout < dptr = opendir(str.c_str());
> if( dptr == NULL)
> {
> cout << "Error(" << errno << ") opening " << dirname <<
> endl;
> return errno;
> }
>
> while( (dir = readdir(dptr)) != NULL)
> {
>
> cout << endl << dir->d_name<
> if((lstat(dir->d_name,&sfile))==0)
> {
>
> if(S_ISDIR(sfile.st_mode))
> {
> char cwdir[MAX_DIR_PATH];
>
> if ((strcmp(dir->d_name,".")==0) ||  (strcmp(dir->d_name,
> "..") == 0) )
> continue;
>
> cout 
> str = cwdir;
>
> strcat(cwdir,"/");
> strcat(cwdir,dir->d_name);
>
> cout << endl << "cwdir concat"<<"\t"< scan_dir(file,cwdir);
>
> chdir(str.c_str());
> }
>
> else if ((S_ISREG(sfile.st_mode)) &&
> !strcmp(dir->d_name,file.c_str()))
>   {
> cout < f = FOUND;
> break;
>   }
> }
> }// eow
> }//scan_dir
> };// end of class decln
> int main()
> {
> string file;
> cout << "Name of file:"< cin >> file;
>