10 Java Intermediate Level Greedy Interview Questions & Answers

This question shows the developer's ability to work with Java array frequencies.

You are given string str. Your task is to rearrange the characters of the string so that any two characters that are adjacent are not the same. If it is not possible to rearrange the string, return the empty string “”.
For the ith character of str, adjacent characters to it are (i - 1)st and (i + 1)st characters.

/*Example*/

Given: str = “aab”
Expected output: “aba”

Given: str = “aaa”
Expected output: “”

Solution:

First, we will count the frequencies of each character in the array freq. We will also track the character mostFreqCharCode which is the most frequency, that is, the character that occurs the most number of times in str. Let len be the length of str, which also be the length of the resultant string. We will try to put the most frequent character at even indices because

● countEvenIndices = countOddIndices, for array of even length
● countEvenIndices = countOddIndices + 1, for array of odd length

The frequency of the most frequent character MUST be less than or equal to countEvenIndices, because, otherwise we will not be able to reorganize the string. For example, let len = 5, the most frequent character is “s” with frequency 4,
countEvenIndices = Math.ceil(len / 2) = 3
array indices: 0 1 2 3 4
array: “s” _ “s” _ “s”

We have placed 3 out of 4 the most frequent characters. Now there are two places left:- index 1 and index 3. But we can’t place “s” at those indices because it will make adjacent characters the same. If it does not satisfy the condition, we will return the empty string “”.

After confirming that the solution exists, we will place all the characters in the res array one by one. We will start with the most frequent character and will place it at even indices. After placing the most frequent character we will place other characters first at remaining even indices (if any) then at odd indices.

class Solution {
    public String reorganizeString(String str) {
        int len = str.length();
        Pair<int[], Integer> count = countChars(str);
        int freq[] = count.getKey();
        int mostFreqCharCode = count.getValue();
 
        if (!isPossible(len, freq[mostFreqCharCode])) {
            return "";
        }
    
        char res[] = new char[len];    
        fillMostFreqChar(res, freq, mostFreqCharCode);
        fillRestChars(res, freq);
    
        return String.valueOf(res);
    }
    
    private Pair<int[], Integer> countChars(String str) {
        int freq[] = new int[26];
        Arrays.fill(freq, 0);
        int len = str.length();
        int mostFreqCharCode = 0;
    
        for (Character ch : str.toCharArray()) {
            int code = ch - 97;
            freq[code]++;
 
            if (freq[code] > freq[mostFreqCharCode]) {
                mostFreqCharCode = code;
            }
        }
        
        return new Pair(freq, mostFreqCharCode);
    }
    
    private boolean isPossible(int len, int freqOfMostFreqCharCode) {
        double countEvenIndices = Math.ceil((double)len / 2);
        return freqOfMostFreqCharCode <= countEvenIndices;
    }
    
    private void fillMostFreqChar(char[] res, int[] freq, 
int mostFreqCharCode) {
        int i = 0;
        
        while (freq[mostFreqCharCode] != 0) {
            res[i] = (char)(mostFreqCharCode + 97);
            i += 2;
            freq[mostFreqCharCode]--;
        }
    }

    private void fillRestChars(char[] res, int[] freq) {
        int i = 0;
        // find first even index which is not filled
        while (i < res.length) {
            if(res[i] != '\u0000') i += 2;
            else break;
        }
    
        for (int charCode = 0; charCode < 26; charCode++) {
            while (freq[charCode] > 0) {
                // all even indices are filled
                // start filling at odd indices
                if (i >= res.length) i = 1;
                res[i] = (char)(charCode + 97);
                i += 2;
                freq[charCode]--;
            }
        }
    }

}

Time complexity- O(len)
Space complexity- O(len)

This question shows the developer's ability to work with Java integers and arrays.

You invent a new single-player game- “The card-power game”. In this game, you are given an integer power and an array of cards initially. The value of cards[i] denotes the power required to play the ith card. Your score is 0 initially. You play a series of moves to maximize your score.
In one move, you choose the ith card with power cards[i]. You can play one in two ways:

1. Play card face up:- If your current power is at least cards[i], you play the ith card face up. Your power decreases by cards[i] and you gain 1 score.
2. Play card face down:- If your current score is at least 1, you play the ith card face down. Your power increases by cards[i] and you lose 1 score.

You can play a card at most once in any order. It may be the case that you don’t play some cards. Return your maximized score.

/*Example*/

Given: cards = [100, 200, 300, 400]		power = 200
Expected output: 2
Explanation:
1.	Play 0th card face up		power = 100	score = 1
2.	Play 3rd card face down	power = 500	score = 0
3.	Play 1st card face up		power = 300	score = 1
4.	Play 2nd card face up		power = 0		score = 2

Solution:

We will play cards face up and face down greedily. First of all, we will sort the cards with their power in increasing order. We will play cards face up starting from the lowest power. If we need more power, we will play the card face down with the highest power.

class Solution {
    public int maxScore(int[] cards, int power) {
        Arrays.sort(cards);
        
        int left = 0;
        int right = cards.length - 1;
        int score = 0;
        int ans = 0;
    
        while(left <= right && (power >= cards[left] || score > 0)) {
            // we have enough power to play lower cards face up
            // this will reduce power and increase score by 1
            while(left <= right && power >= cards[left]) {
                power -= cards[left];
                left++;
                score++;
            }
        
            ans = Math.max(ans, score);
 
            // play a higher card face down to increase power
            if (left <= right && score > 0) {
                power += cards[right];
                right--;
                score--;
            }
        }
    
        return ans;
    }
    
}

Time complexity- O(n logn) // to sort the array
Space complexity- O(1)

This question focuses on Java array generators.

You are given an array of integer generators. You can select some of the integers from the array (possibly none or all), and add them up to "generate” a new integer. Your task is to count and return the number of consecutive integers that you can “generate” from the array generators starting from and including 0.

/*Example*/

Given generators = [1, 3]
Expected output: 2
Explanation: You can generate two consecutive integers viz. 0 and 1.

Given generators = [1, 1, 1, 4]
Expected output: 8
Explanation: You can generate the following consecutive integers:-
[] -> 0
[1] -> 1
[1, 1] -> 2
[1, 1, 1] -> 3
[4] -> 4
[1, 4] -> 5
[1, 1, 4] -> 6
[1, 1, 1, 4] -> 7
Thus you can generate eight consecutive integers from 0 to 1.

Solution:

Let x1, x2, …, xk be the k integers from the given array generators. We call such one integer a “generator”. Let’s assume using these k integers (k generators), we can generate consecutive integers from 0 to a. That is, we have ways to generate the following consecutive integers:
0 1 2 … a - 2 a - 1 a

Now let’s use one more generator other than the mentioned k generators and we wish to generate a new integer (a + 1). We can do it following ways:

if we have one more generator gen = 1 in generators, we can generate (a + 1) using gen = 1 and already generated integer (a),
or if we have one more generator gen = 2 in generators, we can generate (a + 1) using gen = 2 and already generated integer (a - 1),
or if we have one more generator gen = 3 in generators, we can generate (a + 1) using gen = 3 and already generated integer (a - 2),
…
…

or if we have one more generator gen = (a - 1) in generators, we can generate (a + 1) using gen = (a - 1) and already generated integer (2),
or if we have one more generator gen = a in generators, we can generate (a + 1) using gen = a and already generated integer (1),
or if we have one more generator gen = (a + 1) in generators, we can generate (a + 1) by selecting only one number from generators, gen = (a + 1).

Thus, to generate (a + 1), we require one more generator gen with condition 1 <= gen <= (a + 1). When we have such a generator, we can always generate more integers from (a + 1) to (a + gen), or we can say that we can generate all integers from 0 to (a + gen) using generators x1, x2, …, xk and gen.

If we can generate integers from 0 to a, and we can not find such gen, that is, the next-gen is either 0 or gen > a + 1, then we can not generate the consecutive integers further. So our answer will be a + 1 (we can generate a + 1 number of integers from 0 to a).

class Solution {
    public int getMaximumConsecutive(int[] generators) {
        Arrays.sort(generators);
        int currSum = 0;
    
        for (int gen : generators) {
            if (gen > currSum + 1) break;
            currSum += gen;
        }
        
        return currSum + 1;
    }
}

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

This question concentrates on Java stacks.

You are given a string str. Your task is to remove the duplicate characters so that every character in the string appears exactly once. The relative order of the characters in the resultant string must be the same as in the original string and must be the smallest in lexicographical order.

/*Example*/

Given str = “bcabc”
Expected output: “abc”

Given str = “cbacdcbc”
Expected output: “acbd”

Solution:

We will do it greedily. We will maintain an array stack. We will iterate over each letter in character and put them in stack on the following conditions:

=> if we have the current character char which is lexicographically smaller than the top character on stack (topChar), we will pop topChar from the stack and push char to stack. We will pop topChar from the stack only if it wasn’t its last occurrence in the string (isTopCharReduntant function does this job in the code).

To note the index of the last occurrence of each character we will use the function findLastOcc which stores the index of the last occurrence of each character in the str in a Map. Then we will iterate over each char str again and do the process as mentioned above. We will also maintain a Set to flag the characters which are already included in the stack.

For example: str = “cbacdcbc”
lastOcc = {
“c” => 7,
“b” => 6,
“a” => 2,
“d” => 4,
}

After iteration 1:- stack = [“c”] visited = {“c”}
After iteration 2:- stack = [“b”] visited = {“b”}
(“c” is removed from the top because “b” < “c” and index 0 was not the last occurrence of “c”)
After iteration 3:- stack = [“a”] visited = {“a”}
(“b” is removed from the top because “a” < “b” and index 1 was not the last occurrence of “b”)
After iteration 4:- stack = [“a”, “c”] visited = {“a”, “c”}
(“a” is not removed from the top because “c” is not less than “a”)
After iteration 5:- stack = [“a”, “c”, “d”] visited = {“a”, “c”, “d”}
(“c” is not removed from the top because “d” is not less than “c”)
After iteration 6:- stack = [“a”, “c”, “d”] visited = {“a”, “c”, “d”}
(“c” is already visited)
After iteration 7:- stack = [“a”, “c”, “d”, “b”] visited = {“a”, “c”, “d”, b”}
(“d” is not removed from the top because “b” is less than “d” but index 4 was the last occurrence of “d”)
After iteration 8:- stack = [“a”, “c”, “d”, “b”] visited = {“a”, “c”, “d”, b”}
(“c” is already visited)

class Solution {
    
    private Stack<Character> stack;
    private Map<Character, Integer> lastOcc;
    
    public String removeDuplicateLetters(String str) {
        lastOcc = new HashMap<Character, Integer>();
        findLastOcc(str);
        
        Set<Character> visited = new HashSet<Character>();
        stack = new Stack<Character>();
        
    
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
        
            if (visited.contains(ch)) continue;
        
            while(isTopCharReduntant(ch, i)) {
                char top = stack.pop();
                visited.remove(top);
            }
        
            stack.push(ch);        
            visited.add(ch);
        }
        
        StringBuilder sb = new StringBuilder();
        for (Character ch : stack) {
            sb.append(ch);
        }
        
        return sb.toString();
    }
    
    private boolean isTopCharReduntant(char ch, int i){
        if(stack.empty()) return false;
        char topChar = stack.peek();
        
        return ch < topChar &&
            lastOcc.get(topChar) > i;
    }
    
    private void findLastOcc(String str) {
        for (int i = 0; i < str.length(); i++) {
            lastOcc.put(str.charAt(i), i);
        }
    }

}

n = length of str
Time complexity- O(n)
Space complexity- O(26) = O(1)

This question concentrates on JavaScript partitions.

You are given string str consisting of only lowercase English letters. Your task is to partition the string into as many parts as possible in such a way that every letter appears in at most one partition. You need to return the lengths of these partitions in the array.

/*Example*/

Given str = "ababcbacadefegdehijhklij"
Expected output: [9, 7, 8]
Explanation: The possible partitions are "ababcbaca", "defegde" and "hijhklij".

Solution:

We will iterate over the whole string. We will choose the smallest left-justified partition.
Let’s assume the first character (character at index 0) is “a”. The first partition must include it and also the last occurrence of “a”. Let the index of the last occurrence of “a” is last_a.

Let the left index of this partition is leftEnd and the right index is rightEnd. So leftEnd = 0 and rightEnd = last_a.

There may be some other character in between the indices 0 and rightEnd which may result in a bigger partition. Let’s say this character is “b” with the last occurrence index last_b such that last_b > rightEnd. In such a scenario, the last occurrence of “b” must also be included in this partition. So rightEnd is updated to last_b (that is, rightEnd = last_b).

We iterate over the characters for the current partition. As soon as we reach an index equal to rightEnd of the partition, we push it’s length to the answer array and look for another partition.

class Solution {
    public List<Integer> partitionLabels(String str) {
        int last[] = new int[26];
        
        for (int i = 0; i < str.length(); i++) {
            int charIdx = charIdxAt(str, i);
            last[charIdx] = i;
        }
    
        int rightEnd = 0;
        int leftEnd = 0;
        List<Integer> ans = new ArrayList<Integer>();
        
        for (int i = 0; i < str.length(); i++) {
            int charIdx = charIdxAt(str, i);
            rightEnd = Math.max(rightEnd, last[charIdx]);
        
            if (i == rightEnd) {
                ans.add(rightEnd - leftEnd + 1);
                leftEnd = i + 1;
            }
        }
        
        return ans;
    }
    
    private int charIdxAt(String str, Integer idx) {
        int charCode = str.charAt(idx);
        return charCode - 97;
    }
    
}

n = size of logs
Time complexity- O(n)
Space complexity- O(26) = O(1)

This question shows the developer's ability to work with Java iterations.

You are given array nums of non-negative integers. You are initially positioned at the first index of nums. nums[i] represents your maximum jump from that position. Your goal is to reach the last index of the arrays in the minimum number of jumps. Find and return the minimum number of jumps required.

/*Example*/

Given nums = [2, 3, 1, 1, 4]
Expected output: 2
Explanation: The first jump is from index 0 to 1 and next from 1 to the last index.

Solution:

We will iterate overall numbers. We start from the first number at index 0. Let’s say we can jump up to the index currEnd from index 0 (that is nums[0] = currEnd). We can jump in the range [1, currEnd] from index 0 in the first jump. For every index, we will check the farthest that we can reach and store in currFarthest. When we reach currEnd, we trigger the next jump and set currEnd to new currFarthest and increase jumpsCount.

class Solution {
    public boolean canJump(int[] nums) {
        int jumpsCount = 0;
        int currEnd = 0;
        int currFarthest = 0;
        
        for (int i = 0; i < nums.length - 1; i++) {
            currFarthest = Math.max(currFarthest, i + nums[i]);
        
            if (i == currEnd) {
                currEnd = currFarthest;
                jumpsCount++;
            }
        }
        
        return jumpsCount;
    }
    
}

n = size of nums
Time complexity- O(n)
Space complexity- O(1)

This question shows the developer's ability to work with Java iteration.

There is a room with n bulbs arranged in a row. Initially, all the bulbs are turned off.
You are given an array of targets of length n. This represents the desired configuration of the bulbs. If target[i] = “0”, we want ith bulb off. If target[i] = “1”, we want ith bulb on. You perform a series of operations to obtain the desired configurations of the bulbs.

In one operation, you choose index i and flip all the bulbs from index i to n - 1. When any bulb is flipped it means that if it is “0” it changes to “1”' and if it is “1”' it changes to “0”. Your task is to find the minimum number of operations required to obtain the desired configuration.

/*Example*/

Given: target = "10111"
Expected output: 3 
Explanation: Initial configuration is always “00000”
choose i = 2 => the configuration is “00111”
choose i = 0 => the configuration is “11000”
choose i = 1 => the configuration is “10111”
So, at least 3 operations are required.

Solution:

Let’s say we have two bulbs at indices i and j with i < j. If we first put the ith bulb into the desired configuration, we can put the jth bulb to the desired configuration later without disturbing the configuration of the ith bulb. But if we first put the jth bulb into the desired configuration, then while putting the ith bulb into the desired configuration later, the configuration of the jth bulb may be disturbed and we will need to correct the configuration of the jth bulb (thus extra operation). So, it’s optimal to put the lower indexed bulb to the desired configuration first, and then the higher indexed bulbs.

We will iterate over each bulb starting from the 0th bulb. We will maintain the current state of the bulbs after the current bulb that we are iterating now. If the bulb is already in the desired configuration, we need not do anything. If the bulb is not in the desired configuration, we will flip the state of the bulbs after the current bulb and increase the opCount by 1.

class Solution {
    public int minFlips(String target) {
        int opCount = 0;
        String state = "0";
        
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) != state) {
                opCount++;
                state = state.equals("0") ? "1" : "0";
            }
        }
        
        return opCount; 
    }
    
}

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

This interview question shows the developer's ability to work with Java arrays.

The pair sum of a pair (a, b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs. For example if the pairs are (1, 5), (2, 3) and (4, 3), the maximum pair sum is max(1 + 5, 2 + 3, 4 + 3) = 7.

You are given array nums of even length n. Your task is to put these integers in n / 2 pairs such that the maximum pair sum is minimized. You need to return the minimized maximum pair sum.

/*Example*/

Given nums = [3, 5, 4, 2, 4, 6]
Expected output: 8
Explanation: The pairs would be (3, 5), (2, 6), and (4, 4). Thus the maximum pair sum is 8. If they were paired in any other way, let's say (3, 2), (4, 6), and (5, 4), the maximum pair sum is 10 which is larger. But we need to minimize it.

Solution:

We will pair the minimum integer with the maximum integer. Then the next minimum to the next maximum integer and so on. To do this, we will sort the array. And then pair the elements one from start and one from the end.

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        
        int result = 0;
        int len = nums.length;
        int halfLen = len / 2;
        
        for (int i = 0; i < halfLen; i++) {
            int pairSum = nums[i] + nums[len - i - 1];
            
            result = Math.max(result, pairSum);
        }
        
        return result;
    }

}

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

This question shows the developer's skills with Java rows and columns.

You are given a 2-D matrix grid where each value is either 0 or 1. You perform a series of operations on the matrix. In one operation you choose either one row or one column and toggle each value in that row or column. While toggling you change all 0's to 1's and all 1's to 0's.

Every row is interpreted as a binary number. The score of the matrix is the sum of these binary numbers represented by every row. Your task is to perform any number of operations in such a way that the matrix has a maximum score. You need to return the maximum score.

/*Example*/

Given grid = [
	[0, 0, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 0]
]
Expected output: 39
Explanation: We flip these rows/columns:- row0, col2, col3. We get the following matrix:-
grid = [
	[1, 1, 1, 1],
[1, 0, 0, 1],
[1, 1, 1, 1]
]
The score is: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Solution:

We do it greedily.
Let the result be the final maximized score of the matrix. Let rows and cols by the number of rows and the columns in the grid respectively. If the value (bit) in the jth column in a particular row is 1, then the contribution of this value will be equal to 2cols - j - 1 = 1 << (cols - j - 1) (we call this value as the weight of the column).

Now, the weight of the 0th column will be greater than the combined weights of any other column because
2cols - 1 > 2cols - 1 - 1 + 2cols - 2 - 1 + ... + 20

STEP 1- First of all, we make the first bits (0th column) of every row to 1. We select and toggle those rows whose first bit is not 1 initially. The total contribution (worth) of the first column of every row will be equal to:
(number of rows) * (weight of 0th column)
= rows * (1 << (cols - 1))

STEP 2- Now, we have the first bit of every row to 1. We look at other columns and rows. We count the number of 1's in a particular column (in the variable col1Count). For a particular row,
● If the bit in the first column is 1, we didn’t toggle the row in STEP 1. Thus the bit in the current column is not changed after performing the operations in STEP 1. So we increase the col1Count if the bit in the current column is 1 in the original grid.
● If the bit in the first column is 0, we did toggle the row in STEP 1. Thus the bit in the current column is changed/toggled after performing the operations in STEP 1. So we increase the col1Count if the bit in the current column is 0 in the original grid (because it was changed to 1 after an operation on that row).

After getting col1Count for a particular row, we check the maximum number of 1’s that we get in this column before and after operating on this column. col1Count is before operation and rows - col1Count will be the count after operating. Then we calculate the contribution (worth) of the current column.

class Solution {
    public int matrixScore(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int result = 1 << (cols - 1);
        result *= rows;
        
        for (int j = 1; j < cols; j++) {
            int col1Count = 0;
            
            for (int i = 0; i < rows; i++) {
                boolean isRowFirstZero = grid[i][0] == 0;
                boolean isCellZero = grid[i][j] == 0;
                
                if (isRowFirstZero == isCellZero) {
                    col1Count++;
                }
            }
            
            col1Count = Math.max(col1Count, rows - col1Count);
            int columnBitWeight = 1 << (cols - j - 1);
            int columnWorth = col1Count * columnBitWeight;
            
            result += columnWorth;
        }
        
        return result;
    }
    
}

Time complexity- O(rows * cols)
Space complexity- O(1)

This question shows the developer's ability to work with Java queues and sorting.

You are given an array of people. These people are standing in a queue. Each entry of the array of people tells some attributes of that particular person. people[i] = [hi, ki] represents a person with height hi with exactly ki people standing in front of this person who has a height greater than or equal to hi. The array people have these people in jumbled order. Your task is to reconstruct the queue from the given array.

/*Example*/

Given people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
Expected output: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

Solution:

We will generate the queue starting from the tallest people. For this, we will sort the array in decreasing the order of heights of the persons. If two persons have the same height, we arrange them in increasing order of their ki.

Then we iterate over the sorted people. For the current person with tallerPeopleCount = ki, we insert this person in the queue at index tallerPeopleCount.

How does this work?
When we insert a person at index idx, it means there is idx number of persons before the current person (irrespective of their heights).

During one iteration, all the persons in the queue have a height greater than or equal to the current person. So we insert the current person at index tallerPeopleCount, which means it will have exactly a tallerPeopleCount number of people who have heights greater than or equal to the current person.

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // sort people in descending order by their height
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(final int[] p1, final int[] p2) {
                // if the two persons have same height,
                // sort them in increasing order of k
                if (p2[0] == p1[0]) return p1[1] - p2[1];
                return p2[0] - p1[0];
            }
        });
        
        List<int[]> queue = new ArrayList<>();
        
        for (int[] person : people) {
            int tallerPeopleCount = person[1];
            queue.add(tallerPeopleCount, person);
        }
        
        int[][] res = queue.toArray(new int[queue.size()][]);
        return res;
    }
}

Time complexity- O(n2)
Space complexity- O(1)