CareerCup

It can be solve by one-pass and 4log4*n time complexity (O(8n)).

	Treat it as intervals, and try to merge them.

class Tuple3 {
    String id;
    int left;
    int right;
    public Tuple3(String id,int left,int right) {
        this.id = id;
        this.left = left;
        this.right = right;
    }
}

class Tuple2 {
    String id;
    int val;
    public Tuple2(String id,int val) {
        this.id = id;
        this.val = val;
    }
}

public class Solution{
    static Tuple2[] dissembleTuple(Tuple3[] input) {
        Tuple2[] result = new Tuple2[input.length*2];
        
        Comparator c1 = new Comparator<Tuple2>(){
                @Override
                public int compare(Tuple2 t1, Tuple2 t2){
                    return t1.val-t2.val;
                }
        };
        
        PriorityQueue<Tuple2> q = new PriorityQueue(4,c1);
        q.add(new Tuple2(input[0].id,input[0].left));
        q.add(new Tuple2(input[0].id,input[0].right));
        
        for (int i=1;i<input.length;i++) {
            // merge tuple3
            q.add(new Tuple2(input[i].id,input[i].left));
            q.add(new Tuple2(input[i].id,input[i].right));
            result[(i-1)*2]=q.poll();
            result[(i-1)*2+1]=q.poll();
        }
        
        result[input.length*2-2] = q.poll();
        result[input.length*2-1] = q.poll();
        
        return result;
    }

First, the length of S1 and S2 should equal.
It is ez to solve by duplicate s1 or s2 like s2 = s2+s2:

e.g S1="amazon" S2="azonam"
	Assuming we are duplicating S2：
		S2="azonamazonam";

Then, we can scan S2, find whether S2 contains S1.

public static boolean isRotated(String s1, String s2) {
	if (s1.length()!=s2.length())
		return false;
	int len = s1.length();

	// double String "s2";
	s2 = s2+s2;
	for (int i=0;i<len;i++) {
		if (s2.substring(i,i+len).equals(s1))
			return true;
	}

	return false;
}

The time complexity should be O(n), space complexity O(1);

}

First, the length of S1 and S2 should equal.
It is ez to solve by duplicate s1 or s2 like s2 = s2+s2:

e.g S1="amazon" S2="azonam"
	Assuming we are duplicating S2：
		S2="azonamazonam";

Then, we can scan S2, find whether S2 contains S1.

public static boolean isRotated(String s1, String s2) {
	if (s1.length()!=s2.length())
		return false;
	int len = s1.length();

	// double String "s2";
	s2 = s2+s2;
	for (int i=0;i<len;i++) {
		if (s2.substring(i,i+len).equals(s1))
			return true;
	}

	return false;
}

The time complexity should be O(n), space complexity O(1);

}

It could ez solve by using the functions of StringBuilder:

insert(offset,char)
        append(char)

static String reverseWords(String s) {
		if (s==null||s.length()==0)
			return "";
		StringBuilder result = new StringBuilder();
		int j=0;	// position of last [comma,space,numbers]
		for (int i=0;i<s.length();i++) {
			char c = s.charAt(i);
			if (c==' '||Character.isDigit(c)||c==','){
				result.append(c);
				j=i+1;
			} else result.insert(j, c);
		}
		return result.toString();
	}

}