Moo - Google Top Interview Questions

                        Solution in C++ :

void process(string& cows, int i, int j) {
    char l = cows[i], r = cows[j];
    if ((l == '@' || l == 'L') && (r == '@' || r == 'R')) return;
    if ((l == '@' || l == 'L') && r == 'L') {
        while (i < j) cows[i++] = 'L';
    } else if (l == 'R' && (r == '@' || r == 'R')) {
        while (i <= j) cows[i++] = 'R'; 
    } else {
        while (i<j) {
            cows[i++] = 'R';
            cows[j--] = 'L';
        }
    }
}
string solve(string cows) {
    for (int i=0, j=0; j<cows.size(); j++) {
        if (cows[j] != '@' || j == cows.size() - 1) {
            process(cows, i, j);
            i = j;
        }
    }   
    return cows;
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public String solve(String cows) {
        int R = -1;
        // this variable is used to track the index of the character "R" so that when I find the
        // character "L" I can perform some sort of collide -1 means R is not initialized
        int last_event = 0;
        // this variable is used to represent the "last_event" so in the case "L@R@@L" my last event
        // will be at index 2. This will help me track which @ to cover when I find "L"
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cows.length(); i++) {
            // if R is not initialized that means that when I see L then everything to the left of
            // it is going to be charging left now
            if (cows.charAt(i) == 'L' && R == -1) {
                for (int j = 0; j < i - last_event + 1; j++) {
                    sb.append('L');
                }
                // I change the last event
                last_event = i + 1;
            }
            // if R is already initialized and we encounter another R we turn all the cows between
            // it into R case: R@@@@@R@L everything between that will turn into R My intuition is to
            // simply attack all the RL collisions using halves, so it's important that I find the
            // closest R and L when these collisions occur.
            if (cows.charAt(i) == 'R' && R != -1) {
                for (int j = 0; j < i - R; j++) {
                    sb.append('R');
                }
                R = i;
            }
            // If we encountered an 'R' and it's not initialized we will set it to the current
            // index.
            if (cows.charAt(i) == 'R' && R == -1) {
                // We append those still cows in cases like this:
                //@@@R@L
                //@L@@R
                for (int j = 0; j < i - last_event; j++) {
                    sb.append('@');
                }
                R = i;
            }
            // This is when the action happens. I've found the closest R and closest L. If (i-R) % 2
            // == 1 we will NOT append a still cow in the middle.
            if (cows.charAt(i) == 'L' && R != -1) {
                // cases like this:
                // L@@R
                if ((i - R) % 2 == 1) {
                    for (int j = 0; j < (i - R) / 2 + 1; j++) {
                        sb.append('R');
                    }

                    for (int j = 0; j < (i - R) / 2 + 1; j++) {
                        sb.append('L');
                    }
                }
                // cases like this:
                // L@@@R
                else {
                    for (int j = 0; j < (i - R) / 2; j++) {
                        sb.append('R');
                    }
                    sb.append('@');

                    for (int j = 0; j < (i - R) / 2; j++) {
                        sb.append('L');
                    }
                }
                // set last_event
                last_event = i + 1;
                // R will not be initialized anymore because the collision occurs.
                R = -1;
            }
        }

        // after we finish iterating through the string, we need to take care of a couple more cases

        // in this case if we have R@@@@@ in the back of the string we need to change everything
        // after 'R' to 'R'. We can check if case exists by seeing if R is initialized after the for
        // loop
        if (R != -1) {
            sb.append('R');
            for (int i = cows.length() - 1; i >= 0; i--) {
                if (cows.charAt(i) != '@')
                    break;
                sb.append('R');
            }
        }
        // or if the case is simply RL@@@@@ we need to append everything in the back.
        else {
            for (int i = cows.length() - 1; i >= 0; i--) {
                if (cows.charAt(i) != '@')
                    break;
                sb.append('@');
            }
        }
        // return the final string
        return sb.toString();
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, cows):
        Lq = deque()
        Rq = deque()
        cows = list(cows)

        # appending the initiators --> R's and L's into a queue
        for ind, c in enumerate(cows):
            if c == "L":
                Lq.append((ind, 0))
            if c == "R":
                Rq.append((ind, 0))

        # L filling all the @'s to its left while appending the distance of each @ from the initiator
        while Lq:
            cur, dist = Lq.popleft()
            cows[cur] = "L{}".format(dist)
            if cur > 0 and cows[cur - 1] == "@":
                Lq.append((cur - 1, dist + 1))
        # print(" ".join(cows))

        # R's chance to fill / correct the blocks filled by L
        stopDist = isMid = n = len(cows)
        prev = -1
        while Rq:
            cur, dist = Rq.popleft()
            if prev >= cur:
                continue

            # non conflicting @
            while cur < n and cows[cur][0] != "L":
                cows[cur], cur = "R", cur + 1
            if cur >= n:
                break
            # 'R' is getting to know how many Li's it need to overwrite
            Ldist = int(cows[cur][1:])
            stopDist, isMid = divmod(Ldist, 2)
            dist = 0

            # 'R' overwriting the Li's till its part
            while cur < n and dist < stopDist:
                cows[cur] = "R"
                dist, cur = dist + 1, cur + 1

            # correcting the middle '@'
            if cur < n and isMid == 1:
                cows[cur] = "@"
            prev = cur

        return "".join([c[0] for c in cows])