Software Programming

Kunuk Nykjaer

Interview-question: Find two largest elements in array of size n – C# example

with one comment


Design an algorithm to find the two largest elements in a sequence of n numbers.
Number of comparisons need to be O(n) + O(log n)

Answer:
You use a tournament sort.
Here’s an example in C#

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

/// <summary>
/// Author: Kunuk Nykjaer
/// Tournament Sort example
/// http://en.wikipedia.org/wiki/Tournament_sort
/// </summary>
class Program
{
    class P
    {
        public int Strength { get; set; }
        public List<int> Opponents { get; private set; }
        public P()
        {
            Opponents = new List<int>();
        }
    }

    // Return winner of the match and remember opponent
    // O(1)
    static P Play(P p1, P p2)
    {
        if (p1.Strength > p2.Strength)
        {
            p1.Opponents.Add(p2.Strength);
            return p1;
        }
        p2.Opponents.Add(p1.Strength);
        return p2;
    }

    // Runtime O(n) + O(logn)
    static void Main(string[] args)
    {
        // Test data setup, even number list
        var playerStrengths = new[] { 1, 2, 5, 4, 9, 7, 8, 7, 5, 4, 1, 0, 1, 4, 2, 3 };
        var players = playerStrengths.Select(i => new P { Strength = i }).ToList();

        // O(n)
        while (players.Count > 1)
        {
            var nextRound = new List<P>();
            for (int i = 0; i < players.Count - 1; i += 2)
            {
                P winner = Play(players[i], players[i + 1]);
                nextRound.Add(winner); // add winner of the match
            }
            players = nextRound;
        }

        // O(1)
        var tournamentWinner = players.First();
        int first = tournamentWinner.Strength;
        int second = -1;

        // O(logn)            
        foreach (int i in tournamentWinner.Opponents)
            if (i > second)// update                
                second = i;

        Console.WriteLine("First: {0}, Second: {1}", first, second);
        Console.WriteLine("press key..."); Console.ReadKey();
    }
}

Output is:
First: 9, Second: 8

Reference:
http://stackoverflow.com/questions/10591112/interview-algorithm-find-two-largest-elements-in-array-of-size-n

http://en.wikipedia.org/wiki/Tournament_sort

http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

Advertisements

Written by kunuk Nykjaer

May 25, 2012 at 3:42 pm

Posted in Algorithm, Csharp

Tagged with

One Response

Subscribe to comments with RSS.

  1. Aw, this was an exceptionally nice post. Spending some time and actual effort to make a very good article… but what can I say… I put things off a lot and
    don’t manage to get anything done.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: