VUONG VAN THANG
Electronic Engineer - Ho Chi Minh City University of Technology

Tuesday, March 29, 2016

What are examples of questions that may be asked in an interview focused on embedded systems programming in C?

I would test you on something like this:

1) Test your bit-level logic skills: How do you swap the values of two variables without using a third variable?

2) Test your compiler skills: What is volatile/const/static and why are they important/useful?

3) Test your data structure skills: How do you test whether a linked list has a loop in it?

4) Test your algorithm skills: What are the differences between quick sort and bubble sort?

5) Test your memory skills: How would you allocate 1kB of memory and align it to a 16 byte boundary? How do you free it?

6) Test your critical thinking: Implement "int atox(const char* str, int radix)".

7) Test your resource management skills: Write a function that takes an unsigned int and returns it with the bits reversed. Write another function that does this and uses the smallest compute time possible (assume infinite memory).

8) Test your threading knowledge: How would you mitigate a race condition caused by multiple threads trying to read and/or write to a single buffer?

9) Test your technique: Approximately how many lines of code are in the average function, ideally?

10) Test your method: Is readability or efficiency more important? What are your thoughts on TDD?

Posted By Thang Vuong 22:37

How to swap two numbers without using a temporary variable?

Given two variables, x and y, swap two variables without using a third variable.

 Method 1 (Using Arithmetic Operators)
The idea is to get sum in one of the two given numbers. The numbers can then be swapped using the sum and subtraction from sum.
#include <stdio.h>
int main()
{
  int x = 10, y = 5;
  // Code to swap 'x' and 'y'
  x = x + y;  // x now becomes 15
  y = x - y;  // y becomes 10
  x = x - y;  // x becomes 5
  printf("After Swapping: x = %d, y = %d", x, y);
  return 0;
}

Output:
After Swapping: x = 5, y = 10

Multiplication and division can also be used for swapping.
#include <stdio.h>
int main()
{
  int x = 10, y = 5;
  // Code to swap 'x' and 'y'
  x = x * y;  // x now becomes 50
  y = x / y;  // y becomes 10
  x = x / y;  // x becomes 5
  printf("After Swapping: x = %d, y = %d", x, y);
  return 0;
}

Output:
After Swapping: x = 5, y = 10

Method 2 (Using Bitwise XOR)
The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which has all the bits as 1 wherever bits of x and y differ. For example XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111 and XOR of 7 (0111) and 5 (0101) is (0010).
#include <stdio.h>
int main()
{
  int x = 10, y = 5;
  // Code to swap 'x' (1010) and 'y' (0101)
  x = x ^ y;  // x now becomes 15 (1111)
  y = x ^ y;  // y becomes 10 (1010)
  x = x ^ y;  // x becomes 5 (0101)
  printf("After Swapping: x = %d, y = %d", x, y);
  return 0;
}
Output:
After Swapping: x = 5, y = 10

Problems with above methods
1) The multiplication and division based approach doesn’ work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.

2) Both Arithmetic solutions may cause arithmetic overflow. If x and y are too large, addition and multiplication may go out of integer range.


3) When we use pointers to variable and make a function swap, all of the above methods fail when both pointers point to the same variable. Let’s take a look what will happen in this case if both are pointing to the same variable.
// Bitwise XOR based method
x = x ^ x; // x becomes 0
x = x ^ x; // x remains 0
x = x ^ x; // x remains 0
// Arithmetic based method
x = x + x; // x becomes 2x
x = x – x; // x becomes 0
x = x – x; // x remains 0
Let us see the following program.
#include <stdio.h>
void swap(int *xp, int *yp)
{
    *xp = *xp ^ *yp;
    *yp = *xp ^ *yp;
    *xp = *xp ^ *yp;
}
int main()
{
  int x = 10;
  swap(&x, &x);
  printf("After swap(&x, &x): x = %d", x);
  return 0;
}
Output:
After swap(&x, &x): x = 0

Swapping a variable with itself may needed in many standard algorithms. For example see this implementation ofQuickSort where we may swap a variable with itself. The above problem can be avoided by putting a condition before the swapping.
#include <stdio.h>
void swap(int *xp, int *yp)
{
    if (xp == yp) // Check if the two addresses are same
      return;
    *xp = *xp + *yp;
    *yp = *xp - *yp;
    *xp = *xp - *yp;
}
int main()
{
  int x = 10;
  swap(&x, &x);
  printf("After swap(&x, &x): x = %d", x);
  return 0;
}

Output:
After swap(&x, &x): x = 10
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Posted By Thang Vuong 21:41
Subscribe to: Posts ( Atom )