Re: [algogeeks] Find the max element of sets of size K
Hey, isn't it as simple as:
1. Start at sum of the first K elements.
2. Move the "window" of size K by one element to the right at each step.
Subtract the left, add the right => get the new sum. Keep the maximum.
This executes in O(n) steps, requires O(1) memory. The code in C++ seems to
be trivial:
pair max_k(int a[], int n) {
int sum_k = accumulate(a, a+k, 0);
int max_sum = sum_k, max_id = 0;
for (int i = k; i < n; ++i) {
sum_k = sum_k - a[i - k] + a[i];
if (sum_k > max_sum) {
max_sum = sum_k;
max_id = i - k + 1;
}
}
return make_pair(max_id, max_sum);
}
... or do I miss something?
On Wednesday, September 11, 2013 7:14:24 AM UTC-4, kumar raja wrote:
>
> I heard there exists a O(n) algorithm in DP? Does anyone has the idea
> about it?
>
>
> On 11 September 2013 03:21, Aaquib Javed
> > wrote:
>
>> http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/
>>
>>
>> On Tue, Sep 10, 2013 at 11:46 PM, kumar raja
>>
>> > wrote:
>>
>>> suppose we have n numbers and k <=n.
>>>
>>> Then a1,a2... ak is one set.
>>>
>>> then a2,a3 ak+1 is other set.
>>> ...
>>> so totally we can have n-k+1 sets.
>>>
>>> how to figure out the maximum elements of all these k size sets with
>>> least possible time complexity and space complexity?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+...@googlegroups.com .
>>>
>>
>>
>>
>> --
>> Aaquib Javed
>> B.Tech. Final Year
>> Electronics & Comm Engineering
>> MNNIT Allahabad.
>> +91-8953519834
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+...@googlegroups.com .
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Triangle war problem - C++
Start at this one: http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning -IB On Friday, August 2, 2013 1:56:14 AM UTC-4, Naren s wrote: > > > Can anyone help me solve this problem. > > http://poj.org/problem?id=1085 > > > -- > Regards, > *Narayanan S* > > -- 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.
[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: 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.
