I had been hearing about HackerRank and I had a go at it to see just how my Java skills were. I haven’t used Java in some time now as I spent most of my time these days writing either Swift, Javascript or Typescript code relative to the project requirements. HackerRank has 64 questions on Java so far and I have managed to get through about 36 of those. One of the questions was on the “parenthesis balanced” problem. A standard data structure question that almost everyone knows. When I solved it, I realised the HackerRank environment would not accept my java code that worked in Eclipse environment. In this post, I will share my solutions to it, as well as my approach to solving that problem.
HackerRank environment
I was a bit nervous while getting into this, since I have not used Java in a while. However, as I realised once I started working on the problems, Java is still (mostly) Java and I am good at it! There’s a reason why I was a Java tutor at University of New South Wales while doing my research. FYI, One of my students (now friend) is a Principle Java Developer at a very large organisation.
Having said all that, I still haven’t played with some of the new Java 8+ stuff e.g. Stream, optionals etc. However I don’t think picking it up should be a problem because I have worked with those things in Swift, Javascript/Typescript.
Anyway, as I started working through some of the Java problems on HackerRank, I came across the problem.
Problem: Java Stack
One of the most commonly asked problems and pretty much all engineers would know the solution to this.
A string containing only parentheses is balanced if the following is true: 1. if it is an empty string 2. if A and B are correct, AB is correct, 3. if A is correct, (A) and {A} and [A] are also correct.
Examples of some correctly balanced strings are: “{}()”, “[{()}]”, “({()})”
Examples of some unbalanced strings are: “{}(“, “({)}”, “[[“, “}{” etc.
Solution
I tried 3 different solutions using Java Stack and here I will list them all,
Solution 1
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input=sc.next();
Stack<String> paren = new Stack<String>();
for (String p : input.split("")) {
if (paren.isEmpty()) {
paren.push(p);
} else {
String top = paren.peek();
if(p.equals("}") && top.equals("{")
||(p.equals("]") && top.equals("[")
||(p.equals(")") && top.equals("(")))) {
paren.pop();
} else {
paren.push(p);
}
}
}
String toPrint = (paren.isEmpty()) ? "true" : "false";
System.out.println(toPrint);
}I know this was the answer to my problem as it was working in my local (Eclipse) environment, however this code was failing test cases in HackerRank. I thought about it and realised HackerRank prints the the code output (under ‘your output’) for the first test case on console. This gave me an idea, hmm how about I log the size of my paren Stack with that? So I did and realised that for the test cases where it says unbalanced when they are indeed balanced, the size of the stack is 1. Hence my next solution,
Solution 2
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input=sc.next();
Stack<String> paren = new Stack<String>();
for (String p : input.split("")) {
if (paren.isEmpty()) {
paren.push(p);
} else {
String top = paren.peek();
if(p.equals("}") && top.equals("{")
||(p.equals("]") && top.equals("[")
||(p.equals(")") && top.equals("(")))) {
paren.pop();
} else {
paren.push(p);
}
}
}
if(paren.size()<=1){
System.out.println("true");
} else {
System.out.println("false");
}
}This solution worked! I mean, it passes all the test cases but still not quite right is it? Let’s try one more thing,
Solution 3
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String input = sc.next();
Stack<String> paren = new Stack<String>();
for (String p : input.split("")) {
if (!p.isEmpty()) { //THIS WAS MISSING IN THE PREVIOUS METHODS
if (paren.isEmpty()) {
paren.push(p);
} else {
String top = paren.peek();
if (p.equals("}") && top.equals("{")
|| (p.equals("]") && top.equals("[")
|| (p.equals(")") && top.equals("(")))) {
paren.pop();
} else {
paren.push(p);
}
}
}
}
String toPrint = (paren.isEmpty()) ? "true" : "false";
System.out.println(toPrint);
}As you can see, the main difference between this and all other methods is the check to ensure the string isn’t empty before pushing it onto Stack. This is something relative to the HackerRank environment and how the input is read via Scanner. Add to that I am just not that familiar with the HackerRank environment as of yet, hence it took me three tries to get to a solution to a simple problem.
Summary
If there’s one thing that this exercise clarifies to me, it’s my hacker mindset. More than my knowledge of Data Structures, it tells me of my ability to find solutions or to hack something to get the right answer. I cannot believe I thought about printing the Stack size and putting a count check before the empty string check. Actually maybe I can believe it, I’ve always had this hacker mindset and guess what? It’s inherited. My mum has it too, that woman grew up without mobile phones or internet connectivity in her days. However recently she figured out how to cast Youtube from her 6 year old Android tablet to my Sony Bravia Smart TV running Android 8.0. I couldn’t figure out why it wouldn’t cast but she did. Then when I asked her, she walked me through her process of getting it done. It was a simple brute force approach that involved trying some 5+ solutions until one fo them worked.
As usual, if you find any of my posts useful support me by buying or even trying one of my apps on the App Store.
Also, if you can leave a review on the App Store or Google Play Store, that would help too.
0 Comments