We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Functional Programming
  3. Recursion
  4. String Mingling
  5. Discussions

String Mingling

  • abhiranjanChallenge Author + 4 comments

    Something like

    def f(p: List[Char], q: List[Char]) : List[Char] = {
    if (p.isEmpty) List()
    else (p.head :: q.head :: f1 (p.tail, q.tail))
}

    PS: Almost all the challenges are designed such that you don't need mutable variables to solve them.

    • khrak + 0 comments

      Thank you it finally accepted. I'll check for differences those codes to understand what was the problem. Thank you again

    • serhii_nesteruk + 2 comments

      Hello! I wonder why is this solution is better than mine:

      def recursiveZip(l1: List[Char], l2: List[Char], acc: List[Char]): List[Char] = {
    if(l1.isEmpty) acc
    else recursiveZip(l1.tail, l2.tail, acc ++ List(l1.head, l2.head))
}

      It is tail recursive function, list concatenation has linear complexity

      • PRASHANTB1984 + 0 comments

        many compilers are optimized for tail-recursion which makes such functions less inefficient than one would normally expect them to be. For example, the tailRec keyword in Scala.

      • abhiranjanChallenge Author + 1 comment

        @serhii_nesteruk, :: has constant complexity, while ++ is linear.

        In your code you are applying ++ n times. First on the list of length 1, then 2, then 3, and so on. So overall complexity will be 

        O(1) + O(2) + ... + O(n-1) ~= O(n^2)
        • serhii_nesteruk + 0 comments

          thanks for the explanation!

    • ronagrawal + 0 comments
      [deleted]
    • blowkj + 1 comment

      This is the solution that I eventually came up with and it still times out on test case 10. Interestingly, a simple for loop which prints out the characters of the strings also times out on that case and is about twice as long in execution on test case 9. On my local machine, I get stack overflow way before the execution time problem. Any suggestions?

      • abhiranjanChallenge Author + 1 comment

        Hi @blowkj, sorry can't find your solution.

        Common source of long execution is the complexity of + operator (or append method) for strings. It's of Appending two strings, one of length N, other of M, is of complexity O(N+M). Here it's repeatitive addition, so it can be of quadratic complexity.

        • blowkj + 1 comment

          Sorry, I meant the onbe that you posted. Here is my version: def Mingle(P:List[Char],Q:List[Char]):List[Char] = { if(P.isEmpty)return List() return P.head :: Q.head :: Mingle(P.tail,Q.tail) }

          def main(args: Array[String]) {

    val P = readLine().toList
    val Q = readLine().toList
    println(Mingle(P,Q).mkString)

}

          Note that I don't use the + operator. Thanks,

          • blowkj + 0 comments

            OK, got it now. Googling on tail recursion helped.