Given an array, put all repeated characters together.

Question

Ionut · Accepted Answer

depending on the requested space complexity you don't have to sort the chars inside the string.
there are only 26 chars in the alphabet. so, you can have a map or an int array with 26 counters. each counter i will say how many times the char 'a' + i appears in the string.

then iterate once over the string incrementing the specific counters and in the end display the map or array.

Sigiloso · Answer

For the previous answer, you should not assume that the characters are alpha only. You should plan to have to accomodate  for all possible chars, which simply means you have an array of size 256.

Sigiloso · Answer

simply perform the sorting according to their ASCII values.

dev86 · Answer

#include 
#include 
#include 

using namespace std;

int main()
{
    //declare variables
    const int size = 2000; // N
    const int startRange = 97;
    const int endRange = 122;
    const int length = endRange - startRange + 1;
    vector arr(size);
    vector newArr(length);
    char ch = ' ';

    //initialize character array in O(N)
    srand(time(NULL));
    for(int i = 0; i < size; i++) {
        arr[i] = (char) (rand() % length + startRange);
    }

    //sort array in O(Nlong(N))
    sort(arr.begin(), arr.end());

    //combine similar characters in O(N)
    for(int i = 0, j = -1; i < size; i++) {
        if( arr.at(i) == ch) {
            newArr.at(j).append(1, ch);
        } else {
            j++;
            ch = arr.at(i);
            newArr.at(j) = ch;
        }
    }

    for(int i = 0; i < newArr.size(); i++) {
        cout << newArr[i] << endl;
    }

    return 0;
}

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas