# Embedded Interview List
<style>
h2.part{color:#000000;}
h3.part{color:#D92424;}
h4.part{color:#FD6F0A;}
h5.part{color:#005BB0;}
h6.part{color:#4400B0;}
</style>
###### tags: `Interview`
## Leet Code Question
* Move Zeroes
> https://www.geeksforgeeks.org/move-zeroes-end-array/
> https://github.com/LinEmsber/Leetcode/tree/master/move_zeroes
* Two Sum
> https://github.com/LinEmsber/Leetcode/tree/master/two_sum
* Fizz Buzz
> https://github.com/LinEmsber/Leetcode/tree/master/fizz_buzz
* Reverse Words in a String
> https://github.com/LinEmsber/Leetcode/tree/master/reverse_words_in_a_string_III
* Missing Number
> Approach #3 Bit Manipulation [Accepted]
> Approach #4 Gauss' Formula [Accepted]
> https://leetcode.com/articles/missing-number/
* Valid Parentheses
> Use stack approach. Push each string element into stack, and then pop them out.
> https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/
* Reverse Linked List
> https://github.com/LinEmsber/Leetcode/tree/master/reverse_linked_list
* Palindrome Permutation
* Reading a paragraph from a file and print the palindromes.
## Append Topic about
## Linked List
#### a.基本:print, push, add, pop, delete
#### b.應用:reverse, sort, merge多個list, 找出是否有環
## Bit Operation
#### a.基本:set, clear, togger, mask, shift, AND, OR, XOR
#### b.應用:有幾個bit為1, reverse, bit swap, Endianess Swap
## C Key word(Storage Class)
#### const
#### static
#### volatile
#### Inline
#### Marco
#### Union V.S Structure
#### Extern
## OS Concept
* multi-thread
* Mutex, semaphore, interrupt, ISR,
priority inversion, deadlock, shared memory, memory leak, memory alignment

## Embedded C
### <font style="color:red" >Storage Class:
* automatic variable, like int i in main function, as follows:
> The variable i is created by function in run-time and store in stack. After leaving main function, this variable is not available.

int main()
{
    int i = 100;
    return 0;
}

* static function
> 單一檔案看到symbol
* static global var
> 單一檔案看到symbol

    因此對global變數加static的用意是希望限制該變數scope在此source file內而不是整個程式

* static local var
> memory 不會隨著stack消失,存在bss或data section
* static local variable without init.
> layout in .bss section
> static int y;
> you need to zeroize this section in the startup code.
* static variable with init.
> layout in .data section
> static int y = 7;
> Reference: https://www.geeksforgeeks.org/memory-layout-of-c-program/

* keyword: volatile
> 給 compiler 看的

    1. 對於非volitile變數, 編譯過後有可能因為優化的關係導致一些不預期結果, 
    因此加入volitile使得每次存取變數都是對此變數的位址存取
    用volatile的變數 你讀寫他都去記憶體
    非volatile你讀寫他會去Cache (CPU的暫存器)

> 1. Ensure the program can obatin the value which is synchronized and without.
> 2. Avoid the aggressive optimization by compiler.
* extern Symbol
> 給 compiler 看的, 告訴compiler 待會消失的symbol會link

    告訴compiler此變數或function已經存在, 另compiler去其他地方找定義

> Tell compiler that this symbol is defined by other files and linker can find it in likage time.
* static/local/inline/global compare
</font>

* <font style="color:green" >Inline vs Marco (Preprcessor)</font>
> macro: pre-processor 展開
> inline: compiler 展開
> Make sure your C standard, gun89 or C99
> https://en.wikipedia.org/wiki/Inline_function#gnu89
> There is one case: use inline keyword for function in C99 stardard, but only compiler inlines this function. And the linker do not know this situation and it leads a link time error: do not find the function symbol.
* malloc vs calloc ->Find a software bug from a code snippet
* <font style="color:red" >detect memory corruption??</font>
> panic
> In non-Os, we could check two symbols, _heap_end (or _end) and stack pointer (It is uaually is the symbol, _stack in linker script). Usually, we use syscall _sbrk to manipulate memory related operations, and implement operations with linked list as the malloc() related functions. If _heap_end (or _end) is larger than _stack, the heap section and stack section are interleaved, i.e. memory corruption.
> https://github.com/bminor/newlib/blob/master/libgloss/riscv/sys_sbrk.c
> https://embeddedartistry.com/blog/2019/04/17/exploring-startup-implementations-newlib-arm/

* Pre-increment and Post-increment in C/C++
> This is not a good code for programer which is qoute from K&R C, page. 97.
> This could cause some side effect.
> [i++ or ++i](https://github.com/LinEmsber/Basic_C_language/blob/master/other/side_effect_01.c)
* <font style="color:red" >how to find sizeof(data type) without using sizeof()</font>
> Use the feature of pointer in C
> https://www.geeksforgeeks.org/how-to-find-size-of-array-in-cc-without-using-sizeof-operator/
* Memory leaks(malloc not free)
* Tool:Valgrind
> With OS:
> valgrind -> user space
> kmemleak -> kernel space
> non-OS/RTOS:
> Record the value of $sp (stack pointer) entering or leaveing the function. The $sp should not be different.
* Segfaults(assign NULL address to the pointer and assign a vale to *ptr
> Access the illieage address
> https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/SyP9k_86l?type=view#%E9%9D%A2%E8%A9%A6%E5%BF%83%E5%BE%97
* multithreading and synchronization
> pc is at 0xabcdxxx -> addr2line / objdump deassamble
> Use mutex or atomic related mechanism to ensure the data which want to manipulate is synchronized.
* caching?????
* ### what is free()? how does free know how much memory to de-allocate?
> free() sbkr / bkr 回原點
> The _free function is quite straightforward, given a pointer that was previously “malloced” to the user, we must find its metadata (by using the BLOCK_HEADER macro) and add it to our free linked list
> https://medium.com/@andrestc/implementing-malloc-and-free-ba7e7704a473
* Union Vs Structure
> Union 各 member 共用 memory
> The size of structure is the total of all elements.
> The size of union is based on the largest element.
* What are the applications of Unions? and problem-related to Unions.
> Specfiy unserial number of element
> https://github.com/LinEmsber/Programming_Technique_in_C/blob/master/union_struct_01.c
> Print floating value's mantisaa and exponent
> https://stackoverflow.com/questions/15685181/how-to-get-the-sign-mantissa-and-exponent-of-a-floating-point-number
* <font style="color:red" >Implement your own memcp</font>

for (i to size)
    dest[i] = src[i]

> The basic sprition is as follow

while (len0--)
{
  *dst++ = *src++;
}

> Reference:
> [newlib/newlib/libc/string/memcpy.c](https://github.com/bminor/newlib/blob/d8ccbcdaccff12ca9509358d31114515acd20590/newlib/libc/string/memcpy.c)
> [armv7m assembly](https://github.com/bminor/newlib/blob/6497fdfaf41d47e835fdefc78ecb0a934875d7cf/newlib/libc/machine/arm/strcmp-armv7m.S)

> newlib's riscv optimizes memcpy() with unroll-loop to reduce branch times. But we needs to algin the size of data before using this optimized code

  long *la = (long *)a;
  const long *lb = (const long *)b;
  long *lend = (long *)((uintptr_t)end & ~msk);

  if (unlikely (la < (lend - 8)))
    {
      while (la < (lend - 8))
	{
	  long b0 = *lb++;
	  long b1 = *lb++;
	  long b2 = *lb++;
	  long b3 = *lb++;
	  long b4 = *lb++;
	  long b5 = *lb++;
	  long b6 = *lb++;
	  long b7 = *lb++;
	  long b8 = *lb++;
	  *la++ = b0;
	  *la++ = b1;
	  *la++ = b2;
	  *la++ = b3;
	  *la++ = b4;
	  *la++ = b5;
	  *la++ = b6;
	  *la++ = b7;
	  *la++ = b8;
	}
    }

> [newlib/newlib/libc/machine/riscv/memcpy.c](https://github.com/bminor/newlib/blob/6497fdfaf41d47e835fdefc78ecb0a934875d7cf/newlib/libc/machine/riscv/memcpy.c)

* [Print left view of binary search tree]()
* <font style="color:red" >user level threads and kernel threads</font>
* user space UID?
* Memory layout of the C program, Heap & stack allocation
## Algorithm
* interested in data storage and retrieval; hash tables, binary search trees
* What is the computational complexity of various types of search (i.e. Big Oh analysis for array search, binary search, etc.)
* <font style="color:red" >stable & un-stable sorting methods </font>
* <font style="color:green" >Explain and describe how binary search tree work based on your own previous works</font>
* Binary Search
## Array
* Given a list from 1 to 100, name all the different ways you can determine if there are duplicates.
> Use XOR, XOR all of elements to find the element which is duplicated
* swap the values of two pointers without a temp variable
> XOR swap
> https://en.wikipedia.org/wiki/XOR_swap_algorithm
> https://github.com/LinEmsber/Programming_Technique_in_C/blob/master/Bitwise/swap/swap_02.c
* find duplicates in an array
> XOR all element
> [Leetcode No.136](https://leetcode.com/problems/single-number/discuss/42997/my-on-solution-using-xor/41527)
## String manipulation
* Write a C Program to reverse the words in a sentence
* ### if a malloc to guarantee that it was 32-byte aligned
* Big/Little endian conversion
* Write a C program to encode bits in a 32-bit number such that, most significant 16 bits should be reversed but lower 16 bits should be untouched. Then asked to generalize this to any number of bits.
* write a function that determines if a given variable is a power of 2 or not
* Bit manipulation questions
* detect pattern of ones in a 32 bit integer
* write masks to insert pattern of ones in a 32 bit integer
*
## Linked List
* How would you implement a circular buffer?
> Implement a cyclic linked list
* find a loop in a linked list->two ptr(slow,fast)
> 1. Use two pointers wiht the faster and slower speed to traverse the list.
> 2. If two pointers point the same node, then there is a loop.

int detectAndRemoveLoop(struct Node* list) 
{ 
    struct Node *slow_p = list, *fast_p = list; 
  
    while (slow_p && fast_p && fast_p->next) { 
        slow_p = slow_p->next; 
        fast_p = fast_p->next->next; 
  
        /* If slow_p and fast_p meet at some point then there 
           is a loop */
        if (slow_p == fast_p) { 
            removeLoop(slow_p, list); 
  
            /* Return 1 to indicate that loop is found */
            return 1; 
        } 
    } 
  
    /* Return 0 to indeciate that ther is no loop*/
    return 0; 
} 

* Linked list manipulation
* create a custom malloc and free function using linked lists
> 1. Use linked list to record nodes which includes the start, end address and the length of memory.
> 2. It needs system call _sbrk()
> 3. Use a symbol to record address of end of heap section, _end (or _heap_ned) in liker script.
* How to detect and remove the loop from the Linked List.
> 1. Detect:Fast && Slow Pointer
> 2. Remove:
* <font style="color:red" >Implement a queue/fifo with push/pop functionality using linked lists</font>
* <font style="color:green" >create a custom malloc and free function using linked lists</font>
* <font style="color:red" >Write code in C that would hash a string and deal with collision resolution by implementing a linked list. Would this code be thread safe? </font>
## Operation Syatem and Computer Architecture
* Preocess VS Thraed, How to handle thread conflicts?
> process vs thread -> 共用stack
> thread conflicts -> lock

> Process:
* the unique memory page, like a container with only one thread, take more time to context switch, more effor to communicate with other process (IPC)
> thread:
* All the threads running within a process share the same address space, file descriptors, stack and other process related attributes.
* lightweight process, less time to context swith, efficient to communicate with other thread
> Reference:
> [Difference between Process and Thread](https://www.geeksforgeeks.org/difference-between-process-and-thread/)
> [Introduction to PThreads and
Basic Synchronization, page.5](http://www.ittc.ku.edu/~heechul/courses/eecs678/F16/labs/lab6/PThreadsIntro.pdf)

* RTOS vs OS
> Rtos 保證某個task 最少要在多久內response, 作法：isr加入排程
* How are interrupts handled in RTOS?
> 加入排程
> https://www.youtube.com/watch?v=aWlQYllBZDs
> https://www.freertos.org/implementation/a00005.html
> https://www.freertos.org/implementation/a00006.html
* Inversion priority and deadlocks.
> The shared resource which is shared with the higher thread is locked by the lower thread. When the processor execute the lower thread, but the middle thread preempt this lower thread. In that situation, the execution order is the middle thread > the lower thread > the higher thread, i.e. the higher thread is the last one to be executed.
> Solution: Priority Inheritance.
> In Priority Inheritance, when L is in critical section, L inherits priority of H at the time when H starts pending for critical section. By doing so, M doesn’t interrupt L and H doesn’t wait for M to finish.
> [Priority Inversion](https://www.geeksforgeeks.org/difference-between-process-and-thread/)
> [Difference between Priority Inversion and Priority Inheritance](https://www.geeksforgeeks.org/difference-between-priority-inversion-and-priority-inheritance/)
> [Jsver's Priority Inversion on Mars](http://wiki.csie.ncku.edu.tw/embedded/priority-inversion-on-Mars.pdf)
* The most difficult question for me ended up being a multithreading question, mostly because it was the subject least familiar to me.
* How to code kernel accessible by multi-tasks without wait.
* Scheduling
* Deadlocks
>
> [Dining philosophers problem](https://en.wikipedia.org/wiki/Dining_philosophers_problem)
* critical section
* mutex and semaphore
> semaphore: refer to producer-consumer problem
> mutex is a binary semaphore, i.e. only one key
> We have to be careful about: undefined behavior
> We can use PTHREAD_MUTEX_ERRORCHECK
> [Mutex and Semaphore](https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/Skh9Z2DpX?type=view)
* Describe inverse priority in RTOS
* Memory management
* What is atomic programming/non-locking operation?
> 全有全無
> 拿的到就可以拿,拿不到就全等

> The operation which is cannot be interrupted.
> Use specifc instruction to ensure the data is synchronized.
> x86
* [newlib/newlib/libc/sys/linux/machine/i386/atomic.h](https://github.com/eblot/newlib/blob/master/newlib/libc/sys/linux/machine/i386/atomic.h)
* https://stackoverflow.com/questions/8891067/what-does-the-lock-instruction-mean-in-x86-assembly
* [A simple atomic operation with GCC builtin function in C]
> arm
* ldxr/stxr/dmd
* spinlock, write spinlock as 0x1 (stxr), then use dmd, ensure lock is ovbserved.
* spinunlock, use dmd before read lock (ldxr), ensure lock is updated.
> [Prerequisite knowledge for shared memory concurrency, RISC-V, atomic, page.16](https://www.slideshare.net/vh21/pre-knowledge-for-shared-memory-concurrency)

* C- storage class, compiler.
* RTOS- Mutex and semaphore.
* Multi threading.
* Assembly Language- Memory Write and Read implementation using Assembly.
* How multiply is implemented?
* Different System calls and why do we use then
> trap to kernel space (swi)
* Difference between Kernel and Operating System
* Why do we use Cache Memory?
* scheduling
* context switching
* memory,memory maping
* Cache Coherence Protocol and when do we use them
* [What are Static and Dynamic Libraries](https://www.geeksforgeeks.org/static-vs-dynamic-libraries/)
* scheduling, context switching, memory,
* virtual memory, caches, priority inversion, reentrancy, semaphore vs mutex, spinlocks
* Interrupts, Timer, Communication protocols, like SPI, I2c
* How does OS detects stack overflow
* Describe inheritance,watchdog,Multithreading
* Inheritance: Inheritance allows us to define a class in terms if another class, which makes it easier to create and maintain an application. Inheritance allows to reuse the code functionally and fast implementation time.
* Watchdog timer: WDT is a piece of hardware that can be used to automatically detect software anomalies and reset the processor if any occur.
* Multithreading : Multithreading is the ability of a program to manage its use by more than one user at a time and to even manage multiple requests by the same user with out having to have multiple copies of the programming running in the computer.
* virtual memory, caches, priority inversion, reentrancy, semaphore vs mutex, spinlocks

### spinlock

>不允許發生 preempt
不允許發生 context switch
不能使用recursively
不能用於interrupt handler, 會造成鎖兩次形成deadlock
Linux上有實作 IRQ-safe Spin Locks, 此部份會disable all interrupts在local CPU
spin 有釘住的意思, 他就是要將process 或 thread “釘” 在一個處理器上讓他無法被preempt或是migrate到其他處理器
在RTOS中, critical section塞了一些preemption point檢查是否有更高優先權的事要做, 所以critical section內也是可以preempt的

### semaphore

>類似計數器概念, 限制數量存取某一段資源
>比較特別的是可以a鎖b解
#### binary semaphore
>沒有owner的概念, 任何的thread都可能lock(0)/unlock(1)
### mutex

>指允許同一時間只有一個process可以存取某一塊資料 (有保護的功能), 只有鎖住的process才可以解鎖 (有owner概念)
>priority inversion for mutex
假設A,B,C 三個process 優先權 A>B>C, C握有lock，A在等lock造成優先權高的A等待C的情況，若此時B變為可執行的，則B會preempt process C，造成process A需要等待更久的時間，這種情況稱為unbounded priority inversion。
發生這種情況是用priority inheritance protocol來解決，即暫時提高C的priority繼承A的priority，這樣就能阻止process B preempt，等C執行完時再放棄繼承priority，回復原本的priority。

### Virtual Memory
>虛擬記憶體是電腦系統記憶體管理的一種技術。它使得應用程式認為它擁有連續的可用的記憶體（一個連續完整的位址空間），而實際上，它通常是被分隔成多個實體記憶體碎片，還有部分暫時儲存在外部磁碟記憶體上，在需要時進行資料交換。與沒有使用虛擬記憶體技術的系統相比，使用這種技術的系統使得大型程式的編寫變得更容易，對真正的實體記憶體（例如RAM）的使用也更有效率。

#### what’s the different between Virtual memory & Physical memory

分頁表(page table)把Virtual Memory分配到實體
why?

記憶體不夠大？
希望記憶體是連續的而不是零碎的

* What's deadlock? When you bring up the OS, what's happen?
## Internet
* TCP/UDP区别以及更适合使用UDP的网络场景
> TCP 建立連線, 確保封包送達對方
> UDP 不建立連線, 射後不理
* TCP三次握手
* SYNC
* SYNC,ACK
* ACK
* Establishment
* IP,DHCP

## Domain Knowledge
* How would you design an elevator system.Follow up, is there any problems (from a embedded system point of view) you should prevent and how will you prevent it in your design.
* find the degrees between the minute hand and hour hand when a clock is at 3:15
* What is the difference between programming in JAVA and C
* Fibonnaci with recursion and its time complexity derivation
* How would you go about transferring files from one 1tb server to another with only a 1.4mb floppy disk to transfer files?
* * What is the difference between mutex and semaphore?
## Reference Interview
* [3 round reference](https://hackmd.io/9dG1xXtETvG2a1KB-7RIcw?view)
* [Phone Interview](https://hackmd.io/nvIlIRclRvq4-xEmpWCZjA?view)
* [PTT Oversea](https://www.ptt.cc/bbs/Oversea_Job/M.1597533013.A.523.html)