推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 460|回复: 0
收起左侧

WhatsApp OA questions and answers

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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;. more info on 1point3acres.com
                runner1 = runner1->next;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            }
            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;
            }. 1point 3acres 璁哄潧
            runner = runner->next;
        }. 1point3acres.com/bbs
        return pre->next;
    }. more info on 1point3acres.com
. 鍥磋鎴戜滑@1point 3 acres
    // 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;. From 1point 3acres bbs
            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;. 1point 3acres 璁哄潧
        if (!myAnswer || !expectedAnswer). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            return false;
        while (myAnswer && expectedAnswer) {
            if (myAnswer->val != expectedAnswer->val)
                return false;
            myAnswer = myAnswer->next;
            expectedAnswer = expectedAnswer->next;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
        if (myAnswer || expectedAnswer)
            return false;. 1point 3acres 璁哄潧
        return true;
    }

    // print out the linked list
    void printList(ListNode *list) {
-google 1point3acres        if (!list) {
            cout << "NULL" << endl;
            return;
        }
        while (list) {
            cout << list->val << " ";. 鍥磋鎴戜滑@1point 3 acres
            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;
    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))
        cout << "PASS!" << endl;
    else. 鍥磋鎴戜滑@1point 3 acres
        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);
    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);. From 1point 3acres bbs
    tc3_1->next = tc3_2; tc3_2->next = tc3_3;. From 1point 3acres bbs
    cout << "Input: ";
    sol.printList(tc3_1);-google 1point3acres
    ListNode *sorted_tc3_1 = new ListNode(1); ListNode *sorted_tc3_2 = new ListNode(1); ListNode *sorted_tc3_3 = new ListNode(2);
    sorted_tc3_1->next = sorted_tc3_2; sorted_tc3_2->next = sorted_tc3_3;
    myAnswer = sol.mergeSort(tc3_1);. from: 1point3acres.com/bbs
    correctAnswer = sorted_tc3_1;
    cout << "My answer: ";. 1point3acres.com/bbs
    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 4: " << endl;;
    ListNode *tc4_1 = NULL;. From 1point 3acres bbs
    cout << "Input: ";
    sol.printList(tc4_1);
    ListNode *sorted_tc4_1 = NULL;
    myAnswer = sol.mergeSort(tc4_1);. 鍥磋鎴戜滑@1point 3 acres
    correctAnswer = sorted_tc4_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 5: " << endl;;
    ListNode *tc5_1 = new ListNode(1); ListNode *tc5_2 = new ListNode(2); ListNode *tc5_3 = new ListNode(3);
    tc5_1->next = tc5_2; tc5_2->next = tc5_3;
    cout << "Input: ";. Waral 鍗氬鏈夋洿澶氭枃绔,
    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: ";
    sol.printList(myAnswer);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;-google 1point3acres

    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);. visit 1point3acres.com for more.
    correctAnswer = sorted_tc6_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 7: " << endl;;
    ListNode *tc7_1 = new ListNode(3);ListNode *tc7_2 = new ListNode(7);ListNode *tc7_3 = new ListNode(3);.鏈枃鍘熷垱鑷1point3acres璁哄潧
    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);
    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;. Waral 鍗氬鏈夋洿澶氭枃绔,
    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);. Waral 鍗氬鏈夋洿澶氭枃绔,
    cout << "Expected answer: ";. visit 1point3acres.com for more.
    sol.printList(correctAnswer);. Waral 鍗氬鏈夋洿澶氭枃绔,
    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);. 1point 3acres 璁哄潧
    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;
. From 1point 3acres bbs    myAnswer = sol.mergeSort(tc8_1);
    correctAnswer = sorted_tc8_1;
    cout << "My answer: ";
    sol.printList(myAnswer);. more info on 1point3acres.com
    cout << "Expected answer: ";
    sol.printList(correctAnswer);-google 1point3acres
    if (sol.isEqual(myAnswer, correctAnswer)). 鍥磋鎴戜滑@1point 3 acres
        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);-google 1point3acres
    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;. from: 1point3acres.com/bbs
    else
        cout << "FAIL!" << endl;
    cout << endl;
    return 0;
}


本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-22 19:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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