8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

需要帮助解决面试问题:反向 FizzBu​​zz

EC99 2月前

19 0

我最近参加了一家公司的面试,面试官问了我一个编程问题:FizzBu​​zz 是一款经典的儿童游戏,它已经成为一种有趣的编程方式。这个问题可以用以下方式描述:

我最近参加了一家公司的面试,被问到这个编码问题:

FizzBu​​zz 是一款经典的儿童游戏,它已发展成为一种有趣的编码方式。该问题可以用以下规则来描述:

  • 对于给定的整数 f、b 和 n,编写一个程序打印数字 1 到 n
  • 对于 f 的倍数,打印 \'Fizz\'
  • 对于 b 的倍数,打印 \'Buzz\'
  • 对于 f 和 b 的倍数,打印 \'FizzBu​​zz\'
  • 对于其他情况,打印数字

那么...反向 FizzBu​​zz 是什么?我们有 n 个 FizzBu​​zz 输出值,但我们不知道 f 和 b 值。使用 FizzBu​​zz 输出作为我们程序的输入,找到原始 f 和 b 值(所谓的“乘数值”)。

例如,如果输入是 (\'1\', \'2\', \'Fizz\', \'4\', \'Buzz\', \'Fizz\', \'7\', \'8\', \'Fizz\', \'Buzz\', \'11\', \'Fizz\', \'13\', \'14\', \'FizzBu​​zz\'),则输出应为 3 5

代码

import java.util.ArrayList;
import java.util.List;

public class FizzBuzzMultiplierFinder {

    public static void main(String[] args) {
        String[] fizzBuzzOutput = {"1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"};
        findFizzBuzzMultipliers(fizzBuzzOutput);
    }

    public static void findFizzBuzzMultipliers(String[] fizzBuzzOutput) {
        List<Integer> fizzPositions = new ArrayList<>();
        List<Integer> buzzPositions = new ArrayList<>();

        // Find positions of "Fizz" and "Buzz" in the output
        for (int i = 0; i < fizzBuzzOutput.length; i++) {
            if (fizzBuzzOutput[i].contains("Fizz")) {
                fizzPositions.add(i + 1); // +1 to convert index to position
            }
            if (fizzBuzzOutput[i].contains("Buzz")) {
                buzzPositions.add(i + 1); // +1 to convert index to position
            }
        }

        // Determine the smallest multiple for Fizz (f)
        int f = findGCD(fizzPositions);

        // Determine the smallest multiple for Buzz (b)
        int b = findGCD(buzzPositions);

        System.out.println("f = " + f + ", b = " + b);
    }

    // Helper method to find the Greatest Common Divisor (GCD)
    public static int findGCD(List<Integer> numbers) {
        int gcd = numbers.get(0);
        for (int i = 1; i < numbers.size(); i++) {
            gcd = gcd(gcd, numbers.get(i));
        }
        return gcd;
    }

    // Helper method to calculate GCD of two numbers
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

我能够解答找到 f 和 b 之间最大公约数的问题。

后来面试官告诉我,此代码不适用于以下输入:

String[] input5 = { "Fizz", "Buzz", "52", "53", "54", "Fizz", "56", "57", "58", "59", "Fizz", "61", "62", "63", "64", "Fizz", "66", "67", "68", "69", "Fizz" }

预期输出为 5,51。

需要帮助重构我的代码以满足上述测试用例

尝试读取字符串数组并根据数组中的数字更新索引。代码变得太乱,无法找到优化的解决方案

帖子版权声明 1、本帖标题:需要帮助解决面试问题:反向 FizzBu​​zz
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由EC99在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 顺便说一句,最后发布的输入并不完全是 FizzBu​​zz 的反向输入... \'

  • 在这种情况下,您可以做的是获取两个 Fizz/Buzz 之间的偏移/距离,这就是您的 Fizz/Buzz 编号。如果只有一个 Fizz/Buzz,那么 Fizz/Buzz 编号就是它所在的位置,您可以通过获取列表中的第一个数字,然后将其偏移 Fizz/Buzz 索引的位置来计算。

    下面是它的伪代码( 代码假设输入只有一个有效的 Fizz 和 Buzz 值,并且输入中至少有一个数字 ):

    fizzBuzzOutput = { "Fizz", "Buzz", "52", "53", "54", "Fizz", "56", ... }
    
    // same as you did, just dont add +1 to i
    fizzPositions = { 0, 5, ... }
    buzzPositions = { 1 }
    
    // get the index of the first parsable int
    // you could do this with a for loop and try and parse
    firstNumberIndex = 2
    
    if (fizzPositions.length > 1) {
        fizz = fizzPositions[1] - fizzPositions[0] // that would 5
    } else {
        fizz = fizzBuzzOutput[firstNumberIndex] + (fizzPositions[0] - firstNumberIndex)
    }
    
    if (buzzPositions.length > 1) {
        buzz = buzzPositions[1] - buzzPositions[0]
    } else {
        // 52 + (1 - 2)
        buzz = fizzBuzzOutput[firstNumberIndex] + (buzzPositions[0] - firstNumberIndex)
    }
    
    // you don't need the gcd methods
    
  • 实际情况比这更复杂。如果输入以 56 结尾,那么 buzz 可能是 51 或 17。但您的算法只会说它是 51。对于给定的输入,我们知道它不可能是 17,因为输入中有 \'68\' 代替 \'buzz\'。

  • Zart 2月前 0 只看Ta
    引用 5

    是的,fizz 和 buzz 可能有更多的可能性,但在我的回答中,我假设输入只有一个有效的 fizz 和 buzz 值

  • 您的代码不适用于替代数据集,因为您假设列表中的第一个数字始终为 1,因此您只需获取列表中的索引并加 1 即可获得数字。但在本例中,它不是 1,而是 50,其中 1. 表示索引不等于数字 -1,而 2. 表示第一个数字会立即触发嘶嘶声。

    最简单的解决方案可能是使你使用的相对于索引的偏移量动态化。我不会告诉你如何做到这一点,因为这将为你解决面试问题。

  • 我将从两个假设开始,第一个假设,我想我们都认为理所当然的是“1”不是一个有效答案,第二个假设是应该返回找到的值中的最高值(如果有多个),这个假设基于这样一个事实,即最后一个例子承认“5,3”也是“5,17”和“5,51”是有效答案,那么,鉴于面试官认为“5,51”是正确答案,我认为这是一个很好的假设。

    import java.util.ArrayList;
    import java.util.List;
    
    public class FizzBuzzMultiplierFinder {
    
       public static void main( String[] args ) {
          FizzBuzzMultiplierFinder fbmf = new FizzBuzzMultiplierFinder();
          String fizzBuzzOutput[] = { "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz" };
          fbmf.findFizzBuzzMultipliers( fizzBuzzOutput );
       }
    
       public void findFizzBuzzMultipliers( String[] fizzBuzzOutput ) {
          int ini = 0;
    
            // in this step, we identify the numerical value of the first item in the list
          for( int i = 0; i < fizzBuzzOutput.length; i ++ ) {
             if( fizzBuzzOutput[ i ].matches( "[0-9]" ) ) {
                ini = Integer.parseInt( fizzBuzzOutput[ i ] ) - i;
                break;
             }
          }
          System.out.println( getResult( fizzBuzzOutput, ini, "Fizz" ) + " " + getResult( fizzBuzzOutput, ini, "Buzz" ) );
       }
    
         // this method invokes "subMultiples" which creates a list of lists of submultiples, 
         // and returns the value returned by "getNumber", to which it passes as argument, 
         // the obtained list.
       int getResult( String input5[], int ini, String type ) {
          List<List<Integer>> lis = new ArrayList<>();
          for( int i = 0, k = ini; i < input5.length; i ++, k ++ ) {
             if( input5[ i ].equals( type )
                     || input5[ i ].equals( "FizzBuzz" ) ) {
                lis.add( subMultiples( k ) );
             }
          }
          return getNumber( lis );
       }
    
         // return a list of submultiples
       List<Integer> subMultiples( int number ) {
          List<Integer> out = new ArrayList<>();
          for( int i = number; i > 1; i -- ) {
             if( number % i == 0 ) {
                out.add( i );
             }
          }
          return out;
       }
    
         // this method generates the candidates and verifies by calling “isInList”
         // if it is valid, if so, it returns it. 
       int getNumber( List<List<Integer>> lis ) {
          int number;
          for( int i = 0; i < lis.size(); i ++ ) {
             List<Integer> l = lis.get( i );
             for( int k = 0; k < l.size(); k ++ ) {
                number = l.get( k );
                if( isInList( lis, number ) ) {
                   return number;
                }
             }
          }
          return -1;
       }
    
         // return "true" if the number is contained in all lists
       boolean isInList( List<List<Integer>> lis, int number ) {
          for( int i = 0; i < lis.size(); i ++ ) {
             int amount = lis.get( i ).size();
             for( int k = 0; k < lis.get( i ).size(); k ++ ) {
                if( lis.get( i ).get( k ) == number ) {
                   break;
                }
                if( k == amount - 1 ) {
                   return false;
                }
             }
          }
          return true;
       }    
    }
    
返回
作者最近主题: