Summary of written test questions of shopee 2021 autumn recruitment

1、Leetcode13 Roman numeral to integer

class Solution {
    
public:
    int romanToInt(string s) {
    
        int n = s.size();
        unordered_map<string, int> mp;
        mp["I"] = 1, mp["V"] = 5, mp["X"] = 10, mp["L"] = 50,
        mp["C"] = 100, mp["D"] = 500, mp["M"] = 1000;
        mp["IV"] = 4, mp["IX"] = 9;
        mp["XL"] = 40, mp["XC"] = 90;
        mp["CD"] = 400, mp["CM"] = 900;
        int res = 0;
        for(int i = 0; i < n;){
    
            if(i + 1 < n && mp.count(s.substr(i, 2))) res += mp[s.substr(i, 2)], i += 2;
            else res += mp[s.substr(i, 1)], i ++ ;
        }
        return res;
    }
};

2、 String naming conversion

Kong Yiji said “ return ” There are four ways of writing words , There are four common naming styles in programming languages ：

• All initials are capitalized
• First word initial lowercase , The rest of the words are capitalized
• All words are lowercase , Connected by underline
• All words are lowercase , Connected by a minus sign

Please design and implement a caseTransform function , Make a string str It can be conveniently converted into four forms , And the four forms are spliced into a string through spaces and returned for convenience , It is assumed that the input string conforms to the above four English letter combinations .

sample input ：

PascalCaseTest

sample output ：

PascalCaseTest  pascalCaseTest  pascal_case_test pascal-case-test

#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
using namespace std;


int main()
{
    
    string s; cin >> s;
    vector<string> words;
    if(s[0] >= 'A' && s[0] <= 'Z') s[0] += 'a' - 'A';
    s += '-';
    string word;
    for(char c: s){
    
        if(c == '-' || c == '_' || (c >= 'A' && c <= 'Z')){
    
            words.push_back(word);
            word.clear();
            if(c >= 'A' && c <= 'Z'){
    
                c += 'a' - 'A';
                word += c;
            }
        }else word += c;
    }
    string res;
    for(string word: words){
    
        word[0] += 'A' - 'a';
        res += word;
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ){
    
        string t = words[i];
        t[0] += 'A' - 'a';
        res += t;
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ) {
    
        res += '_' + words[i];
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ) {
    
        res += '-' + words[i];
    }
    cout << res << endl;
    return 0;
}

3、 String arithmetic operation

Given a string formula , Returns the result of its calculation . The arithmetic rule is : k*[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .e.g. s = “3*[a2*[c]]”, return “accaccacc”.
sample input ：

3*[a2*[c]]

sample output ：

accaccacc

Answer key ： Classical problems , Stack simulation is enough

class Solution {
    
public:
    string computeString(string s) {
    
        stack<string> st;
        for(char c: s){
    
            string t;
            t += c;
            if(c != ']') st.push(t);
            else{
    
                vector<string> arr;
                while(st.top() != "[") arr.push_back(st.top()), st.pop();
                reverse(arr.begin(), arr.end());
                t = "";
                for(string &a: arr) t += a;
                string num;
                if(st.top() == "[") st.pop();
                if(st.top() == "*") st.pop();
                while(!st.empty() && st.top()[0] >= '0' && st.top()[0] <= '9') num += st.top(), st.pop();
                reverse(num.begin(), num.end());
                int n = stoi(num);
                string temp;
                while(n -- ) temp += t;
                st.push(temp);
            }
        }
        vector<string> res;
        while(!st.empty()){
    
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        string anw;
        for(string r: res) anw += r;
        return anw;
    }
};

4、 Find the leaf node of the binary search tree

Give a binary search tree （Binary Search Tree） The preorder traversal result array of , Print out all leaf nodes .
Input description :

 Enter the array of pre traversal results for the binary search tree , Elements are separated by spaces ：
9 8 7 10

Output description :

 All leaf node elements , Separate... With spaces 
 explain ： Because the representation of binary search tree is :
       9
   8    10
7
 The output leaf node is : 7 10

Input example 1:

9 8 7 10

Output example 1:

7 10

Answer key ： The sequence obtained by traversing the middle order of the binary search tree is increasing , Therefore, we can get the preorder traversal and inorder traversal of the binary tree , Based on this, the binary tree is reconstructed . Leaf nodes can be obtained by traversing the reconstructed binary tree .

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    
    int val;
    TreeNode *left, *right;
    TreeNode(int val){
    
        this->val = val;
        this->left = this->right = NULL;
    }
};

TreeNode *dfs(vector<int> &pre, vector<int> &in, int preL, int preR, int inL, int inR) {
    
    if(preL > preR) return NULL;
    TreeNode *root = new TreeNode(pre[preL]);
    int mid = 0;
    while(in[mid] != pre[preL]) mid ++ ;
    root->left = dfs(pre, in, preL + 1, preL + mid - inL, inL, mid - 1);
    root->right = dfs(pre, in, preL + mid - inL + 1, preR, mid + 1, inR);
    return root;
}

void preOrder(TreeNode *root) {
    
    if(root == NULL) return;
    if(root->left == NULL && root->right == NULL)
        cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

int main() {
    
    vector<int> pre, in;
    int t;
    while(cin >> t) {
    
        pre.push_back(t);
        in.push_back(t);
    }
    sort(in.begin(), in.end());
    int n = pre.size();
    TreeNode *root = dfs(pre, in, 0, n - 1, 0, n - 1);
    preOrder(root);
    return 0;
}

5、 Valid bracket string

Given a string containing only three characters ：（ ,） and *, Write a function to check whether the string is a valid string . Valid strings have the following rules ：

• Any left parenthesis ( There must be a corresponding closing bracket ).
• Any closing parenthesis ) There must be a corresponding left parenthesis ( .
• Left parenthesis ( Must precede the corresponding closing bracket ).
• * Can be treated as a single right parenthesis ) , Or a single left parenthesis ( , Or an empty string .
• An empty string is also considered a valid string .

Input example 1:

"()"

Output example 1:

true

Input example 2:

"(*)"

Output example 2:

true

Input example 3:

"(*))"

Output example 3:

true

Answer key ： Forward scan string ,* When ( Handle , Real time statistics ( and ) number , It is necessary to ensure that the number of left parentheses is not less than the number of right parentheses at all times ; Then reverse scan the string ,* When ) Handle , It is necessary to ensure that the number of right parentheses is not less than the number of left parentheses at all times .

bool checkValidString(string s) {
    
    int l = 0, r = 0;
    for(char c: s){
    
        if(c == '(' || c == '*') l ++ ;
        else r ++ ;
        if(l < r) return false;
    }
    reverse(s.begin(), s.end());
    l = 0, r = 0;
    for(char c: s){
    
        if(c == ')' || c == '*') r ++ ;
        else l ++ ;
        if(r < l) return false;
    }
    return true;
}

6、 Flip the one-way linked list in groups

Give a one-way linked list and an integer N, Make every N Elements are flipped as a group . Time complexity required O(n), Spatial complexity O(1).
Input example 1:

{
    1,2,3,4,5,6,7,8},3

Output example 1:

{
    3,2,1,6,5,4,8,7}

ListNode* reverseLinkedList(ListNode* head, int n) {
    
    int len = 0;
    for(auto p = head; p; p = p->next) len ++ ;
    ListNode *pre = NULL, *cur = head;
    for(int i = 0; i < min(n, len); i ++ ){
    
        auto t = cur->next;
        cur->next = pre;
        pre = cur;
        cur = t;
    }
    if(n > len) return pre;
    head->next = reverseLinkedList(cur, n);
    return pre;
}