Task for job interview for RT embbeded position

Task for job interview for RT embbeded position

This post is a collection of tasks and questions for RT embedded job interviews.

Kernel disassembler

  1. We want you to write a loadable kernel module that could be compiled against any kernel > v4.0 (kernel path will be passed to as an environment variable : KERNEL=/some/path/to/kernel/source)
  2. The kernel should be compiled to include a disassembler, we recommend using zydis as we find it to be the easiest to embed, although you could use what ever you like.
  3. The kernel should support the request for disassembling code from a specific address passed to it through module parameters.
  4. Bonus: We will test the kernel disassembler with known functions, write a method that computes the length of the function (using the disassembler) to disassemble the function from it’s beginning (supplied as a parameter) to it’s end (calculated by you).

See solution here

Letter Counter

Write a program that counts the frequency of each letter in the string and prints in alphabetical order. Example Input: cccccfaaaabbdd Desired Output: 4a2b5c2d1f You may assume the input string consists of lowercase letters

The solution is the histogram of the letter array.

int f(char *h,int N) {
    unsigned int b[26]={0};
    for (int i = 0;i < strlen(h); i++) {
    	  b[h[i]-'a']=b[h[i]-'a'] + 1;
    }
    for (int i = 0;i < 26; i++) {
    	if (b[i])
    		printf ("%u%c" , b[i],'a'+i)
    }
}

Programming Task

Write a program which is comprised of the following:

  1. Sender thread that does the following:
    1.1 Increment a global threadID whenever a sender thread is created (starting from 1)
    1.2 Draws a number n (between 1 to 100) and sends n messages with the thread id and msgid (1..n)
    1.3 Spawns one sender thread if threadID is divisible by 3 and total num of active sender threads is less than 20
    1.4 Spawns two sender threads if threadID is divisible by 7 and total num of active sender threads is less than 20
  2. Main thread will concurrently receive messages from all other sender threads and print the messages to the console formatted as follows: “ThreadID: ID MsgID: n”
  3. The program will initially spawn 6 sender threads and will quit when there are no more pending messages and no more active sender threads
  • The standard std::queue is used to pass messages from the sender threads to the main thread.
std::queue<msg_info> myqueue;

and msg_info defined as:

struct msg_info {
	int threadId;
	int n;
} info;
  • global mutex lock is used whenever the sender and the main thread are touching in common memory.
std::mutex  ql;
ql.lock()
... 
ql.unlock()
  • exit condition

The variable threadId is used as thread counter as required - it will reach 20. The variable threadId1 uses for existing conditions. It is incremented along with threadId and deceased at the end of threads. when it is ZERO, then the program is exit

  • here is code: copy and paste it and build it under Linux using simple command line
g++  task.cpp -o task -O0 -g -lpthread -std=c++14
#include <unistd.h>
#include <iostream>
#include <thread>
#include <queue>
#include <time.h>       /* time */
#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>
#include <vector>
#include <condition_variable>

struct msg_info {
	int threadId;
	int n;
} info;

int threadId ;
int threadId1 ;
std::mutex  ql;
std::vector<std::thread> threads;
std::condition_variable cv;
std::queue<msg_info> myqueue;
void sender(int local_thread_id )
{
	//  1.1
	int n = rand() % 100 + 1;
	for (int i = 0;i < n; i++) {
		ql.lock();
		myqueue.push ( {local_thread_id,i} );
		ql.unlock();


	}

	// 1.3
	if (threadId <20  && n%3 == 0) {
		ql.lock();			
		threads.push_back(std::thread(sender,threadId )); threadId++;threadId1++;   // t starts running
		ql.unlock();	

		// 1.1
	}

	// 1.4
	if (threadId <19 && n%7 == 0) {
		ql.lock();			
		threads.push_back(std::thread(sender,threadId )); threadId++;threadId1++;  // t starts running
		threads.push_back(std::thread(sender,threadId )); threadId++;threadId1++;  // t starts running
		ql.unlock();	

		// 1.1

	}

	ql.lock();
	threadId1--;
	ql.unlock();	
}

int main()
{

	/* initialize random seed: */
	srand (time(NULL));
	threadId = 1;
	threadId1 = 1;

	// request #3
	for (int  i =0;i<6; i++) {
		ql.lock();	

		threads.push_back(std::thread(sender,threadId));threadId++;threadId1++;    // t starts running
		ql.unlock();	

	}

	while (  threadId1>1 ) {
		ql.lock();	
		if (!myqueue.empty()) {
			struct msg_info  info = myqueue.front();
			myqueue.pop();
			std::cout<<"ThreadID:"<<info.threadId<<" MsgID: "<<info.n<<std::endl;

		} 	
		ql.unlock();
	}



	for (auto &t : threads)
		t.join();   // main thread waits for the thread t to finish
	return 0;
}
  • Here is an output example
ThreadID:2 MsgID: 0
ThreadID:3 MsgID: 0
ThreadID:3 MsgID: 1
ThreadID:3 MsgID: 2
ThreadID:3 MsgID: 3
ThreadID:3 MsgID: 4
ThreadID:3 MsgID: 5
ThreadID:3 MsgID: 6
ThreadID:3 MsgID: 7
ThreadID:3 MsgID: 8
ThreadID:3 MsgID: 9
ThreadID:3 MsgID: 10
ThreadID:3 MsgID: 11
ThreadID:3 MsgID: 12
ThreadID:1 MsgID: 0
ThreadID:1 MsgID: 1
ThreadID:1 MsgID: 2
ThreadID:1 MsgID: 3
ThreadID:1 MsgID: 4
ThreadID:1 MsgID: 5
ThreadID:1 MsgID: 6
ThreadID:1 MsgID: 7
ThreadID:1 MsgID: 8
ThreadID:1 MsgID: 9
ThreadID:1 MsgID: 10
ThreadID:1 MsgID: 11
ThreadID:1 MsgID: 12
ThreadID:4 MsgID: 0
ThreadID:5 MsgID: 0
ThreadID:4 MsgID: 1
ThreadID:5 MsgID: 1
ThreadID:6 MsgID: 0
ThreadID:6 MsgID: 1
ThreadID:6 MsgID: 2
ThreadID:6 MsgID: 3
ThreadID:6 MsgID: 4
ThreadID:6 MsgID: 5
ThreadID:6 MsgID: 6
ThreadID:6 MsgID: 7
ThreadID:1 MsgID: 13
ThreadID:1 MsgID: 14
ThreadID:1 MsgID: 15
ThreadID:1 MsgID: 16
ThreadID:1 MsgID: 17
ThreadID:1 MsgID: 18
ThreadID:1 MsgID: 19
ThreadID:1 MsgID: 20
ThreadID:1 MsgID: 21
ThreadID:1 MsgID: 22
ThreadID:1 MsgID: 23
ThreadID:1 MsgID: 24
ThreadID:1 MsgID: 25
ThreadID:1 MsgID: 26
ThreadID:1 MsgID: 27
ThreadID:1 MsgID: 28
ThreadID:1 MsgID: 29
ThreadID:1 MsgID: 30
ThreadID:1 MsgID: 31
ThreadID:1 MsgID: 32
ThreadID:1 MsgID: 33
ThreadID:1 MsgID: 34
ThreadID:1 MsgID: 35
ThreadID:1 MsgID: 36
ThreadID:3 MsgID: 13

Sort Binary Array

Sort an array of 0s and 1s. Example Input: [0,1,1,1,0,1,0] Desired Output: [0,0,0,1,1,1,1] You may assume the input length is at least 2 and that the input consists of 0 and 1 only.

  • simple solution using input and output buffers
void main(char *h) {
  char in[N];
  char out[N];
  for (int i = 0;i < N;i++) {
  	if (in[i] == 0) {
    	out [s] = 0;
    	s++;
    } else {
    	out [e] =  1;
        e--;
    }
  }
}
  • complex solution, using only one buffer
#include <stdio.h>
int f(char *in,int N) {
	int s = 0;
	int e = N - 1;
	while (e>s) {
		if ( in[s] == 0 && in[e] == 1) {
			s++;
			e--;
		} else if ( in[s] == 1 && in[e] == 0) {
			in[s]=0;
			in[e]=1;
			s++;
			e--;
		}  else if ( in[s] == 1 && in[e] == 1) {
			e--;
		} else if ( in[s] == 0 && in[e] == 0) {
			s++;
		}
	}

}

void main () {
	char in[10]={1,1,0,0,1,1,0,1,1};
	for (int i=0;i<sizeof(in);i++) {
		printf ("%d,",in[i]);
	}
	printf("\r\n"); 	
	f(in,sizeof(in));
	for (int i=0;i<sizeof(in);i++) {
		printf ("%d,",in[i]);
	}
	printf("\r\n"); 
}

Sort Two Array

There are two arrays at size of 4 and 10:

  • A1 = [ 2,4,5,8]
  • A2 = [1,3,5,7,9,11,0,0,0,0]

These arrays are sorted, and the second one, A2, is padded with four zeros at its end. The task is to merge the two arrays above into a single sorted array.

Here is my solution


#include <stdio.h>
#define ARR_SIZE(arr) sizeof(arr)/sizeof(int)
void main() 
{
	int A1[4]={2,4,6,8};
	int A2[10]={1,3,5,7,9,11,0,0,0,0};
	printf ("The 2 arrays are: \n");
	printf ("A1=[");
	for (int i = 0;i < ARR_SIZE(A1); i++) {
		printf ("%d,",A1[i]); 
	}
	printf ("]\n");
	printf ("A2=[");
	for (int i = 0;i < ARR_SIZE(A2); i++) {
		printf ("%d,",A2[i]); 
	}
	printf ("]\n");

	int i_A1=ARR_SIZE(A1)-1;
	int i_A2=ARR_SIZE(A2)-1-4;
	for (int i=ARR_SIZE(A2);i--; i) {
		if ( i_A1 >= 0  &&  A1[i_A1] > A2[i_A2]) {
			A2[i] = A1[i_A1];
			i_A1--;
		} else if ( i_A2 >= 0  &&  A2[i_A2] > A1[i_A1]) {
			A2[i] = A2[i_A2];
			i_A2--;
		}
	}

	printf ("Sort A2=[");
	for (int i = 0;i < ARR_SIZE(A2); i++) {
		printf ("%d,",A2[i]); 
	}
	printf ("]\n");
}

The output is:

The 2 arrays are: 
A1=[2,4,6,8,]
A2=[1,3,5,7,9,11,0,0,0,0,]
Sort A2=[1,2,3,4,5,6,7,8,9,11,]
Comments
comments powered by Disqus