NVIDIA Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
4
of 4 vote

I checked it it works !!

#include <stdio.h>
#include <stdlib.h>

/*************************************************
Name :- aligned_malloc
Arguments:- number of bytes & Alignment Boundry
Return :- NULL on error
valid pointer on success

Working :- It will allocate memory with starting address
multiple of alignment passed and returns pointer
to it on success.

Ex.
aligned_malloc(50,128);
This will allocate 50 bytes of memory with
starting address multiple of 128.

*************************************************/

void *aligned_malloc(size_t bytes, size_t alignment)
{
void *p1 ,*p2; // basic pointer needed for computation.

/* We need to use malloc provided by C. First we need to allocate memory
of size bytes + alignment + sizeof(size_t) . We need 'bytes' because
user requested it. We need to add 'alignment' because malloc can give us
any address and we need to find multiple of 'alignment', so at maximum multiple
of alignment will be 'alignment' bytes away from any location. We need
'sizeof(size_t)' for implementing 'aligned_free', since we are returning modified
memory pointer, not given by malloc ,to the user, we must free the memory
allocated by malloc not anything else. So I am storing address given by malloc just above
pointer returning to user. Thats why I need extra space to store that address.
Then I am checking for error returned by malloc, if it returns NULL then
aligned_malloc will fail and return NULL.
*/
if((p1 =(void *) malloc(bytes + alignment + sizeof(size_t)))==NULL)
return NULL;

/* Next step is to find aligned memory address multiples of alignment.
By using basic formule I am finding next address after p1 which is
multiple of alignment.I am storing new address in p2.
*/
size_t addr=(size_t)p1+alignment+sizeof(size_t);

p2=(void *)(addr - (addr%alignment));

/* Final step, I am storing the address returned by malloc 'p1' just "size_t"
bytes above p2, which will be useful while calling aligned_free.
*/
*((size_t *)p2-1)=(size_t)p1;

return p2;
}

/************************************************
Name :- aligned_free
Arguments :- pointer to be freed
Returns :- Nothing

*************************************************/

void aligned_free(void *p )
{
/* Find the address stored by aligned_malloc ,"size_t" bytes above the
current pointer then free it using normal free routine provided by C.
*/
free((void *)(*((size_t *) p-1)));
}

- NewGuy April 26, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why don't you use the function

memalign

? It's in stdlib.h and works perfectly with SSE instructions.

Happy coding!

- tunoheavy October 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the start address of the first allocated memory is given, when free is called with this address, it would free the entire bytes that was allocated at the beginning, based on the extra bits it uses to store that information. how do we handle this, change that info to store only the difference. correct me if my understanding is wrong. thanks !!

- Anonymous May 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the start address of the first allocated memory is given, when free is called with this address, it would free the entire bytes that was allocated at the beginning, based on the extra bits it uses to store that information. how do we handle this, change that info to store only the difference. correct me if my understanding is wrong. thanks !!

- Anonymous May 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Some background on this question, this was asked to me in phone interview at Nvidia. Interviewer gave me 48 hours to solve this and also warned me that do not copy from internet.

I spend almost a day thinking about how to do it . Then looked at implementation of malloc and clicked to me that I can store original address just
before return address. It worked. Need some tuning about how to fix corner cases.

After week of submission , got mail from NVIDIA for another phone interview.

Eventually, got selected after 6-7 onsite interview rounds.

- NewGuy May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous not sure what you meant. Please elaborate.

- NewGuy May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Brilliant!

- AnotherGuy September 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Awesome!!

- Aditya October 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I like it too. thanks for the neet hacky question.

- Anonymous July 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

buggy

- Anonymous September 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if the returned address itself is byte aligned.?

- Anonymous October 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

memalign won't work. The blocksize must be given as a power of two.
So if you want a blocksize of 3, for instance, you are out of luck.

- Mark February 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

memalign won't work. The blocksize must be given as a power of two.
So if you want a blocksize of 3, for instance, you are out of luck.

- Mark February 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is abug in these lines:

size_t addr=(size_t)p1+alignment+sizeof(size_t);
p2=(void *)(addr - (addr%alignment));

The fix is simple:

size_t addr=(size_t)p1+alignment+sizeof(void *);
p1 = (void *)addr + sizeof(void *)
p2=(void *)(p1  - (p1%alignment));

- vvs March 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

check the second line of your code?

- born2code March 31, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

which line?

- Anonymous August 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code they gave is correct.
You don't need 2 void *'s:
addr = (size_t)p1 + alignment + sizeof(size_t);
p2 = (void *)(addr - (addr%alignment));

addr is alignment + sizeof(size_t) bytes away from p1
Therefore addr - (addr%alignment) is at most alignment - 1 bytes from addr, so you will always be sufficiently able to go back sizeof(size_t) bytes.

i.e., *((size_t *)p2 - 1) = p1

- bb February 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can someone please write it in C++? I never liked C format. thanks

- jigili September 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the program given by NewGuy returns the pointer to a buffer whose starting address is alligned. But the size of the buffer that this pointer points to will be more than the number of bytes that are asked to be allocated.

- Anonymous October 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@the person who posted the code.... e1 Rajnikanth bows down 2 u!!

- Rajnikanth March 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cudos Rajini

- Chitty March 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Dude !

- NewGuy May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// Allocates and returns pointer aligned to requested boundary
//
void* AlignedAlloc( size_t cbSize, size_t cbAlign )
{
//
// Align Align-1 ~(Align-1)
// 8 00001000 00000111 11111000
// 16 00010000 00001111 11110000
// 32 00100000 00011111 11100000
// 64 01000000 00111111 11000000
// 128 10000000 01111111 10000000

void *p;
void *ap;
size_t cbExtra = cbAlign+sizeof(void*);

p = LocalAlloc( NONZEROLPTR, cbExtra + cbSize);

ap = (BYTE*) ((size_t)p & ~(cbAlign-1)) + cbAlign;

*((void**)ap-1) = p;

_ASSERT( 0 == (size_t)ap % cbAlign );

return ap;
}

void AlignedFree( void* p)
{
LocalFree( *((void**)p-1) );
}

- dissoupo April 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ #include <map> class AlignedMemoryManager { public: void* MallocAligned( uint size, uint alignment); bool FreeAligned( uintptr_t address); private: std::map<void*,void*> allocationMap_; } void* AlignedMemoryManager::MallocAligned( uint size, uint alignment){ { size_t actualSize = (alignment-1)+size; void * result = malloc(actualSize); void* alignedResult = NULL; if( result != NULL ) { alignedResult = result + result%alignments allocationMap_.insert(make_pair(alignedResult, result ) ); } return alignedResult; } bool AlignedMemoryManager::FreeAligned( uintptr_t address) { std::map<void*,void*>::iterator it = allocationMap_.find( address ); if( it != allocationMap_.end() ) { free( it->second); allocationMap_.erase( it) return true; } return false; } - eZak October 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <map>

class AlignedMemoryManager
{
    public:
        void*     MallocAligned( uint size, uint alignment);
        bool    FreeAligned( uintptr_t address);
    
private:

std::map<void*,void*> allocationMap_;
}

void*    AlignedMemoryManager::MallocAligned( uint size, uint alignment){
{
    size_t actualSize = (alignment-1)+size;
    void * result = malloc(actualSize);
    void* alignedResult = NULL;
    if( result != NULL )
    {
        alignedResult = result + result%alignments
        allocationMap_.insert(make_pair(alignedResult, result ) );
}
return alignedResult;
}

bool    AlignedMemoryManager::FreeAligned( uintptr_t address)
{
    std::map<void*,void*>::iterator it = allocationMap_.find( address );
    if( it != allocationMap_.end() )
{
    free( it->second);
    allocationMap_.erase( it)
    return true;
}
return false;
}

- eZak October 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What does mean by aligned malloc?Is it a user defined function?Is it differ from malloc, what is available in c?

- susanta October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

(SIZE_NEEDED + (WORD_LENGTH - 1)) & ~(WORD_LENGTH - 1)

- Anonymous January 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned padding = alignment - 1 + sizeof(void*);

p1 =(void *) malloc(bytes + padding);

addr=(size_t)p1 + padding;

- Anonymous June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned padding = alignment - 1 + sizeof(void*);

p1    = (void *) malloc( bytes + padding );

addr = (size_t) p1 + padding;

p2=(void *)(addr - (addr%alignment));

- Anonymous June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <malloc.h>

void* align_malloc(int bytes,int align_byte, void** fp)
{

void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;

u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;

u = (unsigned long)u_addr;

if(u % align_byte == 0)
return u_addr;

i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}

a_addr = (void*)i;

*fp = u_addr;

return a_addr;
}

#include <stdio.h>
#include <malloc.h>

void* align_malloc(int bytes,int align_byte, void** fp)
{

void* u_addr;
void* a_addr;
unsigned long i = 0;
unsigned long u = 0;

u_addr = (void*)malloc(bytes+align_byte);
if(u_addr == NULL)
return NULL;

u = (unsigned long)u_addr;

if(u % align_byte == 0)
return u_addr;

i = align_byte;
while(1)
{
if(u/i == 0)
break;
i = i + align_byte;
}

a_addr = (void*)i;

*fp = u_addr;

return a_addr;
}

- sguy March 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <malloc.h>

void* align_malloc(int bytes,int align_byte, void** fp)
{

        void* u_addr;
        void* a_addr;
        unsigned long i = 0;
        unsigned long u = 0;

        u_addr = (void*)malloc(bytes+align_byte);
        if(u_addr == NULL)
                return NULL;

        u = (unsigned long)u_addr;

        if(u % align_byte == 0)
                return u_addr;

        i = align_byte;
        while(1)
        {
                if(u/i == 0)
                        break;
                i = i + align_byte;
        }

        a_addr = (void*)i;

        *fp = u_addr;

        return a_addr;
}

#include <stdio.h>
#include <malloc.h>

void* align_malloc(int bytes,int align_byte, void** fp)
{

        void* u_addr;
        void* a_addr;
        unsigned long i = 0;
        unsigned long u = 0;

        u_addr = (void*)malloc(bytes+align_byte);
        if(u_addr == NULL)
                return NULL;

        u = (unsigned long)u_addr;

        if(u % align_byte == 0)
                return u_addr;

        i = align_byte;
        while(1)
        {
                if(u/i == 0)
                        break;
                i = i + align_byte;
        }

        a_addr = (void*)i;

        *fp = u_addr;

        return a_addr;
}

- sguy March 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sorry, first solution is stupid solution.

Use the OS memory allocation routines, rather than malloc.

- Yes, Buggy. September 11, 2009 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More