Google Interview Question Front-end Software Engineers
I coded only my initial attempt which looped through all links returned by getElementsByTagName and computed the squared distance, keeping track of the min dist link. After that, everything else was a discussion only.
I am considering about using "the longest-prefix match", since we can not do any optimization without processing the links & their coordinates.
we can use "trie tree" to find the nearest link in no more than NumOfDigits(x)+ NumOfDigits(y) steps
We can do a round of pre-processing on all links. Compute the coordinates of each link.
Then the question becomes: given a list of dots, find the nearest dot next to (x, y).
This becomes a "Nearest neighbor search" problem. Using a space partition method can solve the problem in O(logn).
I came across this post while looking for potential questions to ask a candidate during an interview.
This question aims to test more than just that you know how to compute the euclidean distance between two points.
They basically want to know if you are familiar with the DOM model. If you are, you should recognize immediately that the closest link (or any element in general) to a given X,Y coordinate have to be one that would be: A) a sibling to the element on X,Y; or, B) an element with a common ancestor to the element on X,Y, so you should only need to compute distance for those. The only case in which this would lead to computing all distances would be in which the common ancestor turns out to be the 'body' element.
To make a good answer, you should recognize a few border cases, one is where some of the links may be using position:absolute in which case they would be placed arbitrarly on the page.
The second case is in which the X,Y coordinate given is on the border of the window therefore not corresponding to any element but <body>
This sounds ok, but what if dom element is under one parwnt however distant apart using css on the actual screen?
Absolute positioned elements, elements with negative margins, floated elements will all negate your theory, not only for the link element but for the containing elements. Additionally, the element you're hovering over could be under all of those conditions. Now that I think about it, even if there is no styling, I can think of at least one case where your conclusion that the closest has to be a sibling or with a common ancestor: If you have a link that displays at the very bottom of an element, then another element displays right below it, where the mouse is hovering.
I hope you haven't been using that logic in interviews.
Since it says "closest" and "efficient retrieval", the first hint is trie. Now how to generate a suitable key from a coord ? Divide the screen into four quadrants: find in which quadrant does x,y fall into: record that number in the string. Then recursively call this function with this new bounds and keep appending to the string. Eventually you will zoom into the particular x,y.
{{
hash(top, left, bottom, right, x, y)
{
// some break condition for recursion
var midy = (top + bottom)/2;
var midx = (left + right)/2;
var key = // determine which quadrant x,y lies
return key + hash(bounding quadrant coords, x, y)
}
}}
So on mouse move, you'd compute the hash for the current mouse position. Then in your links trie lookup, you will see how far you can go down the tree. Obviously there is going to be mismatch at some level. At this point, the child elements of this node are the closest links.
In other words: divide the screen into gradually zooming-in tiles for each link. find the largest tile which holds both the mouse and the link.
The click event has an event.target element and event.clientX and event.clientY value set.
Using event.target.querySelectorAll("a") will get you all the link anchors and you can move up from there if none is found.
For each element will be able to call element.getClientRects() to get the bounding rectangle with top,left equivalent to clientX/clientY.
Javascript:
let links = Array.from(document.querySelectorAll('a'));
let linkCoords = links.map(link => {
let rect = link.getBoundingClientRect();
return [rect.x, rect.y];
});
document.addEventListener("click", ev => {
let distances = [];
linkCoords.map(linkCoord => {
let distance = Math.hypot(linkCoord[0]-parseInt(ev.clientX), linkCoord[1]-parseInt(ev.clientY));
distances.push(parseInt(distance));
});
let closestLinkIndex = distances.indexOf(Math.min(...distances));
console.log(links[closestLinkIndex]);
});
link coordinates were not given. My code had to illustrate how to get the list of all links and positions, although he allowed me to assume access to jQuery. We also discussed how the distance comparison had to be made to the edges of the bounding box of the link and would need to handle cases where a link was contained in another (z-index comes into play). He also seemed pleased when I suggested using a quad-tree structure to speed up the checking.
- bjh August 16, 2010