CareerCup

//use a queue of size 10 to store each customers data
void updateReadingSpeeds(String customerID, String bookID, int pageNumber)
var queue = getCustomerQueueById(customerID, bookID) //composite key
queue.pop();
queue.enqueue(pageNumber);
save(queue);

void printLeaderboard(String bookID)
var queue = getQueuesByBookId(bookID)
var iterator = queue.iterator();

Iterator listGroupedBySpeed = groupBySpeed(iterator);
Iterator sortedListBySpeed = sort(iterator);
foreach(item in sortedListBySpeed)
print(item)

def sort // sorts by reading speed. trivial implementation
def groupBy //returns new list of items indexed by reading speed. trivial implementation

I did solve this using keyed data structures which holds the problem states.

While printing leader board, I am having to iterate through all customers reading the book and that's O(N2) time complex solution + O(N log N) for sorting the N customers by reading speed time.

Clearly not the best solution, did anyone come up with anything which is highly optimized?

import std.stdio;
import std.string;
import std.algorithm;
import std.exception;

class Speed
{
	private int[]  _speed;
	private size_t _history_len;
	private int    _last_page;

	private string _customer_id;
	private string _book_id;
	
/*
	Current Time:    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]
	Current Page:    [0, 5, 6, 8,12,15,17,21,24,27,29,31,37,42,49,52]
	Current Speed:   [0, 5, 1, 2, 4, 3, 2, 4, 3, 3, 2, 2, 6, 5, 7, 3]
	"Reading Speed": [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 6, 6, 7, 7] 
*/

	this(string customer_id, string book_id, size_t history_len = 10) 
	{ 
		this._customer_id = customer_id;
		this._book_id = book_id;
		this._history_len = history_len;
		this._last_page = 0;
		this._speed ~= 0;
	}

	public void set_page(int page)
	{
		int curent_speed = page - _last_page;
		if (curent_speed < 0) throw new Exception("New page can not be less then prior.");
		_last_page = page;
		if (_speed.length == _history_len) _speed = _speed[1..$];
		_speed ~= curent_speed;
	}

	public int get_max_speed()
	{		
		int max = _speed[0];
		foreach(item; _speed[1..$]) if (max < item)	max = item;
		return max;
	}

	public void read_new_book(string new_book_id)
	{
		this._book_id = new_book_id;
		this._speed.length = 0;
		this._speed ~= 0;
		this._last_page = 0;
	}

	public int[] get_history()
	{
		return _speed;
	}

	public string get_customer_id()
	{
		return _customer_id;
	}

	public string get_book_id()
	{
		return _book_id;
	}
}

unittest
{
	auto rs = new Speed("customer1", "book1");
	
	{
		write("ReadingSpeed::get_customer_id()");
		scope(success) writeln(" ok.");		
		assert("customer1" == rs.get_customer_id);
	}

	{
		write("ReadingSpeed::get_book_id()");
		scope(success) writeln(" ok.");		
		assert("book1" == rs.get_book_id);
	}

	{
		write("ReadingSpeed::set_page(int page)");
		scope(success) writeln(" ok.");		
		
		rs.set_page(5);
		assert([0,5] == rs.get_history);
		assert(5 == rs.get_max_speed);
		assertThrown(rs.set_page(4));
		foreach(page; [6, 8, 12, 15, 17, 21, 24, 27, 29, 31, 37, 42, 49, 52]) rs.set_page(page);		
		assert([2, 4, 3, 3, 2, 2, 6, 5, 7, 3] == rs.get_history); // keep only last 10 records
		assert(7 == rs.get_max_speed); 
	}

	{
		write("ReadingSpeed::read_new_book(string new_book_id)");
		scope(success) writeln(" ok.");		
		rs.read_new_book("book2");
		assert("book2" == rs.get_book_id);
		assert(0 == rs.get_max_speed);
		assert([0] == rs.get_history); 
	}

}


unittest
{
	Speed[string] hash;
	void updateReadingSpeeds(string customer, string book, int page) 
	{
		Speed speed = hash.get(customer, new Speed(customer, book));
		if (book != speed.get_book_id)  speed.read_new_book("book");		
		speed.set_page(page);
		hash[customer] = speed;
	}

	void printLeaderboard(string book) 
	{
		struct Reader
		{
			string customer;
			int speed;
		}

		Reader[] readers;
		foreach(customer, speed; hash)
		{
			if (book == speed.get_book_id)
				readers ~= Reader(customer, speed.get_max_speed);
		}

		sort!("a.speed > b.speed")(readers);
		foreach(i, item; readers)
		{
			writeln(item.customer, ", ", item.speed, ", ", (i+1));
		}
	}

	writeln("public void updateReadingSpeeds(string customer, string book, int page):");
	
	
	foreach(page; [6, 8, 12, 15, 17, 21, 24, 27, 29, 31, 37, 42, 49, 52]) updateReadingSpeeds("customer1", "book1", page);
	foreach(page; [6, 8, 12, 15, 17, 21, 24, 28, 29, 35, 36, 40, 45, 49]) updateReadingSpeeds("customer2", "book1", page);
	foreach(page; [6, 8, 12, 15, 19, 23, 26, 29, 29, 32, 34, 37, 41, 42]) updateReadingSpeeds("customer3", "book1", page);
	
	
	assert(7 == hash["customer1"].get_max_speed); 
	assert(6 == hash["customer2"].get_max_speed); 
	assert(4 == hash["customer3"].get_max_speed); 
	
	writeln("customer1: ", hash["customer1"].get_history);
	writeln("customer2: ", hash["customer2"].get_history);
	writeln("customer3: ", hash["customer3"].get_history);

	
	writeln("void printLeaderboard(string book):");
	printLeaderboard("book1");
}


void main()
{
	
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.ListIterator;
import java.util.Map;

public class BookPageSpeed {
	static Map<String, Map<String, CustomerReadingSpeed>> bookReadingSpeed = new HashMap<String, Map<String, CustomerReadingSpeed>>();
	static Map<String, Integer> maxBookReadingSpeed = new HashMap<String, Integer>();
	static Map<String, ArrayList<ArrayList<String>>> leaderBoard = new HashMap<String, ArrayList<ArrayList<String>>>();
	
	public static void addNewBook(String bookID){
		bookReadingSpeed.put(bookID, null);
		leaderBoard.put(bookID, null);
	}
	
	public static void addNewCustomer(String bookID, String customerID){
		Map<String, CustomerReadingSpeed>  custReadingSpeed;
		CustomerReadingSpeed cust = new CustomerReadingSpeed();
		if(bookReadingSpeed.get(bookID) == null){
			custReadingSpeed = new HashMap<String, CustomerReadingSpeed>();
		}
		else{
			custReadingSpeed = bookReadingSpeed.get(bookID);
		}
		custReadingSpeed.put(customerID, cust);
		bookReadingSpeed.put(bookID, custReadingSpeed);
		maxBookReadingSpeed.put(customerID, 0);
		ArrayList<ArrayList<String>> custLeaderBoard;
		if(leaderBoard.get(bookID) != null){
			custLeaderBoard = leaderBoard.get(bookID);
		}
		else{
			custLeaderBoard = new ArrayList<ArrayList<String>>(100);
			for(int i=0; i<101; i++){
				ArrayList<String> cust_i = new ArrayList<String>();
				custLeaderBoard.add(cust_i);
			}
		}
		custLeaderBoard.get(0).add(customerID);
		leaderBoard.put(bookID, custLeaderBoard);
	}
	
	public static void updateReadingSpeeds(String customerID, String bookID, int pageNumber){
		CustomerReadingSpeed custReadingSpeed = bookReadingSpeed.get(bookID).get(customerID);
		custReadingSpeed.CustomerReadingPage.add(pageNumber);
		int size= custReadingSpeed.CustomerReadingPage.size();
		int speed = custReadingSpeed.CustomerReadingPage.get(size-1) - custReadingSpeed.CustomerReadingPage.get(size-2);
		custReadingSpeed.CustomerReadingSpeed.add(speed);
		int prev_speed = maxBookReadingSpeed.get(customerID);
		if(speed > prev_speed){
			leaderBoard.get(bookID).get(prev_speed).remove(customerID);
			maxBookReadingSpeed.put(customerID, speed);
			leaderBoard.get(bookID).get(speed).add(customerID);
		}
	}
	
	public static void printLeaderboard(String bookID) {
		int index = 100;
		int rank =1;
		System.out.print("CustomerID, Reading Speed, Rank\n");
		ListIterator<ArrayList<String>> it = leaderBoard.get(bookID).listIterator(index);
		while(it.hasPrevious()){
			int readingSpeed = it.previousIndex();
			ArrayList<String> customers = it.previous();
			if(!customers.isEmpty()){
				for(String custID: customers){
					System.out.printf("Customer %s, %d, %d\n", custID, readingSpeed, rank);
				}
				rank++;
			}
		}
	}
	
	public static void main(String[] args){
		addNewBook("A");
		addNewCustomer("A", "A");
		addNewCustomer("A", "B");
		updateReadingSpeeds("A", "A", 2);
		updateReadingSpeeds("B", "A", 5);
		printLeaderboard("A"); 
	}
}



import java.util.ArrayList;

public class CustomerReadingSpeed {

	public ArrayList<Integer> CustomerReadingPage = new ArrayList<Integer>();
	public ArrayList<Integer> CustomerReadingSpeed = new ArrayList<Integer>();

	public CustomerReadingSpeed(){
		CustomerReadingPage.add(0);
		CustomerReadingSpeed.add(0);
	}
	
}

A dequeue (of size 10) can be used to update reading speed in O(1).

I cant do better than O(NlogN), N - # of customers. Assuming that the speeds cannot vary much till like 10 mins the average running time can be reduced (insertioin sort for near sorted i/p or a variant of heap sort)

I would love to see a better solution for ranking(sorting) the customers :)

My solution works for me. The way I looked at it, we need to be able to partition on each minute. And we needed to be able to snapshot a leaderboard every minute. So I think my approach is a bit different from the others I saw on here.

First I maintain a couple hashmaps. First, booksToCustomers. This maintains the set of customers reading the keyed book. Next is the customerToPageNumbers hashmap. This map keys customers to the list of page numbers they have read to each minute.

The way I track the last N minutes of reading it by maintaining a third map: customerToSpeeds. This maps customer to a bounded array of size N (where N is the amount of history to track). So for our case, 10, since we are only interested in the last 10 minutes.

The key functions we will need are:

updateReadingSpeeds(String customerID, String bookID, int pageNumber);
printLeaderBoard(String bookID);

I've added a few helper functions to make things a bit more modular. I will explain each and my reasoning for them below.

void updateCustomerPages(String customerID, int pageNumber, int timeBucket);
void updateCustomerSpeed(String customerID, int timeBucket, int currentSpeed);
void addCustomerToBook(String customerID, String bookID);
int fetchTimeBucket();
int calculateReadingSpeed(String customerID);

The interesting function to note is fetchTimeBucket(). I did this because I figure that we will have many clients hitting us at once. The simplest way I could think of to maintain parity and ensure that all of the speeds are kept logically is to take the time and mod it with the max history time. This function only takes current time and converts it to minutes and mods it with N. This returns the bucket of time the speed should go into for any given customer.

updateCustomerPages updates the current customer for the current time bucket.
updateCustomerSpeed will update the speed array for a given customer
addCustomerToBook simply adds a customer to a book's reader list.
calculateReadingSpeed takes the current timebucket and works its way backwards (a constant number N) and calculates the highest speed over the past N minutes.


Lastly, I've also added a helper structure/static class called LeaderEntry. This is nothing more than a value object to aid in printing the leader list.

The end result is fairly simple and could definitely use work before it is ready for prime-time. But as far as answering the question goes, I think this would suffice.

Implementation follows:

Note that I've stubbed out the time function so that I could test it in the main method. The increasePages function is just a helper for faking some data.

Hope this helps.

import java.util.*;

/**
 * @author chris moran
 */
public class KindleReadingSpeed {
    private static int time = 1;
    private static final int HISTORY_TO_TRACK = 10;
    private static Random random = new Random();
    public static void main(String[] args) {
        int[] pages = new int[4];
        int timeLength = 4;//minutes
        for(int i = 0; i < timeLength; i++) {
            increasePages(pages);
            updateReadingSpeeds("customer0", "book0", pages[0]);
            updateReadingSpeeds("customer1", "book0", pages[1]);
            updateReadingSpeeds("customer2", "book0", pages[2]);
            updateReadingSpeeds("customer3", "book1", pages[3]);
            time++;
        }

//        int speed = calculateReadingSpeed("customerID");
//        System.out.println("speed = " + speed);
        printLeaderBoard("book1");
        System.out.println();
    }
    private static void increasePages(int[] pages) {
        for(int i = 0; i < pages.length; i++) {
            pages[i] += random.nextInt(25);
        }
    }
    private static final Map<String,Set<String>> bookToCustomers = new HashMap<String, Set<String>>();
    private static final Map<String,List<Integer>> customerToPageNumbers = new HashMap<String, List<Integer>>();
    private static final Map<String,int[]> customerToSpeeds = new HashMap<String, int[]>();

    static class LeaderEntry implements Comparable<LeaderEntry>{
        private String customerID;
        private int speed;
        LeaderEntry(String customerID, int speed) {
            this.customerID = customerID;
            this.speed = speed;
        }
        @Override
        public int compareTo(LeaderEntry o) {
            return o.speed == this.speed ? -1 : o.speed - this.speed;
        }
        @Override
        public boolean equals(Object o) {
            if(this == o) return true;
            if(!(o instanceof LeaderEntry)) return false;

            LeaderEntry that = (LeaderEntry) o;

            if(speed != that.speed) return false;
            if(!customerID.equals(that.customerID)) return false;

            return true;
        }
        @Override
        public int hashCode() {
            int result = customerID.hashCode();
            result = 31 * result + speed;
            return result;
        }
    }

    private static void printLeaderBoard(String bookID) {
        System.out.println("Customer ID,Reading Speed,Rank");
        if(!bookToCustomers.containsKey(bookID)) {
            System.out.println("");
            return;
        }
        Set<String> customers = bookToCustomers.get(bookID);

        Set<LeaderEntry> leaders = new TreeSet<LeaderEntry>();
        for(String customerID : customers) {
            int speed = calculateReadingSpeed(customerID);
            LeaderEntry entry = new LeaderEntry(customerID, speed);
            leaders.add(entry);//@TODO: check for failure to add!
        }
        int rank = 1;
        for(LeaderEntry entry : leaders) {
            System.out.println(entry.customerID + "," + entry.speed + "," + rank++);
        }
    }

    private static void updateReadingSpeeds(String customerID, String bookID, int pageNumber) {
        int timeBucket = fetchTimeBucket();
        addCustomerToBook(customerID, bookID);
        updateCustomerPages(customerID, pageNumber, timeBucket);
    }
    private static void updateCustomerPages(String customerID, int pageNumber, int timeBucket) {
        int currentSpeed = pageNumber;
        List<Integer> pageNumbers;
        if(!customerToPageNumbers.containsKey(customerID)) {
            pageNumbers = new ArrayList<Integer>();
        } else {
            pageNumbers = customerToPageNumbers.get(customerID);
            currentSpeed = pageNumber - pageNumbers.get(pageNumbers.size() - 1) ;
        }
        pageNumbers.add(pageNumber);
        customerToPageNumbers.put(customerID, pageNumbers);
        updateCustomerSpeed(customerID, timeBucket, currentSpeed);
    }

    private static void updateCustomerSpeed(String customerID, int timeBucket, int currentSpeed) {
        final int[] speeds;
        if(!customerToSpeeds.containsKey(customerID)) {
            speeds = new int[HISTORY_TO_TRACK];
            Arrays.fill(speeds, 0);
        } else {
            speeds = customerToSpeeds.get(customerID);
        }
        speeds[timeBucket] = currentSpeed;
        customerToSpeeds.put(customerID, speeds);
    }
    private static void addCustomerToBook(String customerID, String bookID) {
        synchronized(bookToCustomers) {
            Set<String> customers = bookToCustomers.containsKey(bookID) ? bookToCustomers.get(bookID) : new HashSet<String>();
            customers.add(customerID);
            bookToCustomers.put(bookID, customers);
        }
    }
    private static int fetchTimeBucket() {
        //Debug
        return time % 10;
//        return (int) ((System.currentTimeMillis() / 60000) % HISTORY_TO_TRACK);
    }

    private static int calculateReadingSpeed(String customerID) {
        if(!customerToSpeeds.containsKey(customerID))
            return 0;
        int max = Integer.MIN_VALUE, timeBucket = fetchTimeBucket();
        int[] speeds = customerToSpeeds.get(customerID);
        for(int j = 0; j < 10; j++) {
            int current = timeBucket - j % 10;
            if(current < 0) {
                current = 10 + current;
            }
            max = Math.max(max, speeds[current]);
        }
        return max;
    }

}

Two functions are required:
1) update
2) getLeaderboard.

for update the approach is straightforward. for each user maintain a map of userid and ((n(number of update events), avg speed of n events)). For new update call, using n and old avg, compute new avg read speed as: avg = ((n*avg)+readingSpeed)/n+1;n=n+1;

This new reading speed for a user needs to be updated in data structure for computing leaderboard.

Approach1:
If we are not maintaining any separate data structure for leaderboard. in that case, update event will take o(1) and computeleaderboard will take o(n^2) time.

Approach2:
if we are maintaining a treemap instead of hashmap for each user. in that case update event will take o(logn) and computeleaderboard will take o(n) time.

Apporach3:
As the reading speed values are very small in range. suppose we are maintaining speed till say first decimal place and max speed possible is say 20 pages per min. so the total possible buckets can be 200. even if we consider inhuman reading speed of say 100 pages per min it will take 1000 buckets.
We will have user data in hashmap of userid and (n,avgSpeed). For leaderboard we will have separate datastructure, i.e. array(buckets) where index corresponds to speed(eg 10.5 pages per min will be 105 index) and value at that index will be set of userids. We can just move userid from one bucket to another in case of update event. That will be o(1) and computeleaderboard will be o(n) as we need to just traverse the array. Banged!!