谷歌OA

Job Hunting Interview
, , , , ,
1

image
image.jpg877×1000 411 KB
image
image.jpg843×1000 307 KB
image
image.jpg833×1000 300 KB

我的代码

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] plants, int capacity1, int capacity2) {
        // write your code in Java SE 8
        if(plants == null || plants.length == 0){
            return 0;
        }
        //To handle the case when there is exactly one plant with capacity = one of the two can's capacity 
        if(plants.length==1 && (plants[0] <= Math.max(capacity1, capacity1))){
            return 1;
        }
        
        //Water first half of the plants
        int count =2;
        int water_cap = capacity1;
        for(int i =0;i<plants.length/2;i++){
            
            //water when possible
            if(water_cap >= plants[i])
                water_cap -= plants[i];
            else{
                //increase the count and refill the can
                count++;
                water_cap = capacity1;
                water_cap -= plants[i];
                
            }
        }
        
        //Water second half of the plants
        int water_cap2 = capacity2;
        int x = plants.length/2;
        if(plants.length%2==0){
            x = (plants.length/2)-1;
        }
        for(int i =plants.length-1;i>x;i--){
            
            //water when possible
            if(water_cap2 >= plants[i])
                water_cap2 -= plants[i];
            else{
                //increase the count and refill the can
                count++;
                water_cap2 = capacity2;
                water_cap2 -= plants[i];
                
            }
        }
        
        //To check the middle flower
        if(plants.length%2 == 1){
            if(water_cap + water_cap2<plants[plants.length/2]){
                count++;
            }
        }
        
        return count;
    }
}
2

image
image.png379×766 108 KB

House Robber (https://leetcode.com/problems/house-robber/) but with an additional parameter num where the robot cannot pick more than num strawberries (the robber cannot rob more than num amount of money).

Example Input:
arr = [50, 10, 20, 30, 40], num = 100

Example Output:
90

3

You are given a string that represents time in the format hh:mm. Some of the digits are blank (represented by ?). Fill the ? to find the maximum possible time that can be represented by this string. Maximum time: 23:59, minimum time: 00:00. You can assume that input string is always valid.

Example 1:

Input: “?4:5?”
Output: “14:59”

Example 2:

Input: “23:5?”
Output: “23:59”

Example 3:

Input: “2?:22”
Output: “23:22”

Example 4:

Input: “0?:??”
Output: “09:59”

Example 5:

Input: “??:??”
Output: “23:59”

4

两道题分别是浇花的变种以及多米诺，详细题目可以参考一下其他帖子。

这里特地说一下浇花题，它变成了由我和我的朋友分别从两头开始浇花，而且我们俩的瓶子容量互不相同，假设容量均不小于最耗水的那朵花花。同时要求说我们俩的步速一致，一个人refill的时候，另一个人不能向前移动，因此我们最终会在中间相遇。如果队列长度为偶数的话那好说，我们俩各浇一半的话，互不干涉；如果是奇数的话，那我们俩最终将会需要共同浇中间那朵尊贵的小花花，如果我们瓶中的水量【加起来】足以浇花的话那就直接浇完了事，否则我们【其中一个人】需要refill然后才能浇上。

多米诺题的话由于是蠡扣原题，我就在OA之前现在那上面跑了一下，发现竟然只beat 12%的人（我用的是C++）。所以就参考了 一下其他人的答案，把两个for loop减少为一个，然后就beat 96%啦嘻嘻~因为之前看别的面筋有说这道题会考虑performance，所以我个人认为提高性能还是挺有必要的！

1 Like