In order to simplify this problem, you could ignore the
irrelevant characters and
add all of the parentheses to a string. Then, you could recursively loop through
the string and remove every immediate pair of open and closed parentheses (()
()) -> ()
. When the string has no more pairs,
the number of remaining
characters will determine if the parentheses were balanced.
As an optimization, every time you add a closed parenthesis to the string you
could check to see if the last character was an open parenthesis and discard them
both instead. In fact, there would be no need for recursion if you did this because
you are essentially treating the string like a stack.
Knowing that, you could solve
this problem efficiently by using an ArrayDeque to push and pop open
parentheses and checking if the stack was empty afterwards.
Given an unsorted list with one missing number from 1 to 100, how would
you determine the missing number?
The simplest solution to this problem is to iterate through the list 100
times and
search for a specific value during each iteration. However, it’s worth criticizing
any solution that runs in quadratic time. If you sort the list first,
you could find
the number that didn’t correspond to an appropriate index in linearithmic time.
Faster still, you could put each value into a HashSet, and find the missing
value in linear time.
It’s impossible to solve this problem
faster than linear time, but it’s important
to note that time complexity only measures the growth rate of an algorithm.
In fact, this problem can be solved more efficiently by computing the sum of all
numbers and subtracting it from the total
sum provided by the formula
n(n+1)/2
. Whenever you critique a solution, remember to take memory into
consideration when time complexity is no longer a factor.
