Embedded System Interview

Hot

Thứ Tư, 22 tháng 4, 2020

Defensive Programming

tháng 4 22, 2020 0
General guidelines:
Here we will present the more general guidelines to be followed.

 1 - Treat all warnings as compiling errors. Increase the warning level.
     Treating warnings as errors can help catch many subtle bugs. The warning level should be raised (in Visual studio W4 should be adequate).
     Please notice that it may be necessary to disable some warnings that are caused by external libraries.

 2 - Keep functions short, when possible, to facilitate code review.
     Straightforward. If the function is too long, consider breaking it into subfunctions.

 3 - Use automated code quality tools (e.g.: Visual Studio)
     This kind of tool also may help to catch bugs. There are a variety of tools available. If you are using Visual Studio, there is a
     build in tool for code analysis in the menu [Analyze->Run Code Analysis]. After clicking this option for the first time, a second option will appear: [Analyze->Configure Code Analysis]. In this option, it is recommended to raise the analysis level to the maximum.
     Please notice that it is likely that you will have to ignore warnings in external code. Also, sometimes the analysis may be wrong, so
     attention is necessary.

 4 - Add logs, data dumps, or visual representations of the system status, to aid finding and fixing more complex bugs.
     Also straightforward. Having some textual or visual representation of the system state may greatly help to catch bugs.

 5 - Add plenty of comments to the code at the same time you are writing it.
     Straightforward. Just take care to update the comments if the source code changes. It is better to write the comments as you code because the meaning of the lines is fresh in one's memory. It would be harder and less precise to comment the code later.

 6 - When possible, prefer simpler flow control methods (avoid goto, recursion, polymorphism, etc.).
     Complex flow control methods add uncertainty and complexity to the source code. When there is recursion, it may be hard to calculate how many times the recursive function will be called. When there is polymorphism, it may be hard to determine which implementation of the function is being called at a given stage. Please notice that if using those complex flow control methods will make the code simpler, then they should be used.

 7 - In a function/method, check the validity of the input, check if the output is valid and has the correct properties, check the collateral effects (when applicable).
     This is a part of Design by Contract (DC) methodology: In a function, the correctness of the input should never be trusted,
     and the correctness of the output be guaranteed. Of course, it may be not possible to check input/output with 100% certainty.
     An example of code without DC:
    
     template<typename T>
     vector<T> random_vector_t(int size, T mean = T(0), T sigma = T(1.0)) {
        static std::default_random_engine generator;
        std::normal_distribution<T> distribution(mean, sigma);

        vector<T> res(size);

        for (int idx = 0; idx < size; idx++) {
            res[idx] = distribution(generator);
        }

        return res;
     }
    
     In the code above, we do not know if the value sigma, the standard deviation, is valid (i.e.: positive, bigger than 0).
     Also, the size of the output vector should not be zero. As a post-condition, the size of the output vector should be the same as the parameter size. We create pre and post condition macros to test the conditions.
    
     //Verification by Design by Contract (Pre-condition)
     #define PRECONDITION( x ) assert ( (x) )
    
     //Verification by Design by Contract (Post-condition)
     #define POSTCONDITION( x ) assert ( (x) )
    
     template<typename T>
     vector<T> random_vector_t(int size, T mean = T(0), T sigma = T(1.0)) {
        PRECONDITION(size > 0);
        PRECONDITION(sigma > 0);
        static std::default_random_engine generator;
        std::normal_distribution<T> distribution(mean, sigma);

        vector<T> res(size);

        for (int idx = 0; idx < size; idx++) {
            res[idx] = distribution(generator);
        }

        POSTCONDITION((int)res.size() == size);
        return res;
     }
    
     In the code above, both input and output conditions are tested.

 8 - Know when to check for error using "assert" or error handling code.
     Asserts can be disabled in the production code. This is useful because the error checking may have a performance impact.
     Hence, asserts must be used to check programming errors. However, if the error may be caused by the user, this error should be handled in the production code as well. For example:
     void foo(FILE * f){
        assert(f != 0);
        fprintf(f, "Hello world\n");
     }
     In the code above, since we assume that "f" will never be null when the source code is correct, we may use "assert(f != 0)".
    
     However, in the code below:
     void foo(string filename){
        File* f = fopen(filename.c_str(), "r");
        if(f == 0){
            //report error and quit!!
        }
        fprintf(f, "Hello world\n");
     }
    
     Even if the code is correct, "f" may be null if the user passes a file with a wrong filename. This check should be in the production code.
-----------------------------------------------------------------------------------------------------------------------------------------------------------
Specific guidelines

 These guidelines are specific good practices that should be followed whenever possible.  

 1 - Do not use assign operators in sub-expressions.
     This may cause side effects hard to guess. Also, it may help avoid confusing = with ==
    
     - Bad example:
     int x;
     if((x = foo()) == 100){...}
    
     - Good example:
     int x = foo();
     if(x == 100){...}
    
 2 - Floating-point expressions shall not be directly or indirectly tested for equality or inequality.
     Some values that have a finite representation in decimal may have an infinite representation in binary. Also, the float operations inherently add error to the computations.
    
     - Bad example:
     float x = ...;
     if( x == 100.0f){...}
    
     - Good example:
     float EPS = 1e-8f;//Small value
     float x = ...;
     if (fabs(x - 100.0f) < EPS){...} //Difference is smaller than the error EPS
    

 3 - The statements forming the body of a loop or an if construct must always be enclosed by {}, even if it is a single statement.
     Having no {} may cause the common mistake of adding a new statement to a loop while forgetting to add the {}.
    
     - Bad example:
     //Original code
     while(x > 0)
        x = foo(x);
     //Error
     while(x > 0)
        float new_x = foo(x);
        x = new_x;//This line is out of the loop!!
    
     - Good example:
     while(x > 0){
        x = foo(x);
     }

 4 - All "if ... else if" constructs shall be terminated with an else clause.
     This is done to make sure all possibilities are being covered. If the final "else" statement is empty, it should contain comments
     explaining why it is so.
    
     - Bad example:
     if((x % 4) == 0){
        ...
     }else if((x % 3) == 0){
        ...
     }
    
     - Good example:
     if((x % 4) == 0){
        ...
     }else if((x % 3) == 0){
        ...
     }else{
        //Final else; may be empty
     }

 5 - All non-empty switch-clause should be finished by a break statement. The final clause shall be a default clause.
     Failing to add a break to the switch clause is generally an error. The rationale about always having a default clause is similar to the final else in the previous guideline.
    
     - Bad example:
     switch( x ){
        case 0:
            foo();//Error!
        case 1:
        case 2:
            bar();//Cases 1 and 2 should have the same effect
            break;
     }//No default!
    
     - Good example:
     switch( x ){
         case 0:
            foo();
            break;
        case 1:
        case 2:
            bar();//Cases 1 and 2 should have the same effect
            break;
        default:
            process_error();//Or some other action...
     }

 6 - A for loop shall contain a single loop counter which shall not have floating type.
     A loop with multiple loop counters or with a float counter is commonly implemented as a "while".
    
     - Bad example:
     y = 0;
     for(x = 0; x < y; x = y++){...}
    

 7 - If the loop counter is not modified by -- or ++, then the loop condition shall be specified by <=, >=, <, or >.
     If the loop is not incremented by units, the stop condition may not occur if == or != is used in the condition.
   
     - Bad example:
     for(int i = 1; i != 10; i += 2){} //Infinite loop
    
     - Good example:
     for(int i = 1; i < 10; i += 2){} //Eventually stops

 8 - The loop counter shall not be modified within the condition or statement.
     Modifying the counter may easily cause errors in the loop.
    
     - Bad example:
     void foo(int& x_p){ (*x)--;}
     ...
     for(x = 10; foo(&x); ){
     //...
     }


 9 - The loop counter shall be modified by one of: --, ++, -=n, or +=n. The value of n remains constant.
     This makes proving the loop termination much easier.
     - Bad example:
     for(int x = 0; x < 100; x = bar(x)){...}
    
     - Good example:
     for(int x = 0; x < 100; x += 10){...}
    
10 - Loop control variables other than the loop counter should not be modified, with exception of boolean flags.
     Same reason as above, with the exception of boolean flags, used to break the loop.
    
     - Bad example:
     float v;
     for(int x = 0; x < 100 && v < 10; x++){
        v = foo();
     }
    
     - Good example:
     bool f = true;
     for(int x = 0; x < 100 && flag; x++){
        float v = foo();
        f = (v < 10);
     }
    
    
11 - If a function generates error information, this information shall be tested.
     Straightforward. It greatly helps to find errors.
    
     - Bad example:
        bool foo(float &x){
            bool error = false;
           
            if(x < 0){
                error = true;
            }else{
                x = sqrt(x);
            }
            return error;
        }
    
        ...
       
        float x = ...;
        foo(x);
       
     - Good example:
        ...
        float x = ...;
        bool error = foo(x);
        if(error){
            //Process error
        }
Read More

Thứ Ba, 3 tháng 3, 2020

How can I be best prepared for Amazon's technical interview in the next 15 days?

tháng 3 03, 2020 0

Answer 1:
I went for my Amazon technical interview with only 5 days worth of preparation and still got the job. Here’s the story -
The Phone Interview

I got a call from Amazon and they were interested in a phone interview. I asked them to schedule it 2 weeks from the day they called but they had a hiring event drive coming up and asked me to take the interview within 3 days.
I was never good with data structures and algorithms or technical interviews for that matter because my bachelors was in electrical engineering. However, I have been working as a Software Engineer for the last 4 years so I can definitely code really well and I am aware of the various design paradigms you require to write good quality code
Now, with absolutely no knowledge of how a graph or a tree works OR how a merge sort would sort data, I devised a simple plan for myself. I spent the first two days on HackerRank practicing every data structure. I did not practice all the questions, but just the ones I thought were important
On the 3rd day , before the phone interview, I solved couple questions from Cracking the Coding Interview and went over every data structure which is commonly asked in interviews.
Now come the day of phone interview, I was able to solve the one slightly hard question my interviewer asked. I was obviously stuck at places, but I made sure to keep saying whatever came to my mind, so he knew how I was thinking. And it worked, because me and my interviewer did a bit of pair programming to solve the question.

Technical Onsite Interview
Now I was invited to the onsite BUT I only had 5 days to prepare for it. Instead of starting from the first day , I went on a two day trip to Vegas (Not kidding). I started on the 3rd day and followed the same routine of solving hackerranks and cracking the coding interview. I did not spend all day on it, just 3–4 hours a day when I felt I would focus the most
You must be wondering this is too good to be true, cracking the interview with such little preparation. Trust me I wonder the same. But there is something I practiced the day before my interview, which I believe is the secret sauce that helped me do well - /
Secret Sauce
  • Step 1 - I really focused and improved upon how I START thinking about the question. This is the most important step according to me. You may know all the data structures in the world, but if you dont start off correctly with a problem, you cant do much. So first step is to just think about how you will start!
     In my case I started of by writing all the inputs given to me, all the outputs required and constraints if any
  • Step 2 - What next? Well now think which data structure will solve the problem?
  • Step 3 - Is there something you should do before using the data structure? Like sorting, arranging, or anything that makes the it easy for the data structure to solve that problem. More often than not, sorting a given input can do wonders
  • Step 4 - Write down all the steps you will be performing. Don’t even think about writing code right now. Just write the steps and write the expected Big O complexity and space complexity
  • Step 5 - Now optimize the solution you wrote above. Were you at least able to write a brute force? Can you use another data structure to improve the complexities ? Can you pre-process the input to reduce the complexities?
  • Step 6 - Only when you are absolutely sure about the optimal solution, start writing the code.
Although the amazon interview was very challenging and not easy at all, I stuck to my steps above.. even when I was nervous as hell. Also, I prepared for my behavioral questions. Please dont think behavior questions dont count. They really do
Repeat these 6 steps during your whiteboard too and you will succeed. I got three job offers apart from Amazon after i used the above approach . And trust me my preparation was bare minimum (like 1–2 days at max)

Answer 2:

I'm the Former VP Global Talent Acquisition for Amazon and trained interviewers at Amazon on how to interview, so this is a topic I know well. In fact, too well--there is some non-public info I cannot disclose.
However, the generally public information I can disclose will help you get prepped for your Amazon interview.
First of all, you didn't say whether it was a phone or in-person interview. Given that it is 15 days out, it likely is an in-person interview.
In either case, you need to read and re-read all of the information you can get your hands on regarding algorithms (many of the tech questions are based on algorithms, not specific languages) and data structures. You need to have one language where you have a level of mastery, ideally two or more (so that you can select the one that matches up best with your interviewer). However, don't worry if the interviewer is not familiar with the specific language you use to solve a technical problem, it's the algorithms and data structures they will be looking at in your answer.
If you are doing an in-person interview, be ready to whiteboard an answer. You need to talk as you write out your answer to show your logic in working out your answer to the problem. Even if the interviewer has not suggested that you use a whiteboard to solve the problem, almost every interview room has one. If there is one in the interview room, ask if you can use the whiteboard to solve the problem.
Your in-person interviews will typically be 30 to 60 minutes each and each interviewer (usually 5-7 interviewers for tech) will be focused on a different competency. Don't expect all interviews to be technical. You will also be asked behavioral-based competency questions. Answer using: "Let me give you an example..." and then provide your best example.
At least one person on the interview team will likely not be from the team for which you are interviewing. If you are interviewing with multiple interviewers from two or more teams, you may be interviewing for roles in more than one team. The "odd out" person person from a different team (usually a senior person from another team) is a Bar Raiser and they are on the interview slate to make sure that the interviewing team makes the right overall hiring decision, raising the talent bar at Amazon.
If one interview (or even two) don't go well, don't worry about it. You can still get an offer even if you blow one interview. Although the exception could be the Bar Raiser.
Overall, use specific examples of work you have done before to show how not just how you would solve a problem, but how you have solved a similar problem in the past. Use the S-T-A-R behavioral approach, giving a Situation or Task, the Action you took and the Results achieved. Try to stay away from hypotheticals and use real life examples whenever possible.
Amazon has a very high bar for tech hiring, similar to Google. Be ready to be tested to your limits and (depending on the interviewer) possibly beyond your limits. The interviewer may want to keep pushing technical boundaries to find out what you don't know, in addition to what you do know. So you might walk away thinking you blew the interview because you couldn't answer their last question, when in fact you went to a pretty high upper limit to find a question to which you didn't know the answer.
The entire day (usually in-person interviews are at least a half day, sometimes a full day or even longer, depending on the role) can be pretty grueling and demanding. You need to be at the top of your game all day long. Get fueled up before going in.
And oh, BTW, if you need the bathroom, you'll probably have to ask to use it. Most interviews are arranged back-to-back-to-back with no breaks in between. Better to ask than squirm in your chair. :)
It's unlikely that you will get feedback same day. There is an interview debrief that will take place with all interviews, can be later that day, but is usually a day or two later. After that meeting is when you will hear back from either the Recruiter or the hiring manager about next steps (either an offer, a decline or, in some cases, further interviews). And a no doesn't necessarily mean no forever. You may still have a chance (if the hire/no hire decision was close) to interview with a different team where you may be a better fit. So keep the doors open.

(source Quora)
Read More

Thứ Hai, 2 tháng 3, 2020

Properties of common sorting algorithms

tháng 3 02, 2020 0
The most common sorting algorithms are:
- Insertion Sort
- Bubble Sort
- Selection Sort
- Merge sort
- Quick Sort

Insertion Sort
This is used when:
- Data set is relatively small
- Items in the data set are semi-sorted already
Worst case performance: O(n²) - So if you have 100 elements in your array, at worst, this algorithm will do 10,000 comparisons. This is when your data set is sorted completely opposite of how you wish to sort the data.
Average case performance: O(n²) - The average case won’t quite be 10,000 comparisons, but it will be higher than O(n) or O(nlogn) time.
Best case performance: O(n) - The best case performance is when the data set is already sorted and it only needs to iterate each item in the array and do one comparison for each item in the data set.
void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) { 
        key = arr[i]; 
        j = i - 1; 
  
        /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

Bubble Sort
This is used when:
- When data set is relatively small
- When items in the data set are semi-sorted already
- Bubble Sort is not online (it cannot sort a stream of inputs without knowing how many items there will be) because it does not really keep track of a global maximum of the sorted elements. When an item is inserted you will need to start the bubbling from the very beginning. This could be useful, when dealing with data coming from network, or some sensor.
- Bubble sort is better than insertion sort only when someone is looking for top k elements from a large list of number i.e. in bubble sort after k iterations you'll get top k elements. However after k iterations in insertion sort, it only assures that those k elements are sorted.
Worst case performance: O(n²) - So if you have 100 elements in your array, at worst, this algorithm will do 10,000 comparisons. This is when your data set is sorted completely opposite of how you wish to sort the data.
Average case performance: O(n²) - The average case won’t quite be 10,000 comparisons, but it will be higher than O(n) or O(nlogn) time.
Best case performance: O(n) - The best case performance is when the data set is already sorted and it only needs to iterate each item in the array and do one comparison for each item in the data set.
void bubbleSort(int arr[], int n) 
{ 
   int i, j; 
   for (i = 0; i < n-1; i++)       
  
       // Last i elements are already in place    
       for (j = 0; j < n-i-1; j++)  
           if (arr[j] > arr[j+1]) 
              swap(&arr[j], &arr[j+1]); 
} 

Selection Sort

This is used when:
- When data set is relatively small
- Insertion Sort would still be more optimal as it has the possibility of fewer comparisons than Selection Sort
Worst case performance: O(n²) - The worst case is the same as both worst case, and best case. This algorithm will still need to do O(n²) comparisons to make sure everything is in order. Which is one disadvantage of this particular algorithm.
Average case performance: O(n²) - The average case is the same as both worst case, and best case. This algorithm will still need to do O(n²) comparisons to make sure everything is in order. Which is one disadvantage of this particular algorithm.
Best case performance: O(n²) - The best case performance is the same as both worst case, and average case. This algorithm will still need to do O(n²) comparisons to make sure everything is in order. Which is one disadvantage of this particular algorithm.


void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 
  
    // One by one move boundary of unsorted subarray 
    for (i = 0; i < n-1; i++) 
    { 
        // Find the minimum element in unsorted array 
        min_idx = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min_idx]) 
            min_idx = j; 
  
        // Swap the found minimum element with the first element 
        swap(&arr[min_idx], &arr[i]); 
    } 
} 

Merge Sort

This is used when:
- Larger data sets
- When there are not memory or storage constraints, as the most common implementations of merge sort uses a secondary list using the same amount of space as original list to help with sorting.
- When items in the data set can be accessed sequentially
- This is the only one that is stable among (Heap Sort and Quick Sort)
- Slower than the other Heap Sort and Quick Sort. Because you have to write all your data into another array and back into your original one. Copying is usually slower than comparing. 
Worst case performance: O(nlogn) - The worst case is the same as both worst case, and best case.
Average case performance: O(nlogn) - The average case is the same as both worst case, and best case.
Best case performance: O(nlogn) - The best case performance is the same as both worst case, and average case.
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    /* create temp arrays */
    int L[n1], R[n2]; 
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 
  
        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
} 

Quicksort

This is used when:
- Large data sets
- When the ordering of equal elements is not important. Quicksort is not a stable algorithm, which means that once the data set is ordered, that elements whose values are equal, are not guaranteed to be in the same ordering as the initial data set.
- Generally the fastest sorting algorithm in practice. It only swaps what needs to be swapped. Swaps are slow!
- Can be performed in-place, but in practice, the stack frames from recursive function calls results in 𝑂(log𝑛)
space complexity.
Worst case performance: O(n²) - For Quicksort, n² running time complexity is rare. This can happen in cases:
1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2) 
Average case performance: O(nlogn) - The average case is the same as best case.
Best case performance: O(nlogn) - The best case performance is the same as average case.
// A utility function to swap two elements 
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
  
/* This function takes last element as pivot, places 
   the pivot element at its correct position in sorted 
    array, and places all smaller (smaller than pivot) 
   to left of pivot and all greater elements to right 
   of pivot */
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 
  
    for (int j = low; j <= high- 1; j++) 
    { 
        // If current element is smaller than the pivot 
        if (arr[j] < pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
/* The main function that implements QuickSort 
 arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 
  
        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
Read More

Chủ Nhật, 1 tháng 3, 2020

Big-O complexities

Algorithms complexities

tháng 3 01, 2020 0

O(1) time
- Accessing Array Index (int a = ARR[5];)
- Inserting a node in Linked List
- Pushing and Poping on Stack
- Insertion and Removal from Queue
- Finding out the parent or left/right child of a node in a tree stored in Array
- Jumping to Next/Previous element in Doubly Linked List

O(n) time
In a nutshell, all Brute Force Algorithms, or Noob ones which require linearity, are based on O(n) time complexity
- Traversing an array
- Traversing a linked list
- Linear Search
- Deletion of a specific element in a Linked List (Not sorted)
- Comparing two strings
- Checking for Palindrome
- Counting/Bucket Sort

O(log n) time
- Binary Search
- Finding largest/smallest number in a binary search tree
- Certain Divide and Conquer Algorithms based on Linear functionality
- Calculating Fibonacci Numbers - Best Method The basic premise here is NOT using the complete data, and reducing the problem size with every iteration

O(n log n) time

The factor of 'log n' is introduced by bringing into consideration Divide and Conquer. Some of these algorithms are the best optimized ones and used frequently.
- Merge Sort
- Heap Sort
- Quick Sort
- Certain Divide and Conquer Algorithms based on optimizing O(n^2) algorithms

O(n^2) time
These ones are supposed to be the less efficient algorithms if their O(nlogn) counterparts are present. The general application may be Brute Force here.
- Bubble Sort
- Insertion Sort
- Selection Sort
- Traversing a simple 2D array
Read More

Application binary interface "ABI" vs Application programming interface "API"

tháng 3 01, 2020 0
You are already familiar with the concept of an API. If you want to use the features of, say, some library or your OS, you will use an API. The API consists of data types/structures, constants, functions, etc that you can use in your code to access the functionality of that external component.
An ABI is very similar. Think of it as the compiled version of an API (or as an API on the machine-language level). When you write source code, you access the library through an API. Once the code is compiled, your application accesses the binary data in the library through the ABI. The ABI defines the structures and methods that your compiled application will use to access the external library (just like the API did), only on a lower level.
ABIs are important when it comes to applications that use external libraries. If a program is built to use a particular library and that library is later updated, you don't want to have to re-compile that application (and from the end-user's standpoint, you may not have the source). If the updated library uses the same ABI, then your program will not need to change. The interface to the library (which is all your program really cares about) is the same even though the internal workings may have changed. Two versions of a library that have the same ABI are sometimes called "binary-compatible" since they have the same low-level interface (you should be able to replace the old version with the new one and not have any major problems).
Sometimes, ABI changes are unavoidable. When this happens, any programs that use that library will not work unless they are re-compiled to use the new version of the library. If the ABI changes but the API does not, then the old and new library versions are sometimes called "source compatible". This implies that while a program compiled for one library version will not work with the other, source code written for one will work for the other if re-compiled.
For this reason, library writers tend to try to keep their ABI stable (to minimize disruption). Keeping an ABI stable means not changing function interfaces (return type and number, types, and order of arguments), definitions of data types or data structures, defined constants, etc. New functions and data types can be added, but existing ones must stay the same. If you expand, say, a 16-bit data structure field into a 32-bit field, then already-compiled code that uses that data structure will not be accessing that field (or any following it) correctly. Accessing data structure members gets converted into memory addresses and offsets during compilation and if the data structure changes, then these offsets will not point to what the code is expecting them to point to and the results are unpredictable at best.
An ABI isn't necessarily something you will explicitly provide unless you are expecting people to interface with your code using assembly. It isn't language-specific either, since (for example) a C application and a Pascal application will use the same ABI after they are compiled.
Edit: Regarding your question about the chapters regarding the ELF file format in the SysV ABI docs: The reason this information is included is because the ELF format defines the interface between operating system and application. When you tell the OS to run a program, it expects the program to be formatted in a certain way and (for example) expects the first section of the binary to be an ELF header containing certain information at specific memory offsets. This is how the application communicates important information about itself to the operating system. If you build a program in a non-ELF binary format (such as a.out or PE), then an OS that expects ELF-formatted applications will not be able to interpret the binary file or run the application. This is one big reason why Windows apps cannot be run directly on a Linux machine (or vice versa) without being either re-compiled or run inside some type of emulation layer that can translate from one binary format to another.
IIRC, Windows currently uses the Portable Executable (or, PE) format. There are links in the "external links" section of that Wikipedia page with more information about the PE format.
Also, regarding your note about C++ name mangling: The ABI can define a "standardized" way for a C++ compiler to do name mangling for the purpose of compatibility. That is, if I create a library and you develop a program that uses the library, you should be able to use a different compiler than I did and not have to worry about the resulting binaries being incompatible due to different name mangling schemes. This is really only of use if you are defining a new binary file format or writing a compiler or linker.
Read More

Thứ Hai, 20 tháng 1, 2020

Low level Memory Q&A

tháng 1 20, 2020 0
Q: What is the memory layout of C program
A: Memory layout of C program includes sections:
- Text or Code Segment
- Initialized data segment
- Uninitialized data segment
- Stack
- Heap
Text or Code Segment:- The text segment contains a binary of the compiled program.
- The text segment is a read-only segment that prevents a program from being accidentally modified.
- It is sharable so that only a single copy needs to be in memory for frequently executed programs such as text editors etc.
DS(Initialized data segment):- It contains the explicitly initialized global and static variables.
- The size of this segment is determined by the size of the values in the program’s source code and does not change at run time.
- It has read-write permission so the value of the variable of this segment can be changed at run time.
- This segment can be further classified into an initialized read-only area and an initialized read-write area.
#include <stdio.h>

char c[]="emb-interview1";     /*  global variable stored in Initialized Data Segment in read-write area*/
const char s[]="emb-interview2";    /* global variable stored in Initialized Data Segment in read-only area*/

int main()
{
    static int i=44;          /* static variable stored in Initialized Data Segment*/
    return 0;
}

BSS(Uninitialized data segment):- It contain all uninitialized global and static variable.
- All variables in this segment initialized by the zero(0) and pointer with the null pointer.
- The program loader allocates memory for the BSS section when it loads the program.
#include <stdio.h>

int i;               /* Uninitialized variable stored in bss*/

int main()
{
    static int j;     /* Uninitialized static variable stored in bss */
    return 0;
}

Stack:
 - It located at a higher address and grows and shrinks opposite to the heap segment.
 - The stack contains local variables from functions and related book-keeping data.
 - A stack frame will create in the stack when a function is called.
 - Each function has one stack frame.
 - Stack frames contain function’s local variables arguments and return value.
 - The stack contains a LIFO structure. Function variables are pushed onto the stack when called and functions variables are popped off the stack when return.
 - SP(stack pointer) register tracks the top of the stack.

#include <stdio.h>
int main(void)
{
    int i; //local variable stored in stack
    return 0;
}

Heap: - It is used to allocate the memory at run time.
 - Heap area managed by the memory management functions like malloc, calloc, free, etc which may internally use the brk and sbrk system calls to adjust its size.
 - The Heap area is shared by all shared libraries and dynamically loaded modules in a process.
 - It grows and shrinks in the opposite direction of the stack.
#include <stdio.h>
int main()
{
    int *p=(char*)malloc(sizeof(int));    /* memory allocating in heap segment */
    return 0;
}

Q: What is Big endian and little endian? Write a C program to check if the underlying architecture is little endian or big endian.
A: Big endian and little endian are two formats to store multibyte data types into computer's memory.
As an example, if x a four byte integer contains a hex value 0x76543210. If program is run on little endian machine, gives "67 45 23 01" as output. If it is run on big endian machine, gives "01 23 45 67" as output

#include <bits/stdc++.h> 
using namespace std; 
int main()  
{  
    unsigned int i = 1;  
    char *c = (char*)&i;  
    if (*c)  
        cout<<"Little endian";  
    else
        cout<<"Big endian";  
    return 0;  
}  
  

Q: Write a function called malloc2d() which allocates a two dimensional array. Minimize the number of calls to malloc() and make sure that the memory is accessible by the notation arr[i][j]
A:
#include <iostream>

using namespace std;

int** malloc2d(int rows, int cols)
{
    int header = rows * sizeof(int*);
    int data = rows * cols * sizeof(int);
    int** rowptr = (int**)malloc(header + data);
    int* buf = (int*)(rowptr + rows);
    int k;
    for (k = 0; k < rows; ++k) {
        rowptr[k] = buf + k*cols;
    }
    return rowptr;
}

int free2d(int** pt)
{
    free(pt);
    return 0;
}

int main(int argc, char* argv[])
{
    int i, j;
    int **p = malloc2d(3,5);

    for( i = 0; i < 3; i++){
        for(j = 0; j < 5; j++){
            p[i][j] = i + j;
            cout << p[i][j] << " ";
        }
        cout << endl;
    }

    free2d(p);

    return 0;
}

Q: Write an aligned malloc() & free() function that takes number of bytes and aligned byte (which is always power of 2)
A:
#include <iostream>
using namespace std;

int aligned_malloc(void **memptr, size_t alignment, size_t size)
{
    size_t len = size + alignment + sizeof(void *);

    void *ptr = malloc(len);

    if(ptr == NULL){
        return 0;
    }

    *memptr = (unsigned int *)((((unsigned)ptr) + alignment + sizeof(void *)) & ~(alignment - 1));

    *((unsigned int *)(((unsigned int *)*memptr) - 1)) = (unsigned)ptr;
    
    return 1;
}

int aligned_free(void *memptr)
{
    if(memptr == NULL){
        return 0;
    }
    else{
        free((void *)(*((unsigned int *)memptr - 1)));
        return 1;
    }
}

int main(int argc, char* argv[])
{
    for(int i = 1; i < 257; i *= 2){
        void *memptr = NULL;
        aligned_malloc(&memptr, i, 1000);
        cout << "aligned :" << i << " -- " << hex << (unsigned)memptr << endl;
        aligned_free(memptr);
    }
 return 0;
}
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