Sunday, August 20, 2017

Are US tech companies so picky nowadays?

For last few months I have been looking for technical job in my area of expertise and experience.  I know, it is harder to find jobs in low-level or embedded system compared to application software, but I never realize even when I got some interviews, there are so picky.  A small mistake (not necessarily to judge that I will not be able to do the job), that's it.  You're done.  Next applicant, please.

I am still endeavoring to land my future job. Meanwhile, I am brushing my skills and learn some new stuff.  For example, I now know there is an opensource doing dataplane packet processing.  I also now relearning  Linux kernel and driver, Bluetooth and Wifi.

Thursday, August 17, 2017

Some videos of My Embedded projects I have done

Couple of projects done during my spare time:

ATMega32 interfacing to MAX7219 7seg via SPI 

PIC18F9520 doing ultrasonic ranging 

I wish I made video for the PIC-based IoT sensors I made (part of Computer Engineering project in my master program; It was able to push temperatur and humidty data to 'remote' server periodically, which then display it on the web)

Thursday, August 10, 2017

FizzBuzz Analysis

Recently I was asked this kind of question. As I was told not to worry too much about it and I got many other questions to answer within short time, I did not pay attention to much on it and just scribbled it on a piece of paper, no time to mentally test the algorithm.

At home I realized I did not complete the answer (blame that to the recruiter).  Anyway, the fizz buzz interview question is to ask interviewee to write a code to print number from 1 to 100, but for every multiplication of 3 to print string "FIZZ" (or something), for every multiplication of 5 to print string "BUZZ", and for every multiplication of 3 and 5 (which is another way to say multiplication of 15) to print "FIZZBUZZ".

Here's my working code in C++:

#include <iostream>

using namespace std;

const static char *s1 = "FIZZ";
const static char *s2 = "BUZZ";

int main()
{
    for(int i=1; i<=100; i++)
    {
        if (i% 3*5==0)
        {
            cout << s1 << s2 << endl;
            continue;
        }
        if (i % 3 == 0)
        {
            cout << s1 << endl;
            continue;
        }
        if (i % 5 == 0)
        {
            cout << s2 << endl;
            continue;
        }

        cout << i << endl;
    }
}

No matter whay you do, the optimal solution is always O(n) (unless you're crazy enough to just print manually without loop, such as cout << "1\n2\FIZZ\n4\BUZZ\n...|").

Some silly optimization can be performed in printing the string, though.

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
    for(int i=1; i<=100; i++)
    {
        if (i%15==0)
        {
            cout << s << endl;
            continue;
        }
        if (i % 3 == 0)
        {
            cout << s.substr(0,3) << endl;
            continue;
        }
        if (i % 5 == 0)
        {
            cout << s.substr(4) << endl;
            continue;
        }

        cout << i << endl;
    }
}

Another thought is to eliminate mod 15.  For example:

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
    int m;
    for(int i=1; i<=100; i++)
    {
        m = 0;
        if (i%3==0)
        {
            cout << s.substr(0,3);
            m++;
        }
        if (i % 5 == 0)
        {
            cout << s.substr(4);
            m++;
        }
        if (m > 0)
            cout << endl;
        else
            cout << i << endl;
    }
}

When I tested it (upper limit set to 1000 and perform "time <program>", the last algorithm shows some speedup.

The last few lines can be optimized to be:

        if (m == 0)
            cout << i;
        cout << endl;

Another tiny optimization is instead of doing post increment (i++), we do preincrement (++i).  This saves tiny bit (no copy to extra variable internally).

Last, we can write it down in Assembly if we want.  The following is suitable for embedded device:

main:
leal 4(%esp), %ecx
andl    $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %edi
pushl %esi
pushl %ebx
pushl %ecx

subl $8, %esp
movl $1, %ebx         ; EBX=1
movl $3, %esi         ; ESI=3
movl $5, %edi         ; EDI=5
jmp CHECK_FIZZ

FOR_I_NEXT:
movl %ebx, %eax       ; eax stores current value of i
cltd
idivl %edi             ; i / 5, result in eax and mod in edx
testl %edx, %edx       ; i % 5
jne PRINT_I          ; i % 5 != 0 -> jump to PRINT_I

CHECK_FUZZ:
subl $8, %esp
pushl stdout
pushl 'f'
call _IO_putc
popl %edx
popl %ecx
pushl stdout
pushl 'i'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc
addl $16, %esp

PRINT_CR:
subl   $8, %esp
pushl stdout
pushl '\n'
call _IO_putc
incl %ebx
addl $16, %esp
cmpl $101, %ebx           ; i == 101 ?
je MAIN_EXIT            ; if (i ==101) goto MAIN_EXIT

CHECK_FIZZ:
movl %ebx, %eax
cltd
idivl %esi
testl %edx, %edx           ; i % 3 == 0
jne FOR_I_NEXT
subl $8, %esp             ; if (i%3==0):
pushl stdout
pushl 'b'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'u'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
movl %ebx, %eax
cltd
idivl %edi
addl $16, %esp
testl %edx, %edx
jne PRINT_CR
jmp CHECK_FUZZ

PRINT_I:
pushl %eax
pushl %ebx
pushl $.LC0
pushl $1
call __printf_chk
addl $16, %esp
jmp PRINT_CR
MAIN_EXIT:
xorl   %eax, %eax
leal -16(%ebp), %esp
popl %ecx
popl %ebx
popl %esi
popl %edi
popl %ebp
leal -4(%ecx), %esp
ret