Quick Sort

This quick sort implementation comes from ‘Programming Pearls’ by Jon Bentley. The basic idea of quick sort is ‘divided and conquer’.

  1. Choose the pivot
  2. Partitioning the array to have half the elements are above the pivot and half the elements are below it.
  3. Repeat for each partition till partitions have one element

The code is

void qsort(l, u)
  if l >= u then
    /* at most one element, do nothing */
    return
  /* goal: partition array around a particular value(pivot),
     which is eventually placed in its correct position p
  */
  qsort(l, p-1)
  qsort(p+1, u)

In quicksort we’ll partition the array x[l..u] around the value t=x[l]. In the below pseudo code, m-th element indicates the right most element which is less than pivot value. It starts from l+1 because l-th element is the pivot. When we find the i-th element which has the value less than pivot, we swap it with ++m-th element which is left most element greater or equal to pivot.

void qsort(l, u)
  if (l >= u)
    return
  m = l
  for i = [l+1, u]
    /* invariant: x[l+1..m]    < x[i] &&
                  x[m+1..i-1] >= x[l] */
    if(x[i] < x[l])
      swap(++m, i)
  swap(l, m)
  /* x[l..m-1] < x[m] <= x[m+1..u] */
  qsort(l, m-1)
  qsort(m+1, u)

When iterating in for loop the partitions are depicted as

image

m indicates the right most element smaller than pivot. When the loop terminates we have

image

We then swap x[l] with x[m] to give

image

Lets say we have the input array x = {12, 3, 20, 8, 19, 21, 7}. After terminating the for loop, x will be x = {7, 3, 8, 12, 19, 21, 20}.

x[l]=12 m=0
i=1, 3<12 ? yes, m=1, swap(1,1)
i=2, 20<12 ? no
i=3, 8<12 ? yes, m=2, swap(2,3), x={12,3,8,20,19,21,7}
i=4, 19<12 ? no
i=5, 21<12 ? no
i=6, 7<12 ? yes, m=3, swap(3,6), x={12,3,8,7,19,21,20}
swap(0,3), x={7,3,8,12,19,21,20}

The quicksort runs in O(n log n) time and O(log n) stack space on the average.


[1] Programming Pearls 2nd ed, Jon Bentley
[2] https://stackoverflow.com/questions/10049579/jon-bentleys-beautiful-quicksort-how-does-it-even-work

Advertisements
Posted in Algorithms, Technical Interview | Tagged , | Leave a comment

Prince of Persia

Today I became to know the source code of old game ‘Prince of Persia’ is available in github. Here is the address. It’s written in 6502 assembly language on the Apple II. I’m pretty sure no one who reads it has the Apple II to play this game.

When I played this game for the first time, it ran on PC XT. Probably it was around 1989 or 1990. I could not afford to buy new PC. I bought used XT replication from my friend, which came with Hercules Graphics Card. The Hercules card also was cheap replication. The friend of mine already had new one having 386 DX. Back then in Sewoon shopping mall (세운상가), Seoul, South Korea, there were many small stores that sells replicates of Apple II, PCs, graphic cards, games and DOS. I heard there were nothing they was not able to replicate. At that time most of us didn’t know what the ‘copyright’ means and even didn’t hear the word.

Prince of Persia (1989) MS-DOC PC Game Play

Some of stores got bigger and became big company. The TriGem Computer was one of them. In early 1990s, it sold the computers more than Samsung Electronics.

Posted in Games | Tagged | Leave a comment

What’s your favorite, C or C++? Which one is better? Especially in embedded system. Why?

Since moving to firmware development three years back, I’ve been using only C. The reason most people prefer C to C++ in programming embedded system is, IMHO, there are not much benefits we can earn from C++. Even worse, by writing firmware with C++, we have more chances to make mistakes and culprits, that end up with bigger excitable(ROM or RAM) size and low performance. This is mostly the result of misuse of C++, not because C++ itself is bad programming language.

C++ is superset of C. C++ offers new features which extends C and make better C. Bjarne Stroustrup who is father of C++ says in his book, ‘The C++ Programming Language’: The C++ programming language is designed to

  • be a better C
  • support data abstraction
  • support object-oriented programming

In many cases it’s not impossible to write C++ code faster than C with even smaller excitable size.[2] But to achieve this goal, we should be well aware of all pros and cons of C++ features.

These are additional features which C++ provides on top of C.

  • Classes
  • Templates
  • Streams
  • Exception handling
  • C++ Standard Library (STL)

Many small embedded system is designed to monitor and control HW. We can make Arduino to read the temperature using ADC converter and display it to 7 segment LED. We may consider to design the software to take advantage of C++, such as creating CTemp class as well as CDisaply to abstract 7 segment LED. We would expect to extend CDisplay to support HDMI or VGA in some day. Well, this may be OK if we have enough memory. Arduino Uno has only 2 KB SRAM and 32 KB flash memory with 16 MHz clock speed.[5] It even doesn’t have OS. Function is getting called in ISR context. We probably don’t want to design the software this way for Arduino Uno. Blindly calling cout instead of printf would increase excitable size and give negative impact on performance.

In summary, C is probably good enough or better for embedded system as well as program for bigger system in case we don’t need of C++ features. If we have enough memory and clear reason to need C++ features, there’s no reason not to go with C++.

[1]The C++ Programming Language, 2nd Ed, Bjarne Stroustrup
[2]http://unthought.net/c++/c_vs_c++.html
[3]Object-orientation in C – http://stackoverflow.com/questions/415452/object-orientation-in-c
[4]When to use C over C++, and C++ over C – http://programmers.stackexchange.com/questions/113295/when-to-use-c-over-c-and-c-over-c
[5]Arduino Uno – https://www.arduino.cc/en/Main/ArduinoBoardUno

Posted in C, C++, Technical Interview | Tagged | Leave a comment

Book: “Teach what you know” by Steve Trautman

This book is about peer mentoring, especially being applicable in software team. The author says he wrote this book based on his experience as a localization program manager in Microsoft in 1990.

  • He defines a several learning styles, that he got an idea from David Kolb’s ‘Experiential Learning: Experience as the Source of Learning and Development’. They are “Why?, “What?”, “How does it work?”  and “What if?” learners. He proposed the different teaching strategy for each learning style. Looks like I’m falling into “How does it work?” learner category. Smile
  • The book includes some templates and worksheet which are handy and useful for everyday mentoring. For example, the training plan template and problem-solving question worksheet.
  • I like the problem-solving question worksheet. This worksheet has self check list:
    • __ How much time do you need?
    • __ Provide a concise description of the problem
    • __ Did the process or procedure ever work?
    • __ What would you like from me (advice, sounding board, support)?
    • __ What did you expect to happen?
    • __ What happened?
    • __ What have you tried to do to solve the problem?
    • __ Who else is working on the problem?
    • __ How big is the crisis (urgency, impact)?
    • __ When does the problem need a resolution?
  • There are many useful tips for effective communication in time saving manner

Overall I like the book. Most of idea in the book aren’t like new to me, but following those small suggestions in the book definitely can improve communication skills in team and save ramp-up time.

Posted in Book | Tagged | Leave a comment

Where do you see yourself in 3-5 years?

Who can tell what will happen in the next year, what alone the next 3 or 5? Then why is it still an interview question?

When interviewers ask you this, they aren’t looking for a definitive reply. Nothing is certain in today’s job market. The reason that a hiring manager asks the question is usually:

  1. Is the candidate actually seeking this job?
  2. Does the candidate have plan on sticking around for long?
  3. What is the candidate’s level of ambition? They want to know if you’ve thought about your professional growth or if you do a plan.
  4. What does the candidate expect in terms of growth, potential advancement and personal challenge?

We need to be honest but show them to balance of focus, ambition, challenge, responsibility and future plans that are aligned to the company.

[references]

 

Posted in Behavior questions | Tagged | 3 Comments

UART (Serial Port)

It sounds like odd. We are using this old technology in 2016. There was the communication card for Apple II in 1978 . RS-232, a standard for serial communication transformation of data was introduced in 1962.

 

Apple Computer Apple Communication Card for the Apple II

The speed of serial port(UART: Universal asynchronous receiver/transmitter) is around a few hundreds Kbits to a few Mbits per second today. There are many fast serial communication devices out there, such as USB 3.0 which can theoretically transfer data at 480 Mbits per second.

But there are still some applications which do not necessarily require such a high speed, for example debug terminal and to control machine like CNC mill. Both HW and SW for serial port is simple, chip and easy to implement/debug.

Long time back (in 1998) I had engaged in a project where I designed and implemented a data link layer on top of UART. That was based on HDLC. I’d recommend to check out Eli Bendersky’s ‘Framing in serial communications’ for anyone wants to quickly catch the idea. Physical layer of UART communication has ability to detect error using parity check, which has limitation. We can add CRC at each frame to detect transmission error if we worry about it.

I got involved in design/implement a similar data link layer on top of UART interface between two embedded processors a year back. This old technology from the ancient is still alive!

Posted in Embedded | Tagged , | Leave a comment

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Difficulty: Easy

The easy solution would be to simply compare each element to the others. It takes O(n2) steps with two loops. Larger the array size leads exponentially increasing amounts of time.

For completing it in O(n) steps we can think of allocating the extra array in which we mark at the position of the integer whenever we find it in the given array. Let’s say we have the mask array M. When we run into ‘324’ in the given array, we mark 1 in M[325]. In this question, because there’s no range limitation of integers, we would need to allocate the extra array with size 232 = 4G + 1. It’s huge and it most likely can fail with limited memory constraints such as embedded systems. We could use the bit mask to reduce the size of mask array. With a 32-bit mask we can mask the integers with range of 0 – 31. To cover whole 32-bit integer range we need around 2G memory (2G and one more bit). It’s still huge.

How can we reduce the memory footprint? At 3rd we can think of using a hash table. This consumes the smallest memory footprint among the 3 approaches. This takes more computing time than bit mask approach. Smaller hash table leads more conflict, meaning taking longer computing time to resolve.

struct node {
    int num;
    struct node *next;
};

#define NHASH 237
#define MULT 31
struct node *bin[NHASH] = { 0 };

unsigned int hash( unsigned int num ) {
    unsigned int h = MULT * num + num;
    return h % NHASH;
}

bool containsDuplicate(int* nums, int numsSize) {
    int i, h;
    struct node *p;
    
    for ( i = 0; i < NHASH; i++ ) {
        if ( bin[i] != NULL ) free( bin[i] );
        bin[i] = NULL;
    }
    
    while ( numsSize-- ) {
        h = hash( *nums );
        printf("\n%d, %d", *nums, h);
        for ( p = bin[h]; p != NULL; p = p->next ) {
            if ( p->num == *nums )
                return true;
        }
        p = malloc( sizeof(struct node) );
        p->num = *nums++;
        p->next = bin[h];
        bin[h] = p;
    };
    
    return false;
}

 

[references]

  1. Interview question – https://leetcode.com/problems/contains-duplicate/
  2. Hash tables – p162, Programming Pearls 2nd ed, Jon Bentley
Posted in Algorithms, C | Tagged , , | Leave a comment

Merged two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists

Difficulty: Easy

image

There may be one more ways to solve this problem. We define the function which return the merged list as:

struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B)

The simple solution is using recursion. When we compare two nodes from A and B, we need to put the node having smaller value into the merged list. So we select node with data 2 in A here, because 2 < 3. The next selected node will be linked to A->next. The code which implements the idea using recursion would look like:

if ( A->val < B->val ) A->next = mergeTwoLists( A->next, B )

It’s always important to make sure to check NULL condition. When either of linked list reaches to its end (NULL), we just put the rest of the nodes in the other linked list to merged list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B) {
    if ( A == NULL ) return B;
    if ( B == NULL ) return A;
    
    if ( A->val < B->val ) {
        A->next = mergeTwoLists( A->next, B );
        return A;
    } else {
        B->next = mergeTwoLists( A, B->next );
        return B;
    }
}

 

The other way is not using recursion and it’s a bit complicating. In recursive solution, we don’t need to allocate memory to store the current state in stack. When recursively calling the next mergeTwoLists, the current states are implicitly saved in the stack. The stack stores pointer of head and current node. With non-reclusive solution we need to explicitly allocates at least two more variables, head and cur to save head and current node pointer respectively.

 image

We first determine the head by comparing heads in A and B. Because 2 < 3, head of A is selected for head of merged list. Then update A with A->next. To trace tail of the merged list, we use cur. At the next step, compare A (now A has 5) and B (3). Because 3 < 5, the node B with data 3 is assigned to cur->next. We update cur = cur->next and B = B->next and continue to loop with the next node pair.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* A, struct ListNode* B) {
    struct ListNode* head = NULL, * cur;
    
    if ( A == NULL ) return B;
    if ( B == NULL ) return A;
    
    while ( A != NULL && B != NULL ) {
        if ( A->val < B->val ) {
            if ( head == NULL ) {
                cur = head = A;
                A = A->next;
                continue;
            }
            cur->next = A;
            A = A->next;
        } else {
            if ( head == NULL ) {
                cur = head = B;
                B = B->next;
                continue;
            }
            cur->next = B;
            B = B->next;
        }
        cur = cur->next;
    }

    if ( A != NULL ) cur->next = A;
    if ( B != NULL ) cur->next = B;
    
    return head;
}

 

-Question from: https://leetcode.com/problems/merge-two-sorted-lists/

Posted in Algorithms, Technical Interview | Tagged , , | Leave a comment

Merge Sorted Array

Given two sorted integer array A and B, merge B into A as one sorted array.

Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Difficulty: Easy

The basic idea is to fill up the array A from the end (from k = m + n – 1) to avoid memmove or memcpy operations. We walk through each array one by one from the end (m –1 and n – 1) as well and copy greater one to k position. Then moving to the next element.

A[k–] = A[i] > B[j] ? A[i–] : B[j–];

image

When we reach to j= 0 condition, it means that we ends up populating every empty space in A. j != 0 means that the rest of elements in B is less or equal than the smallest element in A, i.e. A[0]. We should copy the rest of elements in B to A.

while( j >= 0 ) A[k–] = B[j–];

The final code looks like this:

void merge(int* A, int m, int* B, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;
    
    while ( i >= 0 && j >= 0 ) {
        A[k--] = A[i] > B[j] ? A[i--] : B[j--]; 
    }
    
    while( j >= 0 ) A[k--] = B[j--];
}

 

-The question is from https://leetcode.com/problems/merge-sorted-array/

Posted in Algorithms, Technical Interview | Tagged , , | Leave a comment

Singleton Pattern

어제 ‘Programming game AI by example’을 읽던 중 Singleton이란 개념을 처음(아마 한 8년 전 쯤에는 알았을지도.) 접했다.

If singletons are a new concept to you, and you decide to search the internet for further information, you will discover they fuel many a good argument about the design of object-oriented software. Oh yes, programmers love to argue this stuff, nothing stokes a dispute better than the discussion of global variables or object that masquerade as globals, such as singltons. My own stance on the matter is to use them wherever I think they provide a convenience and, in my opinion, do not compromise the design. I recommend you read the arguments for an against though, and come to your own conclusions. A good staring place is here: http://c2.com/cgi/wiki?SingletonPattern

– p59, Programming game AI by design

Head first design patterns’에서는 Singleton을 이렇게 정의하고 있다.

The Singleton Pattern ensures a class has only one instance, and provides a global point of access to it.

– p177 Head first design patterns

다시 ‘Programming game AI by example’로 돌아오면

There are many ways of implementing a singleton. I prefer to use a static method, Instance. that returns a pointer to a static instance of the class. Here’s an example:

/* ------------------ MyClass.h -------------------- */
#ifndef MY_SINGLETON
#define MY_SINGLETON
class MyClass
{
private:

  // member data
  int m_iNum;

  //constructor is private
  MyClass(){}

  //copy ctor and assignment should be private
  MyClass(const MyClass &);
  MyClass& operator=(const MyClass &);

public:

  //strictly speaking, the destructor of a singleton should be private but some
  //compilers have problems with this so I’ve left them as public in all the
  //examples in this book
  ~MyClass();

  //methods
  int GetVal()const{return m_iNum;}
  static MyClass* Instance();
};
#endif

/* -------------------- MyClass.cpp ------------------- */
//this must reside in the cpp file; otherwise, an instance will be created
//for every file in which the header is included
MyClass* MyClass::Instance()
{
  static MyClass instance;
  return &instance;
}

– p59, Programming Game AI by example.

static 키워드를 사용하는 간단한 방법이다. 단점이라면 한번 MyClass::Instance()로 인스턴스를 만들면 그걸 메모리로 부터 제거할 수 있는 방법이 없어 보인다.

Posted in C++ | Tagged , , | 3 Comments