Which language seems to be the most predominant in Selenium script development?
60% of all Selenium downloads are for Java.
This means that companies use mostly Java for Selenium test automation.
Java is not only the most popular language for Selenium test automation.
It is also more robust when used in enterprise projects.
It has mature and powerful IDEs (Eclipse and IntelliJ) too.
When selecting the language to learn for Selenium, keep this info in mind.
Don't select the language based only on which is the easiest to learn.
You may end up learning an easier language that is not really needed on your job market.
This means that companies use mostly Java for Selenium test automation.
Java is not only the most popular language for Selenium test automation.
Source: http://blog.testproject.io/2015/12/03/worlds-most-desirable-automation-skills/ |
It is also more robust when used in enterprise projects.
It has mature and powerful IDEs (Eclipse and IntelliJ) too.
When selecting the language to learn for Selenium, keep this info in mind.
Don't select the language based only on which is the easiest to learn.
You may end up learning an easier language that is not really needed on your job market.
How to convert test classes from JUNIT to TESTNG
Everybody that I talk to says that they use TestNG. I am still using JUNIT.
Am I the only person still doing it?
I am using TestNG as well.
I started with JUNIT a while ago and switched to TestNG for a number of reasons.
So you think that TestNG is better than JUNIT?
TestNG is better than JUNIT version 4.
Let me tell you why.
It does not use static methods for setting up and cleaning the test environment.
I am referring to the methods that use the @BeforeClass and @AfterClass annotations.
Oh really? This is awesome. What else does TestNG do better?
You can have dependent test scripts.
Test scripts with priorities.
It is easier to run test scripts based on categories and suites.
It is possible to have multiple data providers with values for parameters.
And test scripts can have parameters.
So many good things. Is it difficult to migrate from JUNIT to TestNG?
It is not difficult.
I will show you how it is done.
We will start with simple JUNIT test class and discuss one by one the elements that need changes.
Great, lets start.
This is our sample test class:
The test class uses many JUNIT elements such as
So we will change them one by one.
By the way, you can follow along on your computer while I make the changes.
What's the first thing to do?
First, we remove the JUNIT library from the project by
Next, remove all JUNIT packages from the beginning of the class:
Now, we have lots of errors in the test class because of missing packages.
Second, we add the TestNG library to the project by
We also need to install the TestNG plugin for Eclipse:
Done. We still have those errors in the code. Which one should we fix first?
Lets start with @Test.
Click on the error icon to the left of @Test and import the following package:
import org.testng.annotations.Test;
Is the error still there?
No. It is gone.
Excellent.
Now, about @Ignore.
In TestNG, you can ignore a test using the @Test annotation as well.
How do you do this?
By using the enabled attribute.
So replace @Ignore with @Test(enabled=false).
This should get rid of the error for @Ignore.
Done.
Very good.
Now, lets make the changes for the setUp() and tearDown() methods.
Click on the error messages and import the following 2 packages:
So these methods will not be static any longer in TestNG?
They won't.
How is your code looking so far?
I did all changes. What's next?
Lets continue a bit more with the @Test annotation.
In our JUNIT code, we have a test that tests for exceptions and one that uses a timeout.
For the test with timeout, replace @Test(timeout=1000) with @Test(timeOut=1000)
For the test with exception, replace @Test(expected = IndexOutOfBoundsException.class) with @Test(expectedExceptions = IndexOutOfBoundsException.class).
Do these changes work for you?
They sure do. Everything is simple and smooth so far.
Awesome.
We can work on the assertions now.
In the JUNIT code, we use 2 assertions: assertTrue and assertEquals.
Import the following package:
And prefix both assertions with the name of the package:
The assertions should be good now as well.
The assertions have no more errors. We are making lots of progress.
Yes.
Now, lets deal with the execution order for the test scripts.
In JUNIT, there is not a lot of support for it.
You can run the test scripts alphabetically by name with the @FixMethodOrder(MethodSorters.NAME_ASCENDING).
But if you need the test scripts run in other orders, I am not sure how you can do that.
In TestNG, this is done with the dependsOnMethods attribute of the @Test annotation.
For example,
test2() depends on test4() so test4() executes before test2.
Wow. This is so much better than @FixMethodOrder().
It is much simpler.
Make sure that you update your code before we move on.
My code is changed.
Good.
Now, lets change the code related to parameters.
In TestNG, similar with JUNIT, you need a method that provides the data for the parameter.
This method is annotated with @DataProvider and has a name attribute for the data provider name:
Then, we need to connect the data with the parameter.
We do not need any longer to pass the parameter to the class constructor.
And we dont need a class field for the parameter, either.
The test script uses the parameter in the same way a method uses a parameter.
The test script also uses the dataProvider annotation to specify which dataProvider has the data for the parameter:
Yes.
What else is there to change?
JUNIT Rules.
Right.
In TestNG, you use listeners instead of rules.
They work in a similar way.
Have a look at this sample listener:
The listener can then be attached to a test class using the @Listeners annotation:
This is very clear and similar to the JUNIT rules. With the exception that we dont need to create a class field for the new listener object.
Exactly.
Because the test class know what listener to use through the @Listeners annotation.
We missed something in the JUNIT code: categories.
In JUNIT, you can specify a category for a test script or for the whole test class.
This is done through the @Category annotation as follows:
And they are just another attribute of the @Test annotation.
For example,
OK. So use groups instead of categories.
Yes.
A good side effect is that in TestNg you do not need to create an empty class for each group.
Remember that in JUNIT, before using a category, you had to create an empty class for it.
Yes, that's right. So we will have less classes now.
Yes.
The last change that we will discuss is about JUNIT suites.
In JUNIT, you need test suites to run test scripts from multiple test classes based on categories.
For example:
And how does TestNG solve this?
TestNG uses an xml file called testng.xml for organizing test classes in test suites.
When running the tests, everything happens as per the structure of this file.
In our case, testng.xml could look like this:
In a test class, you can specify the groups to be used.
In the xml file, you can also mention the listener to be used for all test classes.
So no more suite classes?
No more.
Everything is controlled by the testng.xml file.
Let have a look at the final code that uses TestNG:
Lets run the TestNG tests.
They run correctly.
What do you think about converting a test class from JUNIT to TestNG?
Was it too complicated?
With all these details, I felt that it was very easy. I am looking forward to starting using TestNG in my test automation project.
Good luck!
Am I the only person still doing it?
I am using TestNG as well.
I started with JUNIT a while ago and switched to TestNG for a number of reasons.
So you think that TestNG is better than JUNIT?
TestNG is better than JUNIT version 4.
Let me tell you why.
It does not use static methods for setting up and cleaning the test environment.
I am referring to the methods that use the @BeforeClass and @AfterClass annotations.
Oh really? This is awesome. What else does TestNG do better?
You can have dependent test scripts.
Test scripts with priorities.
It is easier to run test scripts based on categories and suites.
It is possible to have multiple data providers with values for parameters.
And test scripts can have parameters.
So many good things. Is it difficult to migrate from JUNIT to TestNG?
It is not difficult.
I will show you how it is done.
We will start with simple JUNIT test class and discuss one by one the elements that need changes.
Great, lets start.
This is our sample test class:
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Collection; import org.junit.AfterClass; import org.junit.BeforeClass; import org.junit.FixMethodOrder; import org.junit.rules.Timeout; import org.junit.runners.MethodSorters; import org.junit.Ignore; import org.junit.Rule; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import org.junit.runners.Parameterized.Parameters; @FixMethodOrder(MethodSorters.NAME_ASCENDING) @RunWith(value = Parameterized.class) public class JUNITClass { @Rule public Timeout globalTimeout = new Timeout(1000); @Rule public CustomTestRule screenshotTestRule = new CustomTestRule(); private String keyword; public JUNITClass(String keyword) { this.keyword = keyword; } @BeforeClass public static void setUp() { } @AfterClass public static void tearDown() { } @Parameters public static Collection< Object[] > data() { Collection< Object[] > params = new ArrayList<>(100); params.add(new Object[] { "java-author-10" }); params.add(new Object[] { "oracle-date-20" }); params.add(new Object[] { "microsoft-title-15" }); return params; } @Test public void test1() { } @Test public void test2() { assertTrue(keyword.length() > 0); assertEquals(keyword.contains("-"), true); } @Ignore public void test3() { } @Test(timeout=1000) public void test4() { } @Test(expected = IndexOutOfBoundsException.class) public void test5() { throw new IndexOutOfBoundsException(); } }
The test class uses many JUNIT elements such as
- annotations (@Test, @Ignore, @BeforeClass, @AfterClass, @RunWith, @Rule, @Parameters)
- annotation attributes (expected = , timeout = )
- test fixtures (setUp() and tearDown() methods)
- assertions
So we will change them one by one.
By the way, you can follow along on your computer while I make the changes.
What's the first thing to do?
First, we remove the JUNIT library from the project by
- displaying the Navigator view in Eclipse
- opening the project
- right clicking the project name and selecting Properties
- selecting the JAVA BUILD PATH option
- selecting the Libraries tab
- selecting JUNIT 4
- clicking the REMOVE button
Next, remove all JUNIT packages from the beginning of the class:
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Collection; import org.junit.AfterClass; import org.junit.BeforeClass; import org.junit.FixMethodOrder; import org.junit.rules.Timeout; import org.junit.runners.MethodSorters; import org.junit.Ignore; import org.junit.Rule; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import org.junit.runners.Parameterized.Parameters;
Now, we have lots of errors in the test class because of missing packages.
Second, we add the TestNG library to the project by
- displaying the Navigator view in Eclipse
- opening the project
- right clicking the project name and selecting Properties
- selecting the JAVA BUILD PATH option
- selecting the Libraries tab
- clicking the ADD LIBRARY button
- selecting TestNG
- clicking the FINISH button
We also need to install the TestNG plugin for Eclipse:
- click Help in the Eclipse menu
- click Eclipse MarketPlace
- search for Test NG
- install the TestNg for Eclipse plugin
Done. We still have those errors in the code. Which one should we fix first?
Lets start with @Test.
Click on the error icon to the left of @Test and import the following package:
import org.testng.annotations.Test;
Is the error still there?
No. It is gone.
Excellent.
Now, about @Ignore.
In TestNG, you can ignore a test using the @Test annotation as well.
How do you do this?
By using the enabled attribute.
So replace @Ignore with @Test(enabled=false).
This should get rid of the error for @Ignore.
Done.
Very good.
Now, lets make the changes for the setUp() and tearDown() methods.
Click on the error messages and import the following 2 packages:
import org.testng.annotations.AfterClass; import org.testng.annotations.BeforeClass;And then remove the static keyword from the setUp() and tearDown() signatures.
So these methods will not be static any longer in TestNG?
They won't.
How is your code looking so far?
I did all changes. What's next?
Lets continue a bit more with the @Test annotation.
In our JUNIT code, we have a test that tests for exceptions and one that uses a timeout.
For the test with timeout, replace @Test(timeout=1000) with @Test(timeOut=1000)
For the test with exception, replace @Test(expected = IndexOutOfBoundsException.class) with @Test(expectedExceptions = IndexOutOfBoundsException.class).
Do these changes work for you?
They sure do. Everything is simple and smooth so far.
Awesome.
We can work on the assertions now.
In the JUNIT code, we use 2 assertions: assertTrue and assertEquals.
Import the following package:
import org.testng.AssertJUnit;
And prefix both assertions with the name of the package:
AssertJUnit.assertTrue(keyword.length() > 0); AssertJUnit.assertEquals(keyword.contains("-"), true);
The assertions should be good now as well.
The assertions have no more errors. We are making lots of progress.
Yes.
Now, lets deal with the execution order for the test scripts.
In JUNIT, there is not a lot of support for it.
You can run the test scripts alphabetically by name with the @FixMethodOrder(MethodSorters.NAME_ASCENDING).
But if you need the test scripts run in other orders, I am not sure how you can do that.
In TestNG, this is done with the dependsOnMethods attribute of the @Test annotation.
For example,
@Test(dependsOnMethods = { "test2" }) public void test1() { } @Test(dependsOnMethods = { "test4" }) public void test2(String keyword) { }In this case, test1() depends on test2() so test2() executes before test1.
test2() depends on test4() so test4() executes before test2.
Wow. This is so much better than @FixMethodOrder().
It is much simpler.
Make sure that you update your code before we move on.
My code is changed.
Good.
Now, lets change the code related to parameters.
In TestNG, similar with JUNIT, you need a method that provides the data for the parameter.
This method is annotated with @DataProvider and has a name attribute for the data provider name:
@DataProvider(name = "data") public Object[][] createData1() { return new Object[][] { {"java-author-10"}, {"oracle-date-20"}, {"microsoft-title-15"} }; }The package org.testng.annotations.DataProvider; needs to be added as well.
Then, we need to connect the data with the parameter.
We do not need any longer to pass the parameter to the class constructor.
And we dont need a class field for the parameter, either.
The test script uses the parameter in the same way a method uses a parameter.
The test script also uses the dataProvider annotation to specify which dataProvider has the data for the parameter:
@DataProvider(name = "data") public Object[][] createData1() { return new Object[][] { {"java-author-10"}, {"oracle-date-20"}, {"microsoft-title-15"} }; } @Test(dataProvider="data") public void test2(String keyword) { }Still following?
Yes.
What else is there to change?
JUNIT Rules.
Right.
In TestNG, you use listeners instead of rules.
They work in a similar way.
Have a look at this sample listener:
package TestNG; import org.testng.ITestContext; import org.testng.ITestListener; import org.testng.ITestResult; import org.testng.Reporter; public class CustomTestListener implements ITestListener { @Override public void onTestStart(ITestResult result) { } @Override public void onTestSuccess(ITestResult result) { System.out.println("PASSED TEST"); } @Override public void onTestFailure(ITestResult testResult) { System.out.println("FAILED TEST"); } @Override public void onTestSkipped(ITestResult result) { } @Override public void onTestFailedButWithinSuccessPercentage(ITestResult result) { } @Override public void onStart(ITestContext context) { } @Override public void onFinish(ITestContext context) { } }The custom listener class implements the ITestListener interface and overrides all its methods.
The listener can then be attached to a test class using the @Listeners annotation:
@Listeners(CustomTestListener.class) public class TestNGClass { ............... }
This is very clear and similar to the JUNIT rules. With the exception that we dont need to create a class field for the new listener object.
Exactly.
Because the test class know what listener to use through the @Listeners annotation.
We missed something in the JUNIT code: categories.
In JUNIT, you can specify a category for a test script or for the whole test class.
This is done through the @Category annotation as follows:
@Category({SlowTests.class}) public class JUNITClass2 { ................... }In TestNG, groups are used instead of categories.
And they are just another attribute of the @Test annotation.
For example,
@Test(groups="slowTests") public void test1() { } @Test(groups="slowTests") public void test2() { }test1() and test2() methods belong to the slowTests group.
OK. So use groups instead of categories.
Yes.
A good side effect is that in TestNg you do not need to create an empty class for each group.
Remember that in JUNIT, before using a category, you had to create an empty class for it.
Yes, that's right. So we will have less classes now.
Yes.
The last change that we will discuss is about JUNIT suites.
In JUNIT, you need test suites to run test scripts from multiple test classes based on categories.
For example:
import org.junit.experimental.categories.Categories; import org.junit.experimental.categories.Categories.IncludeCategory; import org.junit.runner.RunWith; import org.junit.runners.Suite.SuiteClasses; @RunWith(Categories.class) @IncludeCategory(SlowTests.class) @SuiteClasses({ JUNITClass.class, JUNITClass2.class })This test suite runs all test scripts from the 2 classes that are part of the specified category.
And how does TestNG solve this?
TestNG uses an xml file called testng.xml for organizing test classes in test suites.
When running the tests, everything happens as per the structure of this file.
In our case, testng.xml could look like this:
< suite name="My suite" > < listeners > < listener class-name="TestNG.CustomTestListener" /> < / listeners > < test name="test1" > < groups > < run > < include name="slowTests" /> < / run > < / groups > < classes > < class name="TestNG.TestNGClass" /> < class name="TestNG.TestNGClass2" /> < / classes > < / test > < / suite >One thing to notice in the xml file is that a suite is made of tests which are made of test classes.
In a test class, you can specify the groups to be used.
In the xml file, you can also mention the listener to be used for all test classes.
So no more suite classes?
No more.
Everything is controlled by the testng.xml file.
Let have a look at the final code that uses TestNG:
package TestNG; import static org.testng.AssertJUnit.assertTrue; import org.testng.annotations.Test; import org.testng.AssertJUnit; import org.testng.annotations.AfterClass; import org.testng.annotations.BeforeClass; import org.testng.annotations.DataProvider; import org.testng.annotations.Listeners; @Listeners(CustomTestListener.class) public class TestNGClass { @BeforeClass public void setUp() { } @AfterClass public void tearDown() { } @DataProvider(name = "data") public Object[][] createData1() { return new Object[][] { {"java-author-10"}, {"oracle-date-20"}, {"microsoft-title-15"} }; } @Test(dependsOnMethods = { "test2" }) public void test1() { assertTrue(false); } @Test(dataProvider="data", dependsOnMethods = { "test4" }) public void test2(String keyword) { AssertJUnit.assertTrue(keyword.length() > 0); AssertJUnit.assertEquals(keyword.contains("-"), true); } @Test(enabled=false) public void test3() { } @Test(timeOut=1000, groups="slowTests") public void test4() { } @Test(expectedExceptions = IndexOutOfBoundsException.class) public void test5() { throw new IndexOutOfBoundsException(); } }We are almost at the end of the conversion process.
Lets run the TestNG tests.
They run correctly.
What do you think about converting a test class from JUNIT to TestNG?
Was it too complicated?
With all these details, I felt that it was very easy. I am looking forward to starting using TestNG in my test automation project.
Good luck!
The most vital skill for a software tester to have is ?
uTest: The most vital skill for a software tester to have is ?
Gerald Weinberg: Courage.
As Kipling put it,
"If you can keep your head when all about you are losing theirs and blaming it on you."
That's what testers need.
from Testing the limits with Gerald Weinberg
Courage is very important.
Courage to reopen that difficult-to-reproduce bug that the developer closed.
Courage to escalate a bug to the development manager when the developer refuses to fix it.
Courage of having open discussions about how testing and development can be improved.
Courage of saying what things are not done well.
Courage to stop the build deployment to production because there are more serious issues left.
Courage to start learning new skills when your existing skills are old.
Courage to leave a job that keeps you doing the same not-interesting, not-challenging work for years.
Courage of becoming a consultant when you skills are mature so that you can test them out there.
Courage.
If
BY RUDYARD KIPLING
If you can keep your head when all about you
Are losing theirs and blaming it on you,
If you can trust yourself when all men doubt you,
But make allowance for their doubting too;
If you can wait and not be tired by waiting,
Or being lied about, don’t deal in lies,
Or being hated, don’t give way to hating,
And yet don’t look too good, nor talk too wise:
If you can dream—and not make dreams your master;
If you can think—and not make thoughts your aim;
If you can meet with Triumph and Disaster
And treat those two impostors just the same;
If you can bear to hear the truth you’ve spoken
Twisted by knaves to make a trap for fools,
Or watch the things you gave your life to, broken,
And stoop and build ’em up with worn-out tools:
If you can make one heap of all your winnings
And risk it on one turn of pitch-and-toss,
And lose, and start again at your beginnings
And never breathe a word about your loss;
If you can force your heart and nerve and sinew
To serve your turn long after they are gone,
And so hold on when there is nothing in you
Except the Will which says to them: ‘Hold on!’
If you can talk with crowds and keep your virtue,
Or walk with Kings—nor lose the common touch,
If neither foes nor loving friends can hurt you,
If all men count with you, but none too much;
If you can fill the unforgiving minute
With sixty seconds’ worth of distance run,
Yours is the Earth and everything that’s in it,
And—which is more—you’ll be a Man, my son!
You can win at a job interview even if no job offer is made
Any time there is a business transaction between 2 sides, the following outcomes are possible:
- Win - Win (both sides win from the transaction)
- Win - Lose (one side wins, the other loses)
- Lose - Lose (both sides loose)
An individual comes to the interview for getting a new job.
The company organizes the interview to fill a job opening.
For the job interview, a Win - Win outcome means that the individual gets the job and the company fills the open position.
What then is the equivalent of Lose - Lose?
The individual does not get the job and the company wasted time and resources for the interview.
And Win - Lose?
Usually, if a job interview is successful, both sides won.
It is unlikely that the individual is successful in the interview and the company loses something in the transaction.
It is also improbable that the individual does not get the job and the company wins at this.
Still, Win - Lose is possible.
Let's say that you go to an interview and do not do well.
You dont get the job and this sucks.
But during the interview, you learned different ways of approaching problems relevant to your job.
Or you identify gaps in your knowledge.
Or skills that you should have but sadly dont have yet.
This is the Win - Lose outcome.
You gained awareness about what you do and, more important, dont do well.
You see how other people approach problems that you struggled with.
This is a big win.
The company still did not get the position filled.
But maybe next time, you will do better.
Java Interview Test - Determine whether given string of parentheses is properly nested
I was given the following exercise at an interview that I attended a few months ago.
The interviewer wanted to verify not only that I can write Java code but also that I understand simple algorithms and data structures.
These are the exercise details:
A string S consisting of N characters is called properly nested if:
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function int solution(char *S);
that,
given a string S consisting of N characters,
returns 1 if string S is properly nested and 0 otherwise.
For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Assume that the string S consists only of the characters "(" and/or ")".
It was the first time being given this type of problem in an interview.
I was not prepared for it and did not do well.
There was no follow up after the interview and no job offer.
But this was ok because I learned something.
It is not sufficient to say that you know Java in the resume or on the blog.
You have to be ready for proving it with short exercises such as this one.
Solution with lists
I thought again about the exercise yesterday and came with a solution that uses lists.
Lets see how it should work.
We have the following string: (()(())()).
Convert the string to a list of characters.
1. Go through the list from the first to the last character.
Find all () pairs: (()(())())
Remove the () pairs to get a shorter list: (())
2. Go through the shorter list again from the first to the last character.
Find all () pairs: (())
Remove the () pairs to get a shorter list: ()
3. Go through the very short list from the first to the last character.
Find all () pairs: ()
Remove the pairs to get an empty list: []
Another way of doing it is
The code went through a few different versions until it looked good.
Version 1
Not the best code but it seems to work.
Version 2
Version 2 breaks the code into multiple methods (toCharList, pairExists, removePair, isWellFormed) and adds multiple unit tests.
A little better code and more unit tests.
Version 3
Version 3 continues what was started in version 2 and creates more methods so the code even simpler:
I would have probably passed the interview with this algorithm.
But is this the best way of solving the exercise?
It is not.
Using stacks instead of lists leads to a better solution.
Solution with stacks
How would this solution with stacks work?
For example, using the same string value: (()(())())
text[0] = '(' : add ( to stack, stack = (
text[1] = '(' : add ( to stack, stack = ((
text[2] = ')' : remove top element from stack, stack = (
text[3] = '(' : add ( to stack, stack = ((
text[4] = '(' : add ( to stack, stack = (((
text[5] = ')' : remove top element from stack, stack = ((
text[6] = ')' : remove top element from stack, stack = (
text[7] = '(' : add ( to stack, stack = ((
text[8] = ')' : remove top element from stack, stack = (
text[9] = ')' : remove top element from stack, stack = []
The initial value is well formed.
This version is by far the simplest of the 2 versions that we looked at.
It does not need any lists.
And it uses an algorithm that is both simple. fast and efficient.
My interviewer was probably expecting the solution with stacks instead of lists.
Interested in similar JAVA problems?
Click here for another Java problem with full code.
The interviewer wanted to verify not only that I can write Java code but also that I understand simple algorithms and data structures.
These are the exercise details:
A string S consisting of N characters is called properly nested if:
- S is empty
- S has the form "(U)" where U is a properly nested string
- S has the form "VW" where V and W are properly nested strings
For example, string "(()(())())" is properly nested but string "())" isn't.
Write a function int solution(char *S);
that,
given a string S consisting of N characters,
returns 1 if string S is properly nested and 0 otherwise.
For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Assume that the string S consists only of the characters "(" and/or ")".
It was the first time being given this type of problem in an interview.
I was not prepared for it and did not do well.
There was no follow up after the interview and no job offer.
But this was ok because I learned something.
It is not sufficient to say that you know Java in the resume or on the blog.
You have to be ready for proving it with short exercises such as this one.
Solution with lists
I thought again about the exercise yesterday and came with a solution that uses lists.
Lets see how it should work.
We have the following string: (()(())()).
Convert the string to a list of characters.
1. Go through the list from the first to the last character.
Find all () pairs: (()(())())
Remove the () pairs to get a shorter list: (())
2. Go through the shorter list again from the first to the last character.
Find all () pairs: (())
Remove the () pairs to get a shorter list: ()
3. Go through the very short list from the first to the last character.
Find all () pairs: ()
Remove the pairs to get an empty list: []
Another way of doing it is
- Go through the list from the first to the last character.
- Find all () pairs: (()(())())
- Remove the () pairs to get a shorter list: (())
- Continue while you can find more () pairs.
- When no more pairs can be found
- if the list is empty, the initial value is well formed
- if the list is not empty, the initial value is not well formed
Version 1
import java.util.ArrayList; import java.util.List; import org.junit.Test; public class Version1 { @Test public void testNestedBrackets() { String text = "(()(())())"; //convert the string value to a list of characters List< Character > charList = new ArrayList< Character >(); for (char c : text.toCharArray()) charList.add(c); //keep removing brackets fromn the list until there are no brackets left Boolean bracketsLeft = true; while (bracketsLeft == true && charList.size() > 0) { int pairsRemoved = 0; //remove the brackets pairs from the list for (int i = 0; i < charList.size(); i++) if (charList.get(i) == '(' && charList.get(i+1) == ')') { charList.remove(i+1); charList.remove(i); i = i -1; pairsRemoved ++; } if (pairsRemoved == 0) bracketsLeft = false; } } }
Not the best code but it seems to work.
Version 2
Version 2 breaks the code into multiple methods (toCharList, pairExists, removePair, isWellFormed) and adds multiple unit tests.
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.List; import org.junit.Ignore; import org.junit.Test; public class Version2 { //converts a string to a list of characters private List< character > toCharList(String text) { List< character > charList = new ArrayList< character >(); for (char c : text.toCharArray()) charList.add(c); return charList; } //checks if a () pair exists at position i in the list private Boolean pairExists(int i, List< character > list) { return (i == list.size() - 1 ? false : list.get(i) == '(' && list.get(i+1) == ')'); } //removes a () pair from the list from position index private void removePair(int index, List< character > list) { list.remove(index+1); list.remove(index); } //checks if the list of ( and ) is well formed private Boolean isWellFormed(List< character > charList) { while (charList.size() > 0) { int pairsRemoved = 0; for (int i = 0; i < charList.size(); i++) if (pairExists(i, charList)) { removePair(i, charList); pairsRemoved ++; i = i - 1; } if (pairsRemoved == 0) break; } return charList.size() == 0; } @Test public void testNestedBracketsValidString() { String text = "(()(())())"; List< character > charList = toCharList(text); assertTrue(isWellFormed(charList)); } @Test public void testNestedBracketsInValidString() { String text = "(()(())()"; List< character > charList = toCharList(text); assertFalse(isWellFormed(charList)); } @Test public void testNestedBracketsEmptyString() { String text = ""; List< character > charList = toCharList(text); assertTrue(isWellFormed(charList)); } @Test public void testNestedBracketsShortString() { String text = "("; List< character > charList = toCharList(text); assertFalse(isWellFormed(charList)); } }
A little better code and more unit tests.
Version 3
Version 3 continues what was started in version 2 and creates more methods so the code even simpler:
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.List; import org.junit.Ignore; import org.junit.Test; public class Version3 { //convert a string to a list of characters private List< Character > toCharList(String text) { List< Character > charList = new ArrayList< character >(); for (char c : text.toCharArray()) charList.add(c); return charList; } //checks if a () pair exists in the list at position i private Boolean pairExists(int i, List< Character > list) { return (i == list.size() - 1 ? false : list.get(i) == '(' && list.get(i+1) == ')'); } //checks if at least a () pair exists in the list private Boolean pairExists(List< Character > list) { Boolean result = false; if (list.size() > 1) for (int i = 0; i < list.size(); i++) if(pairExists(i, list)) { result = true; break; } return result; } //remove a () pair from the list from position index private void removePair(int index, List< Character > list) { list.remove(index+1); list.remove(index); } //checks if the list of ( and ) is well formed private Boolean isWellFormed(List< Character > charList) { do charList = removePairs(charList); while (pairExists(charList)); return charList.size() == 0; } //removes all () pairs from the list private List< character > removePairs(List< Character > charList) { List< Character > list = charList; for (int i = 0; i < charList.size(); i++) if (pairExists(i, list)) { removePair(i, list); i = i - 1; } return list; } @Test public void testNestedBracketsValidString() { String text = "(()(())())"; List< Character > charList = toCharList(text); assertTrue(isWellFormed(charList)); } @Test public void testNestedBracketsInValidString() { String text = "(()(())()"; List< Character > charList = toCharList(text); assertFalse(isWellFormed(charList)); } @Test public void testNestedBracketsEmptyString() { String text = ""; List< Character > charList = toCharList(text); assertTrue(isWellFormed(charList)); } @Test public void testNestedBracketsShortString() { String text = "("; List< Character > charList = toCharList(text); assertFalse(isWellFormed(charList)); } }
I would have probably passed the interview with this algorithm.
But is this the best way of solving the exercise?
It is not.
Using stacks instead of lists leads to a better solution.
Solution with stacks
How would this solution with stacks work?
- Go through the string from the first to the last character.
- If the current character is (, add it to the stack.
- If the current character is ), remove the top element from the stack.
- After going through all list characters,
- if the stack size is 0, the initial value is well formed.
- If the stack size is greater than 0, the initial value is not well formed
For example, using the same string value: (()(())())
text[0] = '(' : add ( to stack, stack = (
text[1] = '(' : add ( to stack, stack = ((
text[2] = ')' : remove top element from stack, stack = (
text[3] = '(' : add ( to stack, stack = ((
text[4] = '(' : add ( to stack, stack = (((
text[5] = ')' : remove top element from stack, stack = ((
text[6] = ')' : remove top element from stack, stack = (
text[7] = '(' : add ( to stack, stack = ((
text[8] = ')' : remove top element from stack, stack = (
text[9] = ')' : remove top element from stack, stack = []
The initial value is well formed.
import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Stack; import org.junit.Ignore; import org.junit.Test; public class Version4 { private Boolean isWellFormed(String text) { Stack< character > stack = new Stack< character >(); for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == '(') stack.push(text.charAt(i)); if (text.charAt(i) == ')') stack.pop(); displayStack(stack); } return stack.size() == 0; } @Test public void testNestedBracketsValidString() { assertTrue(isWellFormed("(()(())())")); } @Test public void testNestedBracketsInValidString() { assertFalse(isWellFormed("(()(())()")); } @Test public void testNestedBracketsEmptyString() { assertTrue(isWellFormed("")); } @Test public void testNestedBracketsShortString() { assertFalse(isWellFormed("(")); } }
This version is by far the simplest of the 2 versions that we looked at.
It does not need any lists.
And it uses an algorithm that is both simple. fast and efficient.
My interviewer was probably expecting the solution with stacks instead of lists.
Interested in similar JAVA problems?
Click here for another Java problem with full code.
Subscribe to:
Posts (Atom)