08 December 2008

Array puzzle

I know this problem from Rustan Leino:

Assume that malloc(n) takes O(1) time and memset and calloc take O(n) time. Fill in the missing parts below:

struct array {
  //... data

// Creates an array that containes |size| copies of |default_value|.
struct array* array_init(int size, int default_value) {
  // ... code

// a[index] = new_value
void array_set(struct array* a, int index, int new_value) {
  // ... code

// return a[index].
int array_get(struct array* a, int index) {
  // ... code

All methods should return in constant time in the worst case, deterministically.

Send your solutions to radugrigore at gmail.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.