Shuffle an Array

Question:
Given an input array, shuffle it and output a randomized sequence.

Analysis:
The array can actually be of any type, not necessary integer or number. One special example is to shuffle a deck of cards. That happens to be of integer type.

Variations:
There may be different variations of this similar problem. I hope to summarize all the cases here and would like to go through each with some implementation.

1. Randomize an array of n elements
2. Randomly select m elements out of an array of n elements
3. Randomly select m elements out of a stream of n elements (n is known before hand)
4. Randomly select m elements out of a stream of elements (not sure how many elements there are until stopping reading)

This blog talks about Case 1. The code is not hard but there are some tricks. It's better to select from the end of array and that will help control the number of elements remained. Also, the code will be cleaner.


The mathematical proof would be trickier and it's good to have some combinatorics. The probability of any output sequence will be \[\frac{1}{n!}\]

Decide if a Binary Tree is Binary Search Tree

Question:
Given a binary tree, validate if it's a binary search tree.

Analysis:
The elements in a BST are sorted if traversed in-order. This is a very important feature BST and based on the definition, the problem can be solved by in-order traversal.

The class definition of tree node:

Based on the analysis above, we can have the implementation below.

Many people may think we can simply check "left.value < parent.value < right.value" for each node. That being said, we can have an implementation like this:

However, this is not correct. Simply checking the parent and children relationship is not sufficient. Here is a counter-example.

      5
     /  \
    /    \
   3    7
  / \    / \
2  6  4  9

This is a top-down approach although it's not correct. If adding more constraints on the value for each node, there is a working solution for this. Here is the implementation:

Find Next Character in Sorted String

Question:
Given a sorted array of unique elements R, that are letters of English alphabet and an input character x. The elements in R are sorted with the least element appearing first. Find the minimum r in R such that r > x. If there is no r > x, find the first element of the array (wrap around).

Example:
R = ['c', 'f', 'j', 'p', 'v']
if x equals:
'a' => return 'c'
'c' => return 'f'
'k' => return 'p'
'z' => return 'c' (wrap around case)

Is the Number A Power of Two?

Problem:
Given an integer number, decide if it's a power of 2. Return true if yes, otherwise return false.

Analysis:
Can the number be negative?
>> Should not be. Since a power of any number can only be positive. Hence, let me assume non-negative numbers only in this problem.

Solution 1:
Runs in constant time and makes use of bit operations.

Solution 2:
Shifts the bits and counts the number of 1's.

Solution 3:
Uses arithmetic operation only. This is similar to Solution 2. Division by 2 is equivalent to right shift by 1 bit. Check the modulo by 2 is equivalent to check the least significant bit of the integer.

Binary Tree Comparison

Problem:
Given two binary trees, compare if they are the same. If yes, return true, otherwise return false.

Analysis:
This is a very common programming interview question. Not that hard but it's very good to test the idea of recursion. Also, there are some edge cases one needs to consider.

Complexity:
Since it's a binary tree, should consider average case and worst case.
Balanced or unbalanced?

Solution:

Lowest Common Ancestor in Binary Search Tree Given Two Values

Problem:
Given a Binary Search Tree (BST) and two values, find the lowest common ancestor.

Note:
Two values are given in this problem, instead of two nodes. But the idea should be similar. Here I am giving two options: one is to find the node first and then search by node, and the other is to directly search by value. However, these two are the same in nature: comparing by value and validating the nodes.

Assumption:
The values are distinct in the BST. If not, the problem will become complicated. Consider the BST with all equal values in nodes.

Complexity:
Average case? Worst case?
For BST, balanced or unbalanced? Need to take this into consideration.

Solution 1:
Find the nodes first and then search by node.


Solution 2:
Directly search by value and then validate the values.

Loop & Its Entrance in Singly Linked List

Problem:
Given a singly linked list, check whether there is a loop in it. If yes, find the entrance to the loop.

Thinking:
Use 2 pointers, one fast and one slow. If at some time, these 2 pointers meet, then there is a loop; if fast pointer arrives at the end of the list, there is no loop.

Suppose we have above list structure. Assume loop length is \(r(r\in N)\), and the length before the loop (from \(A\) to \(B\)) is \(l\). Always, one can represent \(l\) as \(l=k\cdot r+p\), where \(k=0,1,2,...\) and \(p=0,1,2,...,r-1\).

Then, suppose the moving speed of "fast" is \(a\) times of "slow", where \(a>1\) and \(a\in N\). If "slow" moves one step a time, "fast" will move \(a\) steps a time.

If there is a loop, where will the 2 pointers meet? Suppose they will meet after "fast" finishes \(n\) loops and "slow" finishes \(m\) loops. And suppose also, at this moment, they are at point C, which is of \(q\) steps after the loop entrance \(B\). Here, \(n\ge1, m\ge0, m,n\in N, q=0,1,...,r\). Hence, the following equation holds: \[k\cdot r+p+n\cdot r+q=a(k\cdot r+p+m\cdot r+q)\] We need find values for \(m,n\) and \(q\) so that above equation holds. The equation can be rewritten as \[n\cdot r-a\cdot m\cdot r-k(a-1)r=(a-1)(p+q)\] We can always find a \(q\) such that \(p+q=r\), then \[n-am-k(a-1)=a-1\] \[n=am+(k+1)(a-1)\] For the first time they meet, \(m=0\) and then \[n=(k+1)(a-1)\] To be most efficient, \(a=2\) and \(n=k+1\).

Conclusion:
From above statement, we know that "fast" and "slow" will definitely meet during the first loop round for "slow". Also, at the moment they meet, they are at \(q=r-p\) steps after \(B\), which is equivalent to \(p\) steps before \(B\). Note that the head length \(l=k\cdot r+p\), which means that if two pointers start at \(A\) and \(C\) at the same time and both move one step a time, they will meet at the loop entrance \(B\) for the first time.

Below, I just show the code to find the loop entrance. Actually, the loop check is just part of and can be told from the return value of this program.

Are 2 Strings Anagrams or Not?

Problem:
Given 2 strings, determine if they are anagrams. Anagram means the 2 strings contain exactly the same characters and number of appearances. In other words, we can do a permutation to get the other string from one string.

Solution 1:
Sort the 2 strings first, then if they are anagrams, the sorted strings must be identical. Otherwise, they are not.

In C++, we may use the library function sort in the header < algorithm >. This function is comparison based and the average time complexity is \(O(n\log n)\).


Solution 2:
Since the character values are always in a fixed range, and in this case, counting sort is good approach. In this way, we may obtain \(O(n)\) time complexity and \(O(n)\) space complexity.


Solution 3:
Similar to the idea of counting sort, we don't actually sort the strings. All we need is the counts of characters appearing in the strings. If the counts for each character are equal, then the 2 strings are anagram. This solution also exhibit \(O(n)\) time complexity, but \(O(1)\) space complexity.


Solution 4:
Even more, we can just count the characters for one string, and make judgement while scanning the other. This approach also has \(O(n)\) time complexity and \(O(1)\) space complexity.
There is a bug in Solution 4. What if s1 is longer and contains all characters in s2? For example, s1="abcd", s2="ab".

Two possible solutions for this:

1. Add a length check at the beginning. Two strings must be of the same length to be anagram.
2. Add another round of check on the count array after scanning the second string. All entries should be 0.

Maximize Payoff by Greedy Reordering

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 384, Problem 16.2-7

Problem:
Suppose you are given two sets \(A\) and \(B\), each containing \(n\) positive integers. You can choose to reorder each set however you like. After reordering, let \(a_i\) be the \(i\)th element of set \(A\), and let \(b_i\) be the \(i\)th element of set \(B\). You then receive a payoff of \(\prod_{i=1}^{n}{a_i^{b_i}}\). Given an algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.

Solution:
Greedy Algorithm: Let the set \(\{a_i\}\) be sorted so that \(a_1 \ge a_2 \ge \ldots \ge a_n\) and set \(\{b_i\}\) be sorted so that \(b_1 \ge b_2 \ge \ldots \ge b_n\). Pair \(a_i\) with \(b_i\). This is the required solution.

Complexity:
If the two sets \(A\) and \(B\) are already sorted, the time complexity is \(O(n)\).
If the sets are not sorted, then sort them first and the time complexity is \(O(n\log n)\).

Proof:
Suppose the optimal payoff is not produced from the above solution. Let \(S\) be the optimal solution, in which \(a_1\) is paired with \(b_p\) and \(a_q\) is paired with \(b_1\). Note that \(a_1 \gt a_q\) and \(b_1 \gt b_p\).

Consider another solution \(S'\) in which \(a_1\) is paired with \(b_1\), \(a_q\) is paired with \(b_p\), and all other pairs are the same as \(S\). Then \[\frac{\text{Payoff}(S)}{\text{Payoff}(S')}=\frac{\prod_{S}\hspace{2 mm} a_i^{b_i}}{\prod_{S'}\hspace{2 mm}a_i^{b_i}}=\frac{(a_1)^{b_p} (a_q)^{b_1}}{(a_1)^{b_1} (a_q)^{b_p}}=(\frac{a_1}{a_q})^{b_p - b_1}\] Since \(a_1 \gt a_q\) and \(b_1 \gt b_p\), then \(\text{Payoff}(S) / \text{Payoff}(S') \lt 1\). This contradicts the assumption that \(S\) is the optimal solution. Therefore \(a_1\) should be paired with \(b_1\). Repeating the argument for remaining elements, we can get the result.

0-1 Knapsack Problem

Problem:
A thief robbing a store finds \(n\) items; the \(i\)th item is worth \(v_i\) dollars and weights \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers. He wants to take as valuable a load as possible, but he can carry at most \(W\) pounds in his knapsack for some integer \(W\). Which items should he take?

Analysis:
There are two versions of this problem: fractional knapsack problem and 0-1 knapsack problem.

1. Fractional knapsack problem: the items can be broken into smaller pieces, and the thief can take fractions of items.
2. 0-1 knapsack problem: the items may not be broken into smaller pieces, and the thief must decide whether to take an item or leave it (binary choices).

For fractional knapsack problem, greedy algorithm exists and the problem can be solved in \(O(n\log n)\) time based on sorting. And a better approach may take \(O(n)\) time for the worst case based on linear-time SELECT algorithm.

For 0-1 knapsack problem, no greedy algorithm exists and we need turn to dynamic programming approach. The algorithm will take \(O(nW)\) time.

Solution:
Define \(c[i,w]\) to be the optimal value for items \(1,2,...,i\) and maximum weight \(w\). There are following recursive relations:
\[c[i,w]=\begin{cases}0, & i=0\text{ or }w=0\\c[i-1,w], & w_i\gt w\\ \max\{v_i+c[i-1,w-w_i], c[i-1,w]\}, & i>0 \text{ and }w_i \le w\end{cases}\] We can have the pseudocode:

DP_01_Knapsack(value, weight, W)
   assert value.length = weight.length
   n ← value.length
   for w ← 0 to W:
      c[0,w] ← 0
   for i ← 1 to n:
      c[i,0] ← 0
      for w ← 1 to W:
         c[i,w] ← c[i-1,w]
         if weight[i] ≤ w and value[i]+c[i-1,w-weight[i]] > c[i-1,w]:
            c[i-1,w] ← value[i]+c[i-1,w-weight[i]]

The set of items to take can be deduced from the table, starting at \(c[n,W]\) and tracing backwards where the optimal values came from. If \(c[i,w]=c[i-1,w]\), then item \(i\) is not part of the solution, and we are continue tracing with \(c[i-1,w]\). Otherwise item \(i\) is part of the solution, and we continue tracing with \(c[i-1,w-w_i]\).

References:

Dynamic Programming Solution to the 0-1 Knapsack Problem

A More Efficient Algorithm for Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.
In my previous post, I discussed the dynamic programming approach with time complexity \(O(n^2)\). For this specific problem, we can have a more efficient algorithm which is also based on dynamic programming. Please see Wikipedia for reference.

The algorithm uses only arrays and binary searching. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as \(X[1]\), \(X[2]\), etc. Then, after processing \(X[i]\), the algorithm will have stored values in two arrays:

\(M[j]\) — stores the position \(k\) of the smallest value \(X[k]\) such that there is an increasing subsequence of length \(j\) ending at \(X[k]\) on the range \(k ≤ i\) (note we have \(j ≤ k ≤ i\) here).

\(P[k]\) — stores the position of the predecessor of \(X[k]\) in the longest increasing subsequence ending at \(X[k]\).

In addition the algorithm stores a variable \(L\) representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence \[X[M[1]], X[M[2]], ..., X[M[L]]\] is nondecreasing. For, if there is an increasing subsequence of length \(i\) ending at \(X[M[i]]\), then there is also a subsequence of length \(i-1\) ending at a smaller value: namely the one ending at \(X[P[M[i]]]\). Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L 
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in \(L\). The actual longest sequence can be found by backtracking through the \(P\) array: the last item of the longest sequence is in \(X[M[L]]\), the second-to-last item is in \(X[P[M[L]]]\), etc. Thus, the sequence has the form \[..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].\]
Because the algorithm performs a single binary search per sequence element, its total time can be expressed using Big \(O\) notation as \(O(n\log n)\).


References:

Wikipedia item: longest increasing subsequence

Related Posts:

\(O(n^2)\) Algorithm for Longest Increasing Subsequence

Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.

Brute-force approach:
Enumerate all possible subsequences and then determine which are increasing and store the longest one. This approach is obviously impractical for large \(n\) and its time complexity is exponential.

Dynamic programming approach:
The longest increasing subsequence of an array \(A\) of length \(n\) can be determined based on that of all the prefix arrays. We need use an auxiliary array \(T[n]\), in which \(T[i]\) stores the length of longest increasing (non-decreasing) subsequence ending at \(A[i]\). Notice that is ending at, i.e., the last element must be \(A[i]\). Meanwhile, the global maximum length is also stored in variable \(L\). The time complexity for this algorithm will be \(O(n^2)\).



Related Posts:

\(O(n\log n)\) Algorithm for Longest Increasing Subsequence

Implementation of prev_permutation

In my previous posts, I discussed about various approaches to find the next number in order. The main idea for that is the function of next_permutation in C++, or equivalent implementations in C or Java. Now, I am trying to implement the opposite function prev_permutation.

The function takes a string as input, update the string to the previous one in lexicographical order if there is, and return a bool value. If there is a smaller string, return true; if not, return false and update the string from the smallest to the greatest.

Idea:

1. Search back from the end, find the first greater character compared to the one immediately after it.
2. Search back from the end again, find the first smaller one compared to the great character just found.
3. Swap the 2 characters found from above 2 steps.
4. Reverse the rest string after the character location found in Step 1.

Delete Duplicate Nodes from Linked List

Problem:
Given an unsorted linked list, delete duplicate nodes from the linked list.

Thinking:
This problem is again similar to previous 2 posts (determine uniqueness and remove duplicates). There are several algorithms available.

Node definition:
Suppose the node in this linked list is defined as the class below.

Solution 1:
Without using extra buffer, delete every duplicates for each node encountered. Time complexity \(O(n^2)\).

Solution 2:
Without using extra buffer, each time encountering a node, detect if it's a duplicate. If yes, then delete it. Time complexity \(O(n^2)\).

Solution 3:
Using an extra hash table / hash set / hash map to keep track which nodes have already existed. Average time complexity \(O(n)\).

Notes:

1. Would there be any differences if the linked list is doubly linked?
   ==> Probably not.
2. How about sorting the list first?
   ==> As long as you are allowed to destroy the original order, this should work.

Remove Duplicate Characters

Problem:
Given a string, remove the duplicate characters in the string.

Assumption:
All the characters are from ASCII set and in the range 0~255. Also, the character null character does not appear in the string.

Requirement:
An extra copy of the array is not allowed.

Similar to last post about approaches to deciding unique characters or not, this can be done in place or with an array of fixed size.

Note:
Although C++ algorithm library has unique function, which may seem appropriate for this problem. However, that unique function just removes the consecutive duplicates.

We may also sort the string first if we can remove any duplicates, not necessarily keeping the first one in appearance order. In this way, we may get to time complexity \(O(n\log n)\). Also, this method would destroy the order of unique characters. This solution is not shown in this post.

Solution 1:
For each character in the string and unique, detect all duplicates in the string afterwards. Mark those duplicates and remove them in the end. Suppose the string is given as a char array, otherwise we may need convert a String to StringBuffer, StringBuilder, or CharArray.

Solution 2:
For each character in the string, first determine if it's duplicate. If yes, simply skip it; if not, keep it in the string.

Solution 3:
An extra array of fixed size can be used to record which characters have appeared. This can reduce the time complexity from \(O(n^2)\) to \(O(n)\). Also, we can have boolean array or bitset approaches. Each of them can be applied to the above 2 schemes and we can have 4 different algorithms. Here, I am showing boolean array with Scheme 1 in this solution, and bitset with Scheme 2 for next solution.

Solution 4:
Use bitset with the above Scheme 2 to remove the duplicates.

String Contains All Unique Characters or Not

Problem:
Given a string, determine if this string contains all unique characters.

Assumption:
The characters in this string are from ASCII character set. In other words, the value range is 0~255.

Solution 1:
Directly compare each character in the string with every other character in the string. This approach will take \(O(n^2)\) time and no space.

Solution 2:
If allowed to destroy the string, we may first sort the string using quicksort, and then scan through the string to see if there are 2 adjacent characters are the same. Quicksort will take \(O(n\log n)\) time and \(O(1)\) space. If using mergesort, it will take \(O(n)\) space. In Java, to sort the string, an extra array or StringBuffer is needed.

Solution 3:
Since the characters are in a small range, and we can create an array to record if one certain character has appeared or not. This approach will take \(O(n)\) time and \(O(m)\) space, where \(m\) is the size of character set.

Solution 4:
Similar to Solution 3, but instead of using an array of boolean values, use a set of bits to record the binary values. In Java, \(256/32=8\) int size bits are needed, which can be implemented as an array of 8 integers, and each integer represents 32 characters. In C++, there is a very convenient structure called bitset, which can be beautifully used here.

Notes:
Since the characters are all from the assumed set, and the set size is known. In this case, the maximum length for a string of all unique characters will be the size of the character set. Therefore, for each of the above programs, we may add the following code.

if( s.length() > 256 ) return false;

The Number of Inversions in an Array

Problem:
Let \(A[1...n]\) be an array of \(n\) distinct numbers. If \(i \lt j\) and \(A[i] \gt A[j]\), then the pair \( (i,j) \) is called an inversion of A. Determine the number of inversions given an array of distinct numbers.

Solution 1:
Naive approach. There are \( \frac{n(n-1)}{2} \) number pairs in an array of size \(n\), and check one by one. The time complexity is \(O(n^2)\).

We can have a better solution for this problem, which is proposed as below.

Solution 2:
Divide-and-conquer. This strategy works in similar way to merge-sort, and bears time complexity \(n\log n\).

Various Implementations of pow(x, y)

In this post, I discuss the implementation of function
double pow( double, int ).

Let's first consider the most simple case: y is a positive integer.
The naive and straightforward approach is working with a loop like following.

Next, we need consider all possible integers for y.

We can write a recursive function to calculate x raised to the power y.

The time complexities for all above 3 implementations are \(O(n)\). Use of a temporary variable would help.

Now, the time complexity reduces to \(O(\log n)\). How about non-recursive version? Yes, we can do it.

Actually, we can have one more implementation with bit operations!! Sounds amazing!

Swap 2 Variables

This problem can be seen everywhere, and almost every people knows the solution. In this post, I'm going to summarize 3 functions for swap.

Function 1: naiveSwap

Function 2: xorSwap

Function 3: addSwap

Summary:

	naiveSwap	xorSwap	addSwap
extra variable	need	not need	not need
check \(x \ne y\) (address)	not need	need	need
readability	good	not good	not good
overflow	no problem	no problem	potential problem
aliasing	fine	complicated	complicated
execution model	instruction pipeline	strictly sequential	strictly sequential

Situations for XOR use in practice:

• On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes;
• In a region with high register pressure, it may allow the register allocator to avoid spilling a register;
• In Microcontrollers where available RAM is very limited.

Because these situations are rare, most optimizing compilers don't generate XOR swap code.

Because of the problem of overflow, the add-swap approach is used less often.


References:

Wikipedia item: XOR swap algorithm

Next Number in Order

Problem:
Given a number as string, output the next number in order. The digits you may use are only those already given, plus any number of 0's.

Example:
Given 1234, output 1243;
Given 4321, output 10234.

Solution:
In previous post, I discussed the ways using C++ library function next_permutation. What if we are not allowed to use this function? Can we write de novo code?

First, I tried Java. Since string in Java cannot be updated in place, and hence it needs many auxiliary variables, including StringBuffer objects that can be set at a specific index.

Here is the Java code.

Secondly, I tried to implement this function in C. Suppose the string given was stored in a char array, which is the C style.

Here is the C code.

Related Posts:

Next Number in Order with next_permutation