Discover more from Junaid Effendi | Sharing knowledge for Engineers
Interview Coding Challenge - Nth Prime Number
Today, sharing the interview challenge #2 which is a very common problem and its solution is quite interesting as there are so many ways to solve. From the question it looks very easy for a beginner however when we try to solve in front of the interviewer on a white board most of us gets confused.
Question: Write a function that will return the nth prime number.
Example: 6thprime number is 13. How > (2, 3, 5, 7, 11, 13)
Prime Number: A number that is only divisible by integer 1 and itself is called a prime number, 13 has two, 1 and 13.
Solution: I will write everything in Scala as I have been working in that language for quite a while now. Will try to take it step by step with different approaches.
This one is a naive approach just to get the work done which is absolutely fine if you start your interview with this one.
val n = 6
def nthPrimeNumber(): Array[Int] = {
var result = Array[Int]()
for(i <- 1 to 10 * n){
var count = 0
for(j <- 2 to i-1){
// Check the remainder for each value less than the number
if(i % j == 0){
count = count + 1
}
}
if(count == 0) // Add in Array if no divisor found
result = result :+ i
}
return result
}
nthPrimeNumber()(n)
Second is using high order function, which makes it cleaner and gives a modern look.
def nthPrimeNumber(n: Int) : Int = {
val range = (1 to 10 * n).toArray
val result = range.map(i =>
if((2 until i) forall (i % _ != 0)) i
else 0).filter(_ != 0)
return result(n)
}
nthPrimeNumber(n)
Now, we can make code more clean, no need to have variables, return type and return keyword. It can also be written in one liner.
def nthPrimeNumber(n: Int) =
(1 to 10 * n).toArray.map(i =>
if((2 until i) forall (i % _ != 0)) i
else 0).
filter(_ != 0)(n)
nthPrimeNumber(n)
All these approaches have one thing in common which is they build an array of prime numbers then return the required number by index, but this is not performant, it keeps running till it find all the required combination, in our case 10 * n
(arbitrary equation).
The only way this program might be useful if the same function is called multiple times and we store the value somewhere for instance in cache, then it will just get the number instead of recalculating the whole result.
Lets look at a better way. Modifying first approach to return the result immediately once found. Also, avoiding several iterations by starting the loop with 2
and fetching the result by index-1 (nth – 1)
.
def nthPrimeNumber(n: Int) : Int = {
var result = Array[Int]()
for(i <- 2 to 10 * n){
var count = 0
for(j <- 2 to i-1){
if(i % j == 0){
count = count + 1
}
}
if (result.length-1 == n) return result(n)
if(count == 0 ) result = result :+ i
}
return 0
}
nthPrimeNumber(n-1)
One last touch,making code look beautiful.
def nthPrimeNumber(n: Int) : Int = {
var count = 0
for(i <- 2 to 10 * n){
if((2 until i) forall (i % _ != 0)) count = count + 1
if(count-1 == n) return i // return when found
}
return 0
}
nthPrimeNumber(n-1)
Now you can see how and what changes you can do to make any code better.
High Order functions are cool, but I always prefer to start with the basic if else and loops in coding interviews as they are the underlying logic for several functions.
Let me know your thoughts in the comments. Share your solution!
Subscribe to Junaid Effendi | Sharing knowledge for Engineers
Covering tech, career, data, growth experiences from my journey.