Here are the technical questions from the outsource recruiter:
1. Given
uinsigned int x;
what does x & (x-1) do?
I haven’t programmed in C hardly at all since college, so I had to look up the order of operations on the internet, which is what any decent programmer would do with questions like these anyway. Turns out, as I thought, that parentheses trumps everything, even bitwise AND (whose precedence is lower than I thought and bitwise operations aren’t performed left to right, which was a surprise to me, but I digress.)
Like most human beings, I’m not good at bitwise calculations, and if there’s a trick to this one that sophomores memorize, I don’t know it.
Here are a few sample calculations:
x = 1 → 000001 x-1 = 0 → 000000 & result = 0 → 000000
x = 2 → 000010 x-1 = 1 → 000001 & result = 0 → 000000
x = 3 → 000011 x-1 = 2 → 000010 & result = 2 → 000010
x = 4 → 000100 x-1 = 3 → 000011 & result = 0 → 000000
x = 5 → 000101 x-1 = 4 → 000100 & result = 4 → 000100
x = 16 → 001111 x-1 = 15 → 001110 & result = 15 → 001110
100101 100100 & 100100
110110 110101 & 110100
I don’t see any pattern from this limited set.
2. On your platform, what are sizeof(char), sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double)?
You don’t know what my platform is, so you can’t know if I’m right or wrong, but I ran this quick program on my x86_64 Windows and x86_32 Linux computers and got the same results:
C:\aaron\projects\c>cat sizeof.c
#include "stdio.h"
int main()
{
printf("sizeof(char) %d\n", sizeof(char));
printf("sizeof(short) %d\n", sizeof(short));
printf("sizeof(int) %d\n", sizeof(int));
printf("sizeof(long) %d\n", sizeof(long));
printf("sizeof(float) %d\n", sizeof(float));
printf("sizeof(double) %d\n", sizeof(double));
}
C:\aaron\projects\c>gcc sizeof.c -o sizeof
C:\aaron\projects\c>sizeof.exe
sizeof(char) 1
sizeof(short) 2
sizeof(int) 4
sizeof(long) 4
sizeof(float) 4
sizeof(double) 8
Results are in bytes.
3. Given a structure
struct X {
chat c;
int i;
};
What is sizeof(X)?
Well, a couple of points first:
- I don’t know how big a “chat” is – I’m assuming a typo and that it should be “char”
- You would need to measure sizeof(struct X) or create an instance of it to get sizeof()
[aaron@qa-site ~]$ cat sizeofstruct.c
#include "stdio.h"
struct X {
char c;
int i;
} X;
int main()
{
printf("sizeof(X) %d\n", sizeof(X));
printf("sizeof(struct X) %d\n", sizeof(struct X));
}
[aaron@qa-site ~]$ gcc sizeofstruct.c -o sizeofstruct
[aaron@qa-site ~]$ ./sizeofstruct
sizeof(X) 8
sizeof(struct X) 8
My guess would have been 5, for sizeof(int) + sizeof(char), but gcc (at least) pads the struct for efficiency.
4. Enumerate sort algorithms that you know, and specify their runtime in o notation.
The sort algorithms that I know of off the top of my head are the bubble sort and the quick sort. There are plenty more, and an infinite variety of special cases which depend for efficiency on the goal of memory or processing efficiency based on the expected data.
I don’t even know what “specify their runtime in o notation” means, but a bubble sort (of integers) looks something like this (in pseudocode):
list = e.g. { 2, 5, 1, 8 , -3}
sort(list):
while (increment(iteration) < length_of_list )
while (increment(count) < list[count + 1])
if (list[count] > list[count + 1])
swap (list[count], list[count +1])
Essentially, it loops through the whole list the number of times there are elements in the list. For each element, it compares it with the next (it could also be done by comparing with the previous) element and swapping the two if they are out of order. The reason it has to repeat is that it only shifts one place on each pass, and doesn’t compare with elements before it. It is straightforward, but very inefficient.
A quick sort starts by finding a “middle” and then splitting the list and comparing against both sides and shuffing each element that way. A more memory intensive modification that would be quicker is to copy elements into a new list, adding them above or below as they fit.
I suppose I could have looked up more sorting algorithms on the internet (or from a book), but that’s probably not the point of this exercise.
If you’re looking for an experienced C programmer, that’s not me. If you’re looking for someone who memorizes bitwise operations and sorting algorithms, I’m afraid I don’t think I’d be interested in working somewhere [where|that] that is an important criteria.
Fijiaaron 
for 1.
what you can see is that this operation will remove the first 1 it encounters in the binary representation from right.
explanation : any integer x >=1 can be written in binary as a number finishing by 1 followed by some zeros, say n zeros.
x=a10000… (the … representing with n zeros and a is another integer) [here the notation is the concatenation of number ]
As you can see :
10000… (with n zeros… eventually no zero at all) when you substract 1 is, as the reminder you have to keep when you do the operation in binary will be cancelled by the first 1 found:
01111… (with n ones)
So the “&” will cancel each terms into
00000.. (with n+1 zeros).
So with our x=a10000… (n zeros)
x&x-1=a00000… (n+1 zeros)
if we write in decimal :
x=2^n×(2a+1).
x&(x-1)=(2a)×2^n=2^(n+1)×a
if you compare with : 2^n(2a+1) you can see that you have removed 2^n (where n is still the position of the first 1).
So x&(x-1)=x-2^n.
As n is the position of the first 1, this way of writing the result is just a repetition of the first sentence : x&(x-1) will remove the first 1.
For 3:
sizeof(X) is a syntax error, because you want sizeof(struct X) instead.
But, sizeof(char) is defined to be 1 byte, iirc. Due to alignment considerations, sizeof(struct X) will probably be 2*sizeof(int), but, I think this is compiler dependent, though on most any common platform, it will be 2*sizeof(int), which, on most any common platform these days will be 8 bytes.
Assuming no packing pragmas are in effect.
And you don’t need to create an instance, because sizeof is not a function, but operates at compile time, and can take types as arguments.
Re-reading your post, you probably already got my first and last points.