Google Interview Question for Front-end Software Engineers






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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@bjh Did he ask you to code this ?

- MaYanK August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bjh August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anon June 20, 2011 | Flag
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.

- Ravikant August 14, 2010 | Flag Reply
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) ?

- bebo August 15, 2010 | Flag Reply
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

- leehom liang August 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Teng August 28, 2012 | Flag
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).

- Ryan August 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Teng August 28, 2012 | Flag
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

- Anonymous August 17, 2010 | Flag Reply
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?

- Anonymous August 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, it was onsite and it was in Mountain View

- bjh August 19, 2010 | Flag
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>

- Reinaldo Aguiar August 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhay August 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- MK July 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Teng August 28, 2012 | Flag
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.

- Viv October 17, 2012 | Flag Reply
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.

- Anonymous April 21, 2015 | Flag Reply
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.

- Shiv May 31, 2016 | Flag Reply
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.

- A June 04, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More