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 &lt; tweetsPerSecond.Length; i++)
    {
        // If this is our very first number being added, create new head node
        // Else append a new node to the back of the list, and set it to be the next checked node against the max
        if (head == null) max = back = head = new Node() { Value = tweetsPerSecond[i] };
        else check = back = back.Next = new Node() { Value = tweetsPerSecond[i] };

        // If we have filled up the window with values
        if (count + 1 &gt; 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;
            }
            head = head.Next;
        }
        else count++;

        // Start our checking with the set CHECK node, which is typically just the most recently added node, unless our max fell out of the window
        Node next = check;
        while (next != null)
        {
            // If this node being checked is higher than our highest found value, then set this node to be the highest (MAX), and check the next.
            if (next.Value &gt; max.Value) max = next;
            next = next.Next;
        }

        // Store our found max node in an array.
        maxes[i] = max.Value.ToString();
    }
    File.WriteAllLines("out.txt", maxes);
    //Console.WriteLine(string.Join(Environment.NewLine, maxes));
}
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&lt;T&gt; class, the algorithm would look like this:

public static IEnumerable&lt;int&gt; TweetsPerSecond(int[] tweetsPerSecond, int windowSize)
{
    var size = windowSize + 1;
    var skipList = new SkipList&lt;int&gt;(size);
    for (var i = 0; i &lt; 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&lt;T&gt; and Dictionary&lt;TKey, TValue&gt;. 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&lt;int&gt; TweetsPerSecond(int[] tweetsPerSecond, int windowSize)
{
    var size = windowSize + 1;
    var bag = new SortedBag&lt;int&gt;();
    for (var i = 0; i &lt; tweetsPerSecond.Length; i++)
    {
        if (i &gt; windowSize)
        {
            bag.Remove(tweetsPerSecond[i - size]);
        }

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

private class SortedBag&lt;T&gt;
{
    private readonly Dictionary&lt;T, int&gt; count = new Dictionary&lt;T, int&gt;();
    private readonly SortedSet&lt;T&gt; set = new SortedSet&lt;T&gt;();

    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.