Day 10 Interview

 

LeetCode – Generate Parentheses

 

1. Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”.

2. Idea

This problem can be properly solved by a recursive strategy. Three pieces of information are maintained during the search for all matched parentheses: the exploration prefix so far, the number opening of the remaining opening parentheses, and the number closing of the remaining closing parentheses. When both  opening and  closing (initiallyn ) are zero, no parenthesis is left and we have got a new match. If only opening is zero, a new match is obtained by appending to prefix the remaining ‘)’s. Otherwise, we are safe to append to prefix a ‘(‘, subtract opening by one, and carry on the process recursively. If there has been more ‘(‘ than ‘)’ in the  prefix , we can also append to  prefix a ‘)’, subtract  closing by one, and carry on the process recursively. By this means, all possible valid parentheses will be found.

3. Implementation

4. Wrap-up

You might be interested in knowing the number of such combinations ofn pairs of parentheses. In fact, its number is known as the Catalan number, which is calculated as follows:

Cn=1n+1(nk)=2n!(n+1)!n!=k=2nn+kk.

You are recommended to learn from the Wikipedia page more applications that yields to the Catalan number.

 

LeetCode – Merge k Sorted Lists

1. Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

2. Idea

A trivial solution is to use k1 comparisons to find the smallest node (i.e., whose value is the smallest) among k lists, and repeat this process for ntimes where n is the number of the nodes in all lists. This solution yieldsO(nk) time complexity. Alternatively, there are at least two non-trivial solutions, by divide-and-conquer or by using a min heap.

  • By dividie-and-conquer: This idea resembles that of MergeSort, where a list is sorted by dividing its elements into two parts, sorting each part recursively, and merging them into a list. In the context of this problem, we can divide the sorted lists into two parts, merge each part recursively, and finally merge the two parts into a list. Now suppose the number of the nodes in the k lists is n . It can be seen that the running time T(k) for merging k lists has the recursive expression:
    T(k)=2T(k/2)+O(n).

    By the master theorem (or more vividly by the recursion tree generated by the above equation) and since k=O(n) ,

    T(k)=O(k)+O(nlogk)=O(nlogk).

    Its space complexity is the size of the recursion stack, which is O(logk) .

  • By using a min heap (priority queue): Things become simpler when an appropriate data structure is used. In this case, we can use a min heap of size k to save the smallest node in each list. As long as the heap is not empty, its min node is definitely the smallest among the remaining nodes in all lists, and thus inserted to the resulting list and removed from the heap. When the node has a next node, we put the next node into the heap and repeat the process until the queue is empty (all nodes have been processed). Since each insertion into and removal from the heap cost O(logk) time, and there are exactly n insertions and removals, the time complexity for this approach is O(nlogk) . The space usage is clearly O(k) due to the maintenance of the heap.

3. Implementation

The above non-trivial ideas are individually implemented as follows.

  • Divide and Conquer
  • Priority Heap

4. Wrap-up

Both solutions have the same time complexity, and are accepted by LeetCode OJ. Though the priority queue solution costs slightly more time given the test cases, it is more preferable since it is easy to implemented,highly readable, and does not need to maintain the information for recursion as in the divide-and-conquer one.

 

LeetCode – Swap Nodes in Pairs

 

1. Problem

Given a linked list, swap every two adjacent nodes and return its head. For example, given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

2. Idea

A trivial problem that does not need much elaboration. Just use a reference that points to the node ahead each pair to complete the swapping. Note the use of a header node to avoid boundary check.

3. Implementation

4. Wrap-up

Only an extra node is created. One pass of the nodes suffices to get the work done.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s