[algogeeks] Modify Queue Data Structure which returns min in O(1) time.

[malli]

A queue data structure has functions enqueue(int x) ( inserts element
in right end), dequeue() ( deletes element from left end) functions.
These operations take O(1) time. Modify this queue data structure, so
that  it supports findmin() which returns minimum element of stack in
O(1) time.

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

[algogeeks] Largest Rectangle in a binary Matrix:

[malli]

Largest Rectangle in a Matrix:

Given an n by n matrix with zeros and ones, find the largest sub-
matrix full of ones in linear time.  I was told that a solution with
O(n) time complexity exists. If there are n^2 elements in a n X n
matrix how does a linear solution exist?

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

[algogeeks] Re: All numbers in Array repeat twice except two

[malli]

@mahesh Gupta

Nice solution. Thank you. You have explained it well.

On Oct 4, 5:01 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote:
 The problem could be solved using xor logic. First take xor of all the
 elements .Doing that we get a value which is xor of the two non repeating
 elements(as xor of similar values is 0). Now xor of two non repeating
 numbers contains bits set at those places where the two numbers differ. Now
 if we take any set bit of our result and again xor all those values of set
 where that bit is set we get first non-repeating value. Taking xor of all
 those values where that bit is not set gives the another non-repeating
 number..
 For ex
 let a[]={2,3,4,3,2,6}

 xor of all values=0010
 Now we need to get any set bit. We can extract the rightmost set bit of any
 number n by taking ( n  ~(n-1))

 Here 2nd bit is the rightmost set bit.

 Now when we take xor of all values where 2nd bit is set(this could be done
 as (a[i]  0010) , we get  6
 Taking xor of all values where 2nd bit is not set yields 4.

 Mukesh Gupta
 Delhi College of Engineering



 On Mon, Oct 4, 2010 at 3:17 PM, malli mallesh...@gmail.com wrote:
  I have an array. All numbers in the array repeat twice except two
  numbers which repeat only once. All the numbers are placed randomly.
  Goal is to find out efficiently the two  numbers that have not
  repeated  with O(1) extra memory. Expecting linear solution.

  --
  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.comalgogeeks%2bunsubscr...@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.

[algogeeks] All numbers in Array repeat twice except two

[malli]

I have an array. All numbers in the array repeat twice except two
numbers which repeat only once. All the numbers are placed randomly.
Goal is to find out efficiently the two  numbers that have not
repeated  with O(1) extra memory. Expecting linear solution.

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

[algogeeks] Finding all loops in a directed graph

[malli]

Hello All.

How can I detect all loops in a directed graph?
I would like to detect the starting node of the loop as well as the
closing 
edge of the loop.


Thanks in Advance.

Regards,
Mallikarjun.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Finding all loops in a directed graph

[malli]

using DFS the loop would get detected more than once.
If we use DFS a loop would be detected 'n' times if there are 'n' nodes
in the loop.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---