Tweets per second, using linked list

This is a TalentBuddy Challenge


Your task is to
write a function that prints to the standard output (stdout) the highest number of tweets recorded between each second in the array and the past windowSize seconds before it


Note that your function will receive the following arguments:


TweetsPerSecond
which is an array of integers representing the number of tweets recorded every second


WindowSize
which is the integer number mentioned above

I've ran my code on talentbuddy, and I think their back-end is broken, because it says my test case fails from missing data (far down the line), and when I run the test on my machine with the same inputs it prints out the right amount and correct data, in 30-80 Milliseconds. SO IT WORKS.

I am looking for a general review of my code and practices. Keep in mind that efficiency is key here.

I've added useful comments to document the flow of the program (even though they make it look ugly)

```
class Node
{
public Node Next;
public int Value;
}

public static void TweetsPerSecond(int[] tweetsPerSecond, int windowSize)
{
Node head = null; // Front of the window (where values fall out)
Node max = null; // Node with max value in the window
Node check = null; // Starting node of list of Nodes to be checked against the max
Node back = null; // End of the window (where new values are put in)

int count = 0; // Count of numbers in the window
string[] maxes = new string[tweetsPerSecond.Length]; // Max values to be printed to the console.
for (int i = 0; i windowSize)
{
// If the maximum value is falling out of the window
if (head == max)
{
// Maximum value is defaultly set to the first value in the window
max = head.Next;
// And we set the next nodes to be tested against this new max to be all nodes in the window after the max
check = max.Next;
}

First of all, I think there is an off-by-one error in your code. From my understanding of the question, the correct output for

var tweetsPerSecond = new[] { 1, 3, 2 };
var windowSize = 1;

would be { 1, 3, 3 }, while your code gives the answer { 1, 3, 2 }.

Also a window size of 0 throws a NullReferenceException.

While there are minor stylistic complaints I would focus on in a normal code review, I believe the bigger picture is that you are using the wrong data structures for this problem.

You are duplicating the information stored in tweetsPerSecond, an array, in a linked list. You don't need this duplication, you can just index into the array.

Second, to find the maximum in a range in the array, you are iterating through the entire range. Using a skip list would change this from an \$O(n)\$ operation to an \$O(1)\$ operation, with adding and removing elements being \$O(\log n)\$.

Assuming an implementation of a SkipList class, the algorithm would look like this:

public static IEnumerable TweetsPerSecond(int[] tweetsPerSecond, int windowSize)
{
    var size = windowSize + 1;
    var skipList = new SkipList(size);
    for (var i = 0; i < tweetsPerSecond.Length; i++)
    {
        if (skipList.Count == size)
        {
            skipList.Remove(tweetsPerSecond[i - size]);
        }

        skipList.Add(tweetsPerSecond[i]);
        yield return skipList.Last;
    }
}

If you don't want to go to the trouble of implementing a skip list, I think you can fake it with a combination of SortedSet and Dictionary. I couldn't find guarantees of the run time of the relevant operations on MSDN, but it runs much faster on this test input:

var tweetsPerSecond = Enumerable.Range(0, 100000).Reverse().ToArray();
var windowSize = 10000;

Here is the sample code (possibly buggy):

public static IEnumerable TweetsPerSecond(int[] tweetsPerSecond, int windowSize)
{
    var size = windowSize + 1;
    var bag = new SortedBag();
    for (var i = 0; i  windowSize)
        {
            bag.Remove(tweetsPerSecond[i - size]);
        }

        bag.Add(tweetsPerSecond[i]); 
        yield return bag.Max;
    }
}

private class SortedBag
{
    private readonly Dictionary count = new Dictionary();
    private readonly SortedSet set = new SortedSet();

    public void Remove(T value)
    {
        count[value] = count[value] - 1;
        if (count[value] == 0)
        {
            this.set.Remove(value);
            this.count.Remove(value);
        }
    }

    public void Add(T value)
    {
        int occurrences;
        if (this.count.TryGetValue(value, out occurrences))
        {
            this.count[value] = occurrences + 1;
            return;
        }

        this.count[value] = 1;
        this.set.Add(value);
    }

    public T Max
    {
        get { return this.set.Max; }
    }
}

Edit: there's a better solution with \$O(n)\$ complexity. I had great fun thinking about this problem, and would recommend anyone reading this post to think it through further before clicking that link.

StackExchange Code Review Q#54662, answer score: 5