Google
4.2 of 5 2,092 reviews
www.google.com Mountain View, CA 5000+ Employees

Google Software Engineer Interview Question

I interviewed in New York, NY and was asked:
"Phone Interview: i) Find the number of inversions in an array (describe & code) ii) Find collinear points in a given set of 2D points (describe & code)"
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Interview Review - one of 2,776 Google Interview Reviews

Answers & Comments

1
of 1
vote
- Inversions is the number of changes required to make the array sorted.
- Use merge sort. While merging if value is picked from right array (that means the order was not correct initially) then increment the inversion counter
- Complexity O(nlgn)
- deveffort on Jan 9, 2011 Flag Response
0
of 0
votes
If the element was picked from the right array and there are still elements in the left array.
- Victor on Jan 14, 2011 Flag Response
0
of 0
votes
Collinear points:

Since two points are collinear, the task is to find all complete subsets of 3 or more collinear points, right?
- v on Jan 19, 2011 Flag Response
0
of 0
votes
deveffort

Slight change, you need to not just increment the inversions, you need to add the number of elements remaining in the first part of the array.
- sonofstars on Mar 29, 2012 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Google interview questions and advice. All interview reviews posted anonymously by Google employees and interview candidates.