一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 302|回复: 0
收起左侧

WhatsApp OA questions and answers

[复制链接] |试试Instant~ |关注本帖
wsd10 发表于 2016-9-24 10:29:56 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@WhatsApp - 校园招聘会 - 其他 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
#include <iostream>
using namespace std;
// question 1: create a new datatype for a singly linked list
struct ListNode {
    int val;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // question 2: write a function that merges two sorted linked lists.
    ListNode *merge(ListNode *runner1, ListNode *runner2) {
        ListNode *pre = new ListNode(0);
        ListNode *runner = pre;
        while (runner1 || runner2) {
            if (!runner2) {
                runner->next = runner1;
                runner1 = runner1->next;
            }
            else if (!runner1) {
                runner->next = runner2;. 鍥磋鎴戜滑@1point 3 acres
                runner2 = runner2->next;
            }
            else if (runner1->val < runner2->val) {
                runner->next = runner1;
                runner1 = runner1->next;
            }
            else {
                runner->next = runner2;.1point3acres缃
                runner2 = runner2->next;. Waral 鍗氬鏈夋洿澶氭枃绔,
            }
            runner = runner->next;
        }
        return pre->next;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }

    // question 3: full merge-sort algorithm
    ListNode* mergeSort(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *slow_runner = head, *fast_runner = head;
        while (fast_runner->next && fast_runner->next->next) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            slow_runner = slow_runner->next;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            fast_runner = fast_runner->next->next;
        }
        ListNode *head1 = head, *head2 = slow_runner->next;
        slow_runner->next = NULL;
        return merge(mergeSort(head1), mergeSort(head2));
    }

    // to judge if my answer and expected answer is the same
    bool isEqual(ListNode *myAnswer, ListNode *expectedAnswer) {. visit 1point3acres.com for more.
        if (!myAnswer && !expectedAnswer). from: 1point3acres.com/bbs
            return true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (!myAnswer || !expectedAnswer)
            return false;
        while (myAnswer && expectedAnswer) {
            if (myAnswer->val != expectedAnswer->val)
                return false;. visit 1point3acres.com for more.
            myAnswer = myAnswer->next;
            expectedAnswer = expectedAnswer->next;. 1point3acres.com/bbs
        }
        if (myAnswer || expectedAnswer)
            return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        return true;
    }

    // print out the linked list
    void printList(ListNode *list) {
        if (!list) {. from: 1point3acres.com/bbs
            cout << "NULL" << endl;
            return;
        }
        while (list) {
            cout << list->val << " ";
            list = list->next;
        }
        cout << endl;
    }
};
int main() {
    // question 4: create test cases 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    Solution sol;
    ListNode *myAnswer = NULL, *correctAnswer = NULL;

    cout << "Test case 1: " << endl;;
    ListNode *tc1_1 = new ListNode(1); ListNode *tc1_2 = new ListNode(3); ListNode *tc1_3 = new ListNode(2);
    tc1_1->next = tc1_2; tc1_2->next = tc1_3;
    cout << "Input: ";
    sol.printList(tc1_1);
. From 1point 3acres bbs    ListNode *sorted_tc1_1 = new ListNode(1); ListNode *sorted_tc1_2 = new ListNode(2); ListNode *sorted_tc1_3 = new ListNode(3);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    sorted_tc1_1->next = sorted_tc1_2; sorted_tc1_2->next = sorted_tc1_3;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    myAnswer = sol.mergeSort(tc1_1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    correctAnswer = sorted_tc1_1;
    cout << "My answer: ";
    sol.printList(myAnswer);. from: 1point3acres.com/bbs
    cout << "Expected answer: ";
    sol.printList(correctAnswer);-google 1point3acres
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    else
        cout << "FAIL!" << endl;. from: 1point3acres.com/bbs
    cout << endl;

    cout << "Test case 2: " << endl;;
    ListNode *tc2_1 = new ListNode(2); ListNode *tc2_2 = new ListNode(1);
    tc2_1->next = tc2_2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    cout << "Input: ";.鐣欏璁哄潧-涓浜-涓夊垎鍦
    sol.printList(tc2_1);
    ListNode *sorted_tc2_1 = new ListNode(1); ListNode *sorted_tc2_2 = new ListNode(2);
    sorted_tc2_1->next = sorted_tc2_2;
    myAnswer = sol.mergeSort(tc2_1);
    correctAnswer = sorted_tc2_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    cout << "Test case 3: " << endl;;
    ListNode *tc3_1 = new ListNode(1); ListNode *tc3_2 = new ListNode(2); ListNode *tc3_3 = new ListNode(1);
    tc3_1->next = tc3_2; tc3_2->next = tc3_3;.1point3acres缃
    cout << "Input: ";
    sol.printList(tc3_1);
    ListNode *sorted_tc3_1 = new ListNode(1); ListNode *sorted_tc3_2 = new ListNode(1); ListNode *sorted_tc3_3 = new ListNode(2);. more info on 1point3acres.com
    sorted_tc3_1->next = sorted_tc3_2; sorted_tc3_2->next = sorted_tc3_3;
    myAnswer = sol.mergeSort(tc3_1);
    correctAnswer = sorted_tc3_1;
    cout << "My answer: ";. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer)). From 1point 3acres bbs
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;. 鍥磋鎴戜滑@1point 3 acres

    cout << "Test case 4: " << endl;;
    ListNode *tc4_1 = NULL;
    cout << "Input: ";
    sol.printList(tc4_1);
    ListNode *sorted_tc4_1 = NULL;
    myAnswer = sol.mergeSort(tc4_1);
    correctAnswer = sorted_tc4_1;
    cout << "My answer: ";
    sol.printList(myAnswer);.1point3acres缃
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
.鏈枃鍘熷垱鑷1point3acres璁哄潧    cout << endl;

    cout << "Test case 5: " << endl;;
    ListNode *tc5_1 = new ListNode(1); ListNode *tc5_2 = new ListNode(2); ListNode *tc5_3 = new ListNode(3);. from: 1point3acres.com/bbs
    tc5_1->next = tc5_2; tc5_2->next = tc5_3;
    cout << "Input: ";
    sol.printList(tc5_1);
    ListNode *sorted_tc5_1 = new ListNode(1); ListNode *sorted_tc5_2 = new ListNode(2); ListNode *sorted_tc5_3 = new ListNode(3);
    sorted_tc5_1->next = sorted_tc5_2; sorted_tc5_2->next = sorted_tc5_3;
    myAnswer = sol.mergeSort(tc5_1);
    correctAnswer = sorted_tc5_1;
    cout << "My answer: ";. visit 1point3acres.com for more.
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;. Waral 鍗氬鏈夋洿澶氭枃绔,

    cout << "Test case 6: " << endl;;. visit 1point3acres.com for more.
    ListNode *tc6_1 = new ListNode(1);
    cout << "Input: ";
    sol.printList(tc6_1);
    ListNode *sorted_tc6_1 = new ListNode(1);
    myAnswer = sol.mergeSort(tc6_1);
    correctAnswer = sorted_tc6_1;. Waral 鍗氬鏈夋洿澶氭枃绔,
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer)). Waral 鍗氬鏈夋洿澶氭枃绔,
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;. From 1point 3acres bbs
    cout << endl;. From 1point 3acres bbs

    cout << "Test case 7: " << endl;;
    ListNode *tc7_1 = new ListNode(3);ListNode *tc7_2 = new ListNode(7);ListNode *tc7_3 = new ListNode(3);
    ListNode *tc7_4 = new ListNode(8);ListNode *tc7_5 = new ListNode(1);ListNode *tc7_6 = new ListNode(2);.鏈枃鍘熷垱鑷1point3acres璁哄潧
    ListNode *tc7_7 = new ListNode(8);ListNode *tc7_8 = new ListNode(6);ListNode *tc7_9 = new ListNode(1);
    tc7_1->next = tc7_2; tc7_2->next = tc7_3; tc7_3->next = tc7_4; tc7_4->next = tc7_5;
    tc7_5->next = tc7_6; tc7_6->next = tc7_7; tc7_7->next = tc7_8; tc7_8->next = tc7_9;
    cout << "Input: ";. Waral 鍗氬鏈夋洿澶氭枃绔,
    sol.printList(tc7_1);
    ListNode *sorted_tc7_1 = new ListNode(1);ListNode *sorted_tc7_2 = new ListNode(1);ListNode *sorted_tc7_3 = new ListNode(2);
    ListNode *sorted_tc7_4 = new ListNode(3);ListNode *sorted_tc7_5 = new ListNode(3);ListNode *sorted_tc7_6 = new ListNode(6);
    ListNode *sorted_tc7_7 = new ListNode(7);ListNode *sorted_tc7_8 = new ListNode(8);ListNode *sorted_tc7_9 = new ListNode(8);
    sorted_tc7_1->next = sorted_tc7_2; sorted_tc7_2->next = sorted_tc7_3; sorted_tc7_3->next = sorted_tc7_4;
    sorted_tc7_4->next = sorted_tc7_5; sorted_tc7_5->next = sorted_tc7_6; sorted_tc7_6->next = sorted_tc7_7;
    sorted_tc7_7->next = sorted_tc7_8; sorted_tc7_8->next = sorted_tc7_9;
    myAnswer = sol.mergeSort(tc7_1);
    correctAnswer = sorted_tc7_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);. From 1point 3acres bbs
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    else
        cout << "FAIL!" << endl;
    cout << endl;

    cout << "Test case 8: " << endl;;
    ListNode *tc8_1 = new ListNode(3); ListNode *tc8_2 = new ListNode(2); ListNode *tc8_3 = new ListNode(1);
    tc8_1->next = tc8_2; tc8_2->next = tc8_3;
    cout << "Input: ";
    sol.printList(tc8_1);
.鐣欏璁哄潧-涓浜-涓夊垎鍦    ListNode *sorted_tc8_1 = new ListNode(1); ListNode *sorted_tc8_2 = new ListNode(2); ListNode *sorted_tc8_3 = new ListNode(3);
    sorted_tc8_1->next = sorted_tc8_2; sorted_tc8_2->next = sorted_tc8_3;
    myAnswer = sol.mergeSort(tc8_1);
    correctAnswer = sorted_tc8_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;

    cout << "Test case 9: " << endl;;
    ListNode *tc9_1 = new ListNode(1); ListNode *tc9_2 = new ListNode(1); ListNode *tc9_3 = new ListNode(1);
    tc9_1->next = tc9_2; tc9_2->next = tc9_3;
    cout << "Input: ";
    sol.printList(tc9_1);
    ListNode *sorted_tc9_1 = new ListNode(1); ListNode *sorted_tc9_2 = new ListNode(1); ListNode *sorted_tc9_3 = new ListNode(1);
    sorted_tc9_1->next = sorted_tc9_2; sorted_tc9_2->next = sorted_tc9_3;
    myAnswer = sol.mergeSort(tc9_1);
    correctAnswer = sorted_tc9_1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;
    return 0;
}

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表