## Google Interview Question for Front-end Software Engineers

• 1
of 1 vote

Comment hidden because of low score. Click to expand.
2
of 2 vote

Comment hidden because of low score. Click to expand.
0

@bjh Did he ask you to code this ?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@bjh, did you make in? This is such weird question

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please tell me that the link x,y coordinate are give or not.

Comment hidden because of low score. Click to expand.
0
of 0 vote

for finding the nearest link, any ways we have to look for distance b/w the (x,y) and other links . So, can it really be made faster than O(no. of links) ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Trie can give you O(N) time for querying, however there could be hundred and thousand of DOM elements, and you certainly don't want to store everything into the Trie tree. More importantly Trie is more related to string algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

You need to sort it in order to do the query operation, and that will take O(n log n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't know the answer but I would like to share JQuery for coordinate calculation
http: //docs.jquery.com/Tutorials: Mouse_Position

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey dude, was that an onsite interview and which google site it was?

Comment hidden because of low score. Click to expand.
0

yes, it was onsite and it was in Mountain View

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>

Comment hidden because of low score. Click to expand.
0

This sounds ok, but what if dom element is under one parwnt however distant apart using css on the actual screen?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

That's not correct if you only check for your sibling, parent and common ancestor. You could have a float DIV (position:absolute) with a hyper link in it which could be the nearest one, and unluckily not sharing any common ancestors but body element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Document.elementFromPoint(x,y)

Plug these coordinatis and keep going out till you find the nearest node which is a link.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We could figure out what the nearest target element is based on mouseX, mouseY and then use BFS from that element to find the nearest link.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript:

``````let links = Array.from(document.querySelectorAll('a'));
return [rect.x, rect.y];
});

let distances = [];

distances.push(parseInt(distance));
});

});``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.