Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 1: Quadruple Sum to Target

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

I don't agree with official solution its way to complicated and not practice for interview session

class Solution:

  '''
    first sort the array 

    Then for each array element at i, j 

    add elements at i and j

    now we need to find the remaining elements 

    define start pointer that goes --> and pointer end that goes <-- to find the remaining elements 

    since the array is sorted we know when move a start or end pointer

    add the elements at position start and end and see if this + the i, j additions = target

    -3, -1, 1, 1, 1, 1, 1, 2, 4
     i   j  s  -->        <-- e
  '''
  def searchQuadruplets(self, arr, target):
    quadruplets = []
    seen = set()
    
    arr.sort()
    
    for i in range(len(arr) - 3):
      for j in range(i + 1, len(arr)
A

Anonymous

· 2 years ago

import java.util.*;

class Solution {

  public List<List<Integer>> searchQuadruplets(int[] arr, int target) {
    List<List<Integer>> quadruplets = new ArrayList<>();
    Arrays.sort(arr);
    for(int i = 0; i < arr.length - 3; i++){
        while(i > 0 && arr[i-1] == arr[i]){
          continue;
        }
        findAndPushTriplet(arr, i, quadruplets, target);
    }
    return quadruplets;
  }

  public static void findAndPushTriplet(int[] arr, int firstIndex, List<List<Integer>> quadruplets, int requiredTarget){
    boolean first = true;
    int j = firstIndex + 1;
    while(j < arr.length - 2){
        
        while(!first && arr[j] == arr[j-1] && j < arr.length - 2 ){
          j++;
        } 

        int left = j+1;
        int right = arr.length - 1;
        first =
Show 1 reply
A

Anonymous

· 3 years ago

For the Input [4, 1, 2, -1, 1, -3]

Target : 1

Output : [[1,4,-1,-3],[1,2,1,-3]]

Expected: [[-3,-1,1,4],[-3,1,1,2]]

Aren't both Output and Expected the Same. The Question doesn't really specify anything about Ordering the Quartet . So Both the Arrays are Same

A

Anonymous

· 4 years ago

Python 3 solution appears to fail on LeetCode (4Sum)

Show 2 replies
A

Anonymous

· 4 years ago

Please, add more visual explanations to these problems. A few of them have it but usually the most difficult ones are lacking it. I don't want to just memorize the solution, I want to actually understand how you got to that solution. I see many people on the discussion boards resorting to youtube videos to complement the explanations.

A

Anonymous

· 4 years ago

Seems that DP would work better here - solution would be O(n * target)

Show 1 reply
A

Anonymous

· 5 years ago

For this line of code: int sum = arr[first] + arr[second] + arr[left] + arr[right];

What's the best way to handle overflow case?

For ex: [1000000000,1000000000,1000000000,1000000000] 0

Is typecasting to "long long" a good solution? long long diff = (long long)targetSum - arr[first] - arr[second] - arr[left] - arr[right];

The above typecasting helps but is there a better way to handle overflow case?

Show 2 replies

Reading Progress

0%

Vote for new content