Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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 head = FindSubArray!(sym1,sym2)(data[0..$-1]);
string tail = FindSubArray!(sym1,sym2)(data[1..$]);
return head.length > tail.length ? head : tail;
}
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;
}
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");
}
}
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.
2. Start reading the array.
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.
8. Once reading the linked list is done, we are ready to make a call.
9. Read the linked list again, this time picking up the block that has maximum width. This is your answer.
If the linked list is empty, it means the array consists of only one type of symbol.
#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");
}
}
/*************************************************
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;
}
Lets say you have an array A = **###***#**##*###*#* and you have another array B.
- sachaudh August 03, 2014Step 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.