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: 

• 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

1. Go through the list from the first to the last character.
2. Find all () pairs: (()(())())
3. Remove the () pairs to get a shorter list: (())
4. Continue while you can find more () pairs.
5. When no more pairs can be found
1. if the list is empty, the initial value is well formed
2. if the list is not empty, the initial value is not well formed

The code went through a few different versions until it looked good.



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, 

1. if the stack size is 0, the initial value is well formed.
2. 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.

Share this post