Pure Skills, No Exceptions
Posts tagged Recursion
Nth Element of a BST
011 years
This question seems very straight forward on the surface but an efficient solution is tricky to implement in Java due to pass-by-value semantics. Read on to see why!
Question:
Given a BST of integer elements, return the nth element as quickly as possible. Counting starts at 1 (not 0).
Input (input.txt):
4
3
-1
15
2
7
16
Output (stdout):
7
Solution:
A very naive solution is to traverse through the entire tree in-order, adding each element to an ArrayList as you go, and returning the nth element of the resulting ArrayList. This solution is simple to implement but uses extra memory and has a wasteful run-time if n is small compared to the size of the tree (although the run-time can be improved via early termination).
A better idea is to perform the recursive in-order traversal on the tree nodes while keeping a global counter that we can modify across the recursion stack. (Note that we need to define a custom wrapper object for this counter to simulate pass-by-reference of primitive values.) As far as the search logic goes, we can terminate the search and return the result as soon as the counter is fully decremented from n to 0. One final trick: we need to use the Integer primitive wrapper so we can return a null value when the nth element is not found in a substree.
public static void main (String [] args) throws IOException {
Scanner in = new Scanner (new FileReader("src/input.txt"));
int n = in.nextInt();
BSTNode root = new BSTNode(in.nextInt());
while(in.hasNext()) {
root.insert(new BSTNode(in.nextInt()));
}
System.out.println(findNthElement(root,new Counter(n)));
}
static Integer findNthElement(BSTNode node, Counter counter) {
//If we reached the end of subtree return null to indicate "not found in subtree"
if(node==null ) {
return null;
}
//Traverse left subtree
Integer result = findNthElement(node.left, counter);
//Return result if found in left subtree
if (result!=null) {
return result;
}
//In-order visit
counter.value=counter.value-1;
//Return node value if found
if(counter.value == 0) {
return node.value;
}
//Traverse right subtree
result = findNthElement(node.right, counter);
return result;
}
static class Counter {
int value;
public Counter(int value) {
this.value = value;
}
}
static class BSTNode {
BSTNode left;
BSTNode right;
int value;
public BSTNode(int value) {
this.value = value;
}
//Standard BST insertion algorithm
public void insert(BSTNode node) {
if(node.value<value) {
if (left==null) {
left = node;
} else {
left.insert(node);
}
}
if(node.value>value) {
if (right == null) {
right = node;
} else {
right.insert(node);
}
}
}
}
A Simple Regex Matcher
011 years
This is a classic technical interview question which tests knowledge of string manipulation and recursion.
Question:
Given a regex expression and a string, return true if the regex matches the string. The rules:
- Strings are composed of alphanumeric characters.
- Regexes are composed of alphanumeric characters and 2 special characters ‘.’ and ‘*’.
- A regex matches a string if every character in the regex matches every character in the string.
- Two single characters match if they are equal.
- The special character ‘.’ matches with any single character.
- If the special character ‘*’ appears in the regex, then for our string we can match 0 or more contiguous occurrences of the character preceding the ‘*’. For example, “a*bc” matches “aaabc”.
- For “.*”, we can match 0 or more contiguous occurrences of any character. For example, “.*bc” matches “xyzbc”.
- A pair of quotes (“”) denotes an empty string.
Input (input.txt):
a a
abc abc
a.c axc
a*bc aaabc
a*bc bc
.*bc xyzbc
a*aa aaaa
aa aaa
aaa aa
a* “”
Output (stdout):
true
true
true
true
true
true
true
false
false
true
Solution:
The basic idea is to attempt to match the start of the regex with the start of the string and recursively match the remaining regex against the remaining string.
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("src/input.txt"));
while (in.hasNextLine()) {
String regex = in.next();
String string = in.next();
//Special handling of empty strings
if(regex.equals("\"\"")){
regex="";
}
if(string.equals("\"\"")){
string="";
}
System.out.println(regexMatchesString(regex, string));
}
}
static boolean regexMatchesString (String regex, String string) {
if(regex.equals("") && string.equals("")) {
//Base case when regex matches string.
return true;
} else if (regex.equals("")) {
//Base case when string exceeds regex.
return false;
} else {
//Attempt to match start of regex with start of string.
if(regex.length()>1 && regex.charAt(1)=='*') {
//Handle wild card:
//a)Try ignoring wild card.
boolean matched = regexMatchesString (regex.substring(2), string);
if (matched) {
return true;
}
//b)Try consuming one or more matching characters.
for (int i=0;i<string.length();i++) {
if (matches(regex.charAt(0), string.charAt(i))) {
matched = regexMatchesString (regex.substring(2), string.substring(i+1));
if (matched) {
return true;
}
} else {
return false;
}
}
//Remaining regex does not match remaining string.
return false;
} else if (string.equals("")) {
//Base case when regex exceeds string.
return false;
} else if (matches(regex.charAt(0), string.charAt(0))) {
//Try consuming a single character.
return regexMatchesString (regex.substring(1), string.substring(1));
} else {
//Start of regex does not match start of string.
return false;
}
}
}
//Returns whether a single regex character matches a single string character.
static boolean matches (char regexChar, char stringChar) {
return regexChar == '.' || regexChar == stringChar;
}
The trickiest part of this solution is how the wildcard is handled – we must test all n+1 cases of consuming 0 to n matching characters with our wild card since it not necessarily the case that we want to consume all matching characters. (Ex. “a*ab” should match “aab” – the “a*” only consumes a single “a” in this case.)