Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

yes, the roller can jump and can cover blocks which are not damaged. Also the roller can repeate the same block multiple times but count as 1. The question is min number of blocks ( in my view unique) which roller pass

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

i too did not understand the question clearly.
can the roller jump from one to another damage part.
In the example you gave, what if K=2
Example for above case with K=2, N=3(2,3,6)
_ * * _ _ * _ _ _
1 2 3 4 5 6 7 8 9
would the ans be
4(2,3,5,6) : [2,3],[5,6] if the roller can jump from one to another damaged part
or
5(2,3,4,5,6): when roller has to move block by bock

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

Answer would be 4(2,3,5,6). The rollar can jump

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

Runs in O(n) time and O(1) space:

``````using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

public class Test
{
public static void Main()
{
{
Blocks = CreateBlocks("_**_**_"),
RollarSize = 3
};

}

public static List<Block> CreateBlocks(string blocks)
{
var model = new List<Block>();

foreach(var block in blocks)
{
model.Add(new Block { IsDamaged = block == '*' });
}

return model;
}
}

public class Block
{
public bool IsDamaged { get; set; }
public bool IsRepaired { get; private set; }

public void Repair()
{
IsRepaired = true;
}

public bool IsNew()
{
return !IsDamaged && !IsRepaired;
}

public bool NeedsRepair()
{
return IsDamaged && !IsRepaired;
}
}

{
public List<Block> Blocks { get; set; } = new List<Block>();
public int RollarSize;

public int Repair(int pos)
{
int count = 0;

if (pos < 0 || pos + RollarSize > Blocks.Count) return 0;

for (int i = 0; i < RollarSize; i++)
{
if (!Blocks[pos + i].IsRepaired)
{
Blocks[pos + i].Repair();
count++;
}
}

return count;
}

public int CountMinRepairs()
{
int count = 0;

for (int i = 0; i < Blocks.Count; i++)
{
var block = Blocks[i];
var newBlocks = RollarSize;
int pos = 0, cur = 0;
bool wasRepaired = false;

if (!block.NeedsRepair()) continue;

for (int j = i-(RollarSize-1); j <= i; j++)
{
if (j < 0 || j + RollarSize > Blocks.Count) continue;

cur = 0;

for (int k = 0; k < RollarSize; k++)
{
if (Blocks[j+k].IsNew()) cur++;
}

if (cur <= newBlocks)
{
newBlocks = cur;
pos = j;
wasRepaired = true;
}
}

if (wasRepaired)
{
count += Repair(pos);
}
}

return count;
}
}``````

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

What about expanding the vector and simply iterate throughout it?

``````#include <iostream>
#include <vector>
#include <map>

std::map<int, bool>expandVector(const std::vector<int> &v) {
if (v.size() == 0)
return std::map<int, bool>();
std::map<int, bool> result;
int i = 0;
while (i<v.size()) {
result.insert(std::pair<int, bool>(v.at(i), true));
if ((i+1) == v.size())
return result;
for (int j=v.at(i);j<v.at(i+1);j++)
result.insert(std::pair<int, bool>(j, false));
i++;
}
return result;
}

int minNumberOfBlocks(int rollarLength, const std::vector<int> &v) {
int newPos = it->first + rollarLength;
++it;
int blocksCovered = 1;
std::cout << "new pos: " << newPos << std::endl;
if (it->first <= newPos) {
blocksCovered++;
std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
}
else if (it->first > newPos)
if (it->second == true) {
newPos = it->first + rollarLength;
blocksCovered++;
std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
} else {
std::cout << "Jumping " << it->first << std::endl;
}
}
return blocksCovered;
}

int main() {
std::vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(6);
//v.push_back(10);
/*std::map<int, bool> expanded = expandVector(v);
std::map<int, bool>::iterator it;
for (it=expanded.begin(); it!=expanded.end(); ++it)
std::cout << it->first << " => " << it->second << std::endl;*/
std::cout << "number of blocks " << minNumberOfBlocks(3, v);
}``````

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

Question is clear.
Some buddies gave the solutions. But, I don't understand what approach they followed.

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

Time complexity: O(n*k); n is the size of string
Space comp: O(n) ; boolean array

Idea is simple to iterate through string and check if current block is damaged or not. If damaged then place rollar. Now, from that position to rollar end position, check if by placing another rollar, do we cover any new damaged region? To check new vs. old damaged region, I am maintaining boolean vector which gets set when rollar is placed.

``````bool coversDamage(int start, int end , string &s, vector<bool> & covered){
bool found = false;
for(int i = 0 ; i < s.length();++i){
if(s[i]=='*' && i>=start && i<=end && !covered[i]){
found= true;
covered[i] = true;
}
}
return found;
}
int getRepairCount(string & s, int k){
int pos = 0;
int len = s.length();
vector<bool> covered(len, false);
int minRep = INT_MAX;
int repair = 0;
while(pos<len){
if(s[pos]!='*'){
++pos;
continue;
}else{
int end = pos+k-1;
for(int i = 0 ; i < k ; ++i)
covered[pos+i] = true;
int i = pos+1;
while(i<=end){
if(coversDamage(i,i+k-1, s, covered)){
if(i+k-1<len)
end = i+k-1;
else
end = len-1;
}
++i;
}
//cout << "DBG: " << pos << ", " << end << endl;
repair += (end-pos+1);
pos = end+1;
}
}
return repair;
}

int main(){
//string damage = "_**__*___";
string damage = "_*_*_*_*___";
int k = 2;
cout << getRepairCount(damage, k);
return 0;
}``````

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

this will give wrong answer for input "_***_*** " and k=2.

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

this will give wrong answer for input "_***_*** " and k=2.

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

This is a dynamic programming problem, variant of knapsack. For me, it's easiest to think about these problems in terms of a recursive problem. Then solve for your base case(s), and recurse.

For example (using string for simplicity),

1) we know that if the String doesn't contain a *, your result is 0 "_ _ _ _ _ ".

2) we also know that if your string size is smaller than k, your result is 1 since you'll only need to make one move so your result is 1 "_ * _ " where k = 3.

3) otherwise what do we do? we can iterate over the other possible sub-strings where we remove k items from different places and recurse and return the minimum of those recursions.

4) Great! This solves the problem, but we're doing a LOT of extra work here generating permutations through our recursion. Are there subproblems we're solving again and again? If so, why not store those results so we don't compute them again? Memoization is exactly what this is. You can keep your recursive solution you just drew up and add another parameter to store your results as you go. Or you can refactor into an iterative solution--a little harder to do as it's not always intuitive.

Hope this helps!

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

not sure if I understood correctly the problem statement.

number of blocks = (last index of Damaged - first index of damaged) + 1
example above: (6 - 2) + 1 = 5,
other example, 1,2,3,4,5,6,7,8,9,10,11,12 N = 4(4,6,8,10). Ans would be 10 - 4 + 1 = 7 (4,5,6,7,8,9,10).

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

For your example ans would be 6(4 5 6 8 9 10)

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

``````#include <stdio.h>
#include <stdlib.h>

using namespace std;

int get_block_size(int all[], int all_size, int damage[], int damage_size, int rollar)
{
int start_index = 0, end_index = 0;
int size = 0;

for(start_index = 0; start_index < damage_size; start_index++)
{
if(damage[start_index] != 0)
{
break;
}
}

for(end_index = damage_size - 1; end_index >- 0; end_index--)
{
if(damage[end_index] != 0)
{
break;
}
}

int start   = damage[start_index];
int end     = damage[end_index];

while(all[start_index] != start)
{
start_index++;
}

while(all[end_index] != end)
{
end_index--;
}

while(start_index < end_index)
{
bool found = false;

for(int i = start_index; i < rollar + start_index; i++)
{
if(damage[i] != 0)
{
found = true;
size++;
}
}

if(found)
{
start_index += rollar;
}

found = false;

for(int i = end_index; i > end_index - rollar; i--)
{
if(damage[i] != 0)
{
size++;
}
}

if(found)
{
end_index -= rollar;
}
}
return size;
}

int main(int argc, char** argv)
{
int all_road[]       = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int damage_road_1[]  = {0, 2, 3, 0, 0, 6, 0, 0, 0, 0 };
int damage_road_2[]  = {0, 0, 0, 4, 0, 6, 0, 8, 0, 10};
int rollar_size      = 0;

rollar_size = 3;

rollar_size = 2;
return 0;
}``````

block size 1 = 5
block size 2 = 6

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

for the case _ _ * *_ _ * * *_ _ and k=2, the output of above algorithm will be 7

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

Dp

``````#include<bits/stdc++.h>
using namespace std;

#define MAX 1005

int dp[MAX][MAX];

int k;
string s;

int compute(int i,int j)
{
if(i>=s.size())
return 0;

if(dp[i][j]!=-1)
return dp[i][j];

dp[i][j] = INT_MAX;
if(s[i]=='_')
dp[i][j] = min(compute(i+1,max(j-1,0)),compute(i+1,k-1)+1);
else{

if(j>0)
dp[i][j] = min(compute(i+1,max(j-1,0)),compute(i+1,k-1)+1);
else
dp[i][j] = compute(i+1,k-1)+1;
}
return dp[i][j];
}

int main()
{
memset(dp,-1,sizeof(dp));
cin>>s;
cin>>k;

cout<<compute(0,0)<<endl;
return 0;
}``````

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

could you please explain the logic

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

I just checked the algorithm for input "_ _ * _ * _ * _ *_ _" and k=2, Output was 4. It only returns the number of damaged locations.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````public int numberOfBlocks(String[] array) {
int start = 0, end = 0;
System.out.println(array.length);
for (int i = 0; i < array.length; i++) {
if (array[i].equals("*")) {
start = i;
break;
}
}
for (int i = array.length - 1; i >= 0; i--) {
if (array[i].equals("*")) {
end = i;
break;
}
}
return end-start+1;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

int numberOfBlocks(std::string &array) {
size_t first = array.find_first_of('*');
size_t last = array.find_last_of('*');

if (first != string::npos && last != string::npos && first != last) {
return (last - first + 1);
}
return -1;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

int numberOfBlocks(std::string &array) {
size_t first = array.find_first_of('*');
size_t last = array.find_last_of('*');

if (first != string::npos && last != string::npos && first != last) {
return (last - first + 1);
}
return -1;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````int numberOfBlocks(std::string &array) {
size_t first = array.find_first_of('*');
size_t last = array.find_last_of('*');

if (first != string::npos && last != string::npos && first != last) {
return (last - first + 1);
}
return -1;
}``````

Comment hidden because of low score. Click to expand.

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.