## Google Interview Question for Software Engineers

• 4

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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

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).

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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 ..

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

Does this work for 'abccc'?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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"

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"

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";
}

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)
}
front.occ--;
if (front.occ > 0)

}

return res.toString();
}

}``````

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.

Comment hidden because of low score. Click to expand.
0

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"

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.

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).

Comment hidden because of low score. Click to expand.
0

Doesn't work for abccc

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)

Comment hidden because of low score. Click to expand.
0

Thanks for correcting me

Comment hidden because of low score. Click to expand.
0

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.

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;
}``````

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

This does not seem to work with "baa".

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

dg

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++;

}

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){
}
prev = curr;
}
return String.valueOf(arr);
}``````

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++;

}

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){
}
prev = curr;
}
return String.valueOf(arr);
}``````

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;
}``````

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;
}``````

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.

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.

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;
}

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("");
}``````

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)

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
++nPostponed;
postponed = c;
}
}
}

return true;
}``````

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;
}
};``````

Comment hidden because of low score. Click to expand.
0

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;
}
};``````

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;
}``````

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 :)

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

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

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;

}``````

Comment hidden because of low score. Click to expand.
0

Not correct for the string aaaaccdf. Output: afaccada

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;
}``````

Comment hidden because of low score. Click to expand.
0

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".

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)

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)

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)``````

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)``````

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)

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)``````

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)
else p
}

}

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

``ht``

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

d

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;
}``````

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

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

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;``````

}

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``````

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=[]
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:
else:
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
rearstring=""
s=0
i=0
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``

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)

}
}
return result;
}``````

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``````

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.

### 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.