Massive Technical Interviews Tips: FizzBuzz

Friday, October 9, 2015

FizzBuzz

http://javarevisited.blogspot.com/2015/04/fizzbuzz-solution-in-java-8.html
Problem : For a given natural number greater than zero return:
“Fizz” if the number is dividable by 3
“Buzz” if the number is dividable by 5
“FizzBuzz” if the number is dividable by 15
the same number if number is neither divisible by 3 nor 5.
http://www.forbes.com/sites/quora/2015/04/14/6-tips-for-writing-bug-free-code-during-an-interview/
There are three types of solutions:
Spaghetti
The candidate tests for each multiple, and both multiples, and outputs a separate string in each case.

Conceptually Separated
The candidate builds a string, adding ‘Fizz’ or ‘Buzz’ based on the separate multiples, and outputs it in one place.

Syntactically Separated
The candidate writes a function which returns ‘Fizz’, ‘Buzz’, ‘FizzBuzz’, or ”, and doesn’t know anything about printing or looping. They call that from their main loop to build their output string.

http://rosettacode.org/wiki/FizzBuzz/Java

    public static String fizzBuzz(int number) {
        if (number % 15 == 0) {
            return "FizzBuzz";
        } else if (number % 3 == 0) {
            return "Fizz";
        } else if (number % 5 == 0) {
            return "Buzz";
        }
        return Integer.toString(number);
    }

public static String fizzBuzzInJava8(int number) {
        String result = Optional.of(number)
                .map(n -> (n % 3 == 0 ? "Fizz" : "") + (n % 5 == 0 ? "Buzz" : ""))
                .get();
        return result.isEmpty() ? Integer.toString(number) : result;
  }

    public static String fizzBuzzSolutionJava8(int input) {
        return Optional.of(input)
                .map(i -> {
                    if (i % (3 * 5) == 0) {
                        return "FizzBuzz";
                    } else if (i % 3 == 0) {
                        return "Fizz";
                    } else if (i % 5 == 0) {
                        return "Buzz";
                    } else {
                        return Integer.toString(i);
                    }
                }).get();
    }

http://www.nicolasbize.com/blog/look-at-your-old-code/

(1..100).each{|i|
    if i % 3 == 0 && i % 5 == 0
        print 'FizzBuzz'
    elsif i % 3 == 0
        print 'Fizz'
    elsif i % 5 == 0
        print 'Buzz'
    else
        print i
    end
}

– The if conditionals can be rewritten so they are more readable
– The modulo math operations are performed twice
– The code has a bunch of magical numbers 1, 100, 3, and 5, preventing any easy change in the problem text.
– Nothing is tested
div3 = i%3; div5=i%5;

(1..100).each{|i|
    print 'Fizz' if i % 3 == 0
    print 'Buzz' if i % 5 == 0
    print i if i % 3 > 0 && i % 5 > 0
}

http://blog.codinghorror.com/fizzbuzz-the-programmers-stairway-to-heaven/
http://my.oschina.net/flashsword/blog/261140
Code - https://github.com/code4craft/FizzBuzzWhizz

你是一名体育老师，在某次课距离下课还有五分钟时，你决定搞一个游戏。此时有100名学生在上课。游戏的规则是：

你首先说出三个不同的特殊数，要求必须是个位数，比如3、5、7。
让所有学生拍成一队，然后按顺序报数。
学生报数时，如果所报数字是第一个特殊数（3）的倍数，那么不能说该数字，而要说Fizz；如果所报数字是第二个特殊数（5）的倍数，那么要说Buzz；如果所报数字是第三个特殊数（7）的倍数，那么要说Whizz。
学生报数时，如果所报数字同时是两个特殊数的倍数情况下，也要特殊处理，比如第一个特殊数和第二个特殊数的倍数，那么不能说该数字，而是要说FizzBuzz, 以此类推。如果同时是三个特殊数的倍数，那么要说FizzBuzzWhizz。
学生报数时，如果所报数字包含了第一个特殊数，那么也不能说该数字，而是要说相应的单词，比如本例中第一个特殊数是3，那么要报13的同学应该说Fizz。如果数字中包含了第一个特殊数，那么忽略规则3和规则4，比如要报35的同学只报Fizz，不报BuzzWhizz。

第一步：准备模具——建模及拆分

我认为建模是代码设计最重要的一部分。如何设计一个扩展性强、同时又能很好解决问题的模型，是个比较讲究的地方。

其实整个问题就是将一个顺序的数字串，转化为一个字符串的过程。因为在问题中，各个同学的报数是互不影响的，所以这里我将问题继续拆解，变成“将一个数字转化为一个字符串”的过程NumberSayer，和将多个NumberSayer的结果整合起来的NumberSequenceSayer。在这里，我们考虑数字、输出字符、甚至判断策略都是可变的，而这个接口完全能够满足需要。

这里NumberSayer定义的非常简单，因为接口越简单，系统模块间耦合性越小。

public interface NumberSayer {

    /**
     * Say a number
     * @param number
     * @return can be null
     */
    public String say(int number);
}

根据题目，NumberSayer其实是会有多个的，但是我决定仍然只在NumberSequenceSayer中持有一个NumberSayer，然后用内部组合模式来代替外部的组合——这样可以减少耦合性。

public class NumberSequenceSayer {

    private final NumberSayer numberSayer;

    private final int startNumber;

    private final int endNumber;

    private static String SEPARATOR = System.getProperty("line.separator");

    public NumberSequenceSayer(NumberSayer numberSayer, int startNumber, int endNumber) {
        this.numberSayer = numberSayer;
        this.startNumber = startNumber;
        this.endNumber = endNumber;
    }

    public String say() {
        StringBuilder accum = new StringBuilder();
        for (int i = startNumber; i <= endNumber; i++) {
            String say = numberSayer.say(i);
            if (say != null) {
                accum.append(say).append(SEPARATOR);
            }
        }
        return accum.toString();
    }
}

第二步：填充面粉——细化策略

组合策略

之前说过，我们要使用组合模式。就这个题目的例子而言，我们至少需要两种组合方式：

累加关系 ConcatNumberSayer

多个NumberSayer会同时生效，例如15会输出FizzBuzz。按照添加的顺序决定字符串排列顺序。
互斥关系 OrNumberSayer

只有一个NumberSayer会生效，例如FizzBuzz输出后不再输出15这个数字本身。

单个策略的实现

同时，我们发现，其实目前的几种例子，都是一个“匹配”->“返回指定字符串”的过程，于是我们定义Matcher对象：

public interface Matcher {

    public boolean isMatch(int number);

}

和一个基本类：

public class MatchNumberSayer implements NumberSayer {

    private Matcher matcher;

    private final String mapWord;

    protected MatchNumberSayer(Matcher matcher, String mapWord) {
        this.matcher = matcher;
        this.mapWord = mapWord;
    }

    public String getMapWord() {
        return mapWord;
    }

    @Override
    public String say(int number) {
        if (matcher.isMatch(number)) {
            return getMapWord();
        } else {
            return null;
        }
    }

}

这里我们用模板方法的方式，将mapWord的部分的代码复用了起来。

最后我们只需要定义一些Matcher即可：

//取模判断
public class ModMatcher implements Matcher {

    private int divisor;

    private int remainder;

    protected ModMatcher(int divisor, int remainder) {
        this.divisor = divisor;
        this.remainder = remainder;
    }

    @Override
    public boolean isMatch(int number) {
        return number % divisor == remainder;
    }

}

```java
//数字的字面值包含关系
public class LiteralContainsMatcher extends NumberSayerBuildMatcher {

    private int matchNumber;

    public LiteralContainsMatcher(int matchNumber) {
        this.matchNumber = matchNumber;
    }

    @Override
    public boolean isMatch(int number) {
        return String.valueOf(number).contains(String.valueOf(matchNumber));
    }
}

第三步：加点奶油——方便的API facade

最后我决定使用最近Java比较流行的fluent API，这可以最大程度让程序的API接近自然语言。虽然这种方式不见得最好，但是比起把一堆Factory和Strategy暴露给用户还是要好太多了。这个API是不是看起来有点酷炫？

NumberSequenceSayer numberSequenceSayer = NumberSequenceSayerBuilder.custom()
   .setNumberSayer(
       or(contains(3).thenReturn("Fizz"))
       .or(
           concat(
              mod(3).is(0).thenReturn("Fizz"),
              mod(5).is(0).thenReturn("Buzz"),
              mod(7).is(0).thenReturn("Whizz")
           )
       )
       .or(echoInputNumber())
   )
   .setStartNumber(1).setEndNumber(100).get();
System.out.println(numberSequenceSayer.say());

至此项目完成，总结一下：粗粒度的设计，为了可扩展性；细粒度的实现，为了复用性。