CareerCup

@vran.freelancer
Let me first get it clarified with what your solution talks about. HashCID takes CustomerId as input and gives a hashtable in return. This hashtable is about the PageId being referenced on a particular day.
eg. C1 accesses P1 on D1
C1 accesses P1 on D1
C1 accesses P2 on D1
C2 accesses P1 on D1
C3 accesses P2 on D1

HashCID will look like:
<C1, [<P1,D1>,<P2,D1>]>
<C2, <P1,D1>>
<C3, <P2,D1>>

HashPID will look like
<D1,5>

From the problem, we are expected to find the number of Distinct customers, each of which has accessed atleast 'p' distinct pages in T days.

With your solution, the above requirement is not getting fulfilled. I think the second hashtable should be HashPID (PID, <Day, Count>), otherwise counting access to a page w.r.t to Customer will not be possible.

With log files, you won't be able to do straight up hashing on ram. You can do it the Hadoop way - with an external sort, and merge.

With 2 Hashtables. 1) HashCID<int CID, HashTable<PID,Day>> and 2) HashPID<Day,Count>

I understand that the question is about data structures......But I tried to approach it from a DB perspective

Table:

create table Pages(Date int, CustID int, PageID int);

I did not consider the multiple visits to the same page as it does not add any value to the question asked.

Query to get the output

SELECT CustID , Count (DISTINCT PageID) AS NoOfPages FROM Pages WHERE Date BETWEEN D1 AND D2 Group BY CUSTID HAVING NoOfPages > p;

a) All the distinct customers are Grouped
b) Customers and No of Distinct Pages are calculated between selected dates (T Days)
c) Having clause trims the recordset to remove the customers who have visited less than p Pages

Create a temp table with result recordset. And count the number of customers. Output it.

But I am struggling to convert the sql structure into a MT data structure. Is there a data structure which can extend to n-Column instead of Key Pair?

We can create a Map<CID, List<PID>> by taking the logs of T days. Then we can traverse the map and whenever for a CID the size of List<PID> greater than p, output that CID.

(Approach assuming we can get the logs into memory completely)
Suppose we have to find the no. of distinct customers visiting pages today. This can be decomposed into HashMap<CustomerID, PageID>

Now if we hash all these maps obtained above based on Dates we get required information as follows: HashMap<Date, HashMap<CustomerID, PageID>> and extract the required info.