Google Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview




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

#include <iostream>
using namespace std;

void printRythms(string str, int idx, char cmax, int n, int &count)
{
    if (idx == n) {
        count++;
        cout << str << endl;
        return;
    }
    for (char c = 'A'; c <= cmax; c++) {
        str[idx] = c;
        printRythms(str, idx+1, max(cmax, char(c+1)), n, count);
    }
    
}
int main() {
    const int n = 4;
    int count = 0;
    string str;
    str.insert(0, n, 'A');
    printRythms(str, 0, 'A', n, count);
    cout << count << endl;
	return 0;
}

- radek April 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Grt bro,
Its my dumbness even explaining her plenty of times, I did not see simple thing that only possible character is 1 more than the last character start FROM A.

Others pls see above explanation.

- nitinguptaiit May 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if n > 26? What chars do we need to use then? AA, BB etc?

- Sithis April 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

interviewer did not told about that neither i asked,
i believe its not important, you can assume some other character or numbers ...so its regardless
like we can use small alphabet (a,b,c) or numbers 1,2,3 etc

- nitinguptaiit April 19, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Naive approach :
+ generate all permutation on length n and put them in a set ( sorted bst, so already lexicographical order )
+ Iterate over the set and generate a normalize form.
For example, AAA -> 111, AAB->112, AAC->112, ... BBB -> 111
+ Keep track of already seen normalized forms and discard it while building result set.

- Code Reviewer April 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that i answered and coded too.

- nitinguptaiit April 19, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

dp(i, j) for making a rhyme of length of i you have used j distinct endings i.e A, B,C etc..( i, j) --> (i - 1, j - 1) + (i - 1, j ) * (j)

ans for n : (n,1) + (n,2) ... (n,n)

- bfmrck April 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You just gave bell number recursive eq. Which I already mentioned.

- nitinguptaiit April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;

void print_possible_combination(int rhythm_lines_count, int character_index, int combination_length, string combination_str){
    if(combination_length == rhythm_lines_count && combination_str.size() > 0){
        cout << combination_str << endl;
        return;
    }
    else{
        for(int i=0; i<=character_index; i++){
            char c = 'A' + i;
            print_possible_combination(rhythm_lines_count, i+1, combination_length + 1, combination_str + c);
        }
    }
}

int main(){
    int count; cin >> count;
    print_possible_combination(count, 0, 0, "");
}

- Anonymous May 21, 2019 | 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