## Amazon Interview Question for SDE1s

Country: India
Interview Type: Written Test

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

``````def min_coloring(k, s):
if not isinstance(s, str) or not isinstance(k, int):
return -1

if len(s) == 0:
return 0

curr_seq_len = 1
result = 0
for i in xrange(0, len(s)-1):
if s[i] == s[i+1]:
curr_seq_len += 1
else:
result += curr_seq_len / k + (1 if curr_seq_len % k > 0 else 0)
curr_seq_len = 1
result += curr_seq_len / k + (1 if curr_seq_len % k > 0 else 0)

return result``````

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

I think your solution might be incorrect.
Consider the example k=3 and str=rrgg.
Your solution gives the answer as 2. But clearly it should be -1. As this coloring cannot be achieved.

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

``````static int min_coloring(int num , String s) {
int count =0;
char arr[] = s.toCharArray();
int i=1;
int currentInterval=1;
boolean isSubStringSizeMoreThanK=false;
while( i < arr.length){
if(arr[i] == arr[i-1] ){
currentInterval++;
}
if(arr[i] != arr[i-1] || i == arr.length - 1){
if(currentInterval < num){
count++;
}else{
isSubStringSizeMoreThanK=true;
count +=  (int)Math.ceil((double)currentInterval/num);
}
currentInterval =1;
}
i++;
}
if(isSubStringSizeMoreThanK){
return count;
}else{
return -1;
}
}``````

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

``````static int min_coloring(int num , String s) {
int count =0;
char arr[] = s.toCharArray();
int i=1;
int currentInterval=1;
boolean isFirst=false;
int isSubStringSizeMoreThanK=0;
while( i < arr.length){
if(arr[i] == arr[i-1] ){
currentInterval++;
}
if(arr[i] != arr[i-1] || i == arr.length - 1){
if(currentInterval < num){
count++;
}else{
if(i == currentInterval){
isFirst = true;
}
isSubStringSizeMoreThanK++;
count +=  (int)Math.ceil((double)currentInterval/num);
}
currentInterval =1;
}
i++;
}
if(isSubStringSizeMoreThanK > 0){
if(isSubStringSizeMoreThanK ==1 && isFirst){
count++;
}
return count;
}else{
return -1;
}
}``````

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

``````using namespace std;

bool isEligible(int k, const string& str) {
if(str.size() < k) return false;

char c1 = str.at(str.size()-1);
char c2 = str.at(str.size()-2);
char c3 = str.at(str.size()-3);

if(c1 == c2 && c1 == c3) return true;
return false;
}

int colour_iterative(int k, const string& str) {
if(!isEligible(k, str)) return -1;

int i=0, num =0;
while(i<str.size()) {
int color = 1;
int c = str.at(i);

while(i+color < str.size() && str.at(i+color) == c) ++color;
num += ceil((double)color/k);
i+=color;
}

return num;
}``````

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.