Home CheatSheet - C Problems
Post
Cancel

CheatSheet - C Problems

Posted Jun 15, 2021 Updated Oct 4, 2023
By Adeesh Kale
12 min read

Write a program to count number of high bits in given unsigned integer input

  1. We will first show the optimum solution

    1
2
3
4
5
6
7
8
9
10
11

     #include <stdio.h>

 int numones(unsigned int val)
 {
     int count = 0;
     while (val) {
         count++;
         val &= val - 1;
     }
     return count;
 }

  2. Brute Force

    1
2
3
4
5
6
7
8
9
10
11
12
13

     int numones(unsigned int val) // Brute Force
 {
     int count = 0;
     while (val != 0) {
         // Add to count if LSB bit is high
         // brackets required because binary addition
         // '+' has higher precedence than binary 
         // bitwise and '&'
         count = count + (val & 0x1); 
         val = val >> 1;
     }
     return count;
 }

  3. Brute force without using bitwise operators

    1
2
3
4
5
6
7
8
9

     int numones(unsigned int val) // Without bitwise
 {
     int count = 0;
     while (val != 0) {
         count = count + (val % 2); 
         val = val/2;
     }
     return count;
 }

When we run the test for this function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int main()
{
	// We will test our function here
	struct test{
		unsigned int input;
		int expected;
	};
	struct test tests[] = {
		{0x03, 2},
		{0xFF, 8},
		{0xFFFF, 16},
		{0x0, 0},
		{0xA0A0, 4}
	};
	int numtests = sizeof tests / sizeof(struct test);
	printf("| %9s | %9s | %9s | %9s | %9s |\r\n",
			"Test no.", "Input", "Output", "Expected", "Result");
	printf("|-----------|-----------|-----------|-----------|-----------|\r\n");
	for (int i = 0; i < numtests; i++) {
		int reply = numones(tests[i].input);
		printf("| %9d | %9d | %9d | %9d | %9s |\r\n",
			i, tests[i].input, reply, tests[i].expected,
			reply == tests[i].expected ? "PASS" : "FAIL");
	}
	return 0;
}

1
2
3
4
5
6
7
8

$ gcc numones.c -o numones && ./numones
|  Test no. |     Input |    Output |  Expected |    Result |
|-----------|-----------|-----------|-----------|-----------|
|         0 |         3 |         2 |         2 |      PASS |
|         1 |       255 |         8 |         8 |      PASS |
|         2 |     65535 |        16 |        16 |      PASS |
|         3 |         0 |         0 |         0 |      PASS |
|         4 |     41120 |         4 |         4 |      PASS |

Write a program that shows some common bit operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>

int main()
{
	unsigned int x = 0xAAAAAAAA;
	x |= ((1 << 4) | (1 << 0)); // Set the 4th bit and 0th bit
	x &= ~((1 << 3) | (1 << 7)); // Clear the 3rd bit amd 7th bit
	x ^= (1 << 2) | (1 << 4); // Toggle the 2nd and 4th bits
	x <<= 3; // Left shift x by 3 places, same as x * (2^3)
	x >>= 3; // Right shift x by 3 places, asme as x / (2^3)
	
	// Rotate x 5 times to the right
	for (int i = 0; i < 5; i++) {
		x = (x >> 1) | ((x & 1) << 31);
	}
	
	// Rotate x 5 times to the left
	for (int i = 0; i < 5; i++) {
		x = (x << 1) | ((x & 0x80000000) >> 31);
	}
}

Write the implementation of atoi, a function that converts a string to the corresponding number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int myatoi(char *numstr) // Brute force
{
	long res = 0; // long type, so that INT_MIN conversion passes
	int sign = 1;
	if (*numstr == '-') {
		sign = -1;
		numstr++;
	}
	while (*numstr != '\0') {
		res *= 10;
		res += *numstr - '0';
		numstr++;
	}
	return sign*res;
}

As long as the string is valid, this function will work. But it’s not checking for invalid strings. Simplest case of an invalid string is one in which there are space(s) before or after our number.

Write a program to convert a string of letters to uppercase / lowercase

  1. Convert to Uppercase

    1
2
3
4
5
6
7
8
9

     void touppercase(char *str)
 {
     while (*str != '\0') {
         if (*str >= 'a' && *str <= 'z') {
             *str -= 'a' - 'A';
         }
         str++;
     }
 }

  2. Convert to lowercase

    1
2
3
4
5
6
7
8
9

     void tolowercase(char *str)
 {
     while (*str != '\0') {
         if (*str >= 'A' && *str <= 'Z') {
             *str += 'a' - 'A';
         }
         str++;
     }
 }

Write function to get the n-th fibonacci number

  1. Recursive

    1
2
3
4
5
6

     unsigned int fib(int n)
 {
     if (n == 0 || n == 1)
         return 1;
     return fib(n-1) + fib(n-2);
 }

  2. Iterative

    1
2
3
4
5
6
7
8
9
10
11
12

     unsigned int fib(int n)
 {
     int fib_k = 1, fib_kminus1 = 1;
		
     for (int i = 2; i <= n; i++) {
         int temp = fib_k + fib_kminus1;
         fib_kminus1 = fib_k;
         fib_k = temp;
     }

     return fib_k;
 }

  3. Program that takes input n from command line

    1
2
3
4
5
6
7
8
9
10
11
12

     int main(int argc, char *argv[])
 {
     int n = 1;
     if (argc > 1) {
         n = atoi(argv[1]);
         if (n < 0)
             n = 1;
     }
		
     printf("%d-th fibonacci number is %d\n", n, fib(n));
     return 0;
 }

Write a program that prints out n-lines of pascal’s triangle (n is input from command line)

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

int main(int argc, char *argv[])
{
    int n = 1;
    if (argc > 1) {
        n = atoi(argv[1]);
        if (n < 1)
            n = 1;
    }
		
    int *arr = calloc((n+2), sizeof(int));
    int *arr1 = calloc((n+2), sizeof(int));
    arr[1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= i+1; j++) {
            arr1[j] = arr[j-1] + arr[j];
        }
        for (int j = 1; j <= i+1; j++) {
            arr[j] = arr1[j];
        }
        for (int k = 1; k <= i+1; k++)    
            printf(" %d", arr[k]);
        printf("\n");
    }
    return 0;
}

Write a program that prints whether the system is little endian or big endian

  • 0x01020304
    • Little Endian memory 0x04 0x03 0x02 0x01
    • Big Endian memory 0x01 0x02 0x03 0x03
    1
2
3
4
5
6
7
8
9
10
11

      #include <stdio.h>

  int main()
  {
      union {
          int val;
          unsigned char bytes[sizeof(int)];
      } num;
      num.val = 1;
      printf("This machine is %s endian\n", num.bytes[0] == 1 ? "LITTLE" : "BIG");
  }

Write function to swap endianness

1
2
3
4
5
6
7

unsigned int swapendian(unsigned int x)
{
	return (((x & 0x000000FF) << 24) \
			| ((x & 0x0000FF00) << 8) \
			| ((x & 0x00FF0000) >> 8) \
			| ((x & 0xFF000000) >> 24));
}

Write a function that reverses an input string in-place

  1. Without using string functions 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

     void swap(char *a, char *b)
 {
     char temp = *a;
     *a = *b;
     *b = temp;
 }

 void strrev(char *str)
 {
     char *begin = str;
     char *end = str;
     int len = 0;
     while (*end++ != '\0')
         len++;
     end = begin + len - 1;
     while (begin < end) {
         swap(begin, end);
         begin++;
         end--;
     }
 }
  2. Using string functions 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

     #include <stdio.h>
 #include <string.h>

 void swap(char *a, char *b)
 {
     char temp = *a;
     *a = *b;
     *b = temp;
 }

 void strrev(char *str)
 {
     char *end = str + strlen(str) - 1;
     while (str < end) {
         swap(str++, end--);
     }
 }

Write a program that checks whether a string containing single word is a palindrome

  • 1
2
3
4
5
6
7
8
9
10
11
12

    #include <stdbool.h>
#include <string.h>

bool ispalindrome(char *word)
{
    char *end = word + strlen(word) - 1;
    while (word < end) {
        if (*word++ != *end--)
            return false;
    }
    return true;
}

Write a macro function that concatenates strings where inputs are pointers to the first char

  • Note: the backslash at the end of each line in the macro definition is very critical and error-prone
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define catstr(x, y) 				\
	do{ 					\
		char *p = x; 			\
		while (*p++ != '\0'); 		\
		p--; 				\
		char *q = y; 			\
		while ((*p++ = *q++) != '\0'); 	\
	} while(0);

int main(void)
{
	char a[20] = "hello ";
	char b[20] = "world\n";
	catstr(a,b);
	printf("%s\n", a);
	return 0;
}

Change case of single letter using bit manipulation

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14

    // Logic: If we observe the ASCII table we can see that the 5th bit is 
// the only change between same letter capital vs lowercase. So, if we
// just toggle the 5th bit, we will go from either capital to lower or 
// lower to capital case of the same letter.
// For example, in binary:
// k value is 01101011
// K value is 01001011
//              ^   
// We can see that the 5th bit is the only difference. We can take any
// other letter and we'll observe the same pattern. 
char change_case(char c)
{
    return (c ^ (1 << 5));
}

Reverse the words in a given string

  1. In-place method: First reverse each word one by one then reverse the whole string.
    • Example, we take the string “Hello my name is Arjun”
    • In first step we reverse each word to get “olleH ym eman si nujrA”
    • In the second step we reverse the entire string to get “Arjun is name my Hello”
    • This implementation assumes perfect input, with exactly 1 space between words and no special characters
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

     void reverseblock(char *a, char *b)
 {
     while (b > a) {
         char temp = *b;
         *b = *a;
         *a = temp;
         b--;
         a++;
     }
 }

 void reversewords(char *str)
 {
     char *start = str;
     char *end = str;
     // Reverse each word
     while (*end != '\0') {
         // Find end of this word
         while (*end != '\0' && *end != ' ')
             end++;
         reverseblock(start, end-1);
         if (*end != '\0') {
             start = end+1; // Update start of next word
             end = start;
         }
     }
     // Reverse the entire string
     reverseblock(str, end-1);
 }

The Fizz Buzz Program

  • First approach (straightforward). Program should loop through numbers
    • If number is a multiple of 3, print Fizz
    • If number is a multiple of 5, print Buzz
    • If number is a multiple of 3 and 5 both, print FizzBuzz
    • Else print the number
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

      #include <stdio.h>

  void fizzbuzz(int n)
  {
      int flag;
      for (int i = 0; i <= n; i++) {
          flag = 0;
          if (i % 3 == 0) {
              printf("Fizz");
              flag = 1;
          }
          if (i % 5 == 0) {
              printf("Buzz");
              flag = 1;
          }
          if (flag == 0)
              printf("%d", i);
          printf("\n");
      }
  }
  • And another with a slighly modified version which doesn’t require flags 
    1
2
3
4
5
6
7
8
9
10
11
12
13
14

      #include <stdio.h>

  void fizzbuzz(int n)
  {
      for (int i = 1; i <= n; i++) {
          if (i % 3 && i % 5) printf("%d", i);
          else 
          {
              if (i % 3 == 0) printf("Fizz");
              if (i % 5 == 0) printf("Buzz");
          }
          printf("\n");
      }
  }

Program that counts how many instances of each ASCII character in a given file and prints the most common character

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <stdio.h>
#include <errno.h>

// There are 127 ASCII chars not counting 0
#define NUM_ASCII_CHAR 127

// Returns the index of the max element in array
int maxidx_in_array(int arr[], int numel)
{
	int maxidx = 0;
	for (int i = 1; i < numel; i++) {
		if (arr[maxidx] < arr[i]) {
			maxidx = i;
		}
	}
	return maxidx;
}

int main()
{
	int counts[NUM_ASCII_CHAR]; 
	for (int i = 0; i < NUM_ASCII_CHAR; i++) {
		counts[i] = 0;
	}
	FILE *f = fopen("testfile.txt", "r+");
	if (!f)
		return -ENOENT; // File doesn't exist
	char c;
	while ((c = fgetc(f)) != EOF) {
		counts[c]++;
	}
	int maxchar = maxidx_in_array(counts, NUM_ASCII_CHAR);
	printf("Most common character in test file is %c (val %d)\n", maxchar, maxchar);
	return 0;
}
Interview-prep, C
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents