Embedded System Interview

Hot

Thứ Hai, 20 tháng 1, 2020

C Questions & Answers

tháng 1 20, 2020 0

Q: In printf() Function- What is the difference between "printf(...)" and "sprintf(...)"?
A: sprintf(...) writes data to the character array whereas printf(...) writes data to the standard output device.

Q: Compilation How to reduce a final size of executable?
A: Size of the final executable can be reduced using dynamic linking for libraries.

Q: Can you tell me how to check whether a linked list is circular?
A: Create two pointers, and set both to the start of the list. Update each as follows:
while (pointer1) 
{
    pointer1 = pointer1->next;
    pointer2 = pointer2->next;
    if (pointer2) pointer2=pointer2->next;
    if (pointer1 == pointer2) 
    {
        printf("circular");
    }
}

If a list is circular, at some point pointer2 will wrap around and be either at the item just before pointer1, or the item before that. Either way, its either 1 or 2 jumps until they meet.

Q: Write out a function that prints out all the permutations of a string. For example, abc would give you abc, acb, bac, bca, cab, cba.
A:
#include <stdio.h>
#include <string.h>

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

void main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
} 

Q: What will be the output of the following code?
void main()
{
    int i = 0 , a[3] ;
    a[i] = i++;
    printf ("%d",a[i]) ;
}
A: The output for the above code would be a garbage value. In the statement a[i] = i++; the value of the variable i would get assigned first to a[i] i.e. a[0] and then the value of i would get incremented by 1. Since a[i] i.e. a[1] has not been initialized, a[i] will have a garbage value.

Q: How do I know how many elements an array can hold?
A: The amount of memory an array can consume depends on the data type of an array. In DOS environment, the amount of memory an array can consume depends on the current memory model (i.e. Tiny, Small, Large, Huge, etc.). In general an array cannot consume more than 64 kb. Consider following program, which shows the maximum number of elements an array of type int, float and char can have in case of Small memory model.
void main()

{

    int i[32767] ;

    float f[16383] ;

    char s[65535] ;

}

Q: How do I write code that reads data at memory location specified by segment and offset?
A: Use peekb() function. This function returns byte(s) read from specific segment and offset locations in memory. The following program illustrates use of this function. In this program from VDU memory we have read characters and its attributes of the first row. The information stored in file is then further read and displayed using peek() function.

#include <stdio.h>
#include <dos.h>

void main()
{
    char far *scr = 0xB8000000 ;
    FILE *fp ;
    int offset ;
    char ch ;
    if((fp = fopen("scr.dat", "wb")) == NULL)
    {
        printf("Unable to open file\n") ;
        exit() ;
    }

    // reads and writes to file
    for( offset = 0 ; offset < 160 ; offset++)
        fprintf (fp, "%c", peekb(scr, offset)) ;

    fclose ( fp ) ;
    if ((fp = fopen("scr.dat", "rb")) == NULL)
    {
        printf("Unable to open file\n") ;
        exit() ;
    }

    // reads and writes to file
    for(offset = 0 ; offset < 160 ; offset++)
    {
        fscanf(fp, "%c", &ch);
        printf("%c", ch);
    }
    fclose(fp) ;
}
Read More

TieRopes

tháng 1 20, 2020 0
There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].

We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.

For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.

For example, consider K = 4 and array A such that:
    A[0] = 1
    A[1] = 2
    A[2] = 3
    A[3] = 4
    A[4] = 1
    A[5] = 1
    A[6] = 3

The ropes are shown in the figure below.

We can tie:

        rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
        rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 5.

After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.

Write a function:

    int solution(int K, vector<int> &A);

that, given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.

For example, given K = 4 and array A such that:
    A[0] = 1
    A[1] = 2
    A[2] = 3
    A[3] = 4
    A[4] = 1
    A[5] = 1
    A[6] = 3

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        K is an integer within the range [1..1,000,000,000];
        each element of array A is an integer within the range [1..1,000,000,000].


int solution(int K, vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    int s = 0;
    int num = 0;
    for (size_t i = 0; i < A.size(); i++) {
        s += A[i];
        
        if (s >= K) {
            num++;
            s = 0;
        }
    }
    
    return num;
}
Read More

MaxNonoverlappingSegments

tháng 1 20, 2020 0
Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.

Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].

We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.

For example, consider arrays A, B such that:
    A[0] = 1    B[0] = 5
    A[1] = 3    B[1] = 6
    A[2] = 7    B[2] = 8
    A[3] = 9    B[3] = 9
    A[4] = 9    B[4] = 10

The segments are shown in the figure below.


The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.

Write a function:

    int solution(vector<int> &A, vector<int> &B);

that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.

For example, given arrays A, B shown above, the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..30,000];
        each element of arrays A, B is an integer within the range [0..1,000,000,000];
        A[I] ≤ B[I], for each I (0 ≤ I < N);
        B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).


bool is_overlapped(int a1, int b1, int a2, int b2)
{
    return ((a1 <= a2) && (a2 <= b1)) ||
           ((a2 <= a1) && (a1 <= b2));
}

int solution(vector<int> &A, vector<int> &B) {
    // write your code in C++11 (g++ 4.8.2)
    int s = int(A.size());
    if (s == 0) return 0;
    else if (s == 1) return 1;
    
    int start = A[s- 1];
    int end = B[s - 1];
    int num = 1;
    for (int i = (B.size() - 2); i >= 0; i--) {
        if (!is_overlapped(start, end, A[i], B[i])) {
            num ++;
            start = A[i];
            end = B[i];
        } else {
            start = max(A[i], start);
        }
    }
    
    return num;
}
Read More

MinAbsSumOfTwo

tháng 1 20, 2020 0
Let A be a non-empty array consisting of N integers.

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:
  A[0] =  1
  A[1] =  4
  A[2] = -3

has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2).
The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.
The abs sum of two for the pair (0, 1) is A[0] + A[1] = |1 + 4| = 5.
The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2.
The abs sum of two for the pair (1, 1) is A[1] + A[1] = |4 + 4| = 8.
The abs sum of two for the pair (1, 2) is A[1] + A[2] = |4 + (−3)| = 1.
The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.

Write a function:

    int solution(vector<int> &A);

that, given a non-empty array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:
  A[0] =  1
  A[1] =  4
  A[2] = -3

the function should return 1, as explained above.

Given array A:
  A[0] = -8
  A[1] =  4
  A[2] =  5
  A[3] =-10
  A[4] =  3

the function should return |(−8) + 5| = 3.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].


#include <algorithm>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    if (A.size() == 1) return abs(A[0]) * 2;
    
    sort(A.begin(), A.end(), [](int a, int b) {
        return abs(a) < abs(b); });
    
    int min_sum = abs(A[0]) * 2;
    
    for (int i = 0; i < A.size() - 1; i++) {
        min_sum = min(min_sum, abs(A[i] + A[i + 1]));    
    }
    
    return min_sum;
}
Read More

CountTriangles

tháng 1 20, 2020 0
An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

        A[P] + A[Q] > A[R],
        A[Q] + A[R] > A[P],
        A[R] + A[P] > A[Q].

For example, consider array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).

Write a function:

    int solution(vector<int> &A);

that, given an array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 12

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..1,000];
        each element of array A is an integer within the range [1..1,000,000,000].


#include <algorithm>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    int s = int(A.size());
    
    if (s < 3) return 0;
    
    sort(A.begin(), A.end());
    
    if (A[0] + A[1] > A[s - 1]) {
        return s * (s - 1) * (s -2) / 6;
    }
    
    int num = 0;
    int start = 0;
    int end = 0;
    for (int i = 0; i < s -2; i++) {
        for (int j = i + 1; j < s - 1; j++) {
            for (int k = j + 1; k < s; k++) {
                if (A[i] + A[j] > A[k]) {
                    num++;
                } else {
                    break;
                }
            }
        }
    }
    
    return num;
}
Read More

CountDistinctSlices

tháng 1 20, 2020 0
An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

        A[P] + A[Q] > A[R],
        A[Q] + A[R] > A[P],
        A[R] + A[P] > A[Q].

For example, consider array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).

Write a function:

    int solution(vector<int> &A);

that, given an array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that:
  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 12

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..1,000];
        each element of array A is an integer within the range [1..1,000,000,000].


#include <algorithm>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    
    int s = int(A.size());
    if (s < 3) return 0;
    
    sort(A.begin(), A.end());
    
    if (A[0] + A[1] > A[s - 1]) {
        return s * (s - 1) * (s - 2) / 6;    
    }
    
    int num = 0;
    for (int i = 0; i < s - 2; i++) {
        for (int j = i + 1; j < s - 1; j++) {
            for (int k = j + 1; k < s; k++) {
                if (A[i] + A[j] > A[k]) {
                    num++;
                } else {
                    break;
                }
            }
        }
    }
    
    return num;
}
Read More

AbsDistinct

tháng 1 20, 2020 0
A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that:
  A[0] = -5
  A[1] = -3
  A[2] = -1
  A[3] =  0
  A[4] =  3
  A[5] =  6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function:

    int solution(vector<int> &A);

that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.

For example, given array A such that:
  A[0] = -5
  A[1] = -3
  A[2] = -1
  A[3] =  0
  A[4] =  3
  A[5] =  6

the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];
        array A is sorted in non-decreasing order.


#include <set>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    set<int> s;
    for (auto i: A) {
        s.insert(abs(i));
    }
    
    return s.size();
}
Read More
Thường mất vài phút để quảng cáo xuất hiện trên trang nhưng thỉnh thoảng, việc này có thể mất đến 1 giờ. Hãy xem hướng dẫn triển khai mã của chúng tôi để biết thêm chi tiết. Ðã xong