"Code for Technical Interviews Part 2: Whiteboards." - Views: 352 · Hits: 352 - Type: Public

// SetIntersection.cpp 
// Jon Wiesman, somedisagree.com

#include "stdafx.h"
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <time.h>
#include <chrono>

using namespace std;

class BookmarkedArray
{
	const vector<int>			*m_array;
	vector<int>::const_iterator	m_itr;
public:
	BookmarkedArray(const vector<int> *ar) : m_array(ar)
	{
		m_itr = m_array->begin();
	}

	bool operator < (const BookmarkedArray &other) const 
	{
		return (*m_itr < *other.m_itr);
	}
	bool operator > (const BookmarkedArray &other) const 
	{
		return (*m_itr > *other.m_itr);
	}
	const BookmarkedArray &operator =(const BookmarkedArray &other)
	{
		m_array = other.m_array;
		m_itr = other.m_itr;
		return *this;
	}

	bool AtEnd() const 
	{
		return m_itr == m_array->end();
	}

	int	Value() const
	{
		return *m_itr;
	}
	void	Next() 
	{
		m_itr++;
	}
	
};

void UMIWithHeap(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
	priority_queue<BookmarkedArray, vector<BookmarkedArray>, std::greater<BookmarkedArray>> q;

	for(int i = 0; i < arrayCount; i++)
	{
		q.push(BookmarkedArray(arrays + i));
	}

	out.clear();
	int currentValue = 0;
	int currentCount = 0;
	while(!q.empty())
	{
		if(currentCount == 0)
		{
			BookmarkedArray ba = q.top();
			q.pop();

			currentValue = ba.Value();
			currentCount = 1;
			ba.Next();

			if(!ba.AtEnd())
				q.push(ba);
		}
		else
		{
			BookmarkedArray ba = q.top();
			q.pop();

			int value = ba.Value();
			ba.Next();
			if(!ba.AtEnd())
				q.push(ba);

			if(value == currentValue)
			{
				currentCount++;
			}
			else
			{
				if(currentCount == 1)
				{
					out.push_back(currentValue);
				}
				currentCount = 1;
				currentValue = value;
			}
		}
	}
	if(currentCount == 1)
	{
		out.push_back(currentValue);
	}
}

void UMIWithMap(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
    map<int, int> counts;

    out.clear();
	for(int a = 0; a < arrayCount; a++)
	{
		for(auto i = arrays[a].begin(); i != arrays[a].end(); i++)
		{
			auto mitr = counts.find(*i);
			if(mitr == counts.end())
				counts[*i] = 1;
			else
				mitr->second++;
		}
	}

	for(auto mitr = counts.begin(); mitr != counts.end(); mitr++)
	{
		if(mitr->second == 1)
			out.push_back(mitr->first);
	}
}

void UMINaive(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
    out.clear();
    for(int i = 0; i < arrayCount; i++)
    {
        const vector<int> &a = arrays[i];
        for(auto ai = a.begin(); ai != a.end(); ai++)
        {
            bool duplicate = false;
            for(int k = 0; k < arrayCount; k++)
            {
                if(k == i)
                    continue;
                const vector<int> &a2 = arrays[k];
                for(auto ki = a2.begin(); ki != a2.end(); ki++)
                {
                    if(*ai == *ki)
                    {
                        duplicate = true;
                    }
                }
            }
            if(!duplicate)
            {
                out.push_back(*ai);
            }
        }
    }
    std::sort(out.begin(), out.end());
}

void FillArrays(vector<int> *arrays, int arrayCount, int maxValue, int multiple)
{
	// fill arrays with values to maxValue (each multiple-th element will be in ONLY 1 array)
	int toAppend = 0;
	for(int i = 1; i < maxValue; i++)
	{
		if(i % multiple == 0)
		{
			// add i to one and only one array
			arrays[toAppend].push_back(i);
		}
		else
		{
			// add i to count/2 arrays
			int pushCount = 2 + rand() % (arrayCount/2);
			for(int a = 0; a < pushCount; a++)
			{
				arrays[toAppend].push_back(i);
				toAppend = (toAppend + 1) % arrayCount;
			}
		}
	}
}

enum UMIMethods
{
    UMI_Naive,
    UMI_Map,
    UMI_Heap,
    UMIMethodCount,
};

int _tmain(int argc, _TCHAR* argv[])
{
	const int arrayCount = 15;
	const int maxValue = 100000;
    const int multiple = 5;

    const char *c_methods[] = {
        "UMI naive",
        "UMI using map",
        "UMI using heap",
    };

	vector<int> arrays[arrayCount];
    FillArrays(arrays, arrayCount, maxValue, multiple);

    for(int method = 0; method < UMIMethodCount; method++)
	{
		srand(0);

		vector<int> multiUMI;

        auto begin = std::chrono::high_resolution_clock::now();
        switch(method)
        {
        case UMI_Naive:
            UMINaive(arrays, arrayCount, multiUMI);
            break;
        case UMI_Map:
            UMIWithMap(arrays, arrayCount, multiUMI);
            break;
        case UMI_Heap:
		    UMIWithHeap(arrays, arrayCount, multiUMI);
            break;
        }
		auto end = std::chrono::high_resolution_clock::now();

		printf("%s (%d arrays) = {", c_methods[method], arrayCount);
        int last = -1;
		for(auto itr = multiUMI.begin(); itr != multiUMI.end(); itr++)
		{
            if((*itr % multiple) != 0)
                printf("Error! %d in result.\n", *itr);
            if(*itr <= last)
                printf("Error! %d <= %d!\n", *itr, last);
            last = *itr;
		}
        printf("%d multiples of %d}\n", (int)multiUMI.size(), multiple);
        
        int totalElements = 0;
		printf("Array sizes = {");
		for(int i = 0; i < arrayCount; i++)
		{
			printf("%d, ", arrays[i].size());
            totalElements += arrays[i].size();
		}
        printf("} = %d total elements.\n\n", totalElements);
        printf("Elapsed ticks = %d\n\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count());
	}

	return 0;
}