Created
March 15, 2018 04:09
-
-
Save jianminchen/4155fab43ffc9f6ccbe20ee9d57fb6d1 to your computer and use it in GitHub Desktop.
4 sum algorithm - Give out code review for peer's code - the code has some issues, brute force solution has some issues.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
int do_findArrayQuadruplet(int *arr, int *out, size_t arrLength, int s, int i, int j, int k, int l) | |
{ | |
int sum, ret = 0; | |
if (arrLength < 4) | |
return 0; | |
if (!arr || !out) | |
return 0; | |
sum = arr[i]+arr[j]+arr[k]+arr[l]; | |
if (sum == s) { // Sort out | |
out[0] = arr[i]; | |
out[1] = arr[j]; | |
out[2] = arr[k]; | |
out[3] = arr[l]; | |
return 1; | |
} | |
if (i < arrLength) | |
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i+1, j, k, l); // i, j, k, l | |
if (!ret && j < arrLength) | |
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j+1, k, l); | |
if (!ret && k < arrLength) | |
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k+1, l); | |
if (!ret && l < arrLength) | |
ret = do_findArrayQuadruplet(arr, out, arrLength, s, i, j, k, l+1); | |
return ret; | |
} | |
void findArrayQuadruplet(int const *arr, int* out, size_t arrLength, int s) { | |
// your code goes here | |
/* | |
take first 4 no check if sum is s | |
idx_1, idx_2 , idx_3 idx_4 | |
*/ | |
if (arrLength < 4) | |
return; | |
if (!arr || !out) | |
return; | |
if (do_findArrayQuadruplet(arr, out, arrLength, s, 0, 1, 2, 3)) | |
sort(out, 4); | |
} | |
int main() { | |
return 0; | |
} | |
// sort the array ascending order | |
sort(arr); | |
// four for loops -> O(n^3) -> brute force first two numbers, first <= second | |
// last two numbers with given sum, 4sum - first two number's | |
// two sum -> two pointer technique , line 27 spent O(n^2), line 28, O(n), in total O(n^3) | |
// 1, 2, 3, 4, 5, 6, 7, 8, 9 | |
// find two numbers with given 11, | |
// 1, 9 = 10 < 11 | |
// 1 -> 2, 9 = 11 > 10 | |
for(int i = 0; i < len; i++) | |
for(int j = i + 1; j < len; j++) | |
for(int k = j + 1; k < len; k++) | |
for(int l = k + 1; l < len; l++) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment