Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

Lets say you have an array A = **###***#**##*###*#* and you have another array B.

Step 1: What you can do is go through array A and where a sequence of either * or # starts at index i, place how many are in that sequence at the index i in array B. In this case you'd have something like 20300300120201300111, where each non-zero value is the number of * or # in a sequence starting at that index i in array A.

Step 2: Now go through B using two pointers: x and y. You are only comparing non-zero values. make x point to the first non-zero value and have y be the next one over. if they are equal, save the index and value of x. Now make x point to y and iterate y again to the next one. if that value isn't greater than the one you saved, don't overwrite your saved index and value. keep going to the end. you'll have the index of the start of the sequence and how large it is (where the value you saved should be doubled, since it accounts for only either *'s or #'s not the full sequence of *'s and #'s)

It takes O(N) for Step 1, and O(N) for Step 2, which is O(2N) = O(N) runtime overall. You have O(N) space as well for the array you make.

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

This seems correct:

``````import std.stdio;
import std.string;
import std.exception;
// Given an array containing only stars '*' and hashes '#' . Find longest contiguous sub array that will contain equal no. of stars '*' and hashes '#'.

int CountSymbols(string data, char sym)
{
if (!data.length) return 0;
return  (data[0] == sym ? 1 : 0) + CountSymbols(data[1..\$], sym);
}

unittest
{
assert(0 == CountSymbols("", '#'));
assert(1 == CountSymbols("#", '#'));
assert(2 == CountSymbols("##", '#'));
assert(2 == CountSymbols("*##", '#'));
assert(2 == CountSymbols("##*", '#'));
assert(2 == CountSymbols("#*#", '#'));
assert(0 == CountSymbols("##", '*'));
}

string FindSubArray(char sym1, char sym2)(string data)
{

auto sym1c = CountSymbols(data, sym1);
auto sym2c = CountSymbols(data, sym2);
enforce(sym1c + sym2c == data.length, "String should contain only "~sym1~" or "~sym2~" symbols");
if (sym1c == sym2c) return data;

string tail = FindSubArray!(sym1,sym2)(data[1..\$]);
}

unittest
{
assert(FindSubArray!('#','*')("") == "");
assertThrown(FindSubArray!('#','*')("###***A"));

assert(FindSubArray!('#','*')("###***") == "###***");
assert(FindSubArray!('#','*')("####***") == "###***");
assert(FindSubArray!('#','*')("###****") == "###***");
assert(FindSubArray!('#','*')("#*#*#****") == "#*#*#*");
}

int main(string[] argv)
{
assert(FindSubArray!('#','*')("") == "");
assertThrown(FindSubArray!('#','*')("###***A"));

assert(FindSubArray!('#','*')("###***") == "###***");
assert(FindSubArray!('#','*')("####***") == "###***");
assert(FindSubArray!('#','*')("###****") == "###***");
assert(FindSubArray!('#','*')("#*#*#****") == "#*#*#*");

return 0;
}``````

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

I am trying to author your algorithm using non resursive solution, however its failing for below two cases, Can you suggest why ?

``````assert(FindSubArray!('#','*')("###****") == "###***");
assert(FindSubArray!('#','*')("#*#*#****") == "#*#*#*");
private static void findlongestseq()
{
//char[] str = "**###***#**##*###*#*".ToCharArray();
char[] str = "###****".ToCharArray();
int[] b = new int[str.Length];
int i = 0;
while (i < str.Length)
{
char c = str[i];
int count = 0;
int index = i;
while (index<str.Length && c == str[index] )
{
count++;
index++;
}
bool isFirst = true;
index=i;
while (count >= 1)
{
if (isFirst)
{
b[index] = count;
isFirst = false;
}
else
{
b[index] = 0;
}
count--;
index++;
}
i = index;
}
i=0;
int j = 0;
int maxfound = -1;
int starterindex = 0;
while (i < str.Length)
{
while (i < str.Length && b[i] == 0)
{
i++;
}
j=i+1;
while(j< str.Length && b[j] == 0)
{
j++;
}
if (i < str.Length && j < str.Length)
{
if (b[i] == b[j])
{
if (b[i] > maxfound)
{
maxfound = b[i];
starterindex = i;
}
}
}
j = i;
i++;
}
if (maxfound != -1)
{
Console.WriteLine("Longest string found is ");
int counter = maxfound * 2;
while ( counter> 0)
{
Console.Write(str[starterindex]);
starterindex++;
counter--;
}
}
else
{
Console.WriteLine("NOP");
}

}``````

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

1. Define a block as one that has equal number of *s and #s. A block will have a starting position and an ending position. The block(s) that has the maximum difference between these numbers is/are the answer.
2. Create an empty linked list to hold the blocks.
3. When you encounter a "change" (* followed by # or vice-versa), add a block to the linked list.
4. When you are done reading the array, the linked list will have only blocks.
5. Now read the linked list. Pick the first block. Look at the next block and see if they 'touch' each other (ending position of first one is one less than starting position of the next). If they are throw out both the blocks, coalesce them, and insert the new block in its place.
6. If the next block is not contiguous, go back to the original array and check if there is a * and # combination with one on left or one on right. If so, expand the current block (by changing start and end).
7. Repeat this process for each block in the linked list.

If the linked list is empty, it means the array consists of only one type of symbol.

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

``````#include "stdio.h"

namespace
{
const char* FindLongestStarsAndHashes(const char* str, int& maxLength)
{
const char* longest = NULL;
maxLength = 0;

const char* p = str; // our main scanner

int oldRun = 0;
int run = 0;
char cur = *p; // # or *
++p;
++run;

while (*p)
{
if (*p == cur) ++run;

else // time for ending current run
{
if (oldRun > 0)
{
int localMax = oldRun > run ? run : oldRun;

if (localMax > maxLength)
{
maxLength = localMax;
longest = p - run - localMax; // tricky part
}
}

oldRun = run;
cur = *p;
run = 1;
}

++p;
}

if (oldRun > 0)
{
int localMax = oldRun > run ? run : oldRun;

if (localMax > maxLength)
{
maxLength = localMax;
longest = p - run - localMax;
}
}

return longest;
}

void Solve(const char* str)
{
int length = 0;

const char* longest = FindLongestStarsAndHashes("*###*****#######***", length);

if (longest)
{
for (int aa = 0; aa < (length * 2); ++aa, ++longest)
printf("%c", *longest);

printf("\n");
}
else
printf("sorry\n");
}
}``````

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

/*************************************************
Author:Zhou You
Time:2014.09.09
*************************************************/
#include <iostream>
#include <cstdio>

using namespace std;

struct matrix_element
{
public:
matrix_element():
star_num_(0),
hash_num_(0){}

matrix_element(unsigned star_num,unsigned hash_num):
star_num_(star_num),
hash_num_(hash_num){
}

unsigned star_num_;
unsigned hash_num_;
};

void BuildMatrix(matrix_element *** pmaze,unsigned row_num,unsigned column_num)
{
*pmaze = new matrix_element*[row_num];
for(unsigned i=0;i<row_num;++i){
(*pmaze)[i] = new matrix_element[column_num];
}
}

void ReleaseMatrix(matrix_element ***pmaze,unsigned row_num)
{
if(!pmaze) return;

for(unsigned i=0;i<row_num;++i){
delete [](*pmaze)[i];
}

delete [](*pmaze);
}

void CoreSolve(char **parray,unsigned element_num)
{
matrix_element **pnote = NULL;
BuildMatrix(&pnote,element_num,element_num);

for(unsigned i=0;i<element_num;++i){
if((*parray)[i]=='*'){
++pnote[i][i].star_num_;
}else if((*parray)[i]=='#'){
++pnote[i][i].hash_num_;
}
}

int index_start = -1,index_end = -1;
unsigned cur_length = 0;

for(unsigned sub_array_length = 2;sub_array_length<=element_num;++sub_array_length){
for(unsigned i=0;i<=element_num-sub_array_length;++i){
pnote[i][i+sub_array_length-1].hash_num_ =
pnote[i][i+sub_array_length-2].hash_num_+
pnote[i+sub_array_length-1][i+sub_array_length-1].hash_num_;

pnote[i][i+sub_array_length-1].star_num_ =
pnote[i][i+sub_array_length-2].star_num_+
pnote[i+sub_array_length-1][i+sub_array_length-1].star_num_;

if(pnote[i][i+sub_array_length-1].star_num_==
pnote[i][i+sub_array_length-1].hash_num_){
if(sub_array_length>cur_length){
cur_length = sub_array_length;
index_start = i;
index_end = i+sub_array_length-1;
}
}
}
}

cout<<index_start<<" "<<index_end;

ReleaseMatrix(&pnote,element_num);
}

void Solve()
{
unsigned element_num = 0;
cin>>element_num;

char *parray = new char[element_num];
for(unsigned i=0;i<element_num;++i){
cin>>parray[i];
}

CoreSolve(&parray,element_num);
delete []parray;
}

int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);

unsigned case_num = 0;
cin>>case_num;

for(unsigned i=1;i<=case_num;++i){
cout<<"Case #"<<i<<" ";
Solve();
cout<<endl;
}
return 0;
}

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

Looks like a question to find the longest palindrome in a str.

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.