Mentioned above! Design a Stack.

Question

Anonimo · Accepted Answer

I started with exploratory questions about requirements: Homogenous/ Heterogenous Hold data vs. hold only pointers and the caller will handle the actual data allocation; discussed the tradeoffs. I explained two possible ways of implementation using dynamic arrays vs. linked lists and discussed the tradeoff: For the dynamic array, it will have some memory overhead of empty cells which I said we can dynamically reallocate to adjust the size to alleviate the issue. For the linked list it has to call allocate/deallocate for each push/pop which is time-consuming and has an additional pointer to the next item (memory overhead). The interviewer kept interrupting the thought process by asking too many follow-up questions (for every sentence I told he asked one or two follow-up questions) and he laughed if the answer was wrong in his opinion. Example: What is the time complexity of push with the dynamic array? Answer: O(1) amortized, if we hit the capacity and need allocation it takes more time. He laughed and said how come reallocation can be O(1). He asked to quantify the time complexity of realloc() function which really depends on the system but I answered it can be constant time if there is a contiguous memory available on the heap or it can find another block and needs to copy which can take O(n). But still average TC of the stack is O(1) because *only* when we hit capacity we do reallocate (for the nth push) then we can double the capacity and so on. Anyways he said the linked list approach is better (15 mins left) but how can you remove pointer overhead?! I was really confused as a singly linked list without a pointer is not a linked list. Still don't know but looks like he was looking for a combination of an array and a linked list. Asked for a follow-up about the problem of holding pointers instead of a copy of data and what can you do to handle it safely (answered using smart pointers). Follow-up: How to handle the heterogeneous stack: Answer: Using void* if we only store the pointers, otherwise user provides the size of the element and we can handle it for copying.

Bhavin · Answer

High-Level Memory Layout
Each node will be a blob of memory like:

[ next pointer ][ user data of variable size ]
So:

Push allocates a block: sizeof(void*) + size_of_user_data

Pop frees that block

Top points to the top block’s user data

✅ Design Summary
Stack Node:
struct StackNode {
    struct StackNode* next;
    // Followed by variable-length user data
};
We never declare data[] inside the struct. Instead, we allocate extra memory after the struct.

✅ Full Code: Heterogeneous Generic Stack
#include 
#include 
#include 

typedef struct StackNode {
    struct StackNode* next;
    // Followed by variable-sized data
} StackNode;

typedef struct {
    StackNode* top;
    size_t size;
} Stack;

// Initialize the stack
void stack_init(Stack* s) {
    s->top = NULL;
    s->size = 0;
}

// Push an element of arbitrary size
void stack_push(Stack* s, const void* data, size_t data_size) {
    // Allocate enough for pointer + data
    StackNode* node = malloc(sizeof(StackNode) + data_size);
    if (!node) {
        fprintf(stderr, "Out of memory
");
        exit(1);
    }

    // Link to previous top
    node->next = s->top;
    s->top = node;
    s->size++;

    // Copy the data into the allocated space after the node header
    void* data_location = (void*)(node + 1);
    memcpy(data_location, data, data_size);
}

// Return pointer to the top element’s data
void* stack_top(const Stack* s) {
    if (!s->top) {
        fprintf(stderr, "stack_top on empty stack
");
        exit(1);
    }
    return (void*)(s->top + 1);
}

// Pop the top element
void stack_pop(Stack* s) {
    if (!s->top) {
        fprintf(stderr, "stack_pop on empty stack
");
        exit(1);
    }

    StackNode* node = s->top;
    s->top = node->next;
    free(node);
    s->size--;
}

// Check if empty
int stack_empty(const Stack* s) {
    return s->top == NULL;
}

// Clean up
void stack_destroy(Stack* s) {
    while (!stack_empty(s)) {
        stack_pop(s);
    }
}
✅ Example Usage
c
Copy
Edit
int main() {
    Stack s;
    stack_init(&s);

    int x = 42;
    double y = 3.1415;
    const char* msg = "hello";

    stack_push(&s, &x, sizeof(x));
    stack_push(&s, &y, sizeof(y));
    stack_push(&s, msg, strlen(msg) + 1);  // include null terminator

    printf("Top: %s
", (char*)stack_top(&s)); stack_pop(&s);
    printf("Top: %f
", *(double*)stack_top(&s)); stack_pop(&s);
    printf("Top: %d
", *(int*)stack_top(&s)); stack_pop(&s);

    stack_destroy(&s);
    return 0;
}
✅ Output
less
Copy
Edit
Top: hello
Top: 3.141500
Top: 42
🧠 Why This Is Efficient
Only 1 malloc per element

No wasted memory for fixed buffer sizes

Supports arbitrary types and sizes

Stack footprint is minimal: just a pointer to top node

Arista Networks

Domanda di colloquio di Arista Networks

Risposte di colloquio

Aziende seguite

Ricerche di lavoro