Amazon电面题目-sort 100 IP addresses

2019-04-14 08:40发布

站内文章 / 模拟电子
13002 0 1155
第一次面试，有点紧张，犯了许多错误，电面就挂了。回头题目自己写下。不知道对不对。 题目：排序100个IP地址，其中可能有非法的IP（例如：192.168.2.1.11 ，192.256.7.1，192.010.2.1） #include
#include
#include
#include
#include


using namespace std;


//s1=s2 false
bool myCmp(string s1, string s2){
    if(s1 == s2)
        return false; //


    stringstream ss;
    string w1, w2;    
    ss << s1;
    getline(ss, w1, '.');
    ss >> s1;    
    ss.str("");
    ss.clear();   
    ss << s2;
    getline(ss, w2, '.');
    ss >> s2;
    
    int i1 = atoi(w1.c_str());
    int i2 = atoi(w2.c_str());
    
    if(i1 != i2)
        return i1 < i2;
    //else w1==w2, recure
    return myCmp(s1, s2);
}


bool check(string s){
    int n = s.size();
    //smallest 0.0.0.0  biggest 255.255.255.255
    if(n > 15 || n < 7)
        return false;
    stringstream ss;
    ss << s;
    int part = 0;
    while(getline(ss, s, '.')){
        part++;
        int i = atoi(s.c_str());
        //more than 4 parts, out of[0,255], has 0xx string
        if(part > 4 || i < 0 || i > 255 || s.size() > 1 && s[0] == '0')
            return false;           
    }
    //less than 4 parts
    return part == 4;    
}


void sortIP(vector &IPs){
    //check valid, move invalid ip to the end
    vector::iterator r = IPs.end() - 1;
    vector::iterator l = IPs.begin();
    while(l <= r){
        if(check(*l))
            l++;
        else{
            swap(*l, *r);//*l = *r;
            r--;            
        }            
    }//if all ip are invalid r=-1
    
    //sort valid ip [begin(), r + 1) 
    sort(IPs.begin(), r + 1, myCmp);   
}


int main(){
    vector IPs;
    IPs.push_back("123.4.245.23");
    IPs.push_back("104.244.253.29");
    IPs.push_back("255.255.255.255");
    IPs.push_back("255.255.255.257");
    IPs.push_back("1.198.3.93");
    IPs.push_back("32.183.93.40");
    IPs.push_back("104.30.244.2");
    IPs.push_back("104.244.4.101");
    IPs.push_back("1.0.0.1");
    IPs.push_back("1.0.0.0");
    IPs.push_back("01.0.0.0");
    IPs.push_back("255.192.255");
    IPs.push_back("00.0.0.0");
    IPs.push_back("0.1.0.0");
    IPs.push_back("0.1.0.0.0");
    IPs.push_back("104.244.4.29");
    
    sortIP(IPs);
    for(int i = 0; i < IPs.size(); ++i)
            cout << IPs[i] << endl;
  
    system("pause");
}

热门文章