CareerCup

We cannot do better than O(nlogn), because if all symbols are '<', it becomes a normal sort.

Here is my solution:

1. Sort the array. 
2. After that, maintain two pointers on the array; one pointing to the first element, and the other pointing to the last one. 
3. Iterate on n-1 symbols.
3.a. If the current symbol is '<', then, add the element that the first pointer points to, to the answer and increment the first pointer.
3.b. Otherwise, add the element pointed by the second pointer to the answer and decrement the second pointer.
4. Add the remaining element (both pointers are pointing to it) to the answer

A C++ implementation using sort in STL:

#include <iostream>
#include <algorithm>

using namespace std;

int *solve(int *ary, int n, char* symbols)
{
	sort(ary, ary + n);

	int *ans = new int[n];

	int ptr1 = 0, ptr2 = n-1;

	for (int i = 0; i < n-1; ++i)
	{
		if (symbols[i] == '<')
			ans[i] = ary[ptr1++];

		else
			ans[i] = ary[ptr2--];
	}

	ans[n - 1] = ary[ptr1];

	return ans;
}

you need to assume all numbers are distinct.

#include<iostream>
#include<conio.h>
using namespace std;
struct node
{
int info;
char ch;
struct node *link;
};
int display1(struct node *);
int operatorinsert(struct node *);
int main()
{
struct node *head,*p,*pr;
int n;
cout<<"enter how many numbers you want insert:\n";
cin>>n;
head=NULL;
for(int i=0;i<n;i++)
{
if(head==NULL)
{
p=new node;
cout<<"enter number's:\n";
cin>>p->info;
head=p;
pr=p;
pr->link=NULL;
}
else
{
p=new node;
cin>>p->info;
pr->link=p;
pr=p;
pr->link=NULL;
}
}
struct node *Tr;
Tr=head;
operatorinsert(Tr);
display1(Tr);
getch();
return 0;
}
int operatorinsert(struct node *m)
{
while(m->link!=NULL)
{
if(m->info>m->link->info)
m->ch='>';
else
m->ch='<';
m=m->link;
}
return 0;
}
int display1(struct node *q)
{
while(q->link!=NULL)
{
cout<<q->info<<q->ch;
q=q->link;
}
cout<<q->info;
return 0;
}