CareerCup

#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

map<char, int> vals = { {'I', 1}, 
                        {'V', 5}, 
                        {'X', 10}, 
                        {'L', 50}, 
                        {'C', 100}, 
                        {'D', 500}, 
                        {'M', 1000}
                    };


vector<string> split(const string &s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> tokens;
    while (getline(ss, item, delim)) {
        tokens.push_back(item);
    }
    return tokens;
}


int romanToInt(string s){
    int res = vals[s[s.size() - 1]];
    for (int i = s.size() - 2; i >= 0; i--) {
        if (vals[s[i]] < vals[s[i+1]])
            res -= vals[s[i]];
        else
            res += vals[s[i]];
    }
    return res;
}

bool comp(string a, string b) {
    vector<string> s1 = split(a, ' ');
    vector<string> s2 = split(b, ' ');
    for (auto s: s1)
        cout << s << endl;
    if (s1[0] < s2[0]) return true;
    if (s1[0] == s2[0] and romanToInt(s1[1]) <= romanToInt(s2[1]))
        return true;
    return false;   

}

int main(){
    vector<string> names = {"Richard V","Henry VI","Edward II","Richard XXV","Henry IX","Edward LII"};
    sort(names.begin(), names.end(), comp);
    for (auto name: names)
        cout<< name << '\t';
return 0;
}

Just use quicksort.

Short and Simple Python solution with Backtracking:

def getMinLengthSubsequence(nums, sub):
    def search(nums, sub, startn, starts):
        if starts >= len(nums) or startn >= len(nums):
            return -1, -1
        for idx in range(startn, len(nums)):
            if nums[idx] == sub[starts]:
                if starts == len(sub) - 1:
                    return idx, idx
                start, end = search(nums, sub, idx + 1, starts + 1)
                if start >= 0:
                    return idx, end
        return -1, -1

    start, end = 0, float('inf')
    for idx in range(len(nums)):
        if sub and nums[idx] == sub[0]:
            startx, endx = search(nums, sub, idx, 0)
            if startx != -1 and endx - startx < end - start:
                start, end = startx, endx
    return start, end

def advance(nums, counts, i, j, X, Y):
    while 0 <= i < j and counts[X] > counts[Y]:
        if nums[j] == X:
            counts[X] -= 1
            j -= 1
        else:
            if nums[i] == X:
                counts[X] -= 1
                i += 1
            else:
                i += 1
                j -= 1
    return i, j


def largestContainingXandY(nums, X, Y):
    counts = collections.Counter(nums)
    i, j, res = 0, len(nums) - 1, 0
    while i < j:
        i, j = advance(nums, counts, i, j, X, Y)
        i, j = advance(nums, counts, i, j, Y, X)
        if counts[X] == counts[Y]:
            res = max(res, j - i + 1)
            break
    return res


nums = [7, 42, 5, 6, 42, 8, 7,5, 7, 6, 7]
nums1 = [7, 42, 7, 42, 7, 7, 42, 42, 7, 7, 7, 7, 7, 7, 42]
nums2 = [7, 7]
print(largestContainingXandY(nums1, 7, 42))

def longestWithSumLessThanK(nums, k):
    counts, i, res = 0, 0, float('-inf')
    for j in range(len(nums)):
        counts += nums[j]
        while i <= j and counts > k:
            counts -= nums[i]
            i += 1
        if counts <= k:
            res = max(res, j - i + 1)
    return res if res > float('-inf') else None

nums = [1, 1, 1, 2, 1, 1, 1, 4, 4, 1, 2 ,3, 4, 1]
print(longestWithSumLessThanK(nums, 7))

def generate(num):
    res, s = [], list(int(x) for x in str(num))
    for i in range(0, len(s) - 1):
        left  = s[:i]
        right = s[i+2:]
        res  += "".join(str(x) for x in left + [max(s[i], s[i+1])] + right),

    # I got max 10 digits, so I run maximum 10 times the loop. Each loop takes O(n) time,
    # Where n is the length (10). So at the end I have in the worst case a list of 10 elements each one having 10 digits. Getting the minimum will require me 10 comparisons each one taking 10 (I gotta compare every digit).

    return min(res)
num = 233614
print(generate(num))

One line in Python:

def check_patterns(words, p):
    return [word 
            for word in words 
            if len(word) == len(p) and\
            len(set(zip(word, p))) == len(set(word)) == len(set(p))
            ]

words = ["cdf", "too", "hgfdt" ,"paa"]
p = "abc"
p1 = "acc"
print(check_patterns(words, p))
print(check_patterns(words, p1))

Use partition function of Quicksort, easy-peasy.

import random


def rand_0_5():
    return 1 if random.random() >= 0.5 else 0


def rand_0_75():
    return 0 if not (rand_0_5() + rand_0_5()) else 1