Good day! Hopefully your day has started on the right note. Last evening my wife and I watched Ava on Netflix. I like movies with spies and action. Perhaps the plot could have been more realistic and credible. We gave the movie a thumb up.
Earlier today I decided to work on the Facebook coding practice problem Queue Removals. The problem provides a single sample test. In addition, when you run your code, it will be checked against two tests. There are no additional hints. There are no additional tests.
I read the problem a few times to get the gist of it. I spent a few minutes thinking about a simple way to solve the problem. Nothing came up and I was running out of time so I decided to solve it by following the specified steps. When done, I started a second approach but ran out of time. If you are interested in this problem and solve it using a different approach, please let me know.
I will solve this problem using Java 8 in a Windows 10 machine using the VSCode IDE.
You're given a list of n integers arr, which represent elements in a queue (in order from front to back). You're also given an integer x, and must perform x iterations of the following 3-step process: 1. Pop (remove from the front) x elements from the front of queue (or, if it contains fewer than x elements, pop all of them) 2. Of the elements that were popped, find the one with the largest value (if there are multiple such elements, take the one which had been popped the earliest), and remove it 3. For each one of the remaining elements that were popped (in the order they had been popped), decrement its value by 1 if it's positive (otherwise, if its value is 0, then it's left unchanged), and then add it back to the queue Compute a list of x integers output, the ith of which is the 1-based index in the original array of the element which had been removed in step 2 during the ith iteration. Input: x is in the range [1, 316]. n is in the range [x, x*x]. Each value arr[i] is in the range [1, x]. Output: Return a list of x integers output, as described above.
We are given a string of integers and a number of iterations specified by the argument x. The requirements specify a convoluted set of three steps. That is what hinted me on looking for an alternate before following the specified steps.
The idea is to generate an array with the indices (1-based not 0-based) for the values we remove.
int[] findPositions(int[] arr, int x) {
}
The signature for the function / method we need to address is simple.
I will solve the problem on my machine. Because of this, I need to generate a test scaffolding that will collect the input, pass the arguments and display the result.
1,2,2,3,4,5 5 main <<< arr: [1, 2, 2, 3, 4, 5] main <<< x: 5 <<< i: 0 <<< maxe: [4, 4] <<< ans: [5] <<< i: 1 <<< maxe: [5, 5] <<< ans: [5, 6] <<< i: 2 <<< maxe: [1, 3] <<< ans: [5, 6, 4] <<< i: 3 <<< maxe: [0, 0] <<< ans: [5, 6, 4, 1] <<< i: 4 <<< maxe: [0, 1] <<< ans: [5, 6, 4, 1, 2] main <<< output: [5, 6, 4, 1, 2]
The first two lines are the values for the arguments to our function. The test scaffolding processes the input and displays them to verify all is well so far.
The rest of the output is generated for testing and to follow up on what the code is doing and mapping it to the step described in the problem. The last line displays the contents of an integer with the result.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the input line split values ****
String[] strs = br.readLine().trim().split(",");
// **** read x ****
int x = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// **** populate array of integers ****
int[] arr = Arrays.stream(strs)
.mapToInt(Integer::parseInt)
.toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
System.out.println("main <<< x: " + x);
// **** compute and display output ****
System.out.println("main <<< output: " + Arrays.toString(findPositions(arr, x)));
}
Our test scaffolding opens a buffered reader. We read the values for the array and stored them in an array of strings. We read the value for x and close the buffered reader.
We then parse the array of strings and populate the array we will be passing to the function of interest. The array and x are displayed.
We then call the findPositions() function / method and display the output. The output matches but like I mentioned, the number of tests is not there to have confidence with the solution.
/**
* There must be a simpler way.
*/
static int[] findPositions(int[] arr, int x) {
// **** initialization ****
ArrayList<Integer> ans = new ArrayList<>();
LinkedList<int[]> q = new LinkedList<>();
LinkedList<int[]> wq = new LinkedList<>();
// **** populate q ****
for (int i = 0; i < arr.length; i++) {
// **** value and position in arr ****
int[] e = new int[] {arr[i], i};
// **** append element to q ****
q.addLast(e);
}
// **** loop the specified number of times ****
for (int i = 0; i < x; i++) {
// ???? ????
System.out.println("<<< i: " + i);
// **** [1] move x elements from q to wq ****
int[] maxe = new int[] {-1, -1};
for (int j = 0; j < x && !q.isEmpty(); j++) {
// **** update max value and index ****
if (q.peek()[0] > maxe[0]) {
maxe = q.peek();
}
// **** remove element from q and insert into wq ****
wq.addLast(q.removeFirst());
}
// ???? ????
System.out.println("<<< maxe: " + Arrays.toString(maxe));
// **** [2] find element with largest value (done in [1]) and remove it ****
wq.remove(maxe);
// **** add index to array list ****
ans.add(maxe[1] + 1);
// ???? ????
System.out.println("<<< ans: " + ans.toString());
// **** [3] decrement values by 1 and add them back to the queue ****
while (!wq.isEmpty()) {
// **** remove head element ****
int[] e = wq.removeFirst();
// **** decrement value (if needed) ****
if (e[0] > 0)
e[0]--;
// **** append element to q ****
q.addLast(e);
}
}
// **** convert array list to int[] ****
return ans.stream().mapToInt(Integer::intValue).toArray();
}
We use the array list to return the results. The two queues are used to follow the steps specified in the requirements.
We then populate the queue. It will hold the state of the program at the start of each pass.
We then enter a loop to implement the number of passes called by the variable x.
The comments are there to follow the program. They were not included in the solution. Each of the three steps is performed in order. Note that some of what is called in step 2 in the requirements was due to efficiency, partly performed on step 1.
When we are done with the loop, we return an array with the indices.
I should give this problem more time and try an alternate approach. Not sure when I will be able to get to it.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,905 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com