Candy Problem for k size window I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.
Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour. 
So, the problem is basically for every i in range[1, n] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.
Is there any linear time solution for this?
Compute the sorted scores (and associated children) in the first window with a persistent sorted tree. This step takes $O(k \log k)$ time.
Create a DAG on children and add a directed edge from each child to each other child who is between $p$ and $2p$ places lower than it. This step takes $O(pk)$ time.
Shift the window forward one child at a time. Incrementally update the tree to obtain a new one for this window in $O(\log k)$ time per tree.
In each tree in step 3, place directed edges between pairs of children of distance $p$ where the child that entered the window in this tree is in between the children in the pair. This can be done in $O(p)$ time per tree (avoiding a $\log k$ factor) if one starts at the node obtained by insertion in step 3.
Assign candies to children topologically: each leaf child gets 1 candy; each internal child gets max(child's candies) + 1 candies. This runs in $O(n)$ time.
Sum the candies.


Note: the DAG with all of the edges from steps 2 and 4 sorts children by relative number of candies.

The resulting algorithm runs in $O(n(p+\log k))$ time.