4

I recently worked on an online problem for which answers were not provided, however, I would like to know where I went wrong. The prompt was strange, but I will do my best to explain it:

There is a machine that can fix all potholes along a road 3 units in length. A unit of Road will be represented with a period in a String. For example, "..." = one section of road 3 units in length. Potholes are marked with an "X" in the road, and also count as a unit of length. The task is to take a road of length N and fix all potholes with the fewest possible sections repaired by the machine. This problem is concerned with performance over correctness.

  • Example 1: A road represented by ".X." would require 1 fix.
  • Example 2: A road represented by "..X...X" would require 2 fixes.
  • Example 3: A road represented by "XXX.XXXX" would require 3 fixes.

My approach (shown below) was to count sections of String in increments of 3 chars at once. If that sequence contained an "X", then it needed a fix and vice versa. To account for roads that aren't multiples of 3 in length I just kept the sequence reading and checked whatever was left. I'm also not sure how to make the program better for performance (other than replacing my sequence String with a StringBuilder)

public class Solution {
//Note: I had to re-write this from memory, as I was not given it back by the online problem checker
    public int solution(String S) {
        int fixes = 0;
        String sequence = "";//Perhaps use StringBuilder?
        for (int i = 0; i < S.length(); i++) {//read the entire incoming string
            for (int j = 0; j < 3; j++) {//Count 3 chars at once
                sequence += S.charAt(i);//Add said Chars to our sequence
            }
            if (sequence.contains("X")) {//Check for potholes
                fixes++;//We can fix everything in this sequence
                sequence = "";//reset our sequence
            }
        }
        if (sequence.contains("X")) {//Check anything left, since not all roads are multiples of 3
                fixes++;
            }
        return fixes;
    }
}

I thought this was good enough for what was asked, and it passed all of the given example Strings, but apparently failed horribly upon review. I don't know what I've done wrong, though I feel like there's probably something small and stupid that I'm missing.

UPDATE:

I was indeed missing something obvious, I need to start reading at the first "X", something like this:

        if (S.charAt(i) == 'X') {//Start counting at the first X
            for (int j = 0; j < 3; j++) {//Count 3 chars at once
                if (i + j <= S.length() - 1) {//no outofbounds exceptions please!
                    sequence += S.charAt(i + j);//Add said Chars to our sequence
                }
            }
        }

Now I just need to make sure it meets performance requirements.

Improve this question
0

6 Answers 6

Reset to default
6

and it passed all of the given example Strings

But... how?

Your code is completely wrong. How can it have passed the example strings? Must have been some very unlucky examples, then!

for (int j = 0; j < 3; j++) {//Count 3 chars at once
  sequence += S.charAt(i);//Add said Chars to our sequence
 }

This will add the exact same character, 3 times. i never changes. Thus, sequence is either "..." or "XXX".

if (sequence.contains("X")) {//Check for potholes
  fixes++;//We can fix everything in this sequence
  sequence = "";//reset our sequence
}

This boils down to: If it was "XXX", increment fixes.

if (sequence.contains("X")) {//Check anything left, since not all roads are multiples of 3
               fixes++;
           }

This if cannot possibly trigger. Think about it.

All your code does, is count potholes. In a convoluted way.

I thought this was good enough for what was asked

You've made 3 major errors. Each is individually probably sufficient to get a significant downgrade if this is an exercise for a job:

  • The code contains a performance faux-pas (concatenating strings using + in a loop), when the question explicitly calls out that performance is important. You'd have to call it out and explain why you intentionally broke a rule of thumb, at least.

  • The code straight up doesn't work, at all.

  • Even if you fix it, the code STILL does not work. Take, for example, the input ".X.X..". The correct answer is 1. Even if you fixed your code and you treat each chunk of 3 properly (instead of one at a time due to your messup between j and i), your algorithm returns 2. The question is a little more complicated than you think it is. Not much, mind. Still, the entire algorithm as written should just be tossed in the bin, and start over. Don't start with programming. Start with schetching out the problem and considering the algorithm required. Only then start coding.

Here is the correct algorithm. Just sketched out, thinking the problem through:

Just scan for a pothole. Once you find one, fix it and skip past the next 2 units of road while you're at it. They just do not matter. If they have potholes, we'll fix em for free along with the hole we found.

That's all you need to do. Just count potholes, ignoring any potholes that are 1 or 2 'to the right' of a pothole we fixed.

Here:

public int solution(String s) {
  int holes = 0;
  for (int i = 0; i < s.length(); i++)
    if (s.charAt(i) == 'X') {
      holes++;
      i += 2;
    }
  }
  return holes;
}

This code is much simpler, is correct, and is clearly as fast as it's ever gonna get.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I remember thinking about the first issue you listed when I originally made this, and at the time I got it to properly increment i, but I don't remember what I did.
1

Segmenting the string into groups of 3 will fail when potholes don't align with those divisions. Sometimes it will be optimal for the machine to skip 1 or 2 units, or 4 or 5 -- some number that isn't a multiple of 3.

For example, consider this road:

.X.XX.XX.X

Your algorithm will declare that 4 segments need to be repaired:

|.X.|XX.|XX.|X|

But it can be done in 3 segments:

.|X.X|X.X|X.X|
Improve this answer

2 Comments

There it is! The stupid thing I wasn't thinking of!
Actually, the code as written in the question just counts potholes. solution("XXX") returns 3. Try it. It's got way bigger problems than the fact that it mis-segments.
0

Your program only reads the road in sections of 3 units. It can give a wrong answer for some configurations.

For instance, it will answer "2" for ..X.X...., while this road can be fixed in only one fix.

It will read ..X, .X., ..., when it should read up until the first X, forget what was before, and then do a fix of 3 units before continuing.

It should read .., X.X, ....

Improve this answer

2 Comments

Not the issue here. Edited my answer. Maybe @JohnKugelman was clearer, but he says the same
I understood what you meant, but yes, you two both recognized the stupid thing I missed.
0 
def pothole_fixing(road):
    potholes = 0
    sections = 0
    for i in range(len(road)):
        if road[i] == 'X':
            potholes += 1
        else:
            if potholes > 0:
                sections += -(-potholes // 3)
                potholes = 0
              
    if potholes > 0:
        sections += -(-potholes // 3)
    return(sections)

The function takes a string road representing the road with potholes and returns the minimum number of sections needed to fix all potholes.

Improve this answer

Comments

0 
public static int solution2(String s) {
    int patchCount = 0;
    int i = 0;
    while(i<s.length()){
        if(s.charAt(i)=='X'){
            patchCount ++;
            i += 3-i%3;
        } else {
            i++;
        }
    }
    return patchCount;
}

At first I thought that the matching machine will run with the tri-figures, then if 'X' is the first element among the 3, we'll have to set i=i+2, if 'X' is the 2nd element among the 3, just i =i+1 (general express is 3-i%3). But after referencing above answers, I found that my solution is wrong.

Improve this answer

2 Comments

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.
More information is missing from the answer as it is not clear.
0

The solution I came up with was a bit different than the others shown here, this question is kind of old but maybe this solution can help others in the future.

def solution(S, B):
    # Implement your solution here
    count = 0

    #sliding window technique needed
    arr = []
    temparr = []
    for index in S:
        if index == "x":
            temparr.append(index)
        else:
            arr.append(len(temparr))
            temparr = []
    arr = sorted(arr)
    index = len(arr)-1
    while B > 0 or index == 0:
      if B >= arr[index]+1:
        B -= arr[index]+1
        count += arr[index]
      index -= 1
    return count

I guess my solution is a bit odd,

the idea was to create smaller lists of all contiguous instances of "x" and put that into a main list 'arr'

after that sorting them

then finally using your budget to measure how many potholes you can fix. With the test solutions I used it worked properly but I am sure there are faster solutions.

edit: in my version you had a budget and each patch would cost k+1

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.