can't get fibonacci of 40 or 50 run out of memory

Question

i got the following problem in job interview but couldn't solve it till the end :

you have string "kake" and string "echo"

you have function create( int n) and returns the following:

if n equals 0

    output “kake”

if n equals 1

   output “echo”

if n greater than 1

   output create(n-1) concatenated with create(n-2)

then use this method in another method that takes n and substring

then it finds the number the substring occured in create(n)

the problem is up to n= 35 i have no problems

it is when i try n =40 or 50 i get a out of memory exception and it can't be resolved by increasing memory it seems that ineed to change the algorithm

here's my code :

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Kloc
{
    public static String kw(int n)
    {
        if (n == 0)
            return "kake";
        if (n == 1)
            return "echo";
        String n0 = "kake";
        String n1 = "echo";
        String newN = "";
        for ( int i = 2; i<=n;i++)
        {
            newN = n1 + n0;
            n0 = n1;
            n1 = newN;
            System.gc();
        }
        return newN;
    }
    public static void subOccurence(int n, String sub)
    {
        long occurences = 0;
        String kws = kw(n);
        int kwLen = kws.length();
        int subLen = sub.length();
        char subFirstLetter = sub.charAt(0);

        for (int i=0; i<=kwLen-subLen;i++)
        {
            if(kws.charAt(i) == subFirstLetter)
            {
                boolean occurence = true;
                for (int j =0  ; j< subLen; j++ )
                {
                    if(kws.charAt(i+j) != sub.charAt(j))
                    {
                        occurence = false;
                        i = i+j;
                        break;
                    }
                }
                if (occurence)
                    occurences++;
//                if(kws.substring(i,i+subLen).equalsIgnoreCase(sub))
//                {
//                    //System.out .println(kws.substring(i,i+subLen));
//                    occurences++;
//                }
            }
        }
        System.out.println(occurences);
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
//        subOccurence(40,"kakeecho");
    }
}

I don't understand *"then it finds the number the substring occured in create(n)"*. Do you mean the number of times? Or the index/position? — Andreas, Jul 17 '17 at 04:59
I don't think your algorithm is to blame. Have you worked out how many bytes the 50th string in your sequence will take up? Why wouldn't you run out of memory? — Dawood ibn Kareem, Jul 17 '17 at 05:12
Who added the "recursion" tag? This is not recursive, and there's no reason to suppose that recursion will fix this - in fact it will probably make things worse. @JavaGuyNextDoor please reconsider your edit. — Dawood ibn Kareem, Jul 17 '17 at 08:04
@DawoodibnKareem you are correct, I didn't find how to cancel my edit before it was approved. Although - the **definition** of the question was given in a recursive way. — Ossin Java guy, Jul 17 '17 at 08:29

alainlompo · Answer 1 · 2017-07-17T10:30:34.463

The reason you are having this out of memory exception that seems not to be resolvable by increasing the heap size is because your implementation exceeds the maximum limit of arrays in java.

The first step of the java.util.Arrays.copyOf static method is to try to instanciate a new array with the necessary capacity to store the new string. This will always generate the confusing out of memory exception when the new array's size exceeds the maximum limit of arrays.

The exception you are having looks like the following:

For more information regarding the size of arrays in Java, take a look here. It looks like this maximum value is VM dependant and it is generally close to INTEGER.MAX_VALUE.

We can see that the exception is occuring in the java.utils.Arrays.copyOfmethod. This takes place when java tries to expand the capacity of the StringBuilder it is using to store the computed string at each iteration. In this present the exception occurs precisely on the following line:

newN = n1 + n0;

From one iteration to the other a Fibonaci like algorithm grows almost exponentially. So we can expect the maximum size of arrays to be quickly reached

I made a projection of your implementation on the size of the generated string in order to see how much it grows at each iteration

import java.util.HashMap;
import java.util.Map;

public class FibonaStringSize {
    static Map<Integer, Long> sizeMap = new HashMap<Integer, Long>();
    static {
        sizeMap.put(Integer.valueOf(0), 4L);
        sizeMap.put(Integer.valueOf(1), 4L);
    }
    static long size(int n) {
        if (n == 0) {
            return 4;
        }
        if (n == 1) {
            return 4;
        }

        Long sizeNMin1 = sizeMap.get(Integer.valueOf(n-1));
        Long sizeNMin2 = sizeMap.get(Integer.valueOf(n-2));

        if (sizeNMin1 == null) {
            sizeNMin1 = size(n-1);
            sizeMap.put(Integer.valueOf(n-1), sizeNMin1);
        }

        if (sizeNMin2 == null) {
            sizeNMin2 = size(n-2);
            sizeMap.put(Integer.valueOf(n-2), sizeNMin2);
        }

        return sizeNMin1.longValue() + sizeNMin2.longValue();
    }

    public static void main(String[] args) {
        System.out.println(size(50));
    }
}

Here is how it goes

+--------+-------------+
|   n    |String's size|
+--------+-------------+
|   1    | 4           |
|   10   | 356         |
|   20   | 43784       |
|   30   | 5385076     |
|   40   | 662320564   |
|   50   | 81460044296 |
+--------+-------------+

As we can see, the generated string lenght for n=50is much bigger than INTEGER.MAX_VALUE which is 2147483647

Therefore you should think of another approach and change your algorithm, otherwise the issue will always occure.

I would highly doubt that the interviewer was expecting you to get the exact solution for this but rather demonstrate some level of mastership of the used technologies as well as convincing thinking, reasoning and problem solving approaches. Your are now better prepared if you ever face this question again.

The 'maximum limit of arrays in Java' is 2^31-1 elements. `OutOfMemoryError` means you have run out of memory in this JVM, not that you have hit the maximum limit of Java. — user207421, Jul 17 '17 at 08:48

score 0 · Answer 2 · answered Jul 17 '17 at 09:42

You should do concatenation and searching word by using I/O operations. By this way, heap space error won't occur. The code below works for n=40.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.charset.Charset;

public class Test {

    public static void main(String args[]) throws IOException{

        BufferedReader br = null;

        int limit=40;
        String textToSearch="kakeecho";
        int numberOfOccurence=0;

        try {
            //save each step into a file to avoid java heap space errors.
            PrintWriter writer0 = new PrintWriter("step0.txt", "UTF-8");
            writer0.print("kake");
            writer0.close();

            PrintWriter writer1 = new PrintWriter("step1.txt", "UTF-8");
            writer1.print("echo");
            writer1.close();

            for(int y=2;y<=limit;y++){

                int nextChar;

                PrintWriter writer = new PrintWriter("step"+y+".txt", "UTF-8");
                br = new BufferedReader(new InputStreamReader(
                        new FileInputStream("step"+(y-1)+".txt"),
                        Charset.forName("UTF-8")));

                while((nextChar=br.read())!=-1){
                    writer.print((char)nextChar);
                }

                br.close();

                br = new BufferedReader(new InputStreamReader(
                        new FileInputStream("step"+(y-2)+".txt"),
                        Charset.forName("UTF-8")));

                while((nextChar=br.read())!=-1){
                    writer.print((char)nextChar);
                }

                br.close();

                new File("step"+(y-2)+".txt").delete(); //no need for this file.

                writer.close();

            }

            br = new BufferedReader(new InputStreamReader(
                    new FileInputStream("step"+limit+".txt"),
                    Charset.forName("UTF-8")));

            int ch;
            StringBuilder sb=new StringBuilder();

            while((ch=br.read())!=-1){

                if(sb.toString().length()==textToSearch.length()){

                    if(sb.toString().equals(textToSearch)){
                        numberOfOccurence++;
                    }
                    sb.deleteCharAt(0);

                }

                sb.append((char)ch);

            }

            br.close();

            System.out.println("numberOfOccurence: "+numberOfOccurence);

        } catch (IOException e) {

            e.printStackTrace();

        } finally {

            try {

                if (br != null)
                    br.close();

            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }
}

can't get fibonacci of 40 or 50 run out of memory

2 Answers2