CSSSelector.scala

/**
 * A valid CSSSelector must have at least one value, tag, id or a class.
 *
 * Usually, I would define a private constructor and a method in the companion
 * object to ensure only valid instances are created.
 *
 * Assumes that:
 * - classes is not null but an empty list instead.
 */
case class CSSSelector(
    tag: Option[String],
    id: Option[String],
    classes: List[String])

CSSSelectorParser.scala

/**
 * Allow to parse a CSSSelector from a String.
 *
 * Assumes that:
 * - The String is a valid CSS Selector
 */
class CSSSelectorParser {

  /**
   * A list of selectors is a string with several possible strings
   * separated by a space.
   *
   * It results to be quite convenient to split a selector that is separated by spaces into
   * several selectors, this make the task easier.
   *
   * The expected format is like:
   * - tag#id.class1.class2
   * - tag #id .class .class2
   *
   * Assumes that:
   * - The input is correct
   */
  def parseCSSSelectors(string: String): List[CSSSelector] = {
    string
        .split(" ")
        .toList
        .map(parseCSSSelector)
  }

  /**
   * Parses a single selector, this means that the input doesn't contain spaces.
   *
   * The expected format is like, each part is optional:
   * - tag#id.class1.class2
   *
   * Allowed characters are: A-Z, a-z, 0-9, hyphen (-)
   *
   * Assumes that the input is correct.
   */
  private def parseCSSSelector(string: String): CSSSelector = {
    /**
     * Note: ".class1.class2".split("\\.") = Array("", class1, class2)
     * this means that the first string contains the tag#id part which could be empty
     * the remaining elements are the classes.
     */
    val splitByClass = string.split("\\.")
    val tagOrIdMaybe = splitByClass.headOption.filter(_.nonEmpty)
    val classes = splitByClass.drop(1)

    tagOrIdMaybe
        .map { tagOrIdString =>
          // there is a tag, and id, or both.
          val (tagMaybe, idMaybe) = parseTagOrId(tagOrIdString)
          CSSSelector(tagMaybe, idMaybe, classes.toList)
        }
        .getOrElse {
          // no tag, nor id
          CSSSelector(None, None, classes.toList)
        }
  }

  /**
   * Parses the tag#id part of the selector only.
   */
  private def parseTagOrId(tagOrIdString: String): (Option[String], Option[String]) = {
    /**
     * Note: "#id".split("\\#") = Array("", id)
     * this means that the head is the tag (which could be empty)
     * and the tail is the id (which could be missing).
     */
    val splitById = tagOrIdString.split("\\#")
    val tagMaybe = splitById.headOption.filter(_.nonEmpty)
    val idMaybe = splitById.lift(1).filter(_.nonEmpty)
    (tagMaybe, idMaybe)
  }
}

DOMElement.scala

import scala.collection.JavaConverters.asScalaBufferConverter

/**
 * Scala DOMElement
 *
 * I would create this from a JavaDOMElement, ensuring that nulls are
 * wrapped in the None value to avoid the evil NullPointerException and
 * nested if-else logic.
 *
 * Usually, it would be useful to not use a case class to avoid having
 * malfored elements and rely on the companion object constructor, but
 * as I'm limited to the time, a case class gets practical.
 */
case class DOMElement(
    tag: String,
    id: Option[String],
    classes: List[String],
    children: List[DOMElement])

object DOMElement {
  /**
   * Map a JavaDOMElement to a Scala DOMElement.
   *
   * Ensures that:
   * - if id is null or empty, None is used.
   * - if classes is null, empty list is used.
   * - if children is null, empty list is used.
   *
   * Assumes that:
   * - tag is not null, nor empty
   */
  def fromJava(java: JavaDOMElement): DOMElement = {
    val children = Option(java.children)
        .map(_.asScala.toList)
        .map { list => list.map(fromJava) }
        .getOrElse(List.empty)

    val classes = Option(java.classes)
        .map(_.asScala.toList)
        .getOrElse(List.empty)

    DOMElement(
      java.tag,
      Option(java.id),
      classes,
      children)
  }
}

DOMProcessor.scala

class DOMProcessor {

  /**
   * Count the number of elements matching the given selector list.
   */
  def countMatchingElements(element: DOMElement, selectorList: List[CSSSelector]): Int = selectorList match {
    case selector :: Nil =>
      /**
       * There is only one selector to match, the possibilities are:
       * - the current element matches the whole selector.
       * - any of the descendants (direct or indirect) of the element could match the whole selector.
       */
      val currentCount = if (matches(element, selector)) {
        1
      } else {
        0
      }

      val childrenCount = element
          .children
          .map { child => countMatchingElements(child, selectorList) }
          .sum

      currentCount + childrenCount

    case selector :: remaining =>
      /**
       * We have a selector for an element, and a list of selectors for its descendants, the possibilities are:
       * - The current element matches the first selector, count descendants matching the remaining selectors.
       * - The current element doesn't match the first selector, ignore it and check descendants.
       */
      if (matches(element, selector)) {
        element.children.map { child => countMatchingElements(child, remaining) }.sum
      } else {
        element.children.map { child => countMatchingElements(child, selectorList) }.sum
      }

    /**
     * There are no more elements to match.
     */
    case _ => 0
  }

  /**
   * Checks if the given CSSSelector matches the given element.
   *
   * A selector matches the element if all these conditions are met:
   * - the DOMElement tag is the expected one from the selector (if the selector expects a tag).
   * - the DOMElement id is the expected one from the selector (if the selector expects an id).
   * - the DOMElement contains all the CSSSelector expected classes.
   */
  private def matches(element: DOMElement, selector: CSSSelector): Boolean = selector match {
    case CSSSelector(Some(expectedTag), _, _) =>
      element.tag == expectedTag &&
          matches(element, selector.copy(tag = None))

    case CSSSelector(_, Some(expectedId), _) =>
      element.id.contains(expectedId) &&
          matches(element, selector.copy(id = None))

    case CSSSelector(_, _, expectedClasses) =>
      expectedClasses.forall { expectedClass => element.classes.contains(expectedClass) }

    /**
     * As we match every selector attribute using recursion, this is good enough for our base case,
     * a valid CSSSelector should never be empty anyway.
     */
    case _ => true
  }
}

JavaDOMElement.scala

/**
 * Sadly, Gson doesn't seem to be compatible with Optional data types, hence, I need
 * to deal with null values.
 */
case class JavaDOMElement(
    tag: String,
    id: String,
    classes: java.util.List[String],
    children: java.util.List[JavaDOMElement])

JavaTestCase.scala

/**
 * Gson has poor support for Java, creating java-compatible classes is necessary.
 * If the judge would have supported scala json libraries, this would have not been necessary.
 */
case class JavaTestCase(
    hierarchy: JavaDOMElement,
    tests: java.util.List[String])

object JavaTestCase {
  val ExampleInput =
    """
      |{
      |  "hierarchy": {
      |    "tag": "html",
      |    "children": [
      |      {
      |        "tag": "body",
      |        "classes": [
      |          "mobile"
      |        ],
      |        "children": [
      |          {
      |            "tag": "div",
      |            "id": "content",
      |            "children": [
      |              {
      |                "tag": "p"
      |              },
      |              {
      |                "tag": "p"
      |              }
      |            ]
      |          }
      |        ]
      |      }
      |    ]
      |  },
      |  "tests": [
      |    "p",
      |    "div p",
      |    "#content p",
      |    "body #mobile",
      |    "body#content"
      |  ]
      |}
    """.stripMargin
}

Solution.scala

import java.io.InputStreamReader

import scala.collection.JavaConverters.asScalaBufferConverter

import com.google.gson.Gson

object Solution {

  def main(args: Array[String]): Unit = {
    // usually, we would use dependency injection for getting these objects
    val cssSelectorParser = new CSSSelectorParser
    val domProcessor = new DOMProcessor
    val gson = new Gson()

    // for reading a JSON from the standard input
    val inputReader = new InputStreamReader(java.lang.System.in)

    // the read the test input
    val test = gson.fromJson(inputReader, classOf[JavaTestCase])

    // get the scala DOMElement from the hierarchy, assumes there is one element.
    val rootElementMaybe = Option(test.hierarchy)
        .map(DOMElement.fromJava)

    val answers = Option(test.tests)
        .map(_.asScala.toList)
        .getOrElse(List.empty)
        .map { selectorString =>
          // parse a list of CSSSelector for simpler manipulation
          val selectors = cssSelectorParser.parseCSSSelectors(selectorString)

          rootElementMaybe
              .map { rootElement =>
                domProcessor.countMatchingElements(rootElement, selectors)
              }
              .getOrElse(0)
        }

    // trivial mapping, no gson needed
    val answer = answers.mkString("[", ",", "]")
    println(answer)
  }
}