[algogeeks] Amazon problem
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Intrestting problem
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Median of two sorted arrays of different sizes
How is this code dealing with the scenario where two arrays have common
number. For example where two arrays are same. A[] = {1,2,3,4} and B[] =
{1,2,3,4}. Here the median position is not (4+4)/2 rather it is 4/2.
On Sun, Jun 9, 2013 at 3:12 PM, rahul sharma rahul23111...@gmail.comwrote:
@doncan u plz explain the approach used.I didnt get this.
On 4/25/13, Don dondod...@gmail.com wrote:
Let's say you have two arrays: A[x] and B[y].
The median is the (x+y)/2th value.
If A[i] is the median, then B[(x+y)/2-i] = A[i] and B[(x+y)/2-i+1] =
A[i].
You can use a binary search to find the point where that condition
occurs. Of course you want to search on the smaller array.
You'll need some logic at the end to determine if the median is in A
or in B.
// Input arrays A and B, sizeA = sizeB
int A[sizeA];
int B[sizeB];
int min = 0;
int max = sizeA;
const int medianPos = (sizeA + sizeB) / 2;
while(max = min)
{
i = (min + max) / 2;
j = medianPos-i;
if (B[j] A[i]) min = i+1;
else if (B[j+1] A[i]) max = i-1;
else break;
}
printf(Median is %d\n, (A[i] B[j]) ? A[i] : B[j]);
Don
On Apr 24, 1:19 pm, rahul sharma rahul23111...@gmail.com wrote:
IS this code correct?
float findMedianUtil( int A[], int N, int B[], int M )
{
// If the smaller array has only one element
if( N == 1 )
{
// Case 1: If the larger array also has one element, simply call
MO2()
if( M == 1 )
return MO2( A[0], B[0] );
// Case 2: If the larger array has odd number of elements, then
consider
// the middle 3 elements of larger array and the only element of
// smaller array. Take few examples like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if( M 1 )
return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
// Case 3: If the larger array has even number of element, then
median
// will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3( B[M/2], B[M/2 - 1], A[0] );
}
// If the smaller array has two elements
else if( N == 2 )
{
// Case 4: If the larger array also has two elements, simply
call
MO4()
if( M == 2 )
return MO4( A[0], A[1], B[0], B[1] );
// Case 5: If the larger array has odd number of elements, then
median
// will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element just
//before the middle in bigger array
// 3. Min of second element of smaller array and element just
//after the middle in bigger array
if( M 1 )
return MO3 ( B[M/2],
max( A[0], B[M/2 - 1] ),
min( A[1], B[M/2 + 1] )
);
// Case 6: If the larger array has even number of elements, then
// median will be one of the following 4 elements
// 1) 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
//just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
//just after the second middle in bigger array
return MO4 ( B[M/2],
B[M/2 - 1],
max( A[0], B[M/2 - 2] ),
min( A[1], B[M/2 + 1] )
);
}
int idxA = ( N - 1 ) / 2;
int idxB = ( M - 1 ) / 2;
/* if A[idxA] = B[idxB], then median must exist in
A[idxA] and B[idxB] */
if( A[idxA] = B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] B[idxB], then median must exist in
A[...idxA] and B[idxB] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
}
In the end I suspect the following part:-
if( A[idxA] = B[idxB] )
return findMedianUtil( A + idxA, N / 2 + 1, B, M - idxA );
/* if A[idxA] B[idxB], then median must exist in
A[...idxA] and B[idxB] */
return findMedianUtil( A, N / 2 + 1, B + idxA, M - idxA );
plz comment
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
Re: [algogeeks] Re: Max-Overlapping Intervals
it is better to use Binary Index Tree ( Fenwick Tree) with time complexity O(log n) to update and O(n * log n) for finding max overlapping interval . http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=binaryIndexedTrees this link can be useful for understanding how it will work. Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Mon, Feb 25, 2013 at 10:46 AM, Sairam ravu...@gmail.com wrote: First sort the intervals So, in our example it will be as follows (2,7),(5,10),(6,15). make a map which has got interval with corresponding number of overlaps Now, iterate through each of the interval for(i=0;i(n-1);i++) for(j=0;jn;j++) update the map with the number of overlaps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
Colleagues, how about the following?
At each start point, the total number of leaving elephants increases by
one; at each end point, it decreases by one. We:
1. form a vector of pairs: {5, +1}, {10, -1}, {6, +1}, {15, -1}, {2, +1},
{7, -1} ... -- this takes O(N) time and O(N) additional space
2. Sort this vector by a) ascending .first; b) descending .second (so that
if at the same time there are both newborn and just dead elephants, we
count the overall number properly) -- O(N* logN)
3. Scan the sorted vector keeping maximal value of the counter -- O(N)
int maxcount = 0, count = 0, index = 0;
for (i = 0; i v.size(); ++i) {
count += v[i].second;
if (count maxcount) {
maxcount = count; index = i;
}
}
4. print 'maxcount' between v[index] and v[index+1]
On Thursday, February 21, 2013 4:40:17 AM UTC-5, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
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.
[algogeeks] Re: Max-Overlapping Intervals
igor way is the optimized way using prefix sum just a small correction with
in life period of (l,r) you have to do v[l]++, v[r+1]--(v is initialized
to zero ) take a prefix sum of v and return the max value containing index
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
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.
[algogeeks] Re: Max-Overlapping Intervals
ohh..sorry you have to return interval so give the starting index of prefix
sum array to the last index of containing the maximum value of array
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
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.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
Monish, please take a look at a similar problem about poor elephants in
the neighboring topic started today. I believe the problem has a similar
solution. Each start point increases the no. of active intervals by one;
each end point decreases it. So, we do the following:
1. Convert the input array of pairs (BTW, the points don't have to be of an
integral type!) into the following vector:
{ {2,+1}, {3,-1}, {3, +1}, {4, -1}...} This takes O(N) time and O(N)
additional memory
2. Sort the vector by: a) ascending .first; b) descending .second -- this
makes sure we count the intervals properly in case multiple intervals start
and end at the same point. Complexity is O(N*logN).
3. Convert relative counters to absolute; complexity is O(N).
int count = 0;
for (int i = 0; i v.size(); ++i) {
count += v.second;
assert (count =0);
v.second = count;
}
assert (count == 0);
4. After this preparation work ( O(N*logN) time, O(N) memory), answering
the question about the number of intervals for any numbers takes O(logN) --
use lower_bound() to binary search in the sorted vector.
On Sunday, June 9, 2013 3:20:46 AM UTC-4, 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.
[algogeeks] Re: Intrestting problem
How about the following: 1. Think every cell on a board occupied by an O is a vertex in a non-directed graph. Add a special vertex called OuterWorld. 2. Connect all neighboring vertices with edges, based on how you define surrounded by X-es. E.g. in your picture, diagonals are not allowed. 3. Connect all vertices on the board's boundaries to the OuterWorld vertex. Now, you should split your graph into connected subgraphs (use DFS or BFS - both will work). You will get at most one subgraph containing the OuterWorld vertex (which you don't touch) plus zero or more subgraphs of surrounded O-vertices (where you flip all vertices from O to X. An alternative approach would be to represent O-regions using Disjoint Sets to and use Find-And-Union algorithm to solve it. Thanks! On Tuesday, June 11, 2013 3:05:30 AM UTC-4, Jai Shri Ram wrote: Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Google Interview Question: In how many intervals does a number exists
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 sharadsin...@gmail.com 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.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
Adding to the question. See inline. On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: There are n Intervals. *1 = n = 1,000,000.* *Limits of interval are within 64 bit signed int.* 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 - 2 as 2 lies in *2* intervals. viz. [2,3], [1,4] 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.
[algogeeks] Re: Intrestting problem
// Flip a region including location (x,y) from from to to.
// Returns true if region is surrounded.
bool flip(char board[][], int n, int x, int y, char from, char to)
{
if ((x = 0) (y = 0) (x n) (y n)) return false;
if (board[x][y] != from) return true;
board[x][y] = to;
return flip(board,n,x-1,y) flip(board,n,x+1,y)
flip(board,n,x,y-1) flip(board,n,x,y+1);
}
// Flips all regions of 'O' completely surrounded by 'X' to 'X'
void captureSurrounded(char board[][], int n, int x, int y)
{
int x,y;
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (flip(board,n,x,y,'O','v'))
flip(board,n,x,y, 'v', 'X');
// Set regions not surrounded back to 'O'
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (board[x][y] == 'v') board[x][y] = 'O';
}
On Jun 11, 3:05 am, Jai Shri Ram del7...@gmail.com wrote:
Given a 2D board containing 'X' and 'O', capture all regions surrounded by
'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded
region .
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
