8

When my friend had his interview yesterday, he was asked a question: Implement a function that allocates memory space without using the *alloc or new operator, and the function should return a pointer to the address. Neither he nor I can find the answer.

3
  • 1
    Sorry for this question that make you guys felt stupid. Nevertheless, I got the answer and am improved. I think it's better stupid than ignorant.
    – qwerty
    Apr 24, 2011 at 17:25
  • 3
    What is next? How to compile C++ code without using a compiler?
    – pic11
    Apr 24, 2011 at 17:28
  • 3
    It's a perfectly reasonable question if you're trying to make someone think, or if you're hiring someone to write a C standard library. Obviously I can't say what happened here, but it's possible the interviewer was more interested in the candidate's thought process than the final answer. In that case, saying, "This is silly, I don't know, and I refuse to try!" isn't going to do you any favors. Apr 24, 2011 at 17:45

4 Answers 4

16

I think the question is more of a puzzle than a question that shows experience with programming. My solution would be allocating a global byte-array, that would be used instead of the heap:

char heap[MAX_ALLOWED_MEM];

/*
   The following function uses 'heap' as raw memory!
   void* like_malloc(size_t bytes);
   ...
*/
3
  • Yea, I would look at it as more of a puzzler, like how outside of the box can you think. On these types of questions, its best to try to outline as many possible solutions and discuss their pros and cons, no matter how far out. Identifying more options is a measure of your expertise. The person interviewing will make some kind of determination: 1) no answer, ok basic skill level. 2) at least some ideas = some skill & problem solving, 3) discuss issues with solutions including performance, thread safety, portability = higher level of experience. Apr 24, 2011 at 17:01
  • 4
    This is nothing to do with thinking outside the box, it's a programming knowledge question, since this is more or less how the heap is created in bare-bones systems (you might use a pre-defined part of the memory map rather than let the compiler generate a global, once you know the memory map). The question is saying, "are you the kind of programmer with chance of writing a memory allocator, if called upon to do so?", and the real work is in writing the function (and accompanying free). If you're not, maybe they want a lower-level programmer for the job. Apr 24, 2011 at 19:17
  • By the way, this exact problem as well as solutions (by static allocating your own heap as shown here) are discussed in the K&R's The C Programming Language. Even for C++ jobs this book should be required reading.
    – Brandin
    Jan 25, 2014 at 11:31
3

Depending on your platform you have a few options:

  • Since this is C++, you can cheat and invoke one of the STL allocators. I doubt that's what the interviewer wanted, but who knows for sure?
  • You can always use fixed-size pools as a couple of the answers suggest.
  • sbrk is also an option, but its use is discouraged and it's no longer part of POSIX.
  • You can also use mmap (or VirtualAlloc or CreateFileMapping on Windows) as a source of memory, but if you want memory chunks smaller than whole pages you'll still need to write some code to manage the memory these functions return.

Your allocator should ensure memory is properly aligned for your platform: on some systems, unaligned memory access is an invalid operation and on others there's a performance hit vs. aligned access. In real, production code you'd also likely want to provide a free operation to avoid taking over all the system's memory and locking to make your heap thread-safe.

0
2

You can do it via a system call such as sbrk(), rather than using a C library function or a C++ language feature. There is absolutely no reason to do this, however, so this is a very crappy question.

1
  • What if you need memory backed by a file? How do you get that out of malloc or new? Apr 24, 2011 at 17:32
1

A super simple one that never frees.

class allocator{
        static char mem_pool[1048576];
        char* place;
    public:
        allocator(){
             place = mem_pool;
        }
        allocator(const allocator& a){
             place = a.place;
        }
        char* alloc(size_t size){
            char* ret = place;
            place += size;
            return  ret;
        }
}
1
  • 2
    Good idea, but it'd be easier to do it safely in a function with a couple static local variables. As is, your copy constructor invites people to return overlapping memory regions to subsequent callers of alloc. Apr 26, 2011 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.