Embedded interview questions (algorithm part)

One 、 Base part

1、 The difference between arrays and linked lists ？

（1） The number of elements of the array must be determined when defining , And the types of elements must be consistent ; The number of elements in the linked list is free , And there can be different types of data in the element .
（2） The elements of the array are stored sequentially in memory , The elements of the linked list are stored randomly .
（3） To access the elements of the array, you can access them by subscript index , It's quite fast ; If you insert it / If the operation is deleted , You have to move a lot of elements , So insert the array / The deletion operation is inefficient . Because the linked list is stored randomly , If you want to access an element in the linked list , Then you have to traverse one by one from the head of the list , Until you find the element you need , So the efficiency of random access of linked list is lower than that of array ; The linked list is inserting / It's very efficient to delete （ Relative arrays ）. In one sentence ： The access efficiency of array is high , And the insertion of linked list / Efficient deletion .

2、C Language program code optimization method

（1） Choose the right data structure and Algorithm ;
（2） Use as small a data type as possible ;
（3） Use self adding 、 Minus instruction ;
（4） Using shift to realize multiplication and division ;
（5） For remainder operation &（ Such as a=a%8 Change it to a=a&7）;
（6） Square operation with *（ Such as a=pow(a,2.0) Change it to a=a*a）;
（7） The delay function is changed from self addition to self subtraction ;
（8）switch Statement according to the frequency of occurrence case Sort ;
（9） Reduce the intensity of the operation .

3、 The difference between heap and stack ？

C Heap and stack for language memory allocation	The stack grows downward , Allocate function parameters and local variables in the stack , The allocation method is similar to the stack in the data structure . The pile is growing up , Allocate the memory space requested by the programmer in the heap （ Once you forget to release, it will cause memory leakage ）, The allocation method is similar to the linked list in the data structure
Heap and stack of data structures	Stack is an advanced and backward data structure . Heap is a sort tree data structure （ It's usually a binary pile ）, Each node has a value , The value of the root node is minimum or maximum , Often used to implement priority queues , Heap storage is arbitrary

4、 What are the advantages, disadvantages and applicable scenarios of inline functions ？

（1） advantage ： Inline functions, like macro definitions, expand in place , It saves the cost of function calls , At the same time, it can do type check .

（2） shortcoming ： It will increase the amount of code in the program , Consume more memory space .

（3） Applicable scenario ： There is no loop in the function body （ Short execution time ） And the code is short （ It takes up little memory space ）

4、 What is the output of the following code ？

#include<stdio.h> 
void main()  
{
      
    int a[5] = {
    1, 2, 3, 4, 5};  
    int *ptr = (int *)(&a + 1);  
    printf("%d, %d", *(a + 1), *(ptr - 1));  
}  

answer ： Output is 2, 5

Reading ： a Is the address of the first element of the array , therefore *(a + 1) That's the second element a[1].&a Is the array address , therefore &a +1 Is the next address at the end of the entire array ,*(ptr - 1) Namely a[4].

5、 Structure struct And consortia union The difference between ？

（1） The biggest difference between the two is the use of memory .

（2） Each member of the structure has its own memory , Use each other without interference , Follow the memory alignment principle .

（3） All members of the consortium share a memory space , And at the same time, only one member can get the right to use this memory . The total length of a consortium variable should at least accommodate the largest member variable , And the memory needs to be supplemented .

6、 There are several ways to pass function parameters ？

（1） Two kinds of ： Value passed 、 Pointer passing .
（2） Strictly speaking , There's only one delivery , Value passed , Pointer passing is also by value , The copy is the address .

7、 The difference between heap and stack ？

C Heap and stack for language memory allocation	The stack grows downward , Allocate function parameters and local variables in the stack , The allocation method is similar to the stack in the data structure . The pile is growing up , Allocate the memory space requested by the programmer in the heap （ Once you forget to release, it will cause memory leakage ）, The allocation method is similar to the linked list in the data structure
Heap and stack of data structures	Stack is an advanced and backward data structure . Heap is a sort tree data structure （ It's usually a binary pile ）, Each node has a value , The value of the root node is minimum or maximum , Often used to implement priority queues , Heap storage is arbitrary .

Two 、 The algorithm part

1、 How to interpret the large and small end storage mode of a system ？

(1) Method 1 ：int Cast type to char , use “[]” Quoting

void checkCpuMode(void)  
{
      
    int c = 0x12345678;  
    char *p = (char *)&c;  
    if(p[0] == 0x12)  
        printf("Big endian.\n");  
    else if(p[0] == 0x78)  
        printf("Little endian.\n");  
    else  
        printf("Uncertain.\n");  
}  

（2） Method 2 ：int * Cast type to char , use “” Quoting

void checkCpuMode(void)  
{
      
    int c = 0x12345678;  
    char *p = (char *)&c;  
    if(*p == 0x12)  
        printf("Big endian.\n");  
    else if(*p == 0x78)  
        printf("Little endian.\n");  
    else  
        printf("Uncertain.\n");  
}  

（3） Method 3 ： contain short Follow char Common body of

void checkCpuMode(void)  
{
      
    union Data  
    {
      
        short a;  
        char b[sizeof(short)];  
    }data;  
    data.a = 0x1234;  
  
    if(data.b[0] == 0x12)  
        printf("Big endian.\n");  
    else if(data.b[0] == 0x34)  
        printf("Little endian.\n");  
    else  
        printf("uncertain.\n");  
}  

Big end small end mode ：

Big end model ： It refers to that the contents of the low byte order of a data are placed at the high address , The contents of the high-order byte memory are placed at the low address .

The small end model ： It refers to that the low byte order content of a data is stored at the low address , The contents of the high byte order are stored at the high address .

Such as ： a number 0x12345678 Store in a 4 In byte space
0x12345678 in ,1234 Belong to high position , If the first byte of the low address is stored 0x12 be Is a high byte Stored in the low address , It's big end mode .
Low address --------------------> High address
0x12 | 0x34 | 0x56 | 0x78

Such as ： a number 0x12345678 Store in a 4 In byte space
0x12345678 in ,1234 Belong to high position , If the first byte of the low address is stored 0x12 Is the high byte Stored in High address , It's small end mode .
Low address --------------------> High address
0x78 | 0x56 | 0x34 | 0x12

Link to the original text ：https://blog.csdn.net/ALakers/article/details/116225089

2、 Verify the palindrome string ： Given a string , Verify that it is a palindrome string , Consider only characters and numeric characters , The case of letters can be ignored

（ Palindrome string is a left-right symmetrical string , Such as "A man, a plan, a canal: Panama"）

Ideas ： Double finger needling , A pointer to the beginning of a string , The other one points to the end of the string , Both hands go to the middle
Move and look for characters and numbers , And turn the letters into lowercase , And then compare if it's the same , If not, return false, If the same, continue to look …… So circular , If you don't return until two pointers meet false, Then return to true.

bool isPalindrome(char * s)  
{
      
    char *left = s, *right = s + strlen(s) - 1;  
  
    if(strlen(s) == 0) return true;  
      
    while(left < right)  
    {
      
        while(!((*left >= 'a' && *left <= 'z') || (*left >= 'A' && *left <= 'Z') || (*left >= '0' && *left <= '9')) && left < right)  //  Find letters or numbers  
            left++;  
        while(!((*right >= 'a' && *right <= 'z') || (*right >= 'A' && *right <= 'Z') || (*right >= '0' && *right <= '9')) && right > left)  //  Find letters or numbers  
            right--;  
          
        if(left < right)  
        {
      
            if((*left >= 'A' && *left <= 'Z'))  //  If capitalized , Turn to lowercase  
                *left = *left + 32;  
            if((*right >= 'A' && *right <= 'Z'))  //  If capitalized , Turn to lowercase  
                *right = *right + 32;  
  
            if(*left == *right)  //  Compare  
            {
      
                left++;  
                right--;  
            }     
            else  
                return false;  
        }  
        else  
            return true;  
    }  
      
    return true;  
}  

3、 Write a program , Function required ： Find out and use 1,2,5 The sum of the three different numbers is 100 The number of combinations of . Such as ：100 individual 1 It's a combination ,5 individual 1 Add 19 individual 5 It's a combination .

（1） The easiest algorithm to think of is the violent solution Ideas ： set up x yes 1 The number of ,y yes 2 The number of ,z yes 5 The number of ,number It's the combination number , be aware 0 <= x <=> 100,0 <= y <= 50,0 <= z <= 20.

void count(void)  
{
      
    int x, y, z, number;  
    number = 0;  
    for (x = 0; x <= 100 / 1; x++)  
    {
      
        for (y = 0; y <= 100 / 2; y++)  
        {
      
            for (z = 0; z <= 100 / 5; z++)  
            {
      
                if (x + 2 * y + 5 * z == 100)  
                number++;  
            }  
        }  
    }  
    printf("%d\t", number);  
}  

（2） The time complexity of the above solution is O(n³), The program is somewhat redundant , It is optimized as follows

Ideas ： Notice the third... In the code above for Circulation is not really necessary , Because when 1 and 2 After the number of is determined , Add a certain number of 5 Can it form 100 That's for sure , It is not necessary to use for Cycle one by one to try , Just calculate it directly , After optimization, the time complexity becomes O(n2).

void count(void)  
{
      
    int x, y, z, number;  
    number = 0;  
    for (x = 0; x <= 100 / 1; x++)   
    {
      
        for (y = 0; y <= 100 / 2; y++)  
        {
      
            if (100 - x - y * 2 >= 0 && (100 - x - y * 2) % 5 == 0) //  Judge whether you can 5 to be divisible by  
            number++;  
        }  
    }  
    printf("%d\t", number);  
} 

4、 Determine if the list has links .

Ideas ： Double finger needling , Define two pointers , At the same time, start from the head node of the linked list , One step at a time , The other pointer takes two steps at a time . If the fast pointer catches up with the slow pointer , Then the linked list is a ring linked list ; If the fast pointer goes to the end of the linked list （fast> == NULL） Didn't catch up with the first pointer , Then the linked list is not a ring linked list .

bool IsLoop(NODE *head)   
{
      
    if (head == NULL)  
        return false;  
  
    NODE *slow = head -> next;  //  At the beginning , The slow pointer starts from the first node 1 Step  
    if (slow == NULL)  
        return false;  
  
    NODE *fast = slow -> next;  //  At the beginning , The fast pointer starts from the first node 2 Step  
    while (fast != NULL && slow != NULL)  //  When a single linked list has no rings , Cycle to the end of the linked list  
    {
      
        if (fast == slow)  //  The fast pointer catches up with the slow pointer  
            return true;  
        slow = slow -> next;  //  Slow pointer one step  
        fast = fast -> next;  //  Let's go two steps  
        if (fast != NULL)  
            fast = fast -> next;  
    }  
    return false;  
}