2013亚马逊在线笔试题目

2小时，两个题目。在线编程，英文题目。当时没做好，完了自己把他们完成了。答案是我自己写的，自己测试没问题，若有错误请指正。

                                                         Question 1 / 2

Question:

We have an array representing customer’s shopping records.

For example, it’s an array like this:

custA, item1,

custB, item1,

custA, item2,

 custB, item3,

 custC, item1,

 custC, item3,

 custD, item2,

This array indicates that customer A bought item 1, customer B bought item 1, customer A bought item 2, customer B bought

item 3, etc..

For a given item X and shopping records array, write code to find out what else (item Y) was bought mostly by the customers

who bought item X.

For example, in above example, if X is item 1 then Y should be item 3.

Rules:

1.  One customer can only buy one item once.

2.  The mostly brought item should not be item X.

3.  If no customer brought item X, then return “None”

4.  If all the customers who brought item X only brought item X, then return “None”

5.  The first line of input is the item X. The second line of input is the shopping record array, this shopping record array is

split by space.

6.  If there are many other mostly brought items which have equally brought times, then return any one of those items.

Examples:

Input1:

item1

custA item1 custB item1 custA item2 custB item3 custC item1 custC item3 custD item2

Output1:

item3

 

Input2:

item2

custA item1 custB item1 custC item1 custA item2 custB item3 custA item3

Output2:

item1   

(The output2 can be item3 too)

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>

#include <cstring>
#include <cstdio>

using namespace std;

char* findMostlyBroughtItem(char* shippingRecordArray[], int length, char* givenItem);

inline bool isSpace(char x){
    return x == ' ' || x == '\r' || x == '\n' || x == '\f' || x == '\b' || x == '\t';
}

char * rightTrim(char *str){
    int len = strlen(str);
    while(--len>=0){
        if(isSpace(str[len])){
            str[len] = '\0';
        }else{
            break;
        }
    }
    return str;
}

char * getInputLine(char *buffer, int length){
    if(fgets(buffer,length, stdin)==NULL){
        return NULL;
    }
    rightTrim(buffer);
    if(strlen(buffer)<=0){
        return NULL;
    }
    return buffer;
}

int splitAndConvert(char* strings,char* array[]){
    char*tokenPtr = strtok(strings," ");
    int i=0;
    while(tokenPtr!=NULL){
        array[i] = tokenPtr;
        i++;
        tokenPtr=strtok(NULL," ");
    }
    return i;
}

int main()
{
    char givenItem[1000] = {0} ;
    while(getInputLine(givenItem, 1000)){
    char line[1000];
    getInputLine(line, 1000);

    char* shoppingRecordArray[1000] = {0};

        int length = splitAndConvert(line,shoppingRecordArray);
        if(length==0){
            break;
        }


        char * item = findMostlyBroughtItem(shoppingRecordArray, length, givenItem);
        if (NULL != item)
        {   // 原来系统提供的代码。这里没有NULL判断
            cout<<item<<endl;
            free(item);  // 自己加的
        }
    }
    return 0;
}

void
print(pair<string, int> p) {
    cout << p.first << p.second << endl;
}

//your code is here
//下面才是让写代码的地方，其他的系统已经自动给出。主函数，只有一点点修改。

char* findMostlyBroughtItem(char* shoppingRecordArray[], int length, char* givenItem)
{
    if (NULL == shoppingRecordArray || NULL == givenItem)
        return NULL;

    string obj_item(givenItem);
    // 将用户信息 与 购买商品信息 存入multimap record
    multimap<string, string> record;
    for (int i = 0; i < length; i += 2)
    {
        string customer(shoppingRecordArray[i]);
        string item(shoppingRecordArray[i+1]);

        record.insert(pair<string, string>(customer, item));
    }

    // 提取出购买了obj_item商品的客户名称集合 customers
    set<string> customers;
    for (map<string, string>::iterator it = record.begin(); it != record.end(); it++)
    {
        if (0 == (*it).second.compare(obj_item))
        {
            customers.insert((*it).first);
        }
    }
    // 遍历购买记录 multimap record
    // 若客户名称 在 集合set customers 存在，则将商品插入map result
    map<string, int> result;
    for (map<string, string>::iterator it = record.begin(); it != record.end(); it++)
    {
        for (set<string>::iterator ic = customers.begin(); ic != customers.end(); ic++)
        {
            if (0 == (*it).first.compare(*ic))
            {
                /*
                if (result.end() != result.find((*it).second))
                {
                    result[(*it).second] += 1;
                }
                else
                    result.insert(pair<string, int>((*it).second, 1));
                    */
                result[(*it).second] += 1;
                break;
            }
        }

    }


    pair<string, int> top("None", 0);
    // 遍历map result, 寻找最大，而非obj_item的商品名称
    for (map<string, int>::iterator it = result.begin(); it != result.end(); it++)
    {
        if (0 == (*it).first.compare(obj_item))
            continue;
        if ((*it).second > top.second)
            top = make_pair((*it).first, (*it).second);
    }

    //cout << "Top: " << top.first << "\t" << top.second << endl;

    char *p = (char *)malloc(top.first.length() + 1);
    if (NULL != p)
    {
        strcpy(p, top.first.c_str());
        return p;
    }

    return NULL;
}

                                                       Question 2 / 2

Question:

As you know, two operations of Stack are push and pop. Now give you two integer arrays, one is the original array before

push and pop operations, the other one is the result array after a series of push and pop operations to the first array. Please

give the push and pop operation sequence.

For example:

If the original array is a[] = {1,2,3}, and the result array is b[] = {1,3,2}.

Then, the operation sequence is “push1|pop1|push2|push3|pop3|pop2”(operations are split by ‘|’ and no space).

Rules:

Time Remaining: 00:25:17

1.  The push and pop operations deal with the original int array from left to right.

2.  The input is two integer array. They are the original array and the result array. These interger array is split by space.

3.  The output is the operation sequence.

4.  If the original array cannot make to the result array with stack push and pop, The output should be 'None'.

5.  The operation "push1" means push the first element of the original array to the stack.

6.  The operation "pop1" means pop the first element of the original array from the stack, and add this element to the tail

of the result array.

7.  Please don't include any space in the output string.

Sample1: 

Input:

1 2 3 4

1 2 3 4

Output:

push1|pop1|push2|pop2|push3|pop3|push4|pop4

Sample2: 

Input:

1 2 3 4

4 3 2 1

Output:

push1|push2|push3|push4|pop4|pop3|pop2|pop1

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <stack>

using namespace std;

char* calculateOperationSequence(int *originalArray, int *resultArray, int length);

inline bool isSpace(char x){
    return x == ' ' || x == '\r' || x == '\n' || x == '\r' || x == '\b' || x == '\t';
}

char * rightTrim(char *str){
    int len = strlen(str);
    while(--len>=0){
        if(isSpace(str[len])){
            str[len] = '\0';
        }else{
            break;
        }
    }
    return str;
}

char * getInputLine(char *buffer, int length){
    if(fgets(buffer,length, stdin)==NULL){
        return NULL;
    }
    rightTrim(buffer);
    if(strlen(buffer)<=0){
        return NULL;
    }
    return buffer;
}

int splitAndConvert(char* strings,int *array){
    char*tokenPtr = strtok(strings,",");
    int i=0;
    while(tokenPtr!=NULL){
        array[i] = atoi(tokenPtr);
        i++;
        tokenPtr=strtok(NULL,",");
    }
    return i;
}

int main(){
    char line[1000] = {0} ;
    while(getInputLine(line,1000)){
        int originalArray[30] = {0};
        int originalArrayLength = splitAndConvert(line,originalArray);
        if(originalArrayLength==0){
            break;
        }

    getInputLine(line, 1000);
    int resultArray[30] = {0};
        int resultArrayLength = splitAndConvert(line,resultArray);
        if(resultArrayLength==0){
            break;
        }
        char *operationSequence = calculateOperationSequence(originalArray, resultArray, resultArrayLength);

    if (NULL != operationSequence)
    {   // 原来系统提供的代码。这里没有NULL判断
        cout<< operationSequence <<endl;
        free(operationSequence); // 自己加的
    }
    else
        cout<< "None" <<endl; // 自己加的
    }
    return 0;
}

//your code is here
//下面才是让写代码的地方，其他的系统已经自动给出。主函数，只有一点点修改。
char* calculateOperationSequence(int * originalArray, int * resultArray, int length)
{
    if (NULL == originalArray || NULL == resultArray || length <= 0)
        return NULL;
    //使用一个栈模拟入栈和出栈操作就ok了。
    string str;
    stack<int> st;
    int i = 0;
    int j = 0;
    st.push(originalArray[i]);


    char tmp[5] = "\0";
    str.append("push");
    sprintf(tmp, "%d", originalArray[i]);
    str.append(tmp);
    str.append("|");

    i++;

    while (!st.empty())
    {
        if (j < length && st.top() == resultArray[j])
        {
            str.append("pop");
            sprintf(tmp, "%d", resultArray[j]);
            str.append(tmp);
            str.append("|");
            st.pop();
            j++;

            if (i < length)
            {
                st.push(originalArray[i]);
                str.append("push");
                sprintf(tmp, "%d", originalArray[i]);
                str.append(tmp);
                str.append("|");
                i++;
            }
        }
        else
        {
            if (i < length)
            {
                st.push(originalArray[i]);
                str.append("push");
                sprintf(tmp, "%d", originalArray[i]);
                str.append(tmp);
                str.append("|");
                i++;
            }
            else
                break;
        }
    }


    if (!st.empty())
        return NULL;

    char *p = (char *)malloc(1 + str.length());
    if (NULL != p)
    {
        strcpy(p, str.c_str());
        p[str.length() - 1] = '\0';
        return p;
    }

    return NULL;
}