You Will Face This Problem on Your Next Tech Interview (#2)

Daily Challenge #2

This is my next step under the topic, Data Structures and Algorithms. When you are facing any technical interview for any job title such as software engineer, full-stack developer, system engineer, tech lead etc. you will face this kind of problems. But I cannot assure you this is the problem you have to face exactly. But, If you have a fluent problem-solving skill, you can solve any other problem easily. Therefore you need to practise this kind of questions every day. It will be a profitable investment in future. This series of stories will ease you to help your technical interviews in future. So for that, These stories will help you.

Here I am not assured this is the optimum solution for this problem. But As per my knowledge, I solved and explained this. You can think about this problem again for another better solution. However, You also should refresh your knowledge with algorithms everyday even you are in a high-level profession.

I will write the answer to Java. And I will explain what has happened in the code snippet. You can understand the scenario easily and convert it into any language you prefer. The most important thing is understanding the solution and the problem very well. Let’s go to the problem with the difficulty level is middle.

Problem

  • People are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n.
  • Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker.
  • One person can bribe at most two others.
  • Determine the minimum number of bribes that took place to get to given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

Example:

  • [1,2,3,5,4,6,7,8]

If person 5 bribes person 4, the queue will look like this [1,2,3,4,5,6,7,8]: The only bribe is required. Print 1.

  • [4,1,2,3]

Person 4 had to bribe 3 people to get to the current position. Print Too chaotic.

Solution (In Java8)

// Complete the minimumBribes function below.
static void minimumBribes(int[] q) {
int swaps = 0;
boolean cha = false;


for(int i=q.length-1;i>=0;i--){

if((q[i]-(i+1))>2){
cha = true;
break;
}

for (int j = Math.max(0, q[i] - 2); j < i; j++){
if (q[j] > q[i]) swaps++;
}

}

if(!cha){
System.out.println(swaps);
}else{
System.out.println("Too chaotic");
}
}

Explanation

The method, minimumBribes has the following parameter(s):

  • int a[n]: the array which represents the people in the line

First, The method receives the integer array as q. Then I have initialized two variables, one is for the count of the number of swaps and another one is to identify the line that is too chaotic.

  • swaps(int): To count the number of swaps.
  • cha(boolean): To check the line that is too chaotic.

Then everything wrapped under one for loop which goes through the array from the last element to the first element. Therefore It has maintained the array current position(i).

Then after you accessed the for loop, there have an if condition to check the difference((q[i]-(i+1)) of current position(i+1) and it’s appropriate array value q[i] is greater than 2. If it is? We no more need to continue the code, we break the for loop immediately and print answer.

Otherwise, we go to the next for loop, It has to continue j value from max(0, q[i]-2) to j<i. Because now we know the current array value q[i] will correctly position within two or lower number of swaps. But if q[i]-2 is lower than 0, it will give an ArrayIndexOutOfBoundsException error. Therefore we get the maximum of 0 and (q[i]-2). Also, enough to continue until ( j<i ) because we assured that, the value q[i] is positioned within two or lower number of swaps. Inside the for loop, the swaps value count by one if (q[j] > q[i]).

Finally, we print the answer according to the value of cha variable.

Conclusion

This story solved another interview question you will face in your next interview. So I hope, you have enjoyed it. Please feel free to ask any question you will face in the response section below. Also, ask any other related questions you have.
Happy Coding !!!!
Found this post useful? Kindly tap the 👏 button below! :)

Mobile I Web I Data Science I AI — We write rich & meaningful content on development, technology, digital transformation & life lessons.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store