Re: [algogeeks] Array problem
@gaurav popli: how about this one??
findsummat(int arr[],int n)
{
int *sum ;
sum =(int*)malloc(sizeof(int)*n);
for(int i=0;iwrote:
> @piyush : sorry dude , didnt get your algo . actually you are using
> different array and i get confused which array to be considered when.
>
>
>
> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>
>> 1)First map the array numbers into the position in which they would be,
>> if they are sorted,for example
>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
>> 2)Now for each number ,find the cumulative frequency of index ( = the
>> corresponding number in the map - 1).
>> 3)Output the cumulative frequency and increase the frequency at the
>> position (=the corresponding number in the map) by the number itself.
>> Example
>> {3,5,1,6,7,8} Map of which would be {2,3,1,4,5,6}
>> Process the numbers now,
>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
>> so output 0
>>Increase the frequency at index 2 to the number 3.
>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>>Increase the frequency at index 3 to the number 5.
>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position
>> 1 by 1.
>> Similarly for others.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Novell - Interview (Round-3 Coding)
Let's try
{ reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2)
Think about adding suffixes to the tree from shortest to longest.
So suppose you are now adding something of the form
reverse( $ X a^L Y )
where L is the length of the longest run of a's and X and Y are what
comes before and after. Well we know the length of Y is at most L
and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's
already in the tree will match no more than 2L characters before a new
branch occurs. The new branch will therefore have at least
L(L+1)/2 - 1 - 2L characters. This is O(L^2).
You should do the math more rigorously, but roughly you will be
getting for the total of all branches added,
sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5)
with one character per branch. This is super-linear.
On Mar 13, 12:47 am, reynald reni wrote:
> Construct an infinite family of strings over a fixed alphabet, where
> the total length of the edge-labels on their suffix tree grows faster
> than O(m), where 'm' is the length of the string. [That is, show that
> linear time suffix tree algorithm would be impossible if edge-labels
> were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Novell - Interview (Round-3 Coding)
{ reverse( $ a b a a b b a a a b b b ... a^n b^n ) | n = 0,1,2,... }
On Mar 13, 12:47 am, reynald reni wrote:
> Construct an infinite family of strings over a fixed alphabet, where
> the total length of the edge-labels on their suffix tree grows faster
> than O(m), where 'm' is the length of the string. [That is, show that
> linear time suffix tree algorithm would be impossible if edge-labels
> were written explicitly on the edges.]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Interview Question
Sorry, a small test showed a loop quitting one iteration too soon.
Here is the fix.
import java.util.Random;
public class ListCopy {
class Node {
int val;
Node next, other;
Node() { }
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next) {
p.next = new Node(p);
}
// Use the map to fix up the other pointers in the copies.
for (Node p = this.next; ; p = p.next.next) {
p.other = p.other.next;
if (p.next == null)
break;
}
// Split into original list and list of copies.
Node d = new Node();
for (Node p = this, q = d; p != null; p = p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return d.next;
}
}
void run() {
Node [] test = new Node [10];
int n = test.length;
int i = n - 1;
test[i] = new Node(n, null, null);
Random gen = new Random(42);
for (--i; i >= 0; --i)
test[i] = new Node(i + 1, test[i + 1], null);
for (i = 0; i < n; i++)
test[i].other = test[gen.nextInt(n)];
Node copy = test[0].copy();
int count = 0;
for (Node p = test[0], q = copy; p != null; p = p.next, q
=q.next) {
if (p.val != q.val || p.other.val != q.other.val || p == q
|| p.other == q.other)
System.err.println("error: p=" + p.val + " q=" +
q.val);
count++;
}
System.err.println("# nodes: " + count);
}
public static void main (String [] args) {
new ListCopy().run();
}
}
On Mar 13, 3:15 pm, Gene wrote:
> Copying a full graph requires a BFS or DFS. But here we have a big
> advantage. We know the nodes are linked in a single chain. So we
> don't need to search to find all nodes. We can just use .next
> pointers.
>
> No matter how we do things, we will need Map(A) that returns the copy
> of node A if it already exists.
>
> If you use a separate map like a hash table, then things are very
> simple. Traverse the list one time to make copies of all the nodes,
> chain them in a list, and create the Map. Then traverse the original
> list a second time to set the "other" pointers: for each node A, set
> Map(A).other = Map(A.other).
>
> The Map requires O(L) space for a list of length L.
>
> But it turns out we can store the map in a very tricky way that
> requires zero additional space _if_ we are allowed to change the
> original list while making the copy. If A' is the copy of A, and we
> start with list [ A,B,C,... ], then we transform this in one pass to
> [A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
> created the map without losing any information.
>
> Here's untested code that ought to be at least very close:
>
> class Node {
>
> int val;
> Node next, other;
>
> Node() {}
> Node(int val, Node next, Node other) {
> this.val = val;
> this.next = next;
> this.other = other;
> }
> Node(Node org) {
> this(org.val, org.next, org.other);
> }
>
> /**
> * @return a copy of the list including "other" pointers
> */
> Node copy() {
> // Make the copies and the map.
> for (Node p = this; p != null; p = p.next.next)
> p.next = new Node(p);
> // Use the map to fix up the other pointers in the
> copies.
> for (Node p = this.next; p.next != null; p =
> p.next.next)
> p.other = p.other.next;
> // Split into original list and list of copies.
> Node dummyHead = new Node();
> for (Node p = this, q = dummyHead; p != null; p =
> p.next, q =
> q.next) {
> q.next = p.next;
> p.next = p.next.next;
> }
> return dummyHead.next;
> }
> }
>
> On Mar 13, 2:01 am, Umer Farooq wrote:
>
>
>
>
>
>
>
> > Yes that is exactly what they wanted. I proposed BFS for this solution.
> > Anyway, there was another problem that I was able to solve; but the
> > interviewer brought up a much more efficient approach.
>
> > The problem was:
>
> > - Given a linked a linked list
Re: [algogeeks] Maximum size square sub-matrix with all 1s
@atul read it .. it's good but more or less like the histogram algo.. i wanted a DP. approach.. here is some of wat i heard from a senior in colg.. 1. at every index we can keep 4 variable ht: height of max rectangle possible at index above current wt width " " " " " " " hl:height of max rectangle possible at index left of current wl: """ " " "" now problem is which one to take for current... index On Tue, Mar 13, 2012 at 10:52 AM, atul anand wrote: > @ Sourabh: check solution i have posted in below link > > > http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0 > > > > On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh > wrote: > >> @ ALL >> >> finding square matrix is quite a standard question and nw an easy one as >> everyone knows the reccussence atul has given. >> but i wanted to find max rectangle.. >> >> i know there is a DP for it. in O(n^2). for nxn matrix..don't know the >> whole approach .but here is what i remember.. >> >> 1. aproach is simple to keep track of max rectangle which can be formed >> from any point taking that point as top left corner of max rectangle and >> proceed further down . >> >> can someone suggest how can be proceed further.. >> >> >> [ NOTE: problem occurs mainly when their are more than one rectangles >> which can be formed from same point ] >> >> plz.. don't suggest the histogram method it's just a dirty way of >> avoiding to work on getting this DP right. :-) >> >> >> On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote: >> >>> here is the recurrence for solving this >>> >>> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] >>> ) ); >>> >>> >>> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma >>> wrote: >>> April 4, 2010 Given a binary matrix, find out the maximum size square sub-matrix with all 1s. For example, consider the below binary matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The maximum square sub-matrix with all set bits is 1 1 1 1 1 1 1 1 1 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Interview Question
Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the "other" pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including "other" pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
On Mar 13, 2:01 am, Umer Farooq wrote:
> Yes that is exactly what they wanted. I proposed BFS for this solution.
> Anyway, there was another problem that I was able to solve; but the
> interviewer brought up a much more efficient approach.
>
> The problem was:
>
> - Given a linked a linked list with one pointer pointing to next,
> another pointer pointing to any random pointer in the list. The random
> pointer can be before or after the current pointer or it can even be at the
> same node. Write a piece of code that can produce an exact copy of the
> linked list.
>
>
>
>
>
>
>
>
>
> On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq wrote:
> > Yes that is exactly what they wanted. I proposed BFS for this solution.
> > Anyway, there was another problem that I was able to solve; but the
> > interviewer brought up a much more efficient approach.
>
> > The problem was:
>
> > Given a linked l
>
> > On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote:
>
> >> Since there is no mention of weights, you are looking for any spanning
> >> tree. Primm and Kruskal are for _minimum_ spanning tree. They are
> >> overkill for this problem.
>
> >> You can construct a spanning tree in any graph with DFS. Just record
> >> every edge you find that reaches a vertex that has never been visited
> >> before. This has to find every vertex, and since you are recording
> >> only the first edge used to arrive at each vertex, these edges must
> >> form a tree. This works even if there are cycles. The algorithm is O(|
> >> E|).
>
> >> Note that in general a graph doesn't have a single root. So you'd
> >> search from all roots. Another way to think about this: introduce
> >> your own dummy root and edges to each vertex where there are no
> >> incident "in" edges. Of course you don't report the dummy edges.
>
> >> On Mar 12, 1:09 pm, atul anand wrote:
> >> > i guess they were talking abt spanning tree , so you can use prism or
> >> > kruskal algo to do the same.
>
> >> > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq
> >> wrote:
> >> > > Hello friends,
>
> >> > > I recently had an onsite MS interview. One of the questions that they
> >> > > asked was:
>
> >> > > - Given a directed graph, write a program that takes root of the
> >> graph
> >> > > and returns root of a tree which comprises of all the nodes of the
> >> graph in
> >> > > the same way as they appeared in the graph (the graph contains no
> >> cycles).
>
> >> > > --
> >> > > Umer
>
> >> > > --
Re: [algogeeks] Maximum size square sub-matrix with all 1s
@ Sourabh: check solution i have posted in below link http://groups.google.com/group/algogeeks/browse_thread/thread/91a17f7c78c2319e/991d1c2625a62ff0?hl=en&lnk=gst&q=rectangle+of+max+sum+MS+Q#991d1c2625a62ff0 On Tue, Mar 13, 2012 at 10:26 PM, Sourabh Singh wrote: > @ ALL > > finding square matrix is quite a standard question and nw an easy one as > everyone knows the reccussence atul has given. > but i wanted to find max rectangle.. > > i know there is a DP for it. in O(n^2). for nxn matrix..don't know the > whole approach .but here is what i remember.. > > 1. aproach is simple to keep track of max rectangle which can be formed > from any point taking that point as top left corner of max rectangle and > proceed further down . > > can someone suggest how can be proceed further.. > > > [ NOTE: problem occurs mainly when their are more than one rectangles > which can be formed from same point ] > > plz.. don't suggest the histogram method it's just a dirty way of avoiding > to work on getting this DP right. :-) > > > On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote: > >> here is the recurrence for solving this >> >> R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] ) >> ); >> >> >> On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma >> wrote: >> >>> >>> April 4, 2010 >>> >>> Given a binary matrix, find out the maximum size square sub-matrix with >>> all 1s. >>> >>> For example, consider the below binary matrix. >>> >>>0 1 1 0 1 >>>1 1 0 1 0 >>>0 1 1 1 0 >>>1 1 1 1 0 >>>1 1 1 1 1 >>>0 0 0 0 0 >>> >>> The maximum square sub-matrix with all set bits is >>> >>> 1 1 1 >>> 1 1 1 >>> 1 1 1 >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft Interview Question
This problem is close to copying a graph. For that as you said, just
do DFS or BFS and maintain a map from original nodes to copies. Use
the copy to set pointers whenever it exists. When it doesn't exist,
make a new node and add it to the map.
You can implement the map in various ways. A hash table works fine.
If you can add a pointer to each original vertex node, you can store
the mapping right there. If nodes are numbered consecutively, you can
use these as indices into a table. Etc. Etc. Lots of schemes are
possible. No matter how you do it, the algorithm is the same:
Node copy(Node x)
{
if (x == null) return null;
if (Map(x) != null) return Map(x);
xCopy = new Node();
Set Map(x) = xCopy;
xCopy.next = copy(x.next);
xCopy.other = copy(x.other);
return xCopy;
}
But general graph copy is overkill here. The searching requires O(L)
space for a list of length L. So for this special problem, just
traverse the list once to find and copy all the nodes and then a
second time to set the "other" pointers:
Node Copy(Node x)
{
// Using a dummy head node makes copying simple.
Node dummyHead = new Node();
Node q = dummyHead;
// Make the copied list and fill in the Map.
for (Node p = x; p != null; p = p.next, q = q.next) {
Node pCopy = new Node();
q.next = pCopy;
Set Map(p) = pCopy;
}
// Set all the other pointers.
for (Node p = x; p != null; p = p.next)
Map(p).other = Map(p.other);
return dummyHead.next;
}
The final question is whether you can implement the Map in a tricky
way. After the list is constructed, you have the L "other" pointers
doing nothing, so how can they be exploited?
I'll let you think about that...
On Mar 13, 2:01 am, Umer Farooq wrote:
> Yes that is exactly what they wanted. I proposed BFS for this solution.
> Anyway, there was another problem that I was able to solve; but the
> interviewer brought up a much more efficient approach.
>
> The problem was:
>
> - Given a linked a linked list with one pointer pointing to next,
> another pointer pointing to any random pointer in the list. The random
> pointer can be before or after the current pointer or it can even be at the
> same node. Write a piece of code that can produce an exact copy of the
> linked list.
>
>
>
>
>
>
>
>
>
> On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq wrote:
> > Yes that is exactly what they wanted. I proposed BFS for this solution.
> > Anyway, there was another problem that I was able to solve; but the
> > interviewer brought up a much more efficient approach.
>
> > The problem was:
>
> > Given a linked l
>
> > On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote:
>
> >> Since there is no mention of weights, you are looking for any spanning
> >> tree. Primm and Kruskal are for _minimum_ spanning tree. They are
> >> overkill for this problem.
>
> >> You can construct a spanning tree in any graph with DFS. Just record
> >> every edge you find that reaches a vertex that has never been visited
> >> before. This has to find every vertex, and since you are recording
> >> only the first edge used to arrive at each vertex, these edges must
> >> form a tree. This works even if there are cycles. The algorithm is O(|
> >> E|).
>
> >> Note that in general a graph doesn't have a single root. So you'd
> >> search from all roots. Another way to think about this: introduce
> >> your own dummy root and edges to each vertex where there are no
> >> incident "in" edges. Of course you don't report the dummy edges.
>
> >> On Mar 12, 1:09 pm, atul anand wrote:
> >> > i guess they were talking abt spanning tree , so you can use prism or
> >> > kruskal algo to do the same.
>
> >> > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq
> >> wrote:
> >> > > Hello friends,
>
> >> > > I recently had an onsite MS interview. One of the questions that they
> >> > > asked was:
>
> >> > > - Given a directed graph, write a program that takes root of the
> >> graph
> >> > > and returns root of a tree which comprises of all the nodes of the
> >> graph in
> >> > > the same way as they appeared in the graph (the graph contains no
> >> cycles).
>
> >> > > --
> >> > > Umer
>
> >> > > --
> >> > > You received this message because you are subscribed to the Google
> >> Groups
> >> > > "Algorithm Geeks" group.
> >> > > To post to this group, send email to algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > > algogeeks+unsubscr...@googlegroups.com.
> >> > > For more options, visit this group at
> >> > >http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Umer
>
> --
> Umer
Re: [algogeeks] Maximum size square sub-matrix with all 1s
@ ALL finding square matrix is quite a standard question and nw an easy one as everyone knows the reccussence atul has given. but i wanted to find max rectangle.. i know there is a DP for it. in O(n^2). for nxn matrix..don't know the whole approach .but here is what i remember.. 1. aproach is simple to keep track of max rectangle which can be formed from any point taking that point as top left corner of max rectangle and proceed further down . can someone suggest how can be proceed further.. [ NOTE: problem occurs mainly when their are more than one rectangles which can be formed from same point ] plz.. don't suggest the histogram method it's just a dirty way of avoiding to work on getting this DP right. :-) On Mon, Mar 12, 2012 at 11:29 PM, atul anand wrote: > here is the recurrence for solving this > > R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] ) > ); > > > On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma wrote: > >> >> April 4, 2010 >> >> Given a binary matrix, find out the maximum size square sub-matrix with >> all 1s. >> >> For example, consider the below binary matrix. >> >>0 1 1 0 1 >>1 1 0 1 0 >>0 1 1 1 0 >>1 1 1 1 0 >>1 1 1 1 1 >>0 0 0 0 0 >> >> The maximum square sub-matrix with all set bits is >> >> 1 1 1 >> 1 1 1 >> 1 1 1 >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Maximum size square sub-matrix with all 1s
wats d logic behind this??? On Tue, Mar 13, 2012 at 11:59 AM, atul anand wrote: > here is the recurrence for solving this > > R[i, j] = (M[i,j] == 0 ? 0 : 1 + min( R[i-1, j], R[i-1, j-1], R[i,,j-1] ) > ); > > On Tue, Mar 13, 2012 at 11:48 AM, rahul sharma wrote: > >> >> April 4, 2010 >> >> Given a binary matrix, find out the maximum size square sub-matrix with >> all 1s. >> >> For example, consider the below binary matrix. >> >>0 1 1 0 1 >>1 1 0 1 0 >>0 1 1 1 0 >>1 1 1 1 0 >>1 1 1 1 1 >>0 0 0 0 0 >> >> The maximum square sub-matrix with all set bits is >> >> 1 1 1 >> 1 1 1 >> 1 1 1 >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Hi
interview-str...@googlegroups.com, On Tue, Mar 13, 2012 at 8:34 AM, Supraja Jayakumar wrote: > Hi > > Yes I will do that. I posted it to interview-str...@googlegroups.com. I > do not find this group's id right. Pls tell me the id to which I have to > subscribe. > > Thanks > > > On Mon, Mar 12, 2012 at 10:09 AM, rahul sharma wrote: > >> plz put these on interview street >> >> On Mon, Mar 12, 2012 at 2:59 AM, Supraja Jayakumar < >> suprajasank...@gmail.com> wrote: >> >>> Hi >>> >>> Has anyone here given a VMWare interview. Could someone tell me about >>> it. >>> >>> Thanks >>> >>> -- >>> U >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from 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. >> > > > > -- > U > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft Interview Question
http://www.geeksforgeeks.org/archives/1155 On Tue, Mar 13, 2012 at 11:31 AM, Umer Farooq wrote: > Yes that is exactly what they wanted. I proposed BFS for this solution. > Anyway, there was another problem that I was able to solve; but the > interviewer brought up a much more efficient approach. > > The problem was: > > >- Given a linked a linked list with one pointer pointing to next, >another pointer pointing to any random pointer in the list. The random >pointer can be before or after the current pointer or it can even be at the >same node. Write a piece of code that can produce an exact copy of the >linked list. > > > On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq wrote: > >> Yes that is exactly what they wanted. I proposed BFS for this solution. >> Anyway, there was another problem that I was able to solve; but the >> interviewer brought up a much more efficient approach. >> >> The problem was: >> >> Given a linked l >> >> >> On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote: >> >>> Since there is no mention of weights, you are looking for any spanning >>> tree. Primm and Kruskal are for _minimum_ spanning tree. They are >>> overkill for this problem. >>> >>> You can construct a spanning tree in any graph with DFS. Just record >>> every edge you find that reaches a vertex that has never been visited >>> before. This has to find every vertex, and since you are recording >>> only the first edge used to arrive at each vertex, these edges must >>> form a tree. This works even if there are cycles. The algorithm is O(| >>> E|). >>> >>> Note that in general a graph doesn't have a single root. So you'd >>> search from all roots. Another way to think about this: introduce >>> your own dummy root and edges to each vertex where there are no >>> incident "in" edges. Of course you don't report the dummy edges. >>> >>> On Mar 12, 1:09 pm, atul anand wrote: >>> > i guess they were talking abt spanning tree , so you can use prism or >>> > kruskal algo to do the same. >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq >>> wrote: >>> > > Hello friends, >>> > >>> > > I recently had an onsite MS interview. One of the questions that they >>> > > asked was: >>> > >>> > >- Given a directed graph, write a program that takes root of the >>> graph >>> > >and returns root of a tree which comprises of all the nodes of >>> the graph in >>> > >the same way as they appeared in the graph (the graph contains no >>> cycles). >>> > >>> > > -- >>> > > Umer >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to algogeeks@googlegroups.com. >>> > > To unsubscribe from this group, send email to >>> > > algogeeks+unsubscr...@googlegroups.com. >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> Umer >> > > > > -- > Umer > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Novell - Round-2 Question (Common Substring)
Could anyone please tell me if Suffix Trees would be appropriate here to use? or kindly suggest me a better data structure. On 3/13/12, reynald reni wrote: > Chunyuan, can this complexity be still reduced with any other data > structure? > > On 3/13/12, Chunyuan Ge wrote: >> it's a classic problem like Time = O(n*n), space = O(n) >> >> On Tue, Mar 13, 2012 at 12:55 PM, InThirstOfWisdom.rr < >> reni.reyn...@gmail.com> wrote: >> >>> Algorithm to find the longest common substring of given set of >>> strings, with much less time and space complexity. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from 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] Novell - Round-2 Question (Common Substring)
Chunyuan, can this complexity be still reduced with any other data structure? On 3/13/12, Chunyuan Ge wrote: > it's a classic problem like Time = O(n*n), space = O(n) > > On Tue, Mar 13, 2012 at 12:55 PM, InThirstOfWisdom.rr < > reni.reyn...@gmail.com> wrote: > >> Algorithm to find the longest common substring of given set of >> strings, with much less time and space complexity. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from 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: Microsoft Interview Question
Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: - Given a linked a linked list with one pointer pointing to next, another pointer pointing to any random pointer in the list. The random pointer can be before or after the current pointer or it can even be at the same node. Write a piece of code that can produce an exact copy of the linked list. On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq wrote: > Yes that is exactly what they wanted. I proposed BFS for this solution. > Anyway, there was another problem that I was able to solve; but the > interviewer brought up a much more efficient approach. > > The problem was: > > Given a linked l > > > On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote: > >> Since there is no mention of weights, you are looking for any spanning >> tree. Primm and Kruskal are for _minimum_ spanning tree. They are >> overkill for this problem. >> >> You can construct a spanning tree in any graph with DFS. Just record >> every edge you find that reaches a vertex that has never been visited >> before. This has to find every vertex, and since you are recording >> only the first edge used to arrive at each vertex, these edges must >> form a tree. This works even if there are cycles. The algorithm is O(| >> E|). >> >> Note that in general a graph doesn't have a single root. So you'd >> search from all roots. Another way to think about this: introduce >> your own dummy root and edges to each vertex where there are no >> incident "in" edges. Of course you don't report the dummy edges. >> >> On Mar 12, 1:09 pm, atul anand wrote: >> > i guess they were talking abt spanning tree , so you can use prism or >> > kruskal algo to do the same. >> > >> > >> > >> > >> > >> > >> > >> > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq >> wrote: >> > > Hello friends, >> > >> > > I recently had an onsite MS interview. One of the questions that they >> > > asked was: >> > >> > >- Given a directed graph, write a program that takes root of the >> graph >> > >and returns root of a tree which comprises of all the nodes of the >> graph in >> > >the same way as they appeared in the graph (the graph contains no >> cycles). >> > >> > > -- >> > > Umer >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algogeeks@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com. >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Umer > -- Umer -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft Interview Question
Yes that is exactly what they wanted. I proposed BFS for this solution. Anyway, there was another problem that I was able to solve; but the interviewer brought up a much more efficient approach. The problem was: Given a linked l On Mon, Mar 12, 2012 at 11:31 PM, Gene wrote: > Since there is no mention of weights, you are looking for any spanning > tree. Primm and Kruskal are for _minimum_ spanning tree. They are > overkill for this problem. > > You can construct a spanning tree in any graph with DFS. Just record > every edge you find that reaches a vertex that has never been visited > before. This has to find every vertex, and since you are recording > only the first edge used to arrive at each vertex, these edges must > form a tree. This works even if there are cycles. The algorithm is O(| > E|). > > Note that in general a graph doesn't have a single root. So you'd > search from all roots. Another way to think about this: introduce > your own dummy root and edges to each vertex where there are no > incident "in" edges. Of course you don't report the dummy edges. > > On Mar 12, 1:09 pm, atul anand wrote: > > i guess they were talking abt spanning tree , so you can use prism or > > kruskal algo to do the same. > > > > > > > > > > > > > > > > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq > wrote: > > > Hello friends, > > > > > I recently had an onsite MS interview. One of the questions that they > > > asked was: > > > > >- Given a directed graph, write a program that takes root of the > graph > > >and returns root of a tree which comprises of all the nodes of the > graph in > > >the same way as they appeared in the graph (the graph contains no > cycles). > > > > > -- > > > Umer > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Umer -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
