Create account

DEV Community

Eastkap

Posted on Nov 18, 2019

Cracking up Facebook Paris Code challenge 2019 - Part 1

#javascript #css #algorithms #writeup

Hi everyone. I have been wanting to blog for a long time and now I have found the resolution within myself.

In this series, I'll solve and present some code challenges I was presented at Facebook's event.

Let me add some more context, I was invited by Facebook to take part in a small code hackathon challenge they were organising. We teamed up in groups of four and we had 90 minutes to resolve as many challenges. Each problem had 3 versions of itself, the easy one, the medium one and the difficult one.

Let's get started with CSS Ancestor Selector !

The exercice says :
"The ancestor combinator (<<) is placed between two CSS selectors. It matches only those elements matched by the first selector that are the ancestors of elements matched by the second."

/*
  Selects all <ancestor>s which have <descendant> as a descendant somewhere
  in its DOM hieraracy.
*/
ancestor << descendant {
  /* Styles */
}

Let's run through an example of how it is supposed to work.

Given the following HTML structure:

<html>
<body>
  <div id="a">
    <div id="b">
      <span></span>
      <div id="c">
        <span></span>
      </div>
      <span class="foo"></span>
      <span></span>
      <span></span>
      <span></span>
    </div>
  </div>
  <div id="d">
    <button></button>
  </div>
</body>
</html>

And invoking document.querySelectorAll('div << span') in the browser console will give you three <div> elements - those with ID "a", "b" and "c" - because they contain a <span> somewhere in their hierarchy. Note that <div id="d"> is not selected because it doesn't contain any <span>.

> document.querySelectorAll('div << span')
NodeList(3) [div#a, div#b, div#c]
> document.querySelectorAll('div << span').length
3

So basically, the idea is to put into place the '<<' selector, which will allow to select all the parents from an element.

I chose to do this one with NodeJS to be able to leverage the Cheerio library.

The first step is to select all the DOM children elements whose parents may be good candidates. This problem is actually also possible to solve in a left-right approach, but I found that reversing it and going bottom-up was more natural.

Cheerio actually is kind of a CLI version of jQuery, per the library's definition : "Fast, flexible & lean implementation of core jQuery designed specifically for the server.". This is how easily we can manage to do the first step with it, after loading the html:

        let candidates = [];
        $(selectors[0]).each((i,e)=>{
            candidates.push(e)
        })//all the selected divs are possible candidates

The idea will then be to filter out and scoop through all the candidate divs, checking if one of the elements in their upper-"kinship" is a candidate for the next selector. We simply have to iterate across the n-1 selectors before the first one.

After a quick read and writing some code, we can probably start seeing some of the difficulties;

1) We need the amount of unique elements, so basically we have to filter them out. One way would be to compare all between each other, but the === operator in NodeJS isn't reliable for comparing objects.
Another way to do this, albeit very heavy, is to dump into JSON strings each object and then compare the Strings produced, but this isn't appropriate here since DOM elements are circular. We still could make it work specifying the depth level, but I'm not convinced this method would then be fool-prof.
Finally, the way I came up with is by leveraging Set and array de-structuration to make this easy thanks to the high-level language that NodeJS is.

candidates = new Set(candidates);
candidates = [...candidates]; // we cast to list

2) The hard version of the problem asks us to implement classes on elements. We need to add some parsing on top of our previous code.

if(selector.includes('.')){
  selector = selector.split('.')[0]
  selectorClass = selector.split('.')[1]
}else{
  selectorClass = false;
}

and

//we check its class
if(selectorClass){
    if(temp.parent.attribs.class && temp.parent.attribs.class.includes(selectorClass))
    newcandidates.push(temp.parent)
}else{
    newcandidates.push(temp.parent)
}

Then we write a short main, allowing us to feed the information :

console.log('Test set',getRes({
    html:'test.in',
    selectorsArray:['div << span']
}))

console.log('Easy set',getRes({
    html:'easy.in',
    selectorsArray:['div << div']
}))

console.log('Medium set',getRes({
    html:'medium.in',
    selectorsArray:['div << span << div','span << div << p','span << div']
}))

console.log('Hard set',getRes({
    html:'hard.in',
    selectorsArray : ['span << span','div << span << div','div.zeta << span.alpha << div','span << div.beta << p']
}))

And that's about it!

You can follow me for the next part of the series on my Github, and also find the files and the full code ! Don't hesitate to submit your thoughts and propositions in the comments!