amazon set 8

Q1: A binary search tree is given by 2 nodes interchanged, find the 2 nodes.

my sol : just in-order traveral the tree, it should be ascending sequence.  since there are 2 nodes swapped, scan the sequence, find 2 nodes which is not follow the ascending order, which are the 2 you are looking for.

Q2: Identify all the pythagorian triplets in the given array.

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A primitive Pythagorean triple (PPT) is one in which a, b and c are pairwise coprime. A right triangle whose sides form a Pythagorean triple is called a Pythagorean triangle.

see this link :

http://stackoverflow.com/questions/2032153/how-to-find-pythagorean-triplets-in-an-array-faster-than-on2

sol :

1. square all elements in the array

2. sort it ascending

3. solve it as 3sum

Q3 . find the smallest substring contains all chars in the main string

my sol, http://www.2cto.com/kf/201208/150748.html

#include <iostream>
#include <string.h>
#define MAX 50
using namespace std;

int findMin(int record[])  // 128
{
    int min = -1;
    for(int i = 0; i < 128; i ++)
    {
        if(record[i] >= 0)
        {
            if(min == -1)
                min = record[i];
            else if(min > record[i])
                min = record[i];
        }
    }
    return min;
}

void minSubString(char str[], char set[], char substr[])
{
    int index = -1;
    int record[128];
    int uncovered = 0;
    int minSpan = -1;
    int bestInd = 0;
    for(int i = 0; i < 128; i ++)
    {
        record[i] = -2; // This char is not in the set.
    }
    for(int i = 0; set[i] != ''; i ++)
    {
        record[set[i]] = -1; // in the set, available for recording the index
        uncovered ++;
    }
    for(int i = 0; str[i] != ''; i ++)
    {
        if(record[str[i]] > -2)
        {
            if(record[str[i]] == -1)
            {
                record[str[i]] = i;
                uncovered --;
                if(index == -1)
                    index = i;
            }
            else if(record[str[i]] == index)   // find the min
            {
                record[str[i]] = i;
                index = findMin(record);
            }
            else
            {
                record[str[i]] = i;
            }
        }
        if(uncovered == 0)  // Everyone in the set is covered.
        {
            if(minSpan == -1 || minSpan > (i - index + 1))
            {
                minSpan = i - index + 1;
                bestInd = index;
            }
        }
        cout << record['a'] << "-" << record['b'] << "-" << record['c'] << "-" << str[i] << "-" << index << endl;
    }
    for(int i = 0; i < minSpan; i ++)
    {
        substr[i] = str[i+bestInd];
    }
    cout << minSpan << " " << bestInd << endl;
    substr[minSpan] = '';
}

int main()
{
    char * set = "abc";
    char * str = "ddbccaabbccaabcdddaaabb";
    char substr[MAX];
    minSubString(str, set, substr);
    cout << substr << endl;
    return 0;
}

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s