Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
9
of 9 vote

Here is an approach that runs in O(n) time.

To clarify the idea, we will first assume that every character occurs in the string less than N/2 times, where N is the length of the string. This is not a perfect assumption, because the string may still be valid if there's one letter that occurs N/2 or (N+1)/2 times. e.g. abaca is a valid arrangement. After discussing the general approach, we can take care of this special case.

First, we count the number of occurrences of each character using an array or hash table, depending on whether the size of the alphabet is small or large. After that, we place occurrences of the first character at indices 0, 2, 4, 6, ..., etc., so that occurrences of the character are never together. If the first character used indices 0, 2, ..., 20, the second character would be placed at 22, 24, 26, etc. Upon reaching the end of the array, we would wrap around and start filling odd indices, like 1, 3, 5, in that order

To be precise, we keep a numCharsPlaced variable. If we've already written a total of numCharsPlaced characters (counting repeated chars), the next character is to be placed at (2*numCharsPlaced)%arr.length+adjustment, where adjustment is 1 if the array size is even, 0 if it's odd.

Note that this algorithm never places two identical characters next to each other, except when a character's count is so high that the wraparound to odd indices occurs and we get all the way back to where the even-indexed occurrences of the character occurred. This can only happen if a character occurs at least N/2 times.

If a character occurs (N+1)/2 times, all other character counts are less than N/2. The solution is to detect that character when validating the character occurrence counts, and ensure we start (at index 0) with that character (this will give this character enough space, and all other characters have enough space by the general proof given before). If a character occurs exactly N/2 times, we use the same remedy as for the (N+1)/2 case. In the N/2 case, it's possible that there is one other character that also occurs N/2 times, but we verify that the algorithm behaves correctly in this case.

If a character occurs more than (N+1)/2 times, there is no solution. That's because you can split the input into that many pairs of adjacent locations, and you can argue by pigeonhole principle that at least one such pair of locations must have more than one of the same character, which would mean that the same character occurs twice consecutively.

- eugene.yarovoi October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good job dude, yeah this solution is better than mine which runs in O(nlgn). It is useful remember stuff like pigeonhole principle

- NenadCro October 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene.yarovoi . After reading your long post, I think your solution is similar to mine. Pls see my code and post to see if it has any problem or it is simpler.

- plutoman October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you choose which character you insert next? Do you keep them sorted by frequency (like other solutions using max heap)?

- damluar October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@damluar The whole point is that sorting is unnecessary, so we can take the characters in any order. This is the insight that improves the solution to O (n).

- Anonymous October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@plutoman I think you have the same approach. My post goes into a little more detail as to why all the edge cases work, that's why it's slighly longer. The edge cases correspond to the two modifications you made to your code later.

- Anonymous October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think you can take the put the character in any order

say "aaabc"

if you put 'a' first, you can get the right ouput 'abaca. However, you go first with 'b' or 'c', you will get the wrong output like "baaca", "cabaa" and ..

- capybara October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Does this work for 'abccc'?

- uday November 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it does, it'll give you "cacbc"

- koosha.nejad November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad, Uday is right, it doesn't work for "abccc", here you have indices 0,1,2,3,4 as you said it puts "a" at 0 , "b" at 2, c at 4, c at 1, and c at 3,
you will get "acbcc"

- koosha.nejad November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

No it will work correctly for "abccc" see the mentioned explanation:
"If a character occurs (N+1)/2 times, all other character counts are less than N/2. The solution is to detect that character when validating the character occurrence counts, and ensure we start (at index 0) with that character"

- mmp November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

Initial idea of zd is good, but he missed one tiny details. We actually dont need access to heap internal nodes, we can just put all characters in hashmap, and check in any character is appearing more than n/2 times we return Invalid output.

After that we put all letters in max heap, and each time we pop two items from heap. we put those two in string, decrease occurrence of each one by one, and put them again in heap if their occurrence is bigger than 0. Of course we need to check special cases if we only have one element in heap. We do this n/2 where asymptotic cost of all these operations of popping and adding to heap are 4*lgn so altogether complexity is O(nlgn).

private static String rearrangeLetters(String s) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		
		StringBuilder res = new StringBuilder();
		
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (!map.containsKey(c))
				map.put(c, 0);
			map.put(c, map.get(c) + 1);
		}
		
		PriorityQueue<Letter> PQ = new PriorityQueue<>(new Comparator<Letter>()
				{

					@Override
					public int compare(Letter arg0, Letter arg1) {
						if (arg0.occ > arg1.occ)
							return -1;
						else if (arg0.occ < arg1.occ)
							return 1;
						else
							return 0;
					}
			
				});
		
		for (Character key : map.keySet()) {
			if (map.get(key) > s.length() / 2)
				return "INVALID OUTPUT";
			PQ.add(new Letter(map.get(key), key));
		}
		
		while(!PQ.isEmpty()) {
			Letter front = PQ.poll(), secondFromFront = null;
			if (!PQ.isEmpty())
				secondFromFront = PQ.poll();
			res.append(front.c);
			
			if (secondFromFront != null) {
				res.append(secondFromFront.c);
				secondFromFront.occ--;
				if (secondFromFront.occ > 0)
					PQ.add(secondFromFront);
			}
			front.occ--;
			if (front.occ > 0)
				PQ.add(front);
			
			}
		
		
		return res.toString();
	}

}

- NenadCro October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I have almost exact the same initial idea with @NenadCro. But I don't like the cost of pop and push top elements repeatedly out of and into the heap. Or we could do better with decrease key of node in heap if we have access to heap node.
Then I have an O(n) run time algorithm without the heap. The idea is simple, please see the code. If we have the max occurrence of characters less or equal to n/2, then we can have valid output. We just put same chars together in a string t (put max occurrence char first), and pick t[i] and t[halfLength+i] together to overwrite s. See my post below and let me know if it has problems.

- plutoman October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think there is a minor bug in the code above. You have to round up n/2 first when comparing the max occurrence of characters, otherwise in some special cases we will get invalid output where the length of the string is odd. Like: "abb"

- andyg October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

I have an O(nlogn) solution.

Scan through the string and count character occurrences.
Build a max heap with the character occurrences.
Build a string with the top character.
Then loop: pull the top character and check if its the same as the previous character. If so, check the heap left or heap right to get the next highest occurrence. This means that we need to have access to the heap node internals.

- zd October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 vote

we can use hashing approach here. first, we count the no of each characters.

then we start from first character to the last in the hash table.
then, we start placing each character alternatively (0, 2, 4, ...).
when it reaches the end of string then we place it like (1, 3, 5, ...).
in this way there won't be any two consecutive place with same character.

this approach will work in o(n).

- rajeshkumarsinha12 October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work for abccc

- Anonymous October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

^It works if you sort it by the length of characters in decreasing order. Which is more or less O(nlogn + n) ~ O(nlogn)

- Anonymous January 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for correcting me

- rajeshkumarsinha12 January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And sorting won't take much time since there are at most 256 characters only , we can have their count in one iteration and then we can sort them in 256*log(256) time.

- rajeshkumarsinha12 January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can be done in O(n) time by primarily using a queue an a temp char var to keep track of the last known character. The queue will get populated every time a char is repeated and var last is used for comparison and will determine whether the current char looping through the string should be pushed to the queue or inserted to the resulting string.

string rearrange(string input) {
    queue<char> q;
    char last = ' ';
    string result;
    
    for (int i = 0; i < input.length(); i++) {
        if(last != input[i]) {
            result.insert(result.end(), input[i]);
            if(!q.empty() && q.front() != result.back()) {
                result.insert(result.end(), q.front());
                q.pop();
            }
        }
        else {
            q.push(input[i]);    
        }
        last = input[i];
    }
    return q.empty() == true ? result : NULL;
}

- CL October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This does not seem to work with "baa".

- Tooki October 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

dg

- dfgdg October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MyChar implements Comparable {

	public char c;
	public int count;

	public MyChar(char c, int count) {
		this.c = c;
		this.count = count;
	}

	@Override
	public int compareTo(Object arg0) {
		// TODO Auto-generated method stub
		int res = count-((MyChar)arg0).count;
		if(res != 0) {
			return res;
		}
		return ((MyChar)arg0).c-c;
	}

}

public static String reorder(String s){
		
		char[] arr = s.toCharArray();
		HashMap<Character, MyChar> map = new HashMap<Character, MyChar>();
		TreeSet<MyChar> set = new TreeSet<MyChar>();
		for(char c:arr){
			MyChar my_c = map.get(c);
			if(my_c == null){
				my_c = new MyChar(c,0);
				map.put(c, my_c);
			}
			set.remove(my_c);
			my_c.count++;
			set.add(my_c);
			
		}
		
		MyChar prev = null;
		for(int i =0; i<arr.length;++i){
			if(set.size() == 0){
				System.out.println("n"+i);
				return "no solution found";
			}
			MyChar curr = set.last();
			set.remove(curr);
			curr.count--;
			arr[i]=curr.c;
			if(prev!=null && prev.count>0){
			    set.add(prev);
			}
			prev = curr;
		}
		return String.valueOf(arr);
	}

- Anonymous October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MyChar implements Comparable {

	public char c;
	public int count;

	public MyChar(char c, int count) {
		this.c = c;
		this.count = count;
	}

	@Override
	public int compareTo(Object arg0) {
		// TODO Auto-generated method stub
		int res = count-((MyChar)arg0).count;
		if(res != 0) {
			return res;
		}
		return ((MyChar)arg0).c-c;
	}

}
public static String reorder(String s){
		
		char[] arr = s.toCharArray();
		HashMap<Character, MyChar> map = new HashMap<Character, MyChar>();
		TreeSet<MyChar> set = new TreeSet<MyChar>();
		for(char c:arr){
			MyChar my_c = map.get(c);
			if(my_c == null){
				my_c = new MyChar(c,0);
				map.put(c, my_c);
			}
			set.remove(my_c);
			my_c.count++;
			set.add(my_c);
			
		}
		
		MyChar prev = null;
		for(int i =0; i<arr.length;++i){
			if(set.size() == 0){
				System.out.println("n"+i);
				return "no solution found";
			}
			MyChar curr = set.last();
			set.remove(curr);
			curr.count--;
			arr[i]=curr.c;
			if(prev!=null && prev.count>0){
			    set.add(prev);
			}
			prev = curr;
		}
		return String.valueOf(arr);
	}

- Amsh October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple solution but not efficient would be to use backtracking, this would certainly solve the problem.

#include <iostream>
using namespace std;

string TakeOutChar(string input, int i)
{
	return input.substr(0, i) + input.substr(i+1, string::npos);
}

bool MakeUnique(string input, string uniqueString)
{
	if(input.length() == 0)
	{
		cout<<"Unique string found  :  "<< uniqueString<< endl;
		return true;
	}

	int uniqueStringLen = uniqueString.length();
	for(int i = 0; i < input.length(); ++i)
	{
		if(uniqueStringLen == 0 || uniqueString[uniqueStringLen - 1] != input[i])
		{
			if(MakeUnique(TakeOutChar(input, i), uniqueString + input[i]))
			{
				return true;
			}
		}
	}

	return false;
}

int main(int nArgs, char *args[]) {
	if(!MakeUnique(string(args[1]), ""))
	{
		cout<<"No unique strings found"<<endl;
	}
	return 0;
}

- MS October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You may also do a simple backtracking this solution is of course not an efficient one..

#include <iostream>
using namespace std;

string TakeOutChar(string input, int i)
{
	return input.substr(0, i) + input.substr(i+1, string::npos);
}

bool MakeUnique(string input, string uniqueString)
{
	if(input.length() == 0)
	{
		cout<<"Unique string found  :  "<< uniqueString<< endl;
		return true;
	}

	int uniqueStringLen = uniqueString.length();
	for(int i = 0; i < input.length(); ++i)
	{
		if(uniqueStringLen == 0 || uniqueString[uniqueStringLen - 1] != input[i])
		{
			if(MakeUnique(TakeOutChar(input, i), uniqueString + input[i]))
			{
				return true;
			}
		}
	}

	return false;
}

int main(int nArgs, char *args[]) {
	if(!MakeUnique(string(args[1]), ""))
	{
		cout<<"No unique strings found"<<endl;
	}
	return 0;
}

- MS October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose character occurences are x1 >= x2 >= ...>= xk
Solution will exist iff x1 - 1 <= x2 + x3 + ... + xk, that is for x1 characters we need x1 - 1 separators to achieve non-neighborhoud.
Suppose at some moment solution exists, let's prove that if we take 2 top characters, it will still exist.
x1 - 1 <= x2 + x3 + ... + xk # add x1 + 1 to both sides, n is length of string
2x1 <= n + 1
So we have
n + 1 >= 2x1 >= 2x2 >= 2x3
After we take 1 char from x1 and one from x2:
n - 1 >= 2x1 - 2 >= 2x2 - 2 >= 2x3
We have to prove that n - 1 >= 2x3
n - 1 >= x1+ x2 + x3 - 1 >= 3x3 - 1 >= 2x3, that is x3 >= 1, which is obviously true (unless we've exhausted all characters, then solution is trivial)

So we just have to take two top-frequency characters every time until there are no more characters, that is done with max-heap.
Also you should include characters themself when comparing frequencies (5, 'a') < (5, 'b') for example.

- emb October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution makes sense along with backtracking. So basically pick the character from a pool of largest character. Put it at 0th index and then recurse. In the recursion check the previous character and see if the previous character is same if same then pull the any different character and put in the current index. Recurse for the next state and do the same. Base cases is when you don't have any characters or when you have lot of same characters or same characters size is more than half the length of the string.

- aka[1] October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach is to first get a frequency hash for characters and then for each character place it in the first available position using greedy approach:

function getFreqOfChars(str) {
    var chars = str.split("");
    var result = {};
    for (var i = 0; i < chars.length; i++) {
        if (result[chars[i]]) {
            result[chars[i]]++;
        } else {
            result[chars[i]] = 1;
        }
    }
    return result;
}

function noAdjChars(str) {
    var freq = getFreqOfChars(str);
    var array = [];
    for (var char in freq) {
        array.push({char: char, freq: freq[char]});
    }

    array.sort(function(a, b) { return a.freq - b.freq;});    

    var result = new Array(str.length);    

    while (array.length > 0) {
        var char = array.pop();
        var placed = 0;
        for (var i = 0; i < str.length && placed < char.freq; i++) {                        
            if ((!result[i]) && (result[i - 1] !== char.char)) {
                result[i] = char.char;
                placed++;
            }
        }

        if (placed < char.freq) {
            return null;
        }        
    }

    return result.join("");
}

- ashish.kaila October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create an array arr of alphabet size with number of occurrences of each char.
2. Sort the string.
3. Then go through string and decrement values in arr for chars you've gone through,
If two subsequent chars are equal,determine first char unequal to the current one looking at arr.
Run binary search of this char on the remainings of the string.

Complexity ~O(n * logn)

- sergio471 October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n), one scan and even in place.

Assume you counter nPostponed and last postponed character.
Imagine that this is buffer of nPostponed x postponed characters.
In addition you have a last character that was copied to output.

So in each iteration you first try to take from the 'postponed' buffer if it is different from 'last'
Otherwise you take next character from source string. If it is equal to 'last' then it also must equal to postponed or postponed is empty. In this case you add it to postponed buffet - increment nPostponed
Otherwise you add this character to output and set 'last' equal to it.

At end, if postponed is not empty than task can't be done.

O(n), one scan and even in place

static boolean rearrange(char[] ar) {

        if (ar.length < 2) return true;

        int s = 0; // source;

        char last = ar[s++];
        int t = 1; // destination - first char already there

        char postponed = '?'; // buffer is empty it this value is ignored
        int nPostponed = 0;

        while (s < ar.length || nPostponed > 0) {

            // is character in postponed buffer ?
            if (nPostponed > 0 && postponed != last) {
                // Remove from postponed buffer
                ar[t++] = postponed;
                --nPostponed;
                last = postponed;
            } else {
                if ( ! (s < ar.length) ) {
                    // no more to take from
                    return false;
                }
                char c = ar[s++];
                if (c != last) {
                    ar[t++] = c;
                    last = c;
                } else {
                    // so it must equals postponed if the later is not empty
                    // Add to postponed buffer
                    ++nPostponed;
                    postponed = c;
                }
            }
        }

        return true;
    }

- boaznahum October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have almost exact the same initial idea with @NenadCro. But I don't like the cost of pop and push top elements repeatedly out of and into the heap. Or we could do better with decrease key of node in heap if we have access to heap node.
Then I have an O(n) run time algorithm without the heap. The idea is simple, please see the code. If we have the max occurrence of characters less or equal to n/2, then we can have valid output. We just put same chars together in a string t, and pick t[i] and t[halfLength+i] together to overwrite s.

class Solver{
public:
	bool rearrageString(string& s){
		if(s.empty()) return true;
		vector<int> charNums(52, 0);
		
		int maxNums=0;
		int n=s.size();
		for(int i=0; i<n; i++){
			charNums[ s[i]-'a' ]++;
			maxNums = max(maxNums, charNums[ s[i]-'a' ]);
		}
		
		if(maxNums>n/2) return false;
		string t;
		int count=0;
		for(int i=0; i<n; i++){
			if(charNums[ s[i]-'a' ]>0){
				t.append(charNums[ s[i]-'a' ], s[i]);
				count +=charNums[ s[i]-'a' ];
				charNums[ s[i]-'a' ] =0;
				if(count==n) break;
			}
		}
		
		int halfCount= n/2;
		for(int i=0; i<halfCount; i++){
			s[i*2]= t[i];
			s[i*2+1]= t[halfCount+i];
		}
		if(n%2!=0) s[n-1]=t[halfCount];

		return true;
	}
};

- plutoman October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

made two changes to code above, use ceiling (n+1)/2 instead of n/2. Add max occurrence char first to t. See modified code below.

class Solver{
public:
	bool rearrageString(string& s){
		if(s.empty()) return true;
		vector<int> charNums(52, 0);
		
		int maxNums=0, maxIdx=0;
		int n=s.size();
		for(int i=0; i<n; i++){
			charNums[ s[i]-'a' ]++;
			if(maxNums<charNums[ s[i]-'a' ]){
				maxNums = charNums[ s[i]-'a' ];
				maxIdx = i;
			}
		}
		
		if(maxNums>(n+1)/2) return false;
		string t;
		int count=0;
		//append the max occurrence char first
		t.append(maxNums, s[maxIdx]);
		count +=maxNums;
		charNums[ s[maxIdx]-'a' ] =0;
		for(int i=0; i<n; i++){
			if(charNums[ s[i]-'a' ]>0){
				t.append(charNums[ s[i]-'a' ], s[i]);
				count +=charNums[ s[i]-'a' ];
				charNums[ s[i]-'a' ] =0;
				if(count==n) break;
			}
		}
		
		int halfCount= (n+1)/2;
		for(int i=0; i<halfCount; i++){
			s[i*2]= t[i];
			s[i*2+1]= t[halfCount+i];
		}
		if(n%2!=0) s[n-1]=t[halfCount];

		return true;
	}
};

- plutoman October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, greedy

#include <map>

string rearrange(string str) {
	string result, last, temp;
	map<string, int> counts;
	map<string, int>::iterator it;
	multimap<int, string> remains;
	multimap<int, string>::reverse_iterator rit;
	int i;

	for (i = 0; i < str.size(); i++) {
		temp = str.substr(i, 1);
		it = counts.find(temp);
		if (it != counts.end()) {
			it->second++;
		} else {
			counts.insert(make_pair(temp, 1));
		}
	}

	for (it = counts.begin(); it != counts.end(); it++) {
		remains.insert(make_pair(it->second, it->first));
	}
	counts.clear();

	result = "";
	if (remains.size() > 0) {
		rit = remains.rbegin();
		if (rit->first * 2 - 2 >= str.size()) return "No valid output";
		last = "";
		while (remains.size()) {
			rit = remains.rbegin();
			if (last.compare(rit->second) == 0) rit++;
			i = rit->first;
			last = rit->second;
			remains.erase(next(rit).base());
			result.append(last);
			if (i > 1) remains.insert(make_pair(i - 1, last));
		}
	}

	return result;
}

- kyduke October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a simple solution that's O(n*log(n)) and doesn't require any character counting.

-Sort the array ( O(n*log(n) )
-Traverse the array and make sure no letter appears more than (n/2) times ( O(n) )
-shift elements in odd positions (1,3,5,..) the array by (n/2+1) if n is even or by (n+1)/2 if n is odd.
-you are done :)

- Anonymous October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-Sort the array O(n*log(n))
-Traverse the array and make sure no letter appears more than (n/2) times O(n)
-Shift the items in the odd positions (1,3,5,..) by (n/2+1) if n is even and by (n+1)/2 if n is odd O(n)
-you are done :)
Proof of correctness:
consider any block of letters starting at position x and ending at position y;
1- Since every other element of this block is replaced by a letter of another block, there would be no duplicates in this block.
2- Elements removed from this block will be moved another blocks and they would not be adjacent

- Anonymous October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-Sort the array O(n*log(n))
-Traverse the array and make sure no letter appears more than (n/2) times O(n)
-Shift the items in the odd positions (1,3,5,..) by (n/2+1) if n is even and by (n+1)/2 if n is odd O(n)
-you are done :)
Proof of correctness:
consider any block of letters starting at position x and ending at position y;
1- Since every other element of this block is replaced by a letter of another block, there would be no duplicates in this block.
2- Elements removed from this block will be moved another blocks and they would not be adjacent

- koosha.nejad October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity O(L) where L is the string length; space O(L)

public static  char[] reorder(String s){
	if(s==null || s.length()==0 || (s.length()==2 && s.charAt(0)==s.charAt(1)))
		return "No valid Output.".toCharArray();
	boolean problem=false;
	int i=0,j=s.length() -1;
	char [] temp= s.toCharArray();
	while((i+ 1 ) < j){
		if(temp[i] == temp[i+1]){
			if(temp[i] == temp[j] || (j+1 <temp.length && temp[i]==temp[j+1] ))
				problem=true;
			else{ 
				temp[i+1]=temp[j];
				temp[j]=temp[i];
				problem=false;
				i++;
			}
			j--;
		}
		else
			i++;
	}
			
	if(problem)
		return "No valid Output.".toCharArray();
	
	return temp;
				
}

- toiss October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not correct for the string aaaaccdf. Output: afaccada

- roysongbb10 October 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private String noRepeatingChars(String input) {

	Map<Character, Integer> histogram = new LinkedHashMap<Character, Integer>();
	
	char[] chars = input.toCharArray();
	for (int i = 0; i < chars.length; i++) {
		char c = chars[i];
		if (histogram.contains(c)) {
			histogram.put(c, histogram.get(c) + 1);
		} else {
			histogram.put(c, 1);
		}
	}

	String output = “”;
	Character prevChar = null;
	while (!histogram.isEmpty()) {
		Iterator<Map.Entry<Character, Integer>> iterator;
		for (iterator = histogram.iterator(); iterator.hasNext() ;) {
			Map.Entry<Character, Integer> entry = iterator.next();
			if (entry.key == prevChar) return “INVALID”;
			prevChar = entry.key;
			output = output + prevChar;
			entry.value—;
			if (entry.value == 0) iterator.remove();
		}
	}
	return output;
}

- curtis October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code does not compile. But if assuming this code


private static String noRepeatingChars(String input) {

Map<Character, Integer> histogram = new LinkedHashMap<Character, Integer>();
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (histogram.containsKey(c)) {
histogram.put(c, histogram.get(c) + 1);
} else {
histogram.put(c, 1);
}
}

String output = "";
Character prevChar = null;
while (!histogram.isEmpty()) {
Iterator<Map.Entry<Character, Integer>> iterator;
for (iterator = histogram.entrySet().iterator(); iterator.hasNext() ;) {
Map.Entry<Character, Integer> entry = iterator.next();
if (entry.getKey() == prevChar) return "INVALID";
prevChar = entry.getKey();
output = output + prevChar;
entry.setValue(entry.getValue() - 1);
if (entry.getValue() == 0) iterator.remove();
}
}
return output;
}

=========================
Then it fails for "aabbb".

- mail2abin October 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- Anonymous October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- Ravi October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time 

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- Ravi October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time 

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- Ravi October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- alpha October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character

4)We have printed all the lowest freq character and every other characters with the same number of time 

5)printing order will be from high to low freq character like abcd abc ab a

6)Repeat the same process for the second lowest freq and so on


so total running time => O(n)

- Ravi October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a shorter one in scala...

def rearrange(input: String): String = {
val list = input.groupBy { x => x }.values.flatten
val k = input.groupBy { x => x }.mapValues { x => x.size }
if (k.values.max > Math.ceil(input.length() / 2.0))
"NA"
else {
val part = k.toSeq.sortWith(_._2 > _._2)
.flatMap { elem => List.fill(elem._2)(elem._1) }
val (x, y) = if (s.length() % 2 == 0) part.splitAt(list.size / 2)
else part.splitAt(list.size / 2 + 1)
val p = ((x zip y).flatMap { x => List(x._1, x._2) }).mkString
if(x.size > y.size)
p + x.head
else p
}

}

- mail2abin October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ht

- Larry Wang October 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

d

- larrywang2014 October 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I don't get why all the nlogn answers are voted up, this is a very simple O(n) problem. Simply iterate from left and when you encounter two consecutive characters, send another iterator to search for the next character which isnt the two characters encountered, and replace the second one with that. Then do this from right to left. C++ code:

string noRepeats(string s) {
	
	// assume len at least 2
	int idx = 1;
	int end = 2;
	for (; idx < s.size(); idx++) {
		if (s[idx] == s[idx - 1]) {
			end = max(end, idx + 1);
			while (end < s.size() && s[end] == s[idx]) end++;
			if (end == s.size()) break;
			swap(s[idx], s[end]);
		}
	}

	for (idx = s.size() - 1; idx >= 0; idx--) {
		if (s[idx] == s[idx + 1]) {
			end = min(end, idx - 1);
			while (end >= 0 && s[end] == s[idx]) end--;
			if (end == -1) break;
			swap(s[idx], s[end]);
		}
	}

	for (int i = 1; i < s.size(); i++) {
		if (s[i] == s[i - 1]) {
			return "";
		}
	}

	return s;
}

- Anonymous October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Seems not work for "aabcdaafaaaabrrrtaaaeecccccaaddaaa".
It should output "acacacadacaraeabacaradabadataearcf" but your code will output "".

I have not seen any working O(n) algo so far.

- jiangok2006 November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

using char_count_t = pair<int, char>;
using char_count_queue_t = priority_queue<char_count_t, 
	vector<char_count_t>, std::greater<char_count_t>>;

string rearange(string&& input) {
	sort(input.begin(), input.end());

	map<char, int> count;
	for (char c : input)
		count[c]++;

	char_count_queue_t queue;
	for (auto &counted_char : count) {
		queue.push(counted_char);
	}

	string result;
	auto prev = make_pair('\0', 0);
	while (!queue.empty()) {
		auto counted_char = queue.top(); queue.pop();
		counted_char.second--;
		if (prev.second)
			queue.push(prev);
		prev = counted_char;

		result.push_back(counted_char.first);
	}

	if (prev.second)
		return string("no valid output");

	return result;

}

- jarek October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Run time: O(n)
Assumptions:
1) Input is sorted

Python:

def no_repeat(inp, flip_side=False):
        i = 0
        while i < len(inp) - 1:
                if inp[i] == inp[i+1]:
                        if inp[i] == inp[-1]:
                                if flip_side:
                                        return False
                                else:
                                        rev_inp = list(inp)
                                        rev_inp.reverse()
                                        return no_repeat("".join(rev_inp), True)
                        else:
                                inp = inp[:i+1] + inp[-1] + inp[i+1:-1]
                i+=1
        
        return inp

- uday November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution:

string=input()
def recognization(string):
    characters=dict()
    i=0
    for i in range(len(string)):
        if string[i] not in characters:
            characters[string[i]]=1
        else:
            characters[string[i]]+=1
    return characters
mascharacter=recognization(string)
masch=[]
for i,j in mascharacter.items():
        masch.append([j,i])
print(masch)
def canwerearrange(characters):
    mas=[]
    answer=""
    for i in characters.values():
        mas.append(int(i))
    mas=sorted(mas)
    s=0
    for i in range(len(mas)-1):
        s+=mas[i]
    if mas[len(mas)-1]-s>1:
        answer+="no"
    else:
        answer+="yes"
    return answer
def sort(ch):
    mas=[]
    mas1=[]
    for j in range(len(ch)-1):
        for i in range(len(ch)-1):
            if ch[i][0]<ch[i+1][0]:
                mas.append(ch[i+1][0])
                ch[i+1][0]=ch[i][0]
                ch[i][0]=mas[0]
                mas1.append(ch[i+1][1])
                ch[i+1][1]=ch[i][1]
                ch[i][1]=mas1[0]
            mas=[]
            mas1=[]
    return ch
def rearrange(string,answer,ch):
    rearstring=""
    s=0
    i=0
    if answer!="no":
        for i in range(len(string)):
            if i>0 and  ch[s][1]!=rearstring[i-1]:
                if ch[s][0]>0:
                    rearstring+=ch[s][1]
                    ch[s][0]-=1
                    ch=sort(ch)
            elif i==0:
                if ch[s][0]>0:
                    rearstring+=ch[s][1]
                    ch[s][0]-=1
                    ch=sort(ch)
            elif i>0 and ch[s][1]==rearstring[i-1]:
                s+=1
                if ch[s][0]>0 :
                    rearstring+=ch[s][1]
                    ch[s][0]-=1
                    s-=1
                    ch=sort(ch)
    else:
        print("No valid output")
    return(rearstring)
print(rearrange(string,canwerearrange(recognization(string)),sort(masch)))

input:

aaaaaaabbbbccc

output

ababacacababac

- intainer7 November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution running in O(n logN).
using heap to keep the node with max value.

#include<cstdint>
#include <string>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

struct node {
	char value;
	int count;
	node(char v, int c):value(v), count(c){}
};

bool larger(char prev, char next)
{
	return prev < next;
}
string find_norepeat_str(vector<char>& input)
{
  string result;
  vector<node*> nodes;
  sort(input.begin(), input.end(), larger);
  char cur = INT8_MIN;
  int left = input.size();
  int count = 0;
  for(int i = 0; i < input.size(); i++)
  {
    if (cur == INT8_MIN)
    {
      cur = input[i];
      count++;
    } else if (cur == input[i])
    {
      count++;
    } else {
      nodes.push_back(new node(cur, count));
      cur = input[i];
      count = 1;
    }
  }
  nodes.push_back(new node(cur, count));
  Heap heap(nodes);
  node * longest = 0;
  while (left>0)
  {
    if (!longest || longest->count == 0)
    {
      longest = heap.extract();
    }

    while (longest && longest->count>0)
    {
      node * next = heap.extract();
      if (!next)
      {
        if (longest->count == 1)
        {
          result.push_back(longest->value);
          return result;
        }else
          return "invalid input";
      }
      if(result.length()==0 || (result.length() > 0 && result[result.length()-1] != longest->value))
      {
          result.push_back(longest->value);
          longest->count--;
          left--;
      }
      result.push_back(next->value);
      next->count--;
      left --;
      if (next->count)
        heap.add(next);

    }
  }
  return result;
}

- hankm2004 November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def permutate(s):
    l = list(s)
    mutated = True
    while mutated:
        mutated = False
        for j in range(len(l) - 2):
            if l[j] == l[j + 1] and l[j + 1] != l[j + 2]:
                l[j + 1], l[j + 2] = l[j + 2], l[j + 1]
                mutated = True
    if l[-1] == l[-2]:
        return None
    return l

- tkachoff July 20, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More