CareerCup

Here is the java code for dutch national flag problem. Catering this scenario.

The logic is to align 1's to the left and 3's to the right. the 2's will automatically get into their respective positions.

import java.util.Arrays;

public class DutchNationalFlag {

    public static void dnf(int[] a, int low, int high) {
        int startIndex = 0;
        int endIndex = a.length - 1;
        int temp;

        for (int i = 0; i <= endIndex ;) {
            if (a[i] < low) {
                temp = a[i];
                a[i] = a[startIndex];
                a[startIndex] = temp;
                i++;
                startIndex++;
            } else if (a[i] > high) {
                temp = a[i];
                a[i] = a[endIndex];
                a[endIndex] = temp;
                endIndex--;
                // do not increment i. We have to revisit this again
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[] {1,3,2,2,3,1,1,1,3,2,2,1,1};
        DutchNationalFlag.dnf(a, 2, 2);
        System.out.println(Arrays.toString(a));

    }

}

dutch national flag problem.

A java solution below. Note that given that I do have to keep track of where the ones and threes go, it'd only take an extra variable to count the twos as well and do a bucket sort... but I think this is most in keeping with the spirit of the question.

public static void sort123s(int [] arr)
	{
		int oneAt = 0;
		int threeAt = arr.length-1;
		
		int at = 0;
		while(at <= threeAt)
		{
			if(arr[at] == 1)
			{
				swap(arr, at, oneAt);
				if(at == oneAt)
					at++;
				oneAt++;
			}
			else if(arr[at] == 3)
			{
				swap(arr, at, threeAt--);
			}
			else
			{
				at++;
			}
		}	
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

Its like two values in array just 0 and 1
Now here there are three values 1, 2, 3. Run a loop,with three indexes for three values. two at start and one at the last

#include<iostream>

using namespace std;

#define SIZE 10

int main()
{
int two=0, three=0, size=SIZE-1;

int arr[SIZE] = {1,3,3,2,1,2,3,1,3,2};

for(int i=0;i<SIZE;i++)
{
if(arr[i]==1)
continue;
else if(arr[i]==2)
{
two++;
arr[i] = 1;
}
else if(arr[i]==3)
{
three++;
arr[i] = 1;
}
}

for(int i=0;i<SIZE;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;


cout<<"THREE:: "<<three<<endl;
cout<<"TWO:: "<<two<<endl;


while(three!=0)
{
arr[size] = 3;
three--;
size--;
}
while(two!=0)
{
arr[size] = 2;
two--;
size--;
}

for(int i=0;i<SIZE;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;

return 0;
}

1. Have two pointers, one representing beginning index of 2 and the other representing beginning index of 3.
2.Let their initial values be -1.
3. Traverse from left to right. If you get 1 and the two indices are -1 just leave it, no swap required
4. Let i be the looping index
5. If threestartindex is -1 and twostartindex isnt or viceversa, swap a[correspondingpointer] and a[i], increment correpondingpointer by one
6. if twostartindex is -1 and the two startindex isnt -1 and we have 2 as input, no swaps are necessary, they are in order. Do similarly for vice versa
7. If none of the indices are -1 and we get 2 as input, swap a[i] and a[threestartingpointer] and increment threestartingpointer by one
6. If none of the indices are -1 and we get 1 as input, swap a[i] and a[threestartingpointer] and increment threestartingpointer by one. Swap a[threestartingpointer-1] and a[twostartingpointer] and increment a[twostartingpointer]
7. If none of the indices are -1 and the input is 3, no swap required.

Hope this will work.

/**
* time: O(n)
* space: O(1)
*/
void sort(int[] arr){

int one = -1;
int two = -1;

for( int i =0; i < arr.length; i++ ){
if( arr[i] == 2 ){
ArrayUtils.swap(arr, i, two+1);
++two;
}
else if( arr[i] == 1 ){
ArrayUtils.swap(arr, i, two+1);
ArrayUtils.swap(arr, two+1, one+1);
++one;
++two;
}
else if( arr[i] != 3 ){
throw new IllegalStateException("Incorrect value for array: " + arr[i]);
}
}
}

void sort012(int a[], int arr_size)
{
   int lo = 0;
   int hi = arr_size - 1;
   int mid = 0;
 
   while(mid <= hi)
   {
      switch(a[mid])
      {
         case 0:
           swap(&a[lo++], &a[mid++]);
           break;
         case 1:
           mid++;
           break;
         case 2:
           swap(&a[mid], &a[hi--]);
           break;
      }
   }
}

Its Dutch national flag problem.

void sort(int *arr, int len) {
      int low, mid, high;
      for(low = mid = 0, high = len - 1; mid < high; ) {
              arr[mid] == 1 ? swap(&arr[mid++], arr[low++]) : arr[mid] == 2 ? mid++ : swap(&arr[mid], &arr[high--]);
      }
}

#include<iostream>
using namespace std;
int main()
{
int o,i,m=0,n=6,temp,max=7;
int a[]={3,3,2,1,1,2,2};
for(i=0;i<max;i++)
{if(a[i]==1)
{temp=a[m];
a[m]=a[i];
a[i]=temp;
m++;}
if(a[i]==3)
{temp=a[n];
a[n]=a[i];
a[i]=temp;
n--;max--;}
if(a[i]==2)
{temp=a[m];
a[m]=a[i];
a[i]=temp;}}
for(i=0;i<7;i++)
{ cout<<a[i]<<" ";}
return 0;
}


if this code is correct ans of question

Wouldn't the partition algorithm work?

void Sort(int[] array)
{
    int below = -1;
    int above = array.Length;

    for (int i = 0; i < above; )
    {
        if (array[i] == 1)
        {
            // below
            Swap(array, i, ++below);
            i++;
        }
        else if (array[i] == 3)
        {
            // above
            Swap(array, i, --above);
        }
        else
        {
            // middle
            i++;
        }
    }
}

void Swap(int[] array, int i, int j)
{
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

for(i=1;i<n;i++)
	{
		if(a[i]<a[i-1])
		{
			for(j=i;j>0;j--)
			{
				if(a[j-1]<=a[j])
					break;
				else
				{
					tmp=a[j];
					a[j]=a[j-1];
					a[j-1]=tmp;
				}
			}
		}
	}

This is my solution, with complexity O(n).

void sort(int v[], int n) {
	int begin = 0;
	int end = n - 1;
	int i;
	for ( i = 0; i <= end; i++) {
		if (v[i] == 1)
			swap(v[begin++], v[i]);
		else if (v[i] == 3) {
			while(v[end] == 3 && end > i)
				end--;
			swap(v[i], v[end]);
		} 	
	}
}

void swap(int * input,int i,int j)
{
	int temp = input[j];
	input[j] = input[i];
	input[i] = temp;
}
void sorting(int length, int *input)
{
	int onePointer = 0;
	int threePointer = length-1;
	for(int i = 0; i <= threePointer; i++)
	{
		while(input[onePointer]==1)
		{
			i++;
			onePointer++;
		}
		while(input[threePointer]==3)
		{
			threePointer--;
		}

		if(input[onePointer] == 3 && input[threePointer] == 1)
		{
			onePointer++;
			threePointer--;
			swap(input,i,threePointer);
		}
		else if(input[i] == 1)
		{
			swap(input,i,onePointer);
			onePointer++;
		}
		else if(input[i] == 3)
		{
			swap(input,i,threePointer);
			threePointer--;
			i--;
		}
		
	}
}

package array;

public class arrangeNumbers {

public void arrangeData(int arr[]){
int oneLen=-1;
//int twoLen=-1;
int threeLen=-1;
int arrLen=arr.length-1;
System.out.println("arrlen:"+arrLen);
for (int i=0;i<arr.length;i++){
if (arr[i]==3 && threeLen!=i){
if (threeLen<0){
threeLen=arrLen;
}

while(arr[threeLen]==3 ){
threeLen--;
}
swap(i,threeLen,arr);
threeLen--;
}

if (arr[i]==2){
swap(i,oneLen+1,arr);
}
if (arr[i]==1){
if (oneLen<0){
swap(i,0,arr);
}
else{
swap(oneLen+1,i,arr);
}
oneLen++;

//printnumbers(arr);
}

if (i==threeLen && threeLen>0){
break;
}
}
printnumbers(arr);
}
private void printnumbers(int arr[]){
for(int i:arr){
System.out.println(i);
}

}
private static void swap(int i, int j, int[] arr) {
if (arr[i]==arr[j]||i==j){
return;
}
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String args[]){
int[] arr={1,2,2,2,2,1,3,2,3,1,2,3,3,2,2,3,1,1,2,3,2,1};
arrangeNumbers an=new arrangeNumbers();
an.arrangeData(arr);
}

}

public class arrangeNumbers {
	
	public void arrangeData(int arr[]){
		int oneLen=-1;
		int threeLen=-1;
		int arrLen=arr.length-1;
		System.out.println("arrlen:"+arrLen);
		for (int i=0;i<arr.length;i++){
			if (arr[i]==3 && threeLen!=i){
				if (threeLen<0){
					threeLen=arrLen;
				}
				
				while(arr[threeLen]==3 ){
					threeLen--;
				} 
				swap(i,threeLen,arr);
				threeLen--;
			}
			
			if (arr[i]==2){
				swap(i,oneLen+1,arr);
			}
			if (arr[i]==1){
				if (oneLen<0){
					swap(i,0,arr);
				}
				else{
					swap(oneLen+1,i,arr);
				}
				oneLen++;
				
				//printnumbers(arr);
			}
			
			if (i==threeLen && threeLen>0){
				break;
			}
		}
		printnumbers(arr);
	}
	private void printnumbers(int arr[]){
		for(int i:arr){
			System.out.println(i);
		}
		
	}
	private static void swap(int i, int j, int[] arr) {
	if (arr[i]==arr[j]||i==j){
		return;
	}
	int temp=arr[i];
	arr[i]=arr[j];
	arr[j]=temp;
	}
	public static void main(String args[]){
		int[] arr={1,2,2,2,2,1,3,2,3,1,2,3,3,2,2,3,1,1,2,3,2,1};
		arrangeNumbers an=new arrangeNumbers();
		an.arrangeData(arr);
	}

}

here is a python code. go through the elements of the list. when encountering 1, throw it to the front; when encountering 2, do nothing; when encountering 3, throw it to the end.

Seq = [input sequence of 1, 2, and 3]

i = 0
for j in range(len(Seq)):
  if Seq[i] == 1:
    del Seq[i]
    Seq = [1] + Seq
    i += 1
  elif Seq[i] == 2:
    i += 1
  elif Seq[i] == 3:
    del Seq[i]
    Seq = Seq + [3]

print "Sorted sequence is", Seq

public static void dutchFlag(int [] array)
    {
	int top = 0;
	int bottom = array.length-1;

	int cursor = 0;
	while (cursor <=bottom)
	{
	    if (array[cursor] == 0)
	    {
		swap(array, top, cursor);
		top++;
		cursor++;
	    }
	    else if (array[cursor] == 2)
	    {
		swap(array, bottom, cursor);
		bottom--;
	    }
	    else
	    {
		cursor++;
	    }
	}
    }
 
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

/**
 * You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third. 
 * 
 * Ex: Input [1, 3, 3, 2, 1] 
 * Output [1, 1, 2, 3, 3] 
 * 
 * But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts. 
 * 
 * You are only permitted to swap elements.
 * 
 * @author patrick
 *
 */
public class App {

	private static void swap(int[] values, int i, int j) {
		int x = values[j];
		values[j] = values[i];
		values[i] = x;
	}
	
	public static void sort(int[] values) {
		for(int i=1; i<values.length; i++) {
			int j = i;
			while(j>0) {
				int v = values[j];
				//adjacent value
				int pv = values[j-1];
				//if current value is smaller than adjacent
				if(v < pv) {
					swap(values, j-1, j);
					j--;
				}
				else {
					break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int[] values = new int[] {1, 3, 3, 2, 1};
		
		sort(values);
		
		for(int v : values) {
			System.out.print(v + " ");
		}
	}
	
}

Here is my PHP code:

<?php
	$a = array(1, 2, 1, 2, 3, 3, 3, 1);
	$n = count($a);
	$beginOfOne=0;
	$beginOfThree = $n-1;
	
	for($i=0; $i<$n; $i++)
	{
	a:
		if($a[$i]==1)
		{
			if($i==$beginOfOne)continue;
			swap($i, $beginOfOne);
			++$beginOfOne;
			goto a;
		}
		elseif($a[$i]==2)
		{
			if($i==($beginOfOne+1))continue;
			if($a[$i]==$a[$beginOfOne+1])continue;
			swap($i, ($beginOfOne+1));
			goto a;
		}
		elseif($a[$i]==3)
		{
			if($i>=$$beginOfThree)continue;
			swap($i, $$beginOfThree);
			--$$beginOfThree;
			goto a;
		}
		else die('Error, wrong number in array');
	}
	
	function swap($p, $d)
		{
			global $a;
		
			$swap = $a[$p];
			$a[$p] = $a[$d];
			$a[$d] = $swap;
		}
	
?>

shouldn't it be just a counting sort problem?

#include <stdio.h>

void swap(int *a, int i, int j) {
    int temp = a[i] ;
    a[i] = a[j] ;
    a[j] = temp ;
}

void sort(int *a, int len) {

    int low = 0 ;
    int mid = 0 ;
    int high = len -1 ;

    while(mid <= high) {
	switch(a[mid]) {
	    case 1:
		swap(a, low, mid) ;
		++low;
		++mid;;
		break;
	    case 2:
		++mid;
		break;
	    case 3:
		swap(a, mid, high) ;
		--high;
		break;
	}
    }
}

int main() {
    int a[] = {1,3,3,2,1,3,2} ;

    sort(a, 7) ;

    for(int i = 0 ; i < 7 ; ++i)
	printf("%d ", a[i]) ;
    printf("\n");

}

i dnt knw d exact code..... but what if we consider d 3,3 as single element nd swap it with 1 in i/p array... {1,3,3,2,1} swaping 3,3 with 1 in d end about 2 will just b a single pass... and d array wl b sorted....

My ruby code in O(n)

#!/usr/bin/ruby 
#
#
#

require 'pp'


def sort_array array

  def swap i,j,a
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp
  end

  i = 0
  one = 0
  three = array.size - 1

  while i <= three

      i += 1
      one += 1
      next
    end

    if array[i] == 3
      swap i,three,array
      three -= 1
      
      if array[i] == 1
        swap i,one,array
        one += 1
      end

    end

    i += 1

  end

  return array

end

Here is a simple C implementation with one swap

#include <stdio.h>

void sort(int a[], int n)
{
  int i,one=0,two=0,three=0,temp=0;
  for(i = 0;i<15; i++)
  {
   if(a[i] == 1)
   {
     a[one]=1;
     if(two) a[one+two]=2;
     if(three) a[one+two+three] = 3;one++;
   }
   else if(a[i] == 2)
   {
    a[one + two] = 2;
    if(three) a[one + two + three] = 3;two++;
   }
   else
   {
    three++;
   }
  }
}

main()
{
  int i;
 int array[] = {1,2,3,3,3,2,2,1,1,2,3,3,2,1,2};
 for(i=0;i<15;i++)
 printf(" %d",array[i]);
 printf("\n");
 sort(array,15);
 for(i=0;i<15;i++)
 printf(" %d",array[i]);
  printf("\n");
}

public class FacebookSort{

	static int length;
	static int[] a;
	static int start;
	static int end;
	static int temp;
	
	public static void sort(){
		temp = start;
		while(temp <= end){
			if(a[temp] == 1){
				a[start] = a[temp] + (a[temp] = a[start]) - a[start];
				start ++;
				temp ++;
			}
			else if(a[temp] == 3){
				a[end] = a[temp] + (a[temp] = a[end]) - a[end];
				end --;
			}
			else{
				temp ++;
			}
		}
	}
	
	public static void display(){
		for(int i = 0; i < length; i ++){
			System.out.print(a[i] + " ");
		}
	}
		
	public static void main(String[] args){
		length = args.length;
		a = new int[length];
		end = length - 1;
		for(int i = 0; i < length; i ++){
			a[i] = Integer.parseInt(args[i]);
		}
		sort();
		display();
	}
}

public static void modify123OnePass(int[] array) {
		int oneEnd = -1;
		int twoEnd = -1;
		int threeEnd = -1;
		for (int c : array) {
			if(c == 1) {
				array[++OneEnd] = 1;
				if (twoEnd != -1) {
					array[++twoEnd] = 2;
				}
				if (threeEnd != -1) {
					array[++threeEnd] = 3;
				}
			} else if (c == 2) {
				if (twoEnd == -1 && oneEnd != -1) {
					twoEnd = oneEnd;
				}
				array[++twoEnd] = 2;
				if (threeEnd != -1) {
					array[++threeEnd] = 3
				}
			} else {
				if (threeEnd == -1) {
					if (twoEnd != -1) {
						threeEnd = twoEnd;
					} else {
						threeEnd = oneEnd;
					}
				}
				str[++threeEnd] = 'B';
			}
		}
	}

void rearrange(vector<int>& v)
{
	for (int i = 0, p = -1, q = v.size(); i < q; ) {
		if (v[i] == 1 && i != p) {
			++p;
			swap(v[p], v[i]);
			continue;
		} else if (v[i] == 3 && i != q) {
			--q;
			swap(v[q], v[i]);
			continue;
		}
		
		++i;
	}
}

I think we need to check each element in the array twice for both 1 and 3. Here is my code with time complexity O(n):

void sort(int a[], int n) 
{
	int begin = 0;
	int end = n - 1;
	int i;
	while(a[begin]==1)
	{
		begin++;
	}
	while(a[end]==3)
	{
		end--;
	}
	for(i=begin;i<=end;i++)
	{
		if(a[i]==1)
		{
			swap(a[i], a[begin++]);
			if(a[i]==3)
				swap(a[i], a[end--]);
		}
		else if(a[i]==3)
		{
			swap(a[i], a[end--]);
			if(a[i]==1)
				swap(a[i], a[begin++]);
		}
	}
}

g

public class Test {
int a[]={1,2,1,3,1,2,3,2};
int b[]= new int[20];
static int index=0;
void arrange(int val)
{
for(int i=0;i<a.length;i++)
{
if(a[i]==val)
{
b[index] = a[i];
index++;
}
}
}

public static void main(String args[]){

Test obj = new Test();
obj.arrange(1);
obj.arrange(2);
obj.arrange(3);
for(int j=0;j<index;j++)
{
System.out.print(obj.b[j]);
}
}
}

Bubble sort ?????

I think it will work???