Как решить задачу с собеседования?

Question

[Mikhail_123]

На собеседовании попросили решить задачу, написать функцию для: "ab2(3(c)d)" -> "abcсcdccсd"
Сделал решение для конкретного примера, попросили сделать функцию для любых схожих данных, не смог, подскажите как на Kotlin можно решить

Comments

[Денис Загаевский]

Если на собеседовании сделал для конкретного примера, то это, конечно, дико плохо. Я бы не взял тебя даже стажёром. Это показывает полное непонимание происходящего. Совет - пиши больше кода.

[Тимур Покровский]

а ты уверен, что тебе не слишком рано на собеседования?

[Jungles]

Денис Загаевский, а можно еще пару советов?

[Mikhail_123]

Денис Загаевский, Скорее больше алгоритмических задач а не больше кода, я занимаюсь разработкой приложений на Android, и подобных задач у меня не было, можно написать много разнообразных приложений средней сложности с большим количеством кода без каких то сложных алгоритмов, или даже не сложных, с вашей точки зрения, таких как этот

Answer 1

[acwartz]

Предельно простая задача с циклом while + рекурсия.
скобки образуют вызов рекурсивной функции.
Котлин не знаю.
Примерно так:

function task(str) result string {
  i, j integer = 0;
  max integer = str.length;
  ch char = #0;
  while (i < max) {
    ch = str[i];
    if ch in [0..9] {
      //делаем рекурсию столько раз сколько предписано
      //начало строки которую надо обработать, не включая тек. символ и символ начала рекурсии (
      substrStart Integer = i + 2;
      //конец строки которую надо обработать, ссылается на закрывающую рекурсию скобку )
      substrEnd Integer = str.pos(")", substrStart );
      //цикл повторов выражения в скобках
      for j = 1; j < ch; j++:
        //копируем из строки 2(3(c)d) значение 3(с)d не включая скобки и текущий символ указывающий кол-во повторов
        result = result + task(str.substring(substrStart, substrEnd -1)); 
      end for;
      //Прыгаем за закрываюющую скобку т.к. этот участок обработан рекурсивно, и нужно обработать хвост если он есть, например: aaa2(3(c)dd)QQ
      //в первой итерации task("aaa2(3(c)dd)QQ")
      //тут будет переход на позици подстроки "QQ"
      i = substrEnd + 1;
    } else {
      result = result + ch;
      i = i + 1;
    }
  }
}
}

Comments

[Рональд Макдональд]

Поздравляю, благодаря вам теперь на одного вайтана-"программиста" будет больше.

[acwartz]

Рональд Макдональд,
а где вы увидели готовый код? Или пояснение алгоритма решения задачи на этом ресурсе порицается, и все только и заняты тем что посылают все и друг-друга в гугл?

[Рональд Макдональд]

acwartz, Гугл мозгов не прибавляет.

[javedimka]

2(3(c)d)
str.substring(substrStart, substrEnd -1)

3(c

?

[vreitech]

javedimka, =c

[acwartz]

javedimka, угу, ошибка, надо с конца строки поиск делать и до i + 2, а не наоборот, а то но не отбирать будет вложенные выражения, а этого не нужно :)

[acwartz]

javedimka,
substrStart - substrEnd -1 указывает что надо забрать именно "3(c)d" из "2(3(c)d)", ну так я думал когда писал) так с вашей заметкой чутка багованно, но думаю аффтар сам догадается.

Answer 2

[alekseyHunter]

написать функцию для: "ab2(3(c)d)" -> "abcсcdccсd"

Перефразированная задача из универа. У нас звучала - "Посчитать результат выражения, состоящего из цифр, арифметических операций и скобок". То есть калькулятор через инфиксную/постфиксную запись, кому как удобнее. Тут аналогичный подход.

Сделал решение для конкретного примера, попросили сделать функцию для любых схожих данных

Если бы собеседование было на позицию Senior, то как подкол интервьюера - смешно. В остальных случаях - не очень.

Comments

[Денис Загаевский]

Нет, к калькулятору эта задача не имеет никакого отношения. Это в разы проще. Написать калькулятор за время собеседования сложно.

[alekseyHunter]

Денис Загаевский, а к чему эта задача, если не подобие калькулятора?

Сначала проверяем корректность скобочек через стек, все ли закрыты.
Дальше запускаем хвостовую рекурсию с 1 символа. В ней считываем символы.
Если символ - буква, добавляем в переменную "str". Если символ - цифра, начинаем записывать в переменную "number". Если дальше открыта скобка, Запускаем рекурсию со следующего элемента. Выход из рекурсию - закрытая скобка или конец строки. После возврата происходит конкатенация, а результаты из рекурсии дублируются N раз, в зависимости от значения переменной "number".

Да, она проще калькулятора, но не намного. Все зависит от количества арифметических операций для реализации.

[Денис Загаевский]

alekseyHunter, никакой проверки корректности тут делать не надо, это отдельная задача. Самый простой калькулятор с двумя операциями разного приоритета и скобками будет сложнее в разы.

[Денис Загаевский]

alekseyHunter, для разминки решил написать эти задачки. Калькулятор занял 36 минут, из которых минут 5 вспоминал, как его вообще парсить. Декомпрессия заняла 15 минут.

[Денис Загаевский]

fun main(args: Array<String>) {
    println("""${solve("2+2*2")} == 6?""")
    println("""${solve("3+2*5")} == 13""")
    println("""${solve("1+2+3+4+5+6")} == ${1+2+3+4+5+6}""")
    println("""${solve("1*2*3*4*5*6")} == ${1*2*3*4*5*6}""")
    println("""${solve("(2+2)*2")} == 8""")
    println("""${solve("(2*2)+2")} == 6""")
    println("""${solve("(1+2)*(3+4+5)*(6+7)+(7*8+9)")} == ${(1+2)*(3+4+5)*(6+7)+(7*8+9)}""")
    println("""${solve("(1+2*(2+3*4)+5*(6+(7+8*(9+1))))")} == ${(1+2*(2+3*4)+5*(6+(7+8*(9+1))))}""")
}

fun solve(expr: String) = Solver(expr).solve()

class Solver(private val expr: String) {

    private var cursor = 0
    private lateinit var token: Token

    fun solve(): Int {
        cursor = 0
        next()
        return addExpr()
    }

    private fun addExpr(): Int {
        var result = mulExpr()
        while (token == Plus) {
            next()
            result += mulExpr()
        }

        return result
    }

    private fun mulExpr(): Int {
        var result = unaryExpr()
        while (token == Asterisk) {
            next()
            result *= unaryExpr()
        }
        return result
    }

    private fun unaryExpr(): Int {
        if (token == OpenBrace) {
            next()
            val result = addExpr()
            if (token != CloseBrace) throw IllegalStateException("wrong expression at symbol $cursor")
            next()
            return result
        }

        if (token is Num) {
            val result = (token as Num).v
            next()
            return result
        }

        throw IllegalStateException("wrong expression at symbol $cursor")
    }

    private fun next() {
        if (cursor >= expr.length) {
            token = Eof
            return
        }
        token = when (val c = expr[cursor]) {
            in '0'..'9' -> Num(c.toInt() - '0'.toInt())
            '+' -> Plus
            '*' -> Asterisk
            '(' -> OpenBrace
            ')' -> CloseBrace
            else -> throw IllegalStateException("unknown symbol $c")
        }.also { cursor++ }
    }
}

private sealed class Token
private class Num(val v: Int): Token()
private object Plus: Token()
private object Asterisk: Token()
private object OpenBrace: Token()
private object CloseBrace: Token()
private object Eof: Token()

[Денис Загаевский]

fun main(args: Array<String>) {
    println("""${decompress("a2b3c4(dfgh)5(3w6(Qwe))")}""")
}


fun decompress(s: String): String {

    val result = StringBuilder()
    var cursor = 0
    while(cursor < s.length) {
        when (val c = s[cursor]) {
            in '0'..'9' -> {
                ++cursor
                if (s[cursor] == '(') {
                    val length = findSubstrLength(s, cursor)
                    val decompressedSubStr = decompress(s.substring(cursor + 1, cursor + length))
                            cursor += length + 1
                        ('1'..c).forEach {
                        result.append(decompressedSubStr)
                    }
                } else {
                    ('1'..c).forEach {
                        result.append(s[cursor])
                    }
                    ++cursor
                }
            }

            else -> {
                ++cursor
                result.append(c)
            }
        }
    }

    return result.toString()
}

private fun findSubstrLength(s: String, position: Int): Int {
    var count = 1
    var cursor = position + 1
    while(count != 0 && cursor < s.length) {
        when(s[cursor]) {
            '(' -> ++count
            ')' -> --count
        }
        ++cursor
    }

    if (cursor == s.length && count != 0) throw IllegalStateException()

    return cursor - position - 1
}

Answer 3

[Stalker_RED]

Comments

[acwartz]

решение чисто для ab2(3(c)d) в выражение ab2(3(c)d2(aa)) оно не умеет.