Amazon interview: malloc32 Align & Space reduction


  • 1
    K

    2 Questions that were asked at Amazon for a SW Engineer position:
    1 - You should write malloc32+free32 function:
    * malloc32 should always returns an address that is dividable by 32.
    * you can't use (modulus operator) %.
    * free32 should free the whole allocated space.
    * Time Complexity and space Complexity should be O(1)
    * assumption: Time and Space Complexity of malloc is O(1).
    2 - given a string you should reduce the number of adjacent spaces as follows:
    * if there is more than 1 consecutive spaces it should be reduced to one.
    * if there is 1 or 0 space it should stay the same.
    Time complexity: O(n)
    Space complexity: O(1)


  • 0
    E
    void *malloc32() {
        void *mem = malloc(32+31+sizeof(void*));
        void **ptr = (void**)((uintptr_t)(mem+31+sizeof(void*)) & ~(0x1F));
        ptr[-1] = mem;
        printf("malloc %x %x %x \n", mem, ptr, ptr[-1]);
        return ptr;
    }
    
    void free32(void *ptr) {
        printf("free %x\n", ((void **)ptr)[-1]);
        free(((void **)ptr)[-1]);
    }
    
    int main(void) {
        puts("Hello World!");
        void * x = malloc32();    
        printf("%x %x\n", x, ((void **)x)[-1]);
        free32(x);
        return 0;
    }
    

  • 0
    E
    #include<stdio.h>
    
    const char* x = " asldfjasdlfj asldfjl asdfasl   asdlfj";
    
    int main(void) {
        char last;
        char now;
        int hit = false;
        last = now = x[0];
        printf ("%c", last);
        if (last == ' ') hit = true;
        for (int i=1; i<strlen(x); i++) {
            now = x[i];
            if (now == ' ') {
                if (hit)
                    continue;
                else {
                    hit = true;
                    printf("%c", now);
                }
            }
            else {
                hit = false;
                printf("%c", now);
            }
        }
            
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.