4
\$\begingroup\$

This challenge is from Talent Buddy:

Tweets per second

Japan Castle in the Sky airing broke a Twitter record on August 3, 2013. At one point during the classic anime movie showing, people submitted 143,199 tweets per second. This particular spike was about 25 times greater than Twitter’s steady state.

Given an array of integers representing the number of tweets recorded every second and an integer value K, 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 K seconds before it

Note that your function will receive the following arguments: tps, which is an array of integers representing the number of tweets recorded every second, and k, which is the integer number mentioned above.

Data constraints: the length of the array above will not exceed 500,000 numbers

Efficiency constraints: your function is expected to print the requested result and return in less than 2 seconds

Example Input

tps: 6, 9, 4, 7, 4, 1

k: 3 Output

6 9 9 9 7 7 Please Note: The above program should run in below 2 seconds

Below is my code in c#

public void tweets_per_second(int[] tps, int k) {
    // Write your code here
    // To print results to the standard output you can use Console.WriteLine()
    // Example: Console.WriteLine("Hello world!");

    for(int i=0; i<tps.Length;i++)
    {
        Console.WriteLine(FindMaxLastK(tps, i, k));

    }
}
// method to check the maximum of last k items in the array
public int FindMaxLastK(int[] tps, int start, int k)
{
    k = k-1;
    int max = 0;
 while(k >= 0 && start >= 0)
 {
     max = tps[start] > max? tps[start]:max;
     k--;
     start--;
 }
    return max;
}

The code has been accepted by the website, but somehow I feel it can be done better. Any suggestions?

\$\endgroup\$
2
\$\begingroup\$

Naming

Your FindMaxLastK method doesn't describe it's intention very well, what is tps and k when viewed at a glance?. What you have is a windowing function finding the max within that window. Name your function after that:

static int MaxInWindow(int[] values, int start, int trailingWindowSize)

The conditional expression in your max function could be clearer if you used Math.Max(int, int)


My implementation would look like:

public static int MaxInWindow(int[] values, int start, int trailingWindowSize)
{
    //TODO Validate arguments
    var lowerBound = Math.Max(start - trailingWindowSize, -1);
    var max = values[start];
    for (int index = start - 1; index > lowerBound; index--)
    {
        max = Math.Max(max, values[index]);
    }
    return max;
}

Performance

Your solution is O(m * n) where m is the number of seconds and n is the window size. I just saw the answer in a related question and the optimal solution is O(m).

The solution uses a LinkedList to keep track of the max in the window. Here is my implementation in C#:

public static IEnumerable<T> MaxInSlidingWindow<T>(T[] values, int windowSize)
{
    var comparer = Comparer<T>.Default;
    var window = new LinkedList<Tuple<T, int>>();// Max at position and position

    var length = values.Length;
    for (var index = 0; index < length; index++)
    {
        var value = values[index];
        while (window.Count != 0 && comparer.Compare(window.Last.Value.Item1, value) < 0)
        {
            window.RemoveLast();
        }

        window.AddLast(Tuple.Create(value, index));

        while (window.First.Value.Item2 <= index - windowSize)
        {
            window.RemoveFirst();
        }

        yield return window.First.Value.Item1;
    }
}
\$\endgroup\$

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.