Interview Question

Systems Software Engineer Interview

-Santa Clara, CA

NVIDIA

Given a page size and a number, align the number with the nearest page. (Note: This was a phone interview question. The interviewer and I used an online document to share ideas about this problem.

Tags:technical, c, systems
AnswerAdd Tags

Interview Answers

7 Answers

6

I think that at the faster solution you mean int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & ~(pageSize-1); } Note: There is a difference between !(pageSize-1) and ~(pageSize-1) ~(0x11) is 0xee !(0x11) is 0

The Dude on

3

I just wanted to point out that the "faster solution" only works if the pageSize is assumed to be a power of 2. For example, suppose pageSize = 10 (or 01010 in binary), and valueToAlign = 24 (or 11000 in binary), then the fast method would give 16, but it should be 20. Anyways, thanks for posting the question and solution.

observer on

0

@observer I see how the mask works out for the alignment, why it is works mathematically? Thanks

Cong on

0

@The Dude Good catch! I didn't think about that. (Fortunately, I didn't have to execute the code in the interview--I just typed it in a program similar to Google Docs.) Thanks!

original poster on

0

//naive solution: int getAlignedValue(int pageSize, int valueToAlign) { int index = valueToAlign/pageSize; return index * pageSize; } //faster solution: int getAlignedValue_Fast(int pageSize, int valueToAlign) { return valueToAlign & !(pageSize-1); }

Anonymous on

1

Have you tried using this website? www.rooftopslushie.com It says you can get career advice and interview prep info from Nvidia employees.

Anonymous on

0

The interviewer could be looking for some bit ops. But, the following one, works even page size isn't a power of 2. int mod = (value_to_align % page_size); value_to_align -= mod; if (mod > (page_size - mod)) { value_to_align += page_size; }

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.