CareerCup

Construct a directed graph with nodes A, B, C, ... and edges (A,B), (C,D) etc. Then do a topological sort and you're done.

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
  int number;
  cout<<"\n Enter the number of inputs:";
  cin>>number;

  char inputChar1,inputChar2;
  pairedVector dataVector;

  for(int i=0;i<number; i++)
  {
    /* Reading the user string*/
    cout<<"\n Enter the paired chars:";
    cin>>inputChar1;
    cin>>inputChar2;

    /* pair the char for insetion*/
    charPair p = std::make_pair(inputChar1, inputChar2);

    /* Inserting the data into Vector for string pair*/
    dataVector.push_back(p);
  }

   charPair min;
   for(int i=0; i< dataVector.size()-1; i++)
   {
      min=dataVector[i];
      int swapIndex=i;
      for(int j=i; j<dataVector.size(); j++)
      {
         if(min>dataVector[j])
         {
             min=dataVector[j];
             swapIndex=j;
         }
      }
      /* Swap the values */
      charPair tmp=dataVector[swapIndex];
      dataVector[swapIndex]=dataVector[i];
      dataVector[i]=tmp;

   }
  /* Define an iterator to get the values from the vector*/
   pairedVector::iterator it;
   int i=0;
   for( it=dataVector.begin(); it!=dataVector.end(); ++it)
   {
       cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
       ++i;
   }

    return 0;
}

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
int number;
cout<<"\n Enter the number of inputs:";
cin>>number;

char inputChar1,inputChar2;
pairedVector dataVector;

for(int i=0;i<number; i++)
{
/* Reading the user string*/
cout<<"\n Enter the paired chars:";
cin>>inputChar1;
cin>>inputChar2;

/* pair the char for insetion*/
charPair p = std::make_pair(inputChar1, inputChar2);

/* Inserting the data into Vector for string pair*/
dataVector.push_back(p);
}

charPair min;
for(int i=0; i< dataVector.size()-1; i++)
{
min=dataVector[i];
int swapIndex=i;
for(int j=i; j<dataVector.size(); j++)
{
if(min>dataVector[j])
{
min=dataVector[j];
swapIndex=j;
}
}
/* Swap the values */
charPair tmp=dataVector[swapIndex];
dataVector[swapIndex]=dataVector[i];
dataVector[i]=tmp;

}
/* Define an iterator to get the values from the vector*/
pairedVector::iterator it;
int i=0;
for( it=dataVector.begin(); it!=dataVector.end(); ++it)
{
cout<<"\n Pair < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
++i;
}

return 0;
}

Java Version using Topological Sort:

public class AlphabeticalOrdering {
	static Map<Character, List<Character>> tuples = new HashMap<Character, List<Character>>();
	static int alphabetCount = 0;
	static Map<Character, Boolean> vertex = new HashMap<Character, Boolean>();
	
	public static List<Character> ordering(Tuple tuple[]){
	
		for(Tuple t : tuple){
			if(tuples.containsKey(t.x)){
				tuples.get(t.x).add(t.y);
			}else{
				List<Character> list = new LinkedList<Character>();
				list.add(t.y);
				tuples.put(t.x, list);
			}
			
			vertex.put(t.x, false);
			vertex.put(t.y, false);
		}
		
		alphabetCount = vertex.size();
		
		return topologicalSort();
		
	}
	
	public static List<Character> topologicalSort(){
		Stack<Character> s = new Stack<Character>();
		
		
		for(Map.Entry<Character, Boolean> entry : vertex.entrySet()){
			if(!entry.getValue())
				topologicalSortUtil(entry.getKey(), s);
		}
		
		List<Character> result = new LinkedList<Character>();
		
		while(!s.isEmpty())
			result.add(s.pop());
		
		return result;
	}
	
	public static void topologicalSortUtil(char v, Stack<Character> s){
		vertex.put(v, true);
		
		if(tuples.containsKey(v)){
			Iterator<Character> it = tuples.get(v).listIterator();
			while(it.hasNext()){
				char n = it.next();
				if(!vertex.get(n))
					topologicalSortUtil(n, s);
			}
		}
		
		s.push(v);
	}
	public static void main(String[] args) {
		Tuple tuple[] = {
				new Tuple('A', 'B'),
				new Tuple('C', 'D'),
				new Tuple('C', 'E'),
				new Tuple('D', 'E'),
				new Tuple('A', 'C'),
				new Tuple('B', 'C')
			};
		
		System.out.println(ordering(tuple));
	}

}

class Tuple{
	char x;
	char y;
	
	public Tuple(char a, char b){
		x = a;
		y = b;
	}
}

List<String> newList = Arrays.asList("AB", "BC", "CD", "DE", "MZ", "NM");
char[] chrs;
Set<Character> charSet = new TreeSet<>();
for (Iterator<String> iterator = newList.iterator(); iterator.hasNext();) {
String string = (String) iterator.next();
chrs = string.toCharArray();
for (int i = 0; i < chrs.length; i++) {
char c = chrs[i];
charSet.add(c);

}

}

System.out.println(charSet);

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
  int number;
  cout<<"\n Enter the number of inputs:";
  cin>>number;

  char inputChar1,inputChar2;
  pairedVector dataVector;

  for(int i=0;i<number; i++)
  {
    /* Reading the user string*/
    cout<<"\n Enter the paired chars:";
    cin>>inputChar1;
    cin>>inputChar2;

    /* pair the char for insetion*/
    charPair p = std::make_pair(inputChar1, inputChar2);

    /* Inserting the data into Vector for string pair*/
    dataVector.push_back(p);
  }

   charPair min;
   for(int i=0; i< dataVector.size()-1; i++)
   {
      min=dataVector[i];
      int swapIndex=i;
      for(int j=i; j<dataVector.size(); j++)
      {
         if(min>dataVector[j])
         {
             min=dataVector[j];
             swapIndex=j;
         }
      }
      /* Swap the values */
      charPair tmp=dataVector[swapIndex];
      dataVector[swapIndex]=dataVector[i];
      dataVector[i]=tmp;

   }
  /* Define an iterator to get the values from the vector*/
   pairedVector::iterator it;
   int i=0;
   for( it=dataVector.begin(); it!=dataVector.end(); ++it)
   {
       cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
       ++i;
   }

    return 0;
}

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
  int number;
  cout<<"\n Enter the number of inputs:";
  cin>>number;

  char inputChar1,inputChar2;
  pairedVector dataVector;

  for(int i=0;i<number; i++)
  {
    /* Reading the user string*/
    cout<<"\n Enter the paired chars:";
    cin>>inputChar1;
    cin>>inputChar2;

    /* pair the char for insetion*/
    charPair p = std::make_pair(inputChar1, inputChar2);

    /* Inserting the data into Vector for string pair*/
    dataVector.push_back(p);
  }

   charPair min;
   for(int i=0; i< dataVector.size()-1; i++)
   {
      min=dataVector[i];
      int swapIndex=i;
      for(int j=i; j<dataVector.size(); j++)
      {
         if(min>dataVector[j])
         {
             min=dataVector[j];
             swapIndex=j;
         }
      }
      /* Swap the values */
      charPair tmp=dataVector[swapIndex];
      dataVector[swapIndex]=dataVector[i];
      dataVector[i]=tmp;

   }
  /* Define an iterator to get the values from the vector*/
   pairedVector::iterator it;
   int i=0;
   for( it=dataVector.begin(); it!=dataVector.end(); ++it)
   {
       cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
       ++i;
   }

    return 0;
}

case class LetterOrder(lesser: String, greater: String)

object Prob {
  def main(args: Array[String]): Unit = {
    val orderings = Seq(
      LetterOrder("A", "B"),
      LetterOrder("C", "D"),
      LetterOrder("C", "E"),
      LetterOrder("D", "E"),
      LetterOrder("A", "C"),
      LetterOrder("B", "C")
    )

    val alphabet = orderings
      .flatMap(lo => Seq(lo.lesser, lo.greater))
      .toSet
      .toList

    def sortByOrdering(x: String, y: String): Boolean =
      if (orderings.contains(LetterOrder(x, y))) {
        true
      } else {
        orderings.find(_.lesser == x) match {
          case Some(LetterOrder(_, otherGreater)) =>
            sortByOrdering(otherGreater, y)

          case None =>
            false
        }
      }

    println(alphabet.sortWith(sortByOrdering))
  }
}

Recursive:

def topoSort(ts):
    r,g,v = ([[]],{},set())
    for [a,b] in ts:
        g.update({a: g.get(a, []) + [b]})
    def go(k):
        if k not in v:
            for m in g.get(k, []):
                go(m)
            v.add(k)
            r[0] += [k]
    for k in g.keys():
        go(k)
    return r[0][::-1]
      
print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])

Iterative:

def topoSort(ts):
    r,g,v = ([],{},set())
    for [a,b] in ts:
        g.update({a: g.get(a, []) + [b]})
    for k in g.keys():
        st = [(k, g.get(k, []))]
        while st:
            (k,ms) = st.pop()
            if k not in v:
                if ms:
                    st += [(k, ms[1:])]
                    st += [(ms[0], g.get(k, []))]
                else:
                    v.add(k)
                    r += [k]
    return r[::-1]
      
print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])