CareerCup

sort and get inverted index for each element.
then compare the index array
Onlgn

The code below supports duplicates.

#include <iostream>
#include <vector>

using namespace std;

class Element {
	public:
		Element(int val, int idx)
		{
			val_ = val;
			idx_ = idx;
		}
		bool operator<(Element const &other) const
		{
			if (val_ == other.val_) {
				return idx_ < other.idx_;
			}
			return val_ < other.val_;
		}
		int val_, idx_;
};

bool SamePattern(vector<int> const &a1, vector<int> const &a2)
{
	if (a1.empty() ||
		a1.size() != a2.size())
	{
		return false;
	}
	vector<Element> e1, e2;
	for (int n : a1) {
		e1.push_back(Element(n, e1.size()));
	}
	for (int n : a2) {
		e2.push_back(Element(n, e2.size()));
	}
	sort(e1.begin(), e1.end());
	sort(e2.begin(), e2.end());
	for (int i = 0; i < e1.size(); ++i) {
		if (e1[i].idx_ != e2[i].idx_) {
			return false;
		}
		if (i > 0) {
			if ((e1[i - 1].val_ == e1[i].val_) != (e2[i - 1].val_ == e2[i].val_)) {
				return false;
			}
		}
	}
	return true;
}

bool BruteForce(vector<int> const &a1, vector<int> const &a2)
{
	if (a1.empty() ||
		a1.size() != a2.size())
	{
		return false;
	}
	for (int i = 0; i < a1.size(); ++i) {
		for (int j = i + 1; j < a1.size(); ++j) {
			if ((a1[i] > a1[j]) != (a2[i] > a2[j])) {
				return false;
			}
			if ((a1[i] < a1[j]) != (a2[i] < a2[j])) {
				return false;
			}
		}
	}
	return true;
}

int main()
{
	srand(time(NULL));
	for (int i = 0; i < 1000000; ++i) {
		int size = rand() % 10;
		vector<int> a1, a2;
		for (int j = 0; j < size; ++j) {
			a1.push_back(rand() % 10);
			a2.push_back(rand() % 10);
		}
		if (BruteForce(a1, a2) != SamePattern(a1, a2)) {
			cerr << "mismatch\n";
			return -1;
		}
	}
	cout << "ok\n";
}

public class ArrayPatternDetect {
	
	public boolean checkTwoNumber(int num1, int num2) {
		String n1 = ""+num1;
		String n2 = ""+num2;
		char[] num1s= n1.toCharArray();
		char[] num2s = n2.toCharArray();
		
		Map<Character, Integer> num1Pos = new HashMap<>();
		Map<Character, Integer> num2Pos = new HashMap<>();
		for(int i=0; i<num1s.length;i++) {
			num1Pos.put(num1s[i], i);
			num2Pos.put(num2s[i], i);
		}
		
		Arrays.sort(num1s);
		Arrays.sort(num2s);
		
		String num1Order = "";
		String num2Order = "";
		for(int i=0; i<num1s.length;i++) {
			num1Order+=num1Pos.get(num1s[i]);
			num2Order+=num2Pos.get(num2s[i]);
		}
		
		return num1Order.equals(num2Order);
	}
	
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayPatternDetect arrayPatternDetect = new ArrayPatternDetect();
		System.out.println(arrayPatternDetect.checkTwoNumber(123, 456));
		System.out.println(arrayPatternDetect.checkTwoNumber(321, 654));
		System.out.println(arrayPatternDetect.checkTwoNumber(312, 654));
		
	}

}

what if we check the index of the next smallest element to the left of each element and note its index. If the next smallest element index for each element is not the same in both the arrays it means that the pattern is not the same