Interview Questions

  • View all interview questions
  • blank
  • Dutch national flag sorting problem
    For this problem, your goal is to sort an array of 0, 1 and 2's but you must do this in place, in linear time and without any extra space (such as creating an extra array). This is called the Dutch national flag sorting problem. For example, if the input array is [2,0,0,1,2,1] then your program should output [0,0,1,1,2,2] and the algorithm should run in O(n) time.

    Algorithm

    The solution to this algorithm will require 3 pointers to iterate throughout the array, swapping the necessary elements. (1) Create a low pointer at the beginning of the array and a high pointer at the end of the array. (2) Create a mid pointer that starts at the beginning of the array and iterates through each element. (3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1. (4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1. (5) If the element at arr[mid] is a 1, don't swap anything and just increase the mid pointer by 1. This algorithm stops once the mid pointer passes the high pointer.

    Example

    Code

    function swap(arr, i1, i2) {
      var temp = arr[i1];
      arr[i1] = arr[i2];
      arr[i2] = temp;
    }
    
    function dutchNatFlag(arr) {
      
      var low = 0;
      var mid = 0;
      var high = arr.length - 1;
      
      // one pass through the array swapping
      // the necessary elements in place
      while (mid <= high) {
        if      (arr[mid] === 0) { swap(arr, low++, mid++); }
        else if (arr[mid] === 2) { swap(arr, mid, high--); }
        else if (arr[mid] === 1) { mid++; }
      }
      
      return arr;
      
    }
    
    dutchNatFlag([2,2,2,0,0,0,1,1]); 
    
    def swap(arr, i1, i2):
      temp = arr[i1]
      arr[i1] = arr[i2]
      arr[i2] = temp
    
    def dutchNatFlag(arr):
      
      low = 0
      mid = 0
      high = len(arr) - 1
      
      # one pass through the array swapping
      # the necessary elements in place
      while mid <= high:
        if arr[mid] == 0:
          swap(arr, low, mid)
          low += 1
          mid += 1
        elif arr[mid] == 2:
          swap(arr, mid, high)
          high -= 1
        elif arr[mid] == 1:
          mid += 1
          
      return arr
      
    print dutchNatFlag([2,2,2,0,0,0,1,1]) 
    
    Run Code
    Run Code

    Running time

    This algorithm runs in O(n) time because it only passes through the array once swapping the necessary elements in place.

    Sources

    http://www.glassdoor.com/Interview/Solve-Dutch-National-Flag-problem-QTN_309969.htm
    mrdaniel published this on 11/24/15 | array, sorting, Facebook
    Comments
  • +
  • 2
  • -
  • Provide another way using C#.
    using System.Collections.Generic;
    
            static void Swap(int[] array, int x, int y)
            {
                int temp = array[x];
                array[x] = array[y];
                array[y] = temp;
            }
    
            static void DutchNationalFlag(ref int[] array)
            {
                int low = 0;
                int high = array.Length - 1;
                for (int i = 0; i <= high; i++)
                {
                    if (array[i] == 0)
                        Swap(array, low++, i--);
    
                    if (array[i] == 2)
                        Swap(array, i--, high--);
                }
            }
    
            public static void Main(string[] args)
            {
                int[] array2 = { 2, 2, 2, 0, 0, 0, 1, 1 };
                DutchNationalFlag(ref array2);
                str = string.Join(",", array2);
                Console.WriteLine(str);
            }
    
    
    Login to submit a comment