Ruby 2 个 Ruby 题目,有效率要求

hegwin · 2013年12月23日 · 最后由 dsh0416 回复于 2017年07月08日 · 4091 次阅读

话说我之前有在 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 个超时……如图:

都是大学算法课教过的东西,第一题就是 DP 的经典例子:

def max_sum(a)
    max, head, tail, current_head = 0, 0, 0, 0
    sum = [[0, a.first].max]
    1.upto(a.size - 1) do |i|
        sum[i] = [0, sum[i-1] + a[i]].max
        if sum[i-1] == 0 && sum[i] > 0
          current_head = i
        end
        if sum[i] > max
            max, head, tail = sum[i], current_head, i 
        end
    end
    p "#{a[head..tail]} => #{max}"
end

第 2 题翻书去...我也忘记了...

2 楼 已删除

第二题既然都排序了 为何不 二分

第一题叫Bentley's Problem 第二题用 products 先做个 trie 出来怎么样

#4 楼 @leozwa 嗯,感觉用 trie 可以搞。 不过感觉用 Ruby 弄算法题,效率不高吧。。

第二题由于候选不多,按前 2 字母分组就够了,吃内存还小点

Challenge 1 就是个 DP,Challenge 2 就是个 AC 自动机。而且这题目没有绕弯,基本上都是算法课涉及这两个算法最经典的例题了吧。。。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号