Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 28, 2018 19:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/2d565cca12c445121435819c67997cc4 to your computer and use it in GitHub Desktop.
Save jianminchen/2d565cca12c445121435819c67997cc4 to your computer and use it in GitHub Desktop.
Array quadruplet - being interviewer
import java.io.*;
import java.util.*;
class Solution {
static int[] findArrayQuadruplet(int[] arr, int s) {
// your code goes here
// 1. Scan through arr
// 2. scan through next 3 numbers
// 3. if sum == s, we now all the four numbers, we return then
for (int i=0; i<arr.length;i++) {
// What is the condition I stop?? - to decide
for (int j=i+1;; j++) { // first< second< third < fourth, 1, 2, 3,4
// we have overflow over here.
// e.g 2,7,4,0,9
// 0 1 2 3 4; i+1 % 3
int
int sum = arr[i] + arr[i+1%arr.length] + arr[i+2] + arr[i+3];
}
}
// Leetcode
// Two sum algorithm - two pointer technique
// 1, 2, 3 4 5 6 7 8 9, 10, given two sum = 12
// | |
// 1 + 10 = 11 < 12 -> move smalle value forward
// | | -> 2 + 10 = 12
// time complexity ->
Array.Sort(arr);
// 1, 2, 3, 4, 5 -> all possible - 5 out of 4, 5 choices
int length = arr.length;
for(int first = 0; first < length - 3; first++)
{
for(int second = first + 1; second < length - 2; second++)
{
for(int third = second + 1; third < length - 1; third++)
{
for(int fourth = third + 1; fourth < length; fourth++)
{
int sum = arr[first] + arr[second] + arr[third] + arr[fourth];
if(sum == s)
{
return new int[]{}
}
}
}
}
}
int []res = {0,4,7,9};
return res;
}
public static void main(String[] args) {
myTest();
}
static void myTest () {
int []arr = {2, 7, 4, 0, 9, 5, 1, 3};
int s = 20;
int []expected = {0,4,7,9};
int []output = findArrayQuadruplet(arr, s);
for (int i =0; i<4; i++) {
if (output[i] != expected[i])
System.out.println ("fail");
}
System.out.println ("Success");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment