06/29 Google OA 2018 For Fall Internship

大家好!
這是我第一篇發文，還不是很熟悉請大家多多指教：）
平時在地里受益良多，剛剛做完Google OA，立馬來回報一下！（原本預想會是花圃跟時間的題，結果沒有）
小弟看來是掛了平常人品太差天要亡我QQ...我在最後兩分鐘的時候網路斷了..第一題的正確版本不知道有沒有被存到並送出
抒發完了！來看題吧！大家一起加油！

第一題：
Assume you are playing a card game in which each card has a cost and a damage caused to your opponent.
Write a function:
class Solution
{
      public boolean Solution (int total_money, int total_damage , int[] costs, int[] damages){}
}

that given:

• integer total_money : total money you have
• integertotal_damage : total damage to be caused
• array costs of integers (size N) : the cost of every card
• array damages of integers (size N) : the damage caused to your opponent by every card
  

should return true if it is possible to cause at least total_damage amount of damage to your opponent using
a maximum of total_money units of money, or false otherwise. Each card can be selected only once.


For example, given total_money = 5, total_damage = 3, costs = [4,5,1] and damages = [1,2,3] your function
should return true. You can scause at least total_damage amount of damage to your opponent using a
maximum oftotal_money units of money in 2 different ways:

• By selecting the third card whose cost is 1 and damage is 3.
• By selecting the first and third card whose cost are (4,1) and damage caused to another player are (1,3)
  

It is possible to cause at least 3 units of damage to your opponent, therefore, ther answer is true.


Assume that:

• N, total_money and total_damage are integers within the range [1..1,000]
• each element of arrrays costs, damages is an integer within the range [1...1,000]
  

第二題：
Write a function:
class Solution
{
      public int solution(String S, String T) {}
}


that, given a string S and a string T, return 1 if it's possible to convert string S into string T by deleting some(possible zero)
characters from string S, and otherwise returns 0.


For example, given S="abcd" and T="abd" the function should return 1. We can delete 'c' from string S to convert string S into
string T. However, given S="ab" and T="ba" the function should return 0.


Assume that:

• the length of ('S' , 'T') is within the range [1..1,000]
• strings S and T consist only of lower-case letters (a-z).
  

大家加油！有問題歡迎一起討論！
如果大家願意，賞我一點米吧～感謝大家

Aaronkung00 发表于 2018-7-6 02:32
我是往前掃一遍 或者 recursive 從後面掃都可以
DP的思路我還沒有想過 可以說說看你的想法討論一下！

跟lc那道题可以replace insert delete 三种情况用的dp，这里我不知道能不能用dp

ob123 发表于 2018-7-5 22:19
第二题楼主用什么方法，dp吗

我是往前掃一遍 或者 recursive 從後面掃都可以
DP的思路我還沒有想過 可以說說看你的想法討論一下！

lz, what position you applied? thx

第一题背包？第二题好像扫一遍

Yuedandanyue 发表于 2018-7-5 06:16
lz, what position you applied? thx

Software Engineering Internship

svsf91 发表于 2018-7-5 06:50
第一题背包？第二题好像扫一遍

恩沒錯背包DP

第二题楼主用什么方法，dp吗

请问lz收到回复了吗

Hongbin 发表于 2018-7-6 00:25
请问lz收到回复了吗

7/3 收到電話面試邀請 現在目前還在安排時間中