Task for job interview for RT embbeded position
Published at August 10, 2021 · Last Modified at September 29, 2021 · 6 min read · Tags: c++
This post is a collection of tasks and questions for RT embedded job interviews.
Table Of Contents
Kernel disassembler
- 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)
- 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.
- The kernel should support the request for disassembling code from a specific address passed to it through module parameters.
- 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:
- 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- 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”
- 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,]