Name:
eye
2012-04-04 16:06
Alright geniuses, if you think your programming ability is up to par, lets see you solve this:
Write an algorithm which in O(n) time finds 3 indices i, j, and k such that i < j < k and array[i] < array[j] < array[k].
Name:
Anonymous
2012-04-04 17:16
$ cat sequarr.c
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define ARRFMT "a[%d]:%d\t"
int main(int argc, char** argv){
int *arr, count;
int i, j, k;
count = argc - 1;
arr = calloc(count, sizeof(int));
for(i=0; i<count; ++i){
arr[i] = strtol(argv[i+1], NULL, 10);
}
for(i=0; i<count; ++i){
for(j=i; j<count; ++j){
for(k=j; k<count; ++k){
if( (arr[i] < arr[j]) &&
(arr[j] < arr[k]) ){
goto found;
}
}
}
}
printf("None found!\n");
return 0;
found:
printf(ARRFMT ARRFMT ARRFMT "\n",
i, arr[i], j, arr[j], k, arr[k]);
return 0;
}
$ ./sequarr 9 8 6 5 4 3 2 1
None found!
$ ./sequarr
None found!
$ ./sequarr 2342 123 9999 3 444 8
None found!
$ ./sequarr 2342 123 9999 3 444 8 77
a[3]:3 a[5]:8 a[6]:77
$