话说我之前有在 oDesk 注册过，最近收到他们一个邮件，被邀请参加一个 test 什么的，觉得好玩就去了，结果没搞定，大家觉得愉♂悦的话可以帮忙瞧瞧。

如果之前有人发过，就让他沉了吧……

2 道题目，60 分钟

Challenge 1: Sequence

Given an array of integer numbers

Your task is to

write a function that prints to the standard output (stdout) the largest sum that can be obtained using any sequence of consecutive elements from the array

Note that your function will receive the following arguments:

numbers which is the array of integers described above

Data constraints

the length of the array will not exceed 200,000 each element of the array will be in the [-10000, 10000]

Efficiency constraints

your function is expected to print the requested result and return in less than 2 seconds

Example

Input numbers: 2, -3, 2, 2, -1, 2, -2, 1

Output: 5

Explanation:

The sequence: 2, 2, -1, 2 has sum 5 which is the largest possible.

Challenge 2: Store

All products from an ecommerce site are stored as a list of strings representing their names.

Whenever a user starts typing the name of a product the website immediately suggests the full product name that matches the query string.

If a query string is prefix for a product name then they match.

Given the list of products and a list of query strings

Your task is to

* write a function that prints to the standard output (stdout) for each query the product name that matches the query * if there are multiple products matching the query please select the one that is the smallest lexicographically * all string matches must be case insensitive * if no match is found for a given query please print -1

Note that your function will receive the following arguments:

products which is a an array of strings representing the names of the products queries which is an array of strings representing the queries described above

Data constraints

the length of the arrays above will not exceed 100,000 entries each product name or query string will not exceed 30 characters

Efficiency constraints

your function is expected to print the result in less than 2 seconds

Example

Input

products: ["boat", "bike", "phone"] queries: ["b", "bk", "PHo", "bO"]

Output

bike -1 phone boat

然后是我的答案，可能都比较暴力的缘故，所以效率上比较差 另：不要吐嘈为何是 4 个空格，那个 test 的编辑器 tab 就是 4 个，复制下来懒得改了 :( 第一题（我没怎么研究过算法……感觉这个应该可以从算法上改进的）

def max_sum(numbers)
    max_sum = 0
    len = numbers.size

    if len.zero?
        puts 0
    elsif len == 1
        puts numbers.first
    else    

        (0..(len-1)).each do |start|
            (start..(len-1)).each do |last|
                sum = 0
                numbers[start..last].each { |i|  sum += i}
                max_sum = sum if max_sum < sum
            end
        end
        puts max_sum
    end
end

6 个 test 过了 2 个，剩下 4 个超时…… Test 0: OK! Test 1: OK! Test 2: Error: your code didn't finish in less than 2 seconds. Test 3: Error: your code didn't finish in less than 2 seconds. Test 4: Error: your code didn't finish in less than 2 seconds. Test 5: Error: your code didn't finish in less than 2 seconds.

第二题

def search_products(products, queries)
    # Write your code here
    # To print results to the standard output you can use puts
    # Example puts "Hello world!"
    results = []
    products = products.sort
    queries.each do |query|
        found = false
        query = query.downcase
        products.each do |product|
            if product.downcase =~ /^#{query}/
                found = true
                results << product
                break
            end
        end
        results << -1 if !found
    end
    puts results
end

6 个 test 过了 3 个，剩下 3 个超时……如图：