Moo - Google Top Interview Questions
Problem Statement :
You are given a string cows representing the initial conditions of some cows. Each cow can take one of three values: "L", meaning the cow is charging to the left. "R", meaning the cow is charging to the right. "@", meaning the cow is standing still. Cows charging on a direction will pick up other cows unless the cow receives a force from the opposite direction. Then, it will stand still. Return the orientation of each cow when the cow stop charging. Constraints n ≤ 100,000 where n is the length of cows Example 1 Input cows = "@L@R@@@@L" Output "LL@RRRLLL" Example 2 Input cows = "@@R@@@L@L" Output "@@RR@LLLL"
Solution :
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])
View More Similar Problems
Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →
