View All num of num See all Photos Google This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company?Learn More. www.google.com Employer Engaged Overview Reviews Salaries Interviews Jobs Photos Benefits 3.1k Reviews 11k Salaries 3.8k Interviews 2.0k Jobs Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Engineer Interview New York, NY Google 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) Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 4 Answers ▲ 1 ▼ - 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 ▲ 0 ▼ If the element was picked from the right array and there are still elements in the left array. Victor on Jan 14, 2011 ▲ 0 ▼ 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 ▲ 0 ▼ deveffortSlight 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 Add Answers or Comments To comment on this, Sign In or Sign Up.