(FB phone interview) find all equivalent pairs


  • 1
    D

    Given an array A of integers, find the index of values that satisfy A + B =C + D, where A,B,C & D are integers values in the array. Find all combinations of quadruples.

    output all indexes of quadruple into format List<List<Integer>> indexofQuadruples

    similar to leetcode 4sum, or has better solution ?


  • 4
    S

    Recursive to get all the sum value then compare, shouldnt be hard. but might not be the best eg. [1,2,3,4]

    1 + 2 = 3,
    1 + 3 = 4,
    1 + 4 = 5,

    having a map
    3 => [{1, 2}]
    4 => [{1, 3}]
    5 => [{1, 4}]

    =======================

    2 + 3 = 5
    2 + 4 = 6

    3 => [{1, 2}]
    4 => [{1, 3}]
    5 => [{1, 4}, {2,3}]
    6 => [{2, 4}]

    =====================
    3 + 4 = 7

    3 => [{1, 2}]
    4 => [{1, 3}]
    5 => [{1, 4}, {2,3}]
    6 => [{2, 4}]
    7 => [{3, 4}]

    So the answer is
    [{1, 4}, {2, 3}]


  • 0
    V
    This post is deleted!

  • 4

    2 nested loops and add sum of each 2 elements in a map, then loop through the map and get lists that has size > 1

    Runs in O(n^2) where n is the size of the array
    worst space is O(n) where no any pairs sum equal to other pairs

    class Pair {
    	int x;
    	int y;
    
    	public Pair(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    }
    
    void printEquivalentPairsOf4(int[] arr) {
    		List<List<Integer>> r = equivalentPairsOf4(arr);
    		for (List<Integer> il : r) {
    			System.out.println(il.get(0) + ", " + il.get(1));
    		}
    	}
    
    	List<List<Integer>> equivalentPairsOf4(int[] arr) {
    		HashMap<Integer, List<Pair>> map = new HashMap<>();
    		for (int i = 0; i < arr.length - 1; i++) {
    			for (int j = i + 1; j < arr.length; j++) {
    				int sum = arr[i] + arr[j];
    				if (!map.containsKey(sum))
    					map.put(sum, new ArrayList<Pair>());
    				map.get(sum).add(new Pair(i, j));
    			}
    		}
    
    		List<List<Integer>> result = new ArrayList<>();
    		for (List<Pair> v : map.values()) {
    			if (v.size() > 1) {
    				for (Pair p : v) {
    					result.add(new ArrayList<Integer>());
    					result.get(result.size() - 1).add(p.x);
    					result.get(result.size() - 1).add(p.y);
    				}
    			}
    		}
    		return result;
    	}
    

  • 0
    K

    @k' worst space is O(n^2)


  • 0

    @kyparus said in (FB phone interview) find all equivalent pairs:

    @k' worst space is O(n^2)

    I think worst case is O(n^4). There are O(n^4) quadruplets of indexes, worst case they all equal to each other.


  • 0
    D

    @k' if there are more than two pairs in the map for a particular sum , result will have more than 4 entries instead of having more quadruples. How do you solve this ?


Log in to reply
 

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