Mutex vs. Semaphore

Mutex is a key to a toilet. One person can have the key - occupy the toilet. When finished, the person gives (frees) the key to the next person in queue.

A mutex is really a semaphore with value 1.

Semaphore is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count is set to 4 at beginning, then the count decrease as people are coming in, etc.

A mutex is not a binary semaphore

A mutex is locking mechanism used to synchronize access to a resource. Only one task can acquire the mutex.

It means there will be ownership associated with mutex, and only the owner can release the lock.

Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal).

For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.

Question

link

Find Top k smallest element in an array.

Analysis

There’re 2 solutions.

First solution, use a max-heap. O(nlgk) time complexity.

Second solution is called quickselect, a type of selection algorithm that’s based on quicksort. It’s averaging O(n) time, but O(n²) if pivot selection is poor. The code is posted below. There’s also a similar iterative solution.

To further optimize this, we can change the pivot selection method by dividing into k group and find median of each. This is called Median of medians algorithm. The worst case is O(n) time. And this is the best solution for “Top k” questions.

Why quickselect is O(n) time?

It’s a very good question to ask. Why O(n)?

Well think about it. Let’s assume you always find the pivot that makes you eliminate half of the input.

The first run, you would read n elements. Second time you read half of n, and third time, quarter of n. In the end, you read n + n/2 + n/4 + … = 2n times.

Compared to the Heap method to find top K, quick select has its advantage. Heap top K take O(n lgK) time. So when K is pretty large, quick select might be an better solution.

Code

quickselect

public static void quickSelect1(int[] list, int k) {
    selectHelper1(list, 0, list.length - 1, k);
}

public static void selectHelper1(int[] list, int left, int right, int k) {
    int pivotIndex = partition(list, left, right);
    if (pivotIndex == k) {
        return;
    } else if (k < pivotIndex) {
        selectHelper1(list, left, pivotIndex - 1, k);
    } else {
        selectHelper1(list, pivotIndex + 1, right, k);
    }
}

private static int partition(int[] list, int left, int right) {
    int pivot = left + (right - left) / 2;
    swap(list, right, pivot);
    for (int i = left; i < right; i++) {
        if (list[i] < list[right]) {
            swap(list, i, left);
            left++;
        }
    }
    swap(list, left, right);
    return left;
}

quickselect, iteratively

public static int quickSelect2(int[] arr, int k) {
    if (arr == null || arr.length <= k)
        throw new Error();
    int from = 0, to = arr.length - 1;
    // if from == to we reached the kth element
    while (from < to) {
        int r = from, w = to;
        int mid = arr[(r + w) / 2];
        // stop if the reader and writer meets
        while (r < w) {
            if (arr[r] >= mid) { // put the large values at the end
                swap(arr, w, r);
                w--;
            } else { // the value is smaller than the pivot, skip
                r++;
            }
        }
        // if we stepped up (r++) we need to step one down
        if (arr[r] > mid)
            r--;
        // the r pointer is on the end of the first k elements
        if (k <= r) {
            to = r;
        } else {
            from = r + 1;
        }
    }
    return arr[k];
}

Question

link

Find 10001st Prime Number

Analysis

Use Sieve of Eratosthenes, or 埃氏筛.

Code

private static final int INDEX = 10001;
private static final int LIMIT = 1000000;

private static int get10001stPrime() {
    boolean[] sieveArray = new boolean[LIMIT];
    int primeCount = 0;
    int currentNum = 2;
    while (primeCount < INDEX) {
        if (!sieveArray[currentNum]) {
            primeCount++;
            for (int i = currentNum; i < LIMIT; i += currentNum) {
                sieveArray[i] = true;
            }
        }
        currentNum++;
    }
    return currentNum - 1;
}

Question

link

Predict the output of following program.

public static void main(String[] args) {
    int a = 012;
    System.out.println("a is " + a);
}

Analysis

Putting a 0 before an integer constant makes it an octal number and putting 0x (or 0X) makes it a hexadecimal number.

Answer: 10.

Terminologies

Atomicity, Atomic Operation

Atomicity is unbreakability, or uninterrupted operation.

Atomic operation helps in understanding reentrancy, critical section, thread safety, synchronization primitives, etc.

Critical Section

Critical section is group of instructions/statements or region of code that need to be executed atomically.

If one thread tries to change a shared data while another thread tries to read, the result is unpredictable. It is critical to understand the importance of race condition while writing kernel mode programming.

A simple solution to critical section:

acquireLock();
Process Critical Section
releaseLock();

Synchronization primitives

Synchronization primitives are simple software mechanisms for the purposes of supporting thread or process synchronization.

Mutex, event, conditional variables and semaphores are all synchronization primitives.

Critical section is not a synchronization primitive. It’s a part of an execution path that must be protected from concurrent execution in order to maintain some invariants.

You need to use some synchronization primitives to protect critical section.

Producer–consumer

Two processes, producer and consumer. Producer thread will collect the data and writes it to the buffer. Consumer thread will process the collected data from the buffer.

Producer won’t try to add when buffer’s full and consumer won’t remove when buffer’s empty.

Solution 1: Mutex

A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.

Solution 2: Semaphore

A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.

Interrupt service routine

Interrupt service routine (ISR), is a callback subroutine in an operating system or device driver whose execution is triggered by the reception of an interrupt.

One good example is reading from a hard drive. The drive is slow and you don’t want your OS to wait for the data to come back; you want the OS to go and do other things. So you set up the system so that when the disk has the data (ready), it raises an interrupt. In the ISR for the disk, CPU will take the data and return it to the requester.

ISRs often need to happen quickly as the hardware can have a limited buffer, which will be overwritten by new data if it’s now pulled off quickly enough.

It’s also important to have your ISR complete quickly as while the CPU is servicing one ISR other interrupts will be masked.

Question

link

Question One: Given a string, find the first non-repeating character in it

link

Question Two: Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.

From a string

1. Scan the string from left to right and construct the count array.

2. Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it.

O(n) time.

The array is size of 128 if it’s ASCII encoding. It can also be replaced with a HashMap if the length of the string is small.

From a stream of chars

Use a DLL (doubly linked list), 1 count array and 1 DLL-node array. Alternatively, the 2 arrays can be replaced with 2 HashMaps.

In totally, one DLL and 2 array are used. The DLL is used to get the sequence of non-repeating chars. The 1st array is for char count, and the 2nd array is for fast loop-up in the DLL.

The detailed precedure:

1. Create an empty DLL and 2 arrays: repeated[] and dllMap[].

2. To get the first non-repeating character, return the head of DLL.

3. Following are steps to process a new character ‘x’ in stream.

   1. If repeated[x] is false and dllMap[x] is NULL, append x to DLL and store it in dllMap[x].

   2. If repeated[x] is false and dllMap[x] is not NULL, get DLL node of x using dllMap[x] and remove the node. Set repeated[x] as true and optionally clear dllMap[x].

   3. If repeated[x] is true, ignore it.

I didn’t write code for this question.

Question

link

Convert a BST to a sorted circular doubly-linked list in-place.

Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

One: Inorder

This question can be solved with inorder traversal with the help of a ‘pre’ pointer.

This solution is recommended by L33tcode, but not very intuitive, and difficult to write. The C++ code is attached below. source.

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  // current node's left points to previous node
  p->left = prev;
  if (prev)
    prev->right = p;  // previous node's right points to current node
  else
    head = p; // current node (smallest element) is head of
              // the list if previous node is not available
  // as soon as the recursion ends, the head's left pointer 
  // points to the last node, and the last node's right pointer
  // points to the head pointer.
  Node *right = p->right;
  head->left = p;
  p->right = head;
  // updates previous node
  prev = p;
  treeToDoublyList(right, prev, head);
}

// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
  Node *prev = NULL;
  Node *head = NULL;
  treeToDoublyList(root, prev, head);
  return head;
}

Two: Divide and conquer

The good and intuitive solution is to do D&C and solve left and right recursively. Do note how the circular linked lists are merged, and be careful when replacing the pointers.

The Java code is posted below. source

public static TreeNode convertBstToDLL(TreeNode root) {
    // convert bst to circular dll 
    if (root == null)
        return (null);

    // Recursively do the subtrees (leap of faith!)
    TreeNode lln = convertBstToDLL(root.left);
    TreeNode rrn = convertBstToDLL(root.right);

    // Make root a circular DLL
    root.left = root;
    root.right = root;

    // At this point we have three lists, merge them
    lln = appendDLL(lln, root);
    lln = appendDLL(lln, rrn);

    return lln;
}

public static TreeNode appendDLL(TreeNode a, TreeNode b) {
    // append 2 circular DLL
    if (a == null)
        return b;
    if (b == null)
        return a;

    TreeNode aLast = a.left;
    TreeNode bLast = b.left;

    aLast.right = b;
    b.left = aLast;
    bLast.right = a;
    a.left = bLast;

    return a;
}

Question

link

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

Analysis

There should be TWO versions of the solution.

1. Version A: The stack should be efficient when pushing an item.

2. Version B: The stack should be efficient when popping an item.

Version A

The stack should be efficient when pushing an item.

1. push:

   1. enqueue in queue1

2. pop:

   1. while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
   2. dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B

The stack should be efficient when popping an item.

1. push:

   1. enqueue in queue2
   2. enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2

2. pop:

   1. deqeue from queue1

reference

Learn and compare with another question [Question] Implement Queue Using Stacks.

Code

written by me, Version A.

public class StackBuiltWithTwoQueue {

    // http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

    public static void main(String[] args) {
        StackBuiltWithTwoQueue stack = new StackBuiltWithTwoQueue();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(5);
        stack.push(6);
        stack.push(7);
        stack.push(8);
        stack.push(9);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

    public void push(int val) {
        q1.offer(val);
    }

    public int pop() {
        if (q1.isEmpty()) {
            System.out.print("Stack is empty now ");
            return -1;
        }
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int topVal = q1.poll();
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        return topVal;
    }
}

Question

link

Please get the least number after deleting k digits from the input number.

For example, if the input number is 24635, the least number is 23 after deleting 3 digits.

Analysis

There’s a solution which instead of ‘delete k’, find the smallest number by ‘keeping (n-k) numbers’. It’s more strightforward.

Solution

1. From the start, search till the end.
   1. If a digit is greater than next one, delete it.
   2. If all digits are increasingly sorted, delete last.
2. Each time go back to start to search again.

Example

24635 -> 2435 -> 235 -> 23

Code

from Harry He

public static String getLeastNumberDeletingDigits_1(String number, int k) {
    String leastNumber = number;
    while(k > 0 && leastNumber.length() > 0) {
        int firstDecreasingDigit = getFirstDecreasing(leastNumber);
        if(firstDecreasingDigit >= 0) {
            leastNumber = removeDigit(leastNumber, firstDecreasingDigit);
        }
        else {
            leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
        }

        --k;
    }

    return leastNumber;
}

private static int getFirstDecreasing(String number) {
    for(int i = 0; i < number.length() - 1; ++i) {
        int curDigit = number.charAt(i) - '0';
        int nextDigit = number.charAt(i + 1) - '0';
        if(curDigit > nextDigit) {
            return i;
        }
    }

    return -1;
}

private static String removeDigit(String number, int digitIndex) {
    String result = "";
    if(digitIndex > 0) {
        result = number.substring(0, digitIndex);
    }
    if(digitIndex < number.length() - 1) {
        result += number.substring(digitIndex + 1);
    }

    return result;
}

Question

link

The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Analysis

We suppose the largest such palindrome will have six digits rather than five, because 143*777 = 111111 is a palindrome. And we can tell that 6-digit base-10 palindrome must be a multiple of 11.

So the question becomes finding the largest palindrome under a million that is a product of two 3-digit numbers.

Solution

We now declare variable m and n:

1. step m down from 999 to 100 by 1
2. step n down from 999 to 100 by:
   1. if m is divisible by 11, then step n down by 11
   2. if m is indivisible by 11, then step n down by 1
3. keep track of the largest product found so far: p = r * s
   1. next time when we found such product value (m * n), it must be m <= r. So n have to be really large in order to make the final product larger than p.
   2. i.e. n >= p/m.
   3. As larger palindromes are found, the range of n gets more restricted

reference

Code

C++ code from stackoverflow

int main(void) {
  enum { A=100000, B=10000, C=1000, c=100, b=10, a=1, T=10 };
  int m, n, p, q=111111, r=143, s=777;
  int nDel, nLo, nHi, inner=0, n11=(999/11)*11;

  for (m=999; m>99; --m) {
    nHi = n11;  nDel = 11;
    if (m%11==0) {
      nHi = 999;  nDel = 1;
    }
    nLo = q/m-1;
    if (nLo < m) nLo = m-1;

    for (n=nHi; n>nLo; n -= nDel) {
      ++inner;
      // Check if p = product is a palindrome
      p = m * n;
      if (p%T==p/A && (p/B)%T==(p/b)%T && (p/C)%T==(p/c)%T) {
    q=p; r=m; s=n;
    printf ("%d at %d * %d\n", q, r, s);
    break;          // We're done with this value of m
      }

    }
  }
  printf ("Final result:  %d at %d * %d   inner=%d\n", q, r, s, inner);
  return 0;
}