Iterative Permutation and Recursive Permutation Algorithms.

 

 1. Permutation algorithm with swap and recursion

 class Solution {
public:
   void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }

    void helper(vector<int> &num, int pos, vector<vector<int>> &ans)
    {
        int n = num.size();
        if (pos == n) {
            ans.push_back(num);
            return;
        }
        for(int i = pos; i < n; i++)
        {
            swap(num, pos, i);
            helper(num, pos+1, ans);
            swap(num, pos, i);
        }
    }
    vector<vector<int>> permute(vector<int> &num) {
        int N = num.size();
        vector<vector<int>> output;
        helper(num, 0, output);
        return output;
    }
};

2. Permutation algorithm with a used mask:

class Solution {
public:
    void helper(const vector<int> &num, vector<int> &current, vector<bool> &used, int pos, vector<vector<int>> &ans)
    {
        int n = num.size();
        if (pos == n) {
            ans.push_back(current);
            return;
        }
     
        for(int i = 0; i < n; i++){
            if (!used[i]) {
                used[i] = true;
                current[pos]= num[i];
                helper(num, current, used, pos+1, ans);
                used[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int> &num) {
        vector<vector<int>> output;
        vector<bool> used(num.size(), false);
        vector<int> current(num.size());
        helper(num, current,used, 0, output);
        return output;
    }
};

3. Iterative way by Next permutation
class Solution {
public:
      void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }
    void reverse(vector<int> &num, int i, int j) {
        while(i < j) {
           swap(num, i, j);      
           i++;
           j--;
        }
    }
 
    void nextPermutation(vector<int> &num) {
        int N = num.size();
        int i = N-1;
        while(i >0  && num[i] <= num[i-1])
          i--;
        if (i == 0) {
            reverse(num, 0, N-1);
            return;
        }
        i--;
        int j = N-1;
        while(j > i && num[j] <= num[i])
            j--;
           
        swap(num, i, j);
        reverse(num, i+1, N-1);
    }
 
    vector<vector<int>> permute(vector<int> &num) {
        vector<vector<int>> output;
        sort(num.begin(), num.end());
        int n = num.size();
        int total = 1;
        while(n>1)
            total *=n--;
        while(--total>=0)
        {
            output.push_back(num);
            nextPermutation(num);
        }
        return output;
    }
};

4. Here is my original way of permutation in iterative:

// ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 201３
// ----------------------------------------------------------------------------

class Solution {
public:
   void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }

    vector<vector<int>> permute(vector<int> &num) {
        int N = num.size();
     
        vector<vector<int>> output;
        vector<int> mask(N);
     
        for(int i = 0; i < N; i++)
           mask[i] = i;
     
        while(true) {
            output.push_back(num);
            for(int i = 0; i <= N; i++) {
              if (i == N) return output;
              if (mask[i] == 0) {
                  mask[i] = i;
                  swap(num, 0, i); // Important
              } else {
                  swap(num, mask[i], i);
                  mask[i]--;
                  swap(num, mask[i], i);
                  break;
              }
          }
      }      
    }
};

Longest substring which begins and ends with two unique characters

This is follow up my last post at Longest substring which contains just two unique characters

What if you are asked to find the longest substring which begins and ends with unique characters. For example, the following strings begin and end with unique characters:
  "abc" where 'a' and 'c' are unique
  "ebbcf" where 'e' and 'f' are unique

Here is my solution in (C#):

 

// ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 2013
// ----------------------------------------------------------------------------
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace LongestSubstring
{
 static class Program
 {
    // Find longest substring which begins and ends with unique characters. 
    // i.e. "abc" where 'a' and 'c' are unique
    // "ebbcf" where 'e' and 'f' are unique
    static string LongestSubstring(string str)
    {
        int Len = str.Length;
        // start index of current substring
        int i = 0;
        // end index of current substring
        int j = 0;
        // start index of the longest substring 
        int maxStart = 0;
        // length of the longest substring 
        int maxLen = 0;
        // Occurrence of each char in current substring
        Dictionary<char, int> CountMap = new Dictionary<char, int>();

        while (j < Len)
        {
            char ch = str[j];            
            // add current char into CountMap
            if (!CountMap.ContainsKey(ch))
                CountMap.Add(ch, 1);            else
                ++CountMap[ch];
            // Increment i until the occurrence of str[i] is 1 or i reaches j
            char ch2 = str[i];
            while (i < j && CountMap[ch2] > 1)
            {
                --CountMap[ch2];
                ch2 = str[++i];
            }
            // Update maxStart and maxLen if current substring is the longest one
            // which starts and ends with unique characters.
            if (i < j && CountMap[ch] == 1 && CountMap[str[i]] == 1 &&
                j - i >= maxLen)
            {
                maxStart = i;
                maxLen = j - i + 1;
            }
            ++j;
         }
          return str.Substring(maxStart, maxLen);
     }
     static void Main()
     {          Assert.AreEqual("", LongestSubstring(""));
          Assert.AreEqual("", LongestSubstring("a"));
          Assert.AreEqual("ab", LongestSubstring("ab"));
          Assert.AreEqual("abc", LongestSubstring("abc"));
          Assert.AreEqual("abbc", LongestSubstring("abbc"));
          Assert.AreEqual("bac", LongestSubstring("abac"));
          Assert.AreEqual("bcccccaaaccccd", LongestSubstring("abaaabcccccaaaccccdd"));
     }
   }
} 

Longest substring which contains just two unique characters

This was discussed at http://www.mitbbs.com/article_t/JobHunting/32444763.html

Here is my solution in (C#):

 // ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 2013
// ----------------------------------------------------------------------------
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace LongestSubstring
{
static class Program
{  
    // Find longest substring which contains just two unique characters.
    static string LongestSubstring(string str)
    {
        int Len = str.Length;
        // start index of current substring
        int i = 0;
        // end index of current substring
        int j = 0;            
        // start index of the longest substring
        int maxStart = 0;
        // length of the longest substring
        int maxLen = 0;
        // Occurrence of each char in current substring
        Dictionary<char, int> CountMap = new Dictionary<char, int>();
           
        while (j < Len) 
        {
           char ch = str[j];
           if (!CountMap.ContainsKey(ch))
               CountMap.Add(ch, 1);
           else 
               ++CountMap[ch];
           // Increment i until there are at most
           // 2 unique chars in current substring begin at i and end at j
           while (CountMap.Count > 2 && i < j)
           {
               ch = str[i];
               if (CountMap[ch] > 1) 
                   --CountMap[ch];
               else
                   CountMap.Remove(ch);                                  
               ++i;                           
           }            
           // If we got 2 chars in current substring and its length
           // is the longest so far, update maxStart and maxLen
           if (CountMap.Count == 2 && j - i >= maxLen) 
           { 
               maxStart = i; 
               maxLen = j - i + 1; 
           }                           
           ++j; 
       }
       return str.Substring(maxStart, maxLen); 
    }
    static void Main() 
    {
       Assert.AreEqual("", LongestSubstring(""));
       Assert.AreEqual("", LongestSubstring("a"));
       Assert.AreEqual("ab", LongestSubstring("ab"));
       Assert.AreEqual("cccccaaacccc", LongestSubstring("abaaabcccccaaaccccdd")); 
    } 
 }
}
 

Follow up, take a look at solution for a related but slightly different question:
Longest substring which begins and ends with two unique characters

Score of the Racers

This problem was discussed at http://www.mitbbs.com/article_t/JobHunting/32401359.html.

The Problem: A bunch of racers, each one has start time and end time.  Calculate each racer's score based on the following rule:
  
    score ＝ The number of racers who started after and finished earlier than current racer.

Note: There is no duplicated start time or end time.

 
Let's start defining the Racer as following (in C#):
class Racer
{
     public Racer(int id, int start, int end)
   { 
      Id = id;
      Start = start;
      End = end;
      StartRank = 0;
      Score = 0;
   }
   // Id of the Racer
   public int Id { get; set; }
   // Start time
   public int Start { get; set; }
   // Finish time
   public int End { get; set; }
   // The number of racers started after and finished before current racer.
   public int Score { get; set; }
   // The number of racers started before current racer
   public int StartRank { get; set; }
}

The Algorithm:

1. Sort the Racers based on Start time.
After this sort, the StartRank is assigned to the Racers.
2.Sort the Racers based on End time in ascending order.
In other word, racers finished earlier will be processed earlier in step 3. 
3.The heart of this algorithm. Initialize an empty List called RanksList. 
For each Racer ordered by the End time in 2,
  a. The score of current racer is the number of racers who start later(StartRank is higher than current Racer's StartRank) and finished earlier(StartRank already in RanksList).
  b. Insert current Racer's StartRank into the RanksList so that all the values in RanksList are ordered ascendingly.

step 3. can be done efficiently by leveraging following feature of List<T>.BinarySearch Method 

"If the List<T> does not contain the specified value, the method returns a negative integer. You can apply the bitwise complement operation (~) to this negative integer to get the index of the first element that is larger than the search value. When inserting the value into the List<T>, this index should be used as the insertion point to maintain the sort order.
This method is an O(log n) operation, where n is the number of elements in the range."
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
Implementation 
static void RankRacers(Racer[] racers)
{
  Array.Sort<Racer>(racers, (a, b) => a.Start - b.Start);
  for (int i = 0; i < racers.Length; ++i)
  {
     racers[i].StartRank = i;
  }   
  Aray.Sort<Racer>(racers, (a, b) => a.End - b.End);   
  List<int> StartRanks = new List<int>();
  for (int i = 0; i < racers.Length; ++i)
  { 
    racers[i].Score = BinarySearchInsert(StartRanks, racers[i].StartRank);
  }
}          
static int BinarySearchInsert(List<int> processedRanks, int startRank)
{
   int index = processedRanks.BinarySearch(startRank);
   index = (index < 0) ? ~index : index;
   int score = processedRanks.Count - index;
   processedRanks.Insert(index, startRank);  
  
   return score;        
} 

Test code:
static void PrintRacerScores(Racer[] racers)
{
   foreach (Racer racer in racers)
   {     
      Console.WriteLine("Racer - " + racer.Id);
      Console.WriteLine("Start - " + racer.Start);
      Console.WriteLine("End - " + racer.End);      Console.WriteLine("Score - " + racer.Score); 
      Console.WriteLine();
    }
} 

static void Main(string[] args)
{
   Racer[] racers = new Racer[] {
       new Racer(0, 1, 100),
       new Racer(1, 2, 10),
       new Racer(2, 3, 4),
       new Racer(3, 5, 6),
   }; 
   RankRacers(racers);   Array.Sort<Racer>(racers, (a, b) => a.Id - b.Id);
   PrintRacerScores(racers);
} 

Sample Output: 
Racer - 0
Start - 1
End - 100
Score - 3

Racer - 1
Start - 2
End - 10
Score - 2

Racer - 2
Start - 3
End - 4
Score - 0

Racer - 3
Start - 5
End - 6
Score - 0 

Rain Water Trap (2D Version)

This was discussed in http://www.mitbbs.com/article/JobHunting/32342353_3.html.
and http://leetcode.com/groups/twitter-interview/forum/topic/rain-water-trap-2d-version/

Here is my solution:

 

// ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 2013
// ----------------------------------------------------------------------------
int FindMaxWater2D(int[,] matrix, int m, int n)
{
    //Two extra 2d array with same size as matrix
    int[,] potentialWaterRows = new int[m, n];
    int[,] potentialWaterCol = new int[m, n];
    FindMaxHeightRows(matrix, potentialWaterRows, m, n);
    FindMaxHeightCols(matrix, potentialWaterCol, m, n);
    int sum = 0;
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            Debug.Assert(Math.Min(potentialWaterRows[i, j], potentialWaterCol[i, j]) >= matrix[i, j]);
            sum += Math.Min(potentialWaterRows[i, j], potentialWaterCol[i, j]) - matrix[i, j];
        }
    }
    return sum;
}

void FindMaxHeightRows(int [,] matrix, int[,] newMatrixRows, int m, int n)
{
    for (int i = 0; i < m; ++i)
    {
        // Find the ascending sequence from left to right
        int[] ascL_R = new int[n];
        ascL_R[0] = matrix[i, 0];
        for (int j = 1; j < n; ++j)
        {
            ascL_R[j] =Math.Max(ascL_R[j-1], matrix[i,j]);
        }
        // Find the ascending sequence from Right to Left
        int[] ascR_L = new int[n];
        ascR_L[n-1] = matrix[i, n-1];
        for (int j = n-2; j >=0; --j)
        {
            ascR_L[j]= Math.Max(ascR_L[j+1], matrix[i,j]);
        }
              
        for(int j = 0; j < n; ++j)
        {
            newMatrixRows[i, j] = Math.Min(ascR_L[j], ascL_R[j]);
        }
    }
}
    
void FindMaxHeightCols(int [,] matrix, int[,] newMatrixCols, int m, int n)
{     
    for (int j = 0; j < n; ++j)
    {
        // Find the ascending sequence from Top to bottom
        int[] ascT_B = new int[n];
        ascT_B[0] =matrix[0, j];
        for (int i = 1; i < m; ++i)
        {
            ascT_B[i] =Math.Max(ascT_B[i-1], matrix[i,j]);
        }
        // Find the ascending sequence from Top to bottom
        int[] ascB_T = new int[n];
        ascB_T[m-1] = matrix[m-1, j];
        for (int i = m-2; i >=0; --i)
        {
            ascB_T[i] = (Math.Max(ascB_T[i+1], matrix[i, j]));
        }
              
        for(int i = 0; i < n; ++i)
        {
            newMatrixCols[i, j] = Math.Min(ascB_T[i], ascT_B[i]);
        }
    }
}