Sample Industry Interview Questions
The following is some technical questions some UPL members were asked (along with solutions) while looking for internships and jobs. They are posted for educational use so that others may get a feel for what might be asked in a technical interview.
What is the quickest way to determine if a point exists inside of a polygon?
The fastest way is to draw a line (parallel to the X-axis tends to be easy) and see how many edges of the polygon this line intercepts. Even means the point is outside, odd means it is inside.
You have a balance scale and 8 marbles. One of the marbles is lighter or heaver than the others. What is the minimum number of weighings to guarantee you have found the bad marble?
3
Given N marbles, figure out the minimum number of weighings to find the bad marble.
Log base 3 of N. Rounded up
Why base 3 and not base 2?
Although you can only weigh two groups of marbles at a time, in doing so, you also learn information about any marbles that you do not weigh. Therefore, you may split the marbles into 3 groups and break the problem set down faster.
What is a Union, in the C programming language?
A union is like a struct, but instead of containing all of the members, it only contains 1 of the specified members, but the member that the union contains is determined at runtime.
What is a static function in C?
The static keyword in C has three different meanings depending on where it is used. A static parameter may not be changed. A static local variable retains its value between function calls (useful for counting how many times a function is called for example). A static function may only be called from within the file that it is declared in. This can be useful for declaring helper functions such that their names do not conflict with functions in other libraries.
I was asked this by a hardware company, so I knew my solution needed to be efficient, both in memory usage and time.
Implement the following two functions
void * aligned_malloc(size_t bytes, size_t alignment);
void aligned_free(void * p);
aligned_malloc and aligned_free functions may only use the C runtime functions malloc and free in their implementation and cannot use any static memory. aligned_malloc takes the size of the buffer you would like to allocate and also alignment which is a power of two that will force the starting address of the buffer you return to the user to start on an alignment boundary. For example, I may request 1000 bytes starting on a 128 byte boundary by calling aligned_malloc(1000, 128). aligned_free frees the buffer returned from aligned_malloc.
Solution: You can find solutions on the internet, but you need to keep in mind that many of them have bugs and flaws.
What makes this tricky is a few things
1. calling malloc is very expensive, and calling it multiple times really doesn't help you in this problem
2. the exact address that malloc returns must be provided to free.
So, malloc the number of bytes for the buffer + the boundary + 4 (for 32-bit systems). This gives you space to store the original address so that you may later pass it to free, and guarantees that somewhere in the chunk of memory is the desired byte boundary followed by the buffer. All you need to do now is store the original address in the 4 bytes before the buffer (if you put it after, the end user might over write it by accident, but they should never touch the memory before their buffer) calculate the desired start address to return. In the free function, you just need to read the original address, a simple constant time read.
