Uber - Find MidPoint of two points in an array of points in constant time.- Possible?


  • 0
    L

    You are given an array of points where each point has X and Y values. Find the midpoint of two points which exist in array in constant time.

    class Point {
    int x;
    int y;
    }

    public List<Point> getMidPoint (Point[] list) {
    // One way to find this to find midpoint of all points with each other and
    // check if midpoint exist in array, but, that would be O(n^2).

    }
    I am wondering if it's possible to write Constant time solution for this.

    This is the best I could think of:

    private static List<IntPoint> findMidPoint(IntPoint[] array) {

      List<IntPoint> result = new ArrayList<IntPoint>();
      Map<Integer, Integer> mapper=  new HashMap<Integer, Integer>();
    for (int i = 0; i < array.length; i++) 
    	mapper.put(array[i].X, array[i].Y);
    	
    for (int i = 0; i < array.length; i++) {
    	for(int j = i + 1; j < array.length; j++) {
    		int midPointX = (array[i].X + array[j].X) / 2;
    		int midPointY = (array[i].Y + array[j].Y) / 2;
    		if(mapper.containsKey(midPointX) && mapper.get(midPointX) == midPointY) {
    		result.add(array[i]);
    		result.add(array[j]);
    		return result;
    		}			
    	}
    }
    return result;
    }
    

    //O(n^2) where n is the number of IntPoint in array and k is some constant


  • 0

    @VishalRuhela do you suggest time complexity to be better than quadratic and points are with integer coordinates?Thank you


  • 0
    L

    @elmirap Yes, I meant how can we do better for runtime. And, points are integer coordinates.

    I cannot think of Constant time solution for this problem.


  • 1

    Did you get some hints for time complexity from the interviewer?


  • 0
    L

    @elmirap Not really, Interviewer keep focussing on the fact that Constant time solution exist, but, I wasn't sure how.

    In my understanding I do not think there is a solution which can be constant time to find midpoint in an array of Points.


  • 1

    Should we return all mid points or only one?I think that either you or the interviewer didnt understand your discussion.When you have variable number of points it is impossible to get all midpoints for constant time.Can you share the example he gave you please?


  • 0
    A

    It looks like you don't have to find an index of midpoint in the array, just midpoint. Can we just calculate it with formula:

    (x1 + x2)/2 , (y1 + y2)/2
    

    ?


  • 3
    A

    "You are given an array of points where each point has X and Y values. Find the midpoint of two points which exist in array in constant time."

    I don't understand the question.
    Are you given two points from the array and you need to compute the midpoint (very easy, constant time)?
    Or do you have to verify that the midpoint is in the array (precompute a hash table of the points so you can determine if a point is in the array in O(1) time)?
    Or do you want to find the point in the array that is closest to a computed midpoint of two points (not a midpoint problem, just a problem of searching array of points. Should be solved by sorting with O(nlog n) precomputation, and look up in O(log n))?


  • 0
    K
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.