Java Interview Guide: How to Build Confidence With a Solid Understanding of Core Java Principles pdfdrive com


Given a line of text, how would you verify that the number of open and



Yüklə 0,53 Mb.
Pdf görüntüsü
səhifə40/47
tarix06.05.2023
ölçüsü0,53 Mb.
#108601
1   ...   36   37   38   39   40   41   42   43   ...   47
Java Interview Guide

Given a line of text, how would you verify that the number of open and
closed parentheses are balanced?


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.



Yüklə 0,53 Mb.

Dostları ilə paylaş:
1   ...   36   37   38   39   40   41   42   43   ...   47




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin