Software Programming

Kunuk Nykjaer

Posts Tagged ‘interview-question

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

Interview-question: How to find all permutations of a given word in a given text? – Java example

with one comment

Write a function (in Java) to find all permutations of a given word that appear in a given text. For example, for word abc and text abcxyaxbcayxycab the function should return abc, bca, cab.

Answer:
To find a permutation of a string you can use number theory.

There is a method where you can calculate a hash of a string using prime numbers. Every permutation of the same string will give the same hash value. All other string combination which is not a permutation will give some other hash value.

The hash-value is calculated by c1 * p1 + c2 * p2 + … + cn * pn
where ci is a unique value for the current char in the string and where pi is a unique prime number value for the ci char.

Here is the implementation.
Main.java

// Author: Kunuk Nykjaer
public class Main {
	final static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 
		19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
		73, 79, 83, 89, 97, 101, 103, 107, 109, 113 };
	
	public static void main(String[] args) {		
		final char[] text = "abcxaaabbbccyaxbcayaaaxycab"
			.toCharArray();			
		int hash = val(new char[]{'a','b','c'});					
		for (int i = 0; i < text.length - 2; i++) {
			char[] _123 = new char[]{text[i],text[i+1],text[i+2]};			
			if(val(_123)==hash){
				System.out.println(new String(_123) );		
			}
		}
	}	
	static int p(char c) {
		return primes[(int)c - (int)'a'];
	}	
	static int val(char[] cs) {
		return 
		p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2];
	}
}

The output is: abc bca cab

Reference:
http://stackoverflow.com/questions/10727118/how-to-find-all-permutations-of-a-given-word-in-a-given-text

Written by kunuk Nykjaer

May 25, 2012 at 1:20 pm

Posted in Algorithm, Java

Tagged with

Interview-question: Getting top 100 URL from a large log file – C# example

leave a comment »

We have a fairly large log file, about 5GB. Each line of the log file contains an url which a user has visited on our site. We want to figure out what’s the most popular 100 urls visited by our users. How to do it?

Answer:
Because the log file is fairly large you should read the log-file using a stream-reader.
Don’t read it all in the memory.
I would expect it is feasible to have the number of possible distinct links in the memory while we work on the log-file since it is links within a website.

// Pseudo
Hashmap map<url,count>
while(log file has nextline){
    url = nextline in logfile
    add url to map and update count
}

List list 
foreach(m in map){
    add m to list         
}

sort the list by count value
take top n from the list

The runtime is O(n) + O(m*log(m)) where n is the size of the log-file in lines and where the m is number of distinct found links.

Here’s a C# implementation of the pseudo-code. An actual file-reader and a log-file is not provided.
A simple emulation of reading a log-file using a list in the memory is provided instead.

The algorithm uses a hashmap to store the found links. A sorting algorithm founds the top 100 links afterward. A simple data container data-structure is used for the sorting algorithm.

The memory complexity is dependent on expected distinct links. The hashmap must be able to contain the found distinct links, else this algorithm won’t work.

Program.cs

// Implementation
using System;
using System.Collections.Generic;
using System.Linq;

// Author: Kunuk Nykjaer
public class Program
{
    public static void Main(string[] args)
    {
        RunLinkCount();
        Console.WriteLine("press a key to exit"); 
        Console.ReadKey();
    }

    class LinkData : IComparable
    {
        public string Url { get; set; }
        public int Count { get; set; }
        public int CompareTo(object obj)
        {
            var other = obj as LinkData;
            int i = other == null ? 0 : other.Count;
            return i.CompareTo(this.Count);
        }
    }

    static void RunLinkCount()
    {
        // Data setup
        var urls = new List<string>();
        var rand = new Random();
        const int loglength = 500000;
        // Emulate the log-file
        for (int i = 0; i < loglength; i++)
        {
            urls.Add(string.Format("http://{0}.com", rand.Next(1000)
                 .ToString("x")));
        }

        // Hashmap memory must be allocated 
        // to contain distinct number of urls
        var lookup = new Dictionary<string, int>();

        var stopwatch = new System.Diagnostics.Stopwatch();
        stopwatch.Start();

        // Algo-time
        // O(n) where n is log line count
        foreach (var url in urls) // Emulate stream reader, readline
        {
            if (lookup.ContainsKey(url))
            {
                int i = lookup[url];
                lookup[url] = i + 1;
            }
            else
            {
                lookup.Add(url, 1);
            }
        }

        // O(m) where m is number of distinct urls
        var list = lookup.Select(i => new LinkData 
             { Url = i.Key, Count = i.Value }).ToList();
        // O(mlogm)
        list.Sort();
        // O(m)
        var top = list.Take(100).ToList(); // top urls

        stopwatch.Stop();
        // End Algo-time

        // Show result
        // O(1)
        foreach (var i in top)
        {
            Console.WriteLine("Url: {0}, Count: {1}", i.Url, i.Count);
        }

        Console.WriteLine(string.Format("Time elapsed msec: {0}",
           stopwatch.ElapsedMilliseconds));
    }
}

Reference:
http://stackoverflow.com/questions/10733983/getting-top-100-url-from-a-log-file

Written by kunuk Nykjaer

May 25, 2012 at 1:01 pm

Posted in Algorithm, Csharp

Tagged with