задачки на интервью(прескрин)

[anyone40]

привет всем !
прилетело тут (см ниже) может у кого есть уже заготовка ?

-------------------------------
Write a program in Java to assess a given string whether it complies with following patterns. Return true if a given string complies with these patterns else false.

N = N1 + N2
N>= N1 >= N2

where N is the Nth element in the string or element at Nth position;
N1 is the (N-1) element in the string & N2 is the (N-2) element in the string.

Example 1: 224610
Elements in this string are 2, 2, 4, 6, 10.
First Set: 2+2=4 (N2=2; N1=2 & N= 4);
Second Set: 2+4=6 (N2=2; N1=4 & N=6);
Third Set: 4+6=10 (N2=4; N1=6 & N= 10)

Example 2: 1112233558
Elements in this string are 1, 11, 12, 23, 35, 58

Example 3: 1101102203
Elements in this string are 1, 101, 102, 203.

This is a simple problem of recursion, which includes determination of this elements programmatically and running these patterns.

[DropAndDrag]

почти никогда не писал рекурсивных функций.
взял бы за критерий длину элементов N2 и N1.
рекурсивную функцию - bool Search( int N2N1, int CurrentPositionInInputString, int CurrentPositionInOutputString)

for( int Length = 2; Length < InputString.Length * 2 /3 +1; Length++){
if( Search( 0, 0) == true) break;
}
перебор получается N*N ...

[Alexander Z]

Ряд Фибоначчи с линейной сложностью алгоритма?

[Сабина]

привет всем !
прилетело тут (см ниже) может у кого есть уже заготовка ?

-------------------------------
Write a program in Java to assess a given string whether it complies with following patterns. Return true if a given string complies with these patterns else false.

N = N1 + N2
N>= N1 >= N2

where N is the Nth element in the string or element at Nth position;
N1 is the (N-1) element in the string & N2 is the (N-2) element in the string.

Example 1: 224610
Elements in this string are 2, 2, 4, 6, 10.
First Set: 2+2=4 (N2=2; N1=2 & N= 4);
Second Set: 2+4=6 (N2=2; N1=4 & N=6);
Third Set: 4+6=10 (N2=4; N1=6 & N= 10)

Example 2: 1112233558
Elements in this string are 1, 11, 12, 23, 35, 58

Example 3: 1101102203
Elements in this string are 1, 101, 102, 203.

This is a simple problem of recursion, which includes determination of this elements programmatically and running these patterns.

Code: Select all

public class Test {

   public static void main(String[] args) {
       System.out.println(split(""));
       System.out.println(split("0"));
       System.out.println(split("1"));
       System.out.println(split("12"));
       System.out.println(split("213"));
       System.out.println(split("011"));
       System.out.println(split("1235"));
       System.out.println(split("121325"));
       System.out.println(split("121325446"));
       System.out.println(split("11011022031112233558"));
    }
    
    public static List<BigInteger> split(String str) {
        return splitNext(BigInteger.ZERO, BigInteger.ZERO, 0, str);
    }
    
    public static List<BigInteger> splitNext(BigInteger first, BigInteger second, int startPosition, String str) {
        List<BigInteger> solution = null;
        char ch[] = str.toCharArray();
        StringBuilder thirdBuilder = new StringBuilder();
        for(int i = startPosition; i < ch.length; i++) {
            thirdBuilder.append(ch[i]);
            BigInteger third = new BigInteger(thirdBuilder.toString());
            if(third.compareTo(second) > 0 && (first == BigInteger.ZERO || second == BigInteger.ZERO ||
                    third.equals(first.add(second)))){
                if(i == ch.length - 1 && first != BigInteger.ZERO && second != BigInteger.ZERO) {
                    solution = Collections.singletonList(third);
                } else {
                    List<BigInteger> tailSolution = splitNext(second, third, i + 1, str);
                    if(tailSolution != null) {
                        solution = new ArrayList<>();
                        solution.add(third);
                        solution.addAll(tailSolution);
                    }
                }
            }
            if(solution != null) break;
        }
        return solution;
    }
    
}