Passes all examples given but Timeout Error

Question about the task

Resolved

Can anyone cast a more experience eye over this? It works with many examples but it is timing out on the server. I have use recursion for this solution and I've tried to make it as readable as possible. Have I over engineered this?

Read from the console the name of a file containing HTML.

Example:
Info about Leela Leela Turanga
Supergirl

The main method's first parameter is a tag name. For example, "span".
Display all tags that match the specified tag.
The order should match their order in the file, each tag on a new line.
The number of spaces, newline characters (\n), or carriage returns (\r) does not affect the result.
The file does not have a CDATA tag. Each opening tag has a separate closing tag, and there are no self-closing tags.
Tags may have nested tags.

Example output:
Leela Turanga Leela Turanga Super girl

Tag templates:
<tag>text1</tag> <tag text2>text1</tag> <tag text2>text1</tag>

text1 and text2 can be empty

Requirements:

The program must read the file name from the console (use BufferedReader).
The BufferedReader used for reading input from the console must be closed after use.
The program must read the file's contents (use FileReader).
The file input stream (FileReader) must be closed.
The program must write to the console all the tags that match the tag specified by the argument passed to the main method.

package com.codegym.task.task19.task1918; import java.io.BufferedReader; import java.io.FileReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Map; import java.util.TreeMap; public class Solution { private static TreeMap<Integer, String> tags = new TreeMap<>(); private static char[] buffer; private static String openTag; private static String closeTag; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String filename = br.readLine(); br.close(); openTag = String.format("<%s>", args[0]); closeTag = String.format("</%s>", args[0]); getBuffer(filename); //populate buffer tagFinder(0, 0); printTags(); } public static void tagFinder(int startPos, int openTags) { int totalTagCount = openTags; //the number of tags currently open int myOpeningTagCount = 0; //number of tags I have open int myTagStartPoint = startPos; //my starting point int nextTagStartPoint; //starting point fo any new matching tags for recursion int myTagEndPoint = 0; //ending point when all my tags closed boolean recordTag = false; //currently building a new tag to check? boolean myFirstPass = true; //is this my first pass finding a matching tag? String currentTag = ""; for (int i = startPos; i < buffer.length; i++) { char tempChar = buffer[i]; if (tempChar == '<') { //begin building <tag> - used to check if tag needed or ignored recordTag = true; } else if (tempChar == '>') { //close <tag> ensure tag is full (>) stop recording further chars currentTag = currentTag + tempChar; recordTag = false; if (tagOpenMatch(currentTag)) { //check if tag is an open match e.g. <tag> equals <tag> totalTagCount++; //add one to overall tags open myOpeningTagCount++; //add one to myOpenTag count if (myFirstPass) { //if this is the first pass set the starting point for recording overall string then set first pass to false myTagStartPoint = (i - currentTag.length()) + 1; myFirstPass = false; } else { //if not first pass then begin recursion pass to new method the start point of the new matching tag and current tags open nextTagStartPoint = (i - currentTag.length()) + 1; tagFinder(nextTagStartPoint, totalTagCount); // somewhere here needs recursion check logic for if current tag already being worked on (so don't call same twice). } currentTag = ""; //reset currentTag string to "" for the next tag search } else if (tagCloseMatch(currentTag)) { //if the tag isn't a match for open tags check if it matches closed tags currentTag = ""; //reset currentTag string to "" for next tag to be found totalTagCount--; //reduce the total tag count myOpeningTagCount--; //reduce myOpenTagCount by one if (myOpeningTagCount == 0) { myTagEndPoint = i; } } else { currentTag = ""; } } if (recordTag) { //record current char to currentTag if we are currently building a tag to check currentTag = currentTag + tempChar; } if (myOpeningTagCount == 0 && !myFirstPass) { //if I have all open tags closed and this is not my first pass then add my tag string to the map String myCompleteTagString = ""; for (int j = myTagStartPoint; j < ((myTagEndPoint) + 1); j++) { //loop from myTagStartPoint to myEndPoint adding each char we find myCompleteTagString = myCompleteTagString + buffer[j]; } if (!tags.containsKey(myTagStartPoint)) { tags.put(myTagStartPoint, myCompleteTagString); //add the tag to the map } if (totalTagCount > 0) { //if my tags are all closes but there are still some open then break the loop this closes this method/recursion and we go back to calling code (previous recursive) break; } } } } //pass in current tempTag and see if it matches the open tag of args e.g. <tag> public static boolean tagOpenMatch(String tagInput) { String tempTag = ""; String tagToFind = openTag; for (char c : tagInput.toCharArray()) { if (c == '\n' || c == '\r' || c == ' ') { break; } else if (c == '/') { //be sure not to return true for closed tag e.g. </tag> return false; } tempTag = tempTag + c; } tempTag = tempTag.replaceAll("<|>", ""); //removes <> for comparisons tagToFind = tagToFind.replaceAll("<|>", ""); //removes <> for comparisons return tempTag.equals(tagToFind); } //pass in current tempTag and see if it matches the close tag of args e.g. </tag> public static boolean tagCloseMatch(String tagInput) { String tagToFind = closeTag; return tagInput.equals(tagToFind); } //populate buffer public static void getBuffer(String filename) throws Exception { BufferedReader reader = new BufferedReader(new FileReader(filename)); ArrayList<String> input = new ArrayList<>(); String s; int charCount = 0; while ((s = reader.readLine()) != null) { s = s + "\n"; input.add(s); charCount = charCount + s.length(); } reader.close(); buffer = new char[charCount]; int fillCount = 0; for (int i = 0; i < input.size(); i++) { String tempLine = input.get(i); for (int j = 0; j < tempLine.length(); j++) { buffer[fillCount] = tempLine.charAt(j); fillCount++; } } } //print tags public static void printTags() { if (!tags.isEmpty()) { for (Map.Entry<Integer, String> pair : tags.entrySet()) { String s = pair.getValue(); s = s.replaceAll("\n|\r", ""); System.out.println(s); } } } }

Comments (5)

Popular
New
Old

You must be signed in to leave a comment

Guadalupe Gagnon

Level 37 , Tampa, United States

5 June 2020, 15:54

useful

In the example given in this task I added a new span directly following the first one like this: [span[span test[/span] ....... [/span] (i couldn't post exactly because the text here crops out HTML) The output completely changed where it only output the last three spans instead of the 5 it should have. Try duplicating this and see if you can locate your bug. As far as "over engineering", yes, it is very over engineered. At your level however this is not a bad thing. You have taken the knowledge and understanding of code that you have up to this point and applied it to a problem in a creative way. This is a skill that will never lose value for you and definitely gets two thumbs up!! As your knowledge grows, and as you come across new technique, your code will become less complicated, more compact, and more efficient. Here is one of your methods redone as I would do it. Simple methods that are all part of the Java language. This isn't "better" than your code, just with different techniques the method does the same thing but in half the code. As your knowledge grows your code will start looking more like this:

public static void getBuffer(String filename) throws Exception {
   FileInputStream fis = new FileInputStream(filename);
   byte[] byteBuffer = new byte[fis.available()]; // creates a buffer the size of the file
   fis.read(byteBuffer); // reads the file's bytes and stores in buffer;

   // passing in a byte array to String constructor converts bytes to human readable String
   String data = new String(byteBuffer);

   // converts string into char array
   buffer = data.toCharArray();
}

BlueJavaBanana

Level 37

5 June 2020, 16:05

I didn't use file input stream becuase the bloody task says use File Reader! That's very frustrating! Thank you for your help!

BlueJavaBanana

Level 37

5 June 2020, 16:35

May you also explain a bit more what you mean by your tag example ? do you mean: [span][span] or do you mean? [span[span]] I wasn't aware a tag can be inside a tag body <...>?

Guadalupe Gagnon

Level 37 , Tampa, United States

5 June 2020, 16:48

useful

nope, just like i posted. I added in like this: [span[span test[/span] xml:lang="en" lang="en"][b][span]Leela Turanga [/span][/b][/span]

Guadalupe Gagnon

Level 37 , Tampa, United States

5 June 2020, 16:56

useful

That code I shared above was just an example and not a correction to your code. I actually didn't read about using a FileReader. Here is code with a FileReader instead. (i also forgot to close the stream above. That is a no no at my level)

public static void getBuffer(String filename) throws Exception {
   StringBuilder data = new StringBuilder();
   BufferedReader br = new BufferedReader(new FileReader(filename));

   while(br.ready()) data.append(br.readLine());
   br.close();

   buffer = data.toString().toCharArray();
}