10
\$\begingroup\$

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 < 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 > 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 > 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));
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Probably a naive question but what is back = back.Next = value; supposed to do ? \$\endgroup\$ – Josay Jun 18 '14 at 21:09
  • 1
    \$\begingroup\$ @Josay Cascading assignment from right to left. \$\endgroup\$ – BenVlodgi Jun 18 '14 at 21:15
5
\$\begingroup\$

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<T> class, the algorithm would look like this:

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

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

private class SortedBag<T>
{
    private readonly Dictionary<T, int> count = new Dictionary<T, int>();
    private readonly SortedSet<T> set = new SortedSet<T>();

    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.

\$\endgroup\$
  • \$\begingroup\$ { 1, 3, 2 } is actually the correct output. I believe my current solution could be considered a skip list, as once I pick a max, I never check values before it. You are correct though that I am duplicating data when I could/should just use indices. I've ran your code, and it does work(except for that false assumption about the last frame. However your implementation is on average 4 times slower than mine. Thank you for the link as-well, the final solution is something I had tried to implement on a static scale (1 fallback value), and failed. I will try again with a scaleable list. \$\endgroup\$ – BenVlodgi Jun 19 '14 at 14:56
  • \$\begingroup\$ Thanks for the feedback and clarification of the problem. Could you please post a test case where my solution runs slower? I'll have a look at it after work. \$\endgroup\$ – mjolka Jun 20 '14 at 1:33
  • \$\begingroup\$ I actually made a github repo, and added you as a contributor for it. It has 2 test cases, one for quickly recognizing if the algorithm runs correctly, and a massive one for performance testing. \$\endgroup\$ – BenVlodgi Jun 20 '14 at 3:52
  • \$\begingroup\$ Accepted as answer because you reviewed my code, pointed out some flaws, and provided an interesting alternative solution to the problem, with a link to a helpful resource about my exact problem and solution. Thanks! \$\endgroup\$ – BenVlodgi Jun 20 '14 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.