Amazon Interview Question for Software Engineer / Developers


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.

- sachaudh August 03, 2014 | Flag Reply
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 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;
}

- Anonymous August 05, 2014 | Flag Reply
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");
            }

        }

- billu August 06, 2014 | Flag Reply
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.
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.

- Code Monkey August 09, 2014 | Flag Reply
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");
    }
}

- Anonymous September 01, 2014 | Flag Reply
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;
}

- zhouyouisme September 09, 2014 | Flag Reply
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.

- kg October 22, 2014 | 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