811. Subdomain Visit Count

GitBook

/* You are in charge of a display advertising program. Your ads are displayed on websites all over the internet. You have some CSV input data that counts how many times that users have clicked on an ad on each individual domain. Every line consists of a click count and a domain name, like this:

counts = [ "900,google.com", "60,mail.yahoo.com", "10,mobile.sports.yahoo.com", "40,sports.yahoo.com", "300,yahoo.com", "10,stackoverflow.com", "20,overflow.com", "5,com.com", "2,en.wikipedia.org", "1,m.wikipedia.org", "1,mobile.sports", "1,google.co.uk"]

Write a function that takes this input as a parameter and returns a data structure containing the number of clicks that were recorded on each domain AND each subdomain under it. For example, a click on "mail.yahoo.com" counts toward the totals for "mail.yahoo.com", "yahoo.com", and "com". (Subdomains are added to the left of their parent domain. So "mail" and "mail.yahoo" are not valid domains. Note that "mobile.sports" appears as a separate domain near the bottom of the input.)

Sample output (in any order/format):

calculateClicksByDomain(counts) => com: 1345 google.com: 900 stackoverflow.com: 10 overflow.com: 20 yahoo.com: 410 mail.yahoo.com: 60 mobile.sports.yahoo.com: 10 sports.yahoo.com: 50 com.com: 5 org: 3 wikipedia.org: 3 en.wikipedia.org: 2 m.wikipedia.org: 1 mobile.sports: 1 sports: 1 uk: 1 co.uk: 1 google.co.uk: 1

n: number of domains in the input (individual domains and subdomains have a constant upper length) */

import java.io.*;
import java.util.*;

public class Solution {
  public static void main(String[] argv) {
    String[] counts = {
      "900,google.com",
      "60,mail.yahoo.com",
      "10,mobile.sports.yahoo.com",
      "40,sports.yahoo.com",
      "300,yahoo.com",
      "10,stackoverflow.com",
      "20,overflow.com",
      "5,com.com",
      "2,en.wikipedia.org",
      "1,m.wikipedia.org",
      "1,mobile.sports",
      "1,google.co.uk"
    };

    System.out.println(calculateClicksByDomain(counts));
  }

// O(n * m2) n is size of counts, m is how many part I can split in one domain String
// --> TC: O(n)
// --> SC: O(n)
  public static Map<String, Integer> calculateClicksByDomain(String[] counts)
  {
      Map<String, Integer> resultMap = new HashMap<>();
      for(int i = 0; i< counts.length; i++)
      {
          String[] record = counts[i].split("\\,");
          int singleCount = Integer.parseInt(record[0]);
          String fullDomain = record[1];
          String[] domainBreakDown = record[1].split("\\.");

          for(String element : getAllSubDomain(domainBreakDown))
          {
             if(resultMap.containsKey(element))
             {
                resultMap.put(element ,resultMap.get(element) + singleCount);
             }else
             {
               resultMap.put(element , singleCount);
             }
          } 
      }
      return resultMap;
   }

   //  0(m2)
    public static List<String> getAllSubDomain(String[] domainBreakDown)
    {
          List<String> res = new ArrayList<>();
          int size = domainBreakDown.length;
          for(int i = 0; i< size; i++)
          {
            res.add(getDomain(domainBreakDown, i));
          }
          return res;
    }

// O(m) m is size of domainBreakDown
    public static String getDomain(String[] domainBreakDown, int startIndex)
    {
        //form from startIndex -- end
        StringBuilder sb = new StringBuilder();
        for(int i = startIndex; i< domainBreakDown.length; i++)
        {
            if(i == domainBreakDown.length -1)
            {
              sb.append(domainBreakDown[i]);
            }else{
              sb.append(domainBreakDown[i]).append(".");
            }
        }
        return sb.toString();
    }
}