Google Interview Question
Software EngineersCountry: United States
This was not a trivial problem in implementation :-)
#include <stdio.h>
#include <stdlib.h>
void
print_array(int *arr, int size)
{
int i;
for(i=0; i<size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size) \
do \
{ \
register size_t __size = (size); \
register char *__a = (a), *__b = (b); \
do \
{ \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size > 0); \
} while (0)
/* Byte-wise set one item of size SIZE. */
#define SET(a, b, size) \
do \
{ \
register size_t __size = (size); \
register char *__a = (a), *__b = (b); \
do \
{ \
*__a++ = *__b++; \
} while (--__size > 0); \
} while (0)
void
insertion_sort(void *ptr, int nitems, int item_size, int (*functionp)(const void *, const void *))
{
int i=0;
char *val, backup_val;
int j;
char *arg1, *arg2, *arg3;
char *charPtr = (char *)ptr;
for(j=0; j<nitems-1; j++) { // 3 4 2 1....2 3 4 1.....1 2 3 4
// Move last element of one sub-array to its final position.
i = j+1;
val = (charPtr + (i*item_size));
SET(&backup_val, val, item_size);
i--;
for(i; i>=0; i--) {
arg1 = (charPtr + (i*item_size));
arg2 = &backup_val;
if (functionp((void *)arg1, (void *)arg2) == 1) {
arg3 = (charPtr + ((i+1)*item_size));
SET(arg3, arg1, item_size); // IMP: SET(dst, src)
} else {
break;
}
}
arg1 = charPtr + ((i+1)*item_size);
arg2 = &backup_val;
SET(arg1, arg2, item_size); // found final place for one element
}
}
int
compare_ints(const void *x, const void *y)
{
int *a, *b;
a = (int *)x;
b = (int *)y;
if (*a < *b) {
return (-1);
} else if (*a > *b) {
return (1);
} else {
return (0);
}
}
void
GoogleSort(void *ptr, int nitems, int item_size, int (*functionp)(const void *, const void *))
{
insertion_sort(ptr, nitems, item_size, functionp);
}
int
main(void)
{
int arr[] = {4, 3, 2, 1};
printf("Array contents before sorting:\n");
print_array(arr, sizeof(arr)/sizeof(int));
GoogleSort(arr, sizeof(arr)/sizeof(int), sizeof(int), compare_ints);
printf("Array contents after sorting:\n");
print_array(arr, sizeof(arr)/sizeof(int));
return (0);
}
OK, I debugged it. Was fun to do with GDB. The function insertion_sort() where setting backup_val on its stack ;) Here is a fixed version:
#include <stdio.h>
#include <stdlib.h>
void
print_array(int *arr, int size)
{
int i;
for(i=0; i<size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size) \
do \
{ \
register size_t __size = (size); \
register char *__a = (a), *__b = (b); \
do \
{ \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size > 0); \
} while (0)
/* Byte-wise set one item of size SIZE. */
#define SET(a, b, size) \
do \
{ \
register size_t __size = (size); \
register char *__a = (a), *__b = (b); \
do \
{ \
*(__a++) = *(__b++); \
} while (--__size > 0); \
} while (0)
void
insertion_sort(void *ptr, int nitems, int item_size, int (*functionp)(const void *, const void *))
{
int i=0;
char *val, *backup_val = (char*)malloc(item_size);
int j;
char *arg1, *arg2, *arg3;
char *charPtr = (char *)ptr;
for(j=0; j<nitems-1; j++) { // 3 4 2 1....2 3 4 1.....1 2 3 4
// Move last element of one sub-array to its final position.
i = j+1;
val = (charPtr + (i*item_size));
SET(backup_val, val, item_size);
i--;
for(; i>=0; i--) {
arg1 = (charPtr + (i*item_size));
arg2 = backup_val;
if (functionp((void *)arg1, (void *)arg2) == 1) {
arg3 = (charPtr + ((i+1)*item_size));
SET(arg3, arg1, item_size); // IMP: SET(dst, src)
} else {
break;
}
}
arg1 = charPtr + ((i+1)*item_size);
arg2 = backup_val;
SET(arg1, arg2, item_size); // found final place for one element
}
free(backup_val);
}
int
compare_ints(const void *x, const void *y)
{
int *a, *b;
a = (int *)x;
b = (int *)y;
if (*a < *b) {
return (-1);
} else if (*a > *b) {
return (1);
} else {
return (0);
}
}
void
GoogleSort(void *ptr, int nitems, int item_size, int (*functionp)(const void *, const void *))
{
insertion_sort(ptr, nitems, item_size, functionp);
}
int
main(void)
{
int arr[] = {4, 3, 2, 1};
printf("Array contents before sorting:\n");
print_array(arr, sizeof(arr)/sizeof(int));
GoogleSort(arr, sizeof(arr)/sizeof(int), sizeof(int), compare_ints);
printf("Array contents after sorting:\n");
print_array(arr, sizeof(arr)/sizeof(int));
return (0);
}
#include <stdio.h>
#include <iostream>
using namespace std;
void GoogleSort(void *ptr, int number, int SIZE, int (*functionp)(const void *, const void *))
{
for( int n = 0; n < number; n++ )
{
for(int m = n; m < number; m++)
{
if( functionp( (const char *)(ptr) + (n * SIZE), (const char *)(ptr) + (m * SIZE) ))
{
int temp = *((int *)ptr + m);
*((int*)ptr + m ) = *((int*)ptr + n );
*((int*)ptr + n ) = temp;
}
}
}
}
int compare(const void *a, const void *b)
{
if( *(int*)a > *(int*)b)
return 1;
else
return 0;
}
int main()
{
int arr [] = {2,5,7,9,4,2,6,4,5};
int size = sizeof(arr)/sizeof(int);
GoogleSort(arr, size, sizeof(int), compare);
for(int n = 0; n < size; n++)
cout << arr[n] << " ";
return 0;
}
what?
- Anonymous January 30, 2016