一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 400|回复: 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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
// question 1: create a new datatype for a singly linked list
struct ListNode {
    int val;. 1point 3acres 璁哄潧
    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;
            }. from: 1point3acres.com/bbs
            else if (!runner1) {
                runner->next = runner2;
                runner2 = runner2->next;
            }
            else if (runner1->val < runner2->val) {
                runner->next = runner1;
                runner1 = runner1->next;
            }
            else {
                runner->next = runner2;
                runner2 = runner2->next;
            }
            runner = runner->next;
        }
.1point3acres缃        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) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            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) {
        if (!myAnswer && !expectedAnswer)
            return true;
        if (!myAnswer || !expectedAnswer)
            return false;
        while (myAnswer && expectedAnswer) {
            if (myAnswer->val != expectedAnswer->val)
                return false;
            myAnswer = myAnswer->next;
            expectedAnswer = expectedAnswer->next;
        }
        if (myAnswer || expectedAnswer)
            return false;
        return true;
    }

    // print out the linked list
    void printList(ListNode *list) {
        if (!list) {
            cout << "NULL" << endl;
            return;
        }
        while (list) {
            cout << list->val << " ";
            list = list->next;
        }
        cout << endl;
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
};
int main() {
    // question 4: create test cases
    Solution sol;. 1point3acres.com/bbs
    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);
    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;
    myAnswer = sol.mergeSort(tc1_1);
    correctAnswer = sorted_tc1_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer)).1point3acres缃
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;

    cout << "Test case 2: " << endl;;
    ListNode *tc2_1 = new ListNode(2); ListNode *tc2_2 = new ListNode(1);
    tc2_1->next = tc2_2;
    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);. more info on 1point3acres.com
    cout << "Expected answer: ";
    sol.printList(correctAnswer);. from: 1point3acres.com/bbs
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;
. From 1point 3acres bbs
    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;
    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);. 鍥磋鎴戜滑@1point 3 acres
    sorted_tc3_1->next = sorted_tc3_2; sorted_tc3_2->next = sorted_tc3_3;
    myAnswer = sol.mergeSort(tc3_1);
    correctAnswer = sorted_tc3_1;. visit 1point3acres.com for more.
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";. 1point 3acres 璁哄潧
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else. more info on 1point3acres.com
        cout << "FAIL!" << endl;
    cout << endl;

    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);. From 1point 3acres bbs
    correctAnswer = sorted_tc4_1;
    cout << "My answer: ";
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴    sol.printList(myAnswer);. visit 1point3acres.com for more.
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer)). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    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);. Waral 鍗氬鏈夋洿澶氭枃绔,
    tc5_1->next = tc5_2; tc5_2->next = tc5_3;. From 1point 3acres bbs
    cout << "Input: ";. more info on 1point3acres.com
    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);-google 1point3acres
    sorted_tc5_1->next = sorted_tc5_2; sorted_tc5_2->next = sorted_tc5_3;
    myAnswer = sol.mergeSort(tc5_1);. more info on 1point3acres.com
    correctAnswer = sorted_tc5_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
.1point3acres缃    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;. visit 1point3acres.com for more.
    cout << endl;

    cout << "Test case 6: " << endl;;
    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;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else. 1point 3acres 璁哄潧
        cout << "FAIL!" << endl;
    cout << endl;

    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);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    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: ";
    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);. From 1point 3acres bbs
    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);. From 1point 3acres bbs
    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;. From 1point 3acres bbs
    cout << "My answer: ";. 鍥磋鎴戜滑@1point 3 acres
    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 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);. visit 1point3acres.com for more.
    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;. 1point3acres.com/bbs
    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;
. Waral 鍗氬鏈夋洿澶氭枃绔,    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;
    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;. visit 1point3acres.com for more.
}

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-27 16:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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