No results found for the specified position. What is the smallest letter greater than t... Java Beginner Level Binary Search Mock Interview

MockQuestions

Java Beginner Level Binary Search Mock Interview

Question 2 of 2 for our Java Beginner Level Binary Search Mock Interview

Get More Information About Our Java Beginner Level Binary Search Interview Questions

Question 2 of 2

What is the smallest letter greater than the target?

This interview question concentrates on the developer's skills working with Java arrays and binary search.

You are given an array of English lowercase letters in sorted order. You are also given a target letter. Your task is to find the smallest element in the array that is larger than the given target.

NOTE:- Letters do wrap around. It means if we don’t have any element in the array larger than the target, we return the smallest letter as the answer. See examples.

/*Example*/

letters = [“c”, “g”, “l”]
target = “a”
expected output = “c”

letters = [“c”, “g”, “l”]
target = “c”
expected output = “g”

letters = [“c”, “g”, “l”]
target = “d”
expected output = “g”

letters = [“c”, “g”, “l”]
target = “j”
expected output = “c” (letters wrapped around)

letters = [“c”, “g”, “l”]
target = “k”
expected output = “c” (letters wrapped around)

Solution:

This is a lot like a search for integers. So we can use binary search for this. We need to care about the “wrap around” case. For handling this, we increase our search space. Instead of using letters.length - 1 for right pointer, we will use letter.length. The left pointer after the loop will be the index of the letter satisfying the given condition. When we can not find any letter greater than the target, the value of left will be letters.length after the loop. Then we take modulo to return the first element of the array.

class Solution {
	public char nextGreatestLetter(char[] letters, char target) {
    	    int left = 0;
    	    int right = letters.length;
   	 
    	    while(left < right) {
        	    int mid = left + (right -left) / 2;
        	    if (letters[mid] > target) {
            	    right = mid;
        	    } else {
            	    left = mid + 1;
        	    }
    	    }
    	    return letters[left % letters.length];
	}    
}

Time complexity- O(log n)
Space complexity- O(1)

Written by on May 21st, 2021

Previous Question

Next Question

How to Answer: What is the smallest letter greater than the target?

Advice and answer examples written specifically for a Java Beginner Level Binary Search job interview.

  • 2. What is the smallest letter greater than the target?

      This interview question concentrates on the developer's skills working with Java arrays and binary search.

      You are given an array of English lowercase letters in sorted order. You are also given a target letter. Your task is to find the smallest element in the array that is larger than the given target.

      NOTE:- Letters do wrap around. It means if we don’t have any element in the array larger than the target, we return the smallest letter as the answer. See examples.

      /*Example*/

letters = [“c”, “g”, “l”]
target = “a”
expected output = “c”

letters = [“c”, “g”, “l”]
target = “c”
expected output = “g”

letters = [“c”, “g”, “l”]
target = “d”
expected output = “g”

letters = [“c”, “g”, “l”]
target = “j”
expected output = “c” (letters wrapped around)

letters = [“c”, “g”, “l”]
target = “k”
expected output = “c” (letters wrapped around)

      Solution:

      This is a lot like a search for integers. So we can use binary search for this. We need to care about the “wrap around” case. For handling this, we increase our search space. Instead of using letters.length - 1 for right pointer, we will use letter.length. The left pointer after the loop will be the index of the letter satisfying the given condition. When we can not find any letter greater than the target, the value of left will be letters.length after the loop. Then we take modulo to return the first element of the array.

      class Solution {
	public char nextGreatestLetter(char[] letters, char target) {
    	    int left = 0;
    	    int right = letters.length;
   	 
    	    while(left < right) {
        	    int mid = left + (right -left) / 2;
        	    if (letters[mid] > target) {
            	    right = mid;
        	    } else {
            	    left = mid + 1;
        	    }
    	    }
    	    return letters[left % letters.length];
	}    
}

      Time complexity- O(log n)
      Space complexity- O(1)

      Written by Jennie Taylor on May 21st, 2021

    • Next Question