## Walmart Labs Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 vote

The solution becomes more apparent after analyzing the input a bit. Based only on the first and last character, there are 4 types of strings: RR (starts in R, ends in R), RB (starts in R, ends in B), BR and BB.

We can combine all RRs into one big RR string, and all BBs into one big BB string. Both these big strings can be combined with any BR or RB string. If the input does not have any BR or RB strings then we return the size of the longest big string. It the input has at least one BR or RB, then we add the size of both big strings to our solution.

Now we reduced the problem into finding a solution when the input only has strings of type RB or BR. We gradually add to our solution the size of the longest strings, oscillating between the two classes. When we ran out of strings in one class, we can add one more string from the other class (if there is one) and then we are done.

The complexity in worst case scenario is n*log(n), due to sorting. Below is a Python implementation of the algorithm. Any feedback is most welcome.

``````strings = ['RRRR', 'BBB', 'R', 'BBB', 'RBBBB', 'RRB', 'BRBR', 'RBBB', 'BR']

RR = 0
BB = 0
RB = []
BR = []
for s in strings:
if s + s[-1] == 'BB':
BB += len(s)
elif s + s[-1] == 'RR':
RR += len(s)
elif s == 'R':  # and s[-1] = 'B'
RB.append(len(s))
else:
BR.append(len(s))

if not BR and not RB:
solution = max(RR, BB)
else:
RB.sort(reverse=True)
BR.sort(reverse=True)

solution = BB + RR
for i in range(min(len(BR), len(RB))):
solution += BR[i] + RB[i]

if len(RB) < len(BR):
solution += BR[len(RB)]
elif len(BR) < len(RB):
solution += RB[len(BR)]

print solution``````

Comment hidden because of low score. Click to expand.
0

I had the exact same intuition as you did.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Great solution. One quick question. Shouldn't the final if-else condition be

``````if len(RB) < len(BR):
solution += BR[-1]
elif len(BR) < len(RB):
solution += RB[-1]``````

as the maximum value is required?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Arrang

Comment hidden because of low score. Click to expand.
0
of 0 vote

Question says last character and first character should be same; RR and BB are valid combinations;

Comment hidden because of low score. Click to expand.
0
of 0 vote

Construct a directed graph using the given strings. For example 1.RBR 2.BB 3.BRRR. Now make these strings as nodes of a graph and give connection if the given constraint satisfies. The edges will be 2-->3, 3-->1. Now apply DFS algorithm to find maximum length path at each node.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n + n log n) ( O( n log n) ) complexity with O(n) memory by
1. Dividing the input strings into 4 groups based on input and output (O (n) )
a. for BB or RR like strings, simply add up the lengths
2. Sort the BR and RB collections lengths for greedy selection (this is the O(n log n) piece)
3. Ping-ponging between the RB and BR groups

``````public static int getLongest(Collection<String> strs){
if(strs == null){
throw new NullPointerException();
}
if(strs.size() == 0){
return 0;
}

//break the input into major groupings
int bbLength = 0;
ArrayList<Integer> br = new ArrayList<Integer>();
int rrLength = 0;
ArrayList<Integer> rb = new ArrayList<Integer>();
for(String str : strs){
if(str.charAt(0) == 'B'){
if(str.charAt(str.length() - 1) == 'B'){
bbLength += str.Length();
}
else{
}
}
else{
if(str.charAt(str.length() - 1) == 'B'){
}
else{
rr += str.length();
}
}
}
//Sort to support greedy operations
Collections.sort(br);
Collections.sort(rb);

//now do the ping ponging
//if there are BR strings
if(br.size() > 0){
int val = 0;
//if there are also RB strings
if(rb.size() > 0){
//if there are more BR strings, start there
if(br.size() > rb.size()){
val = br.remove(br.size() - 1);
}
//if there are more RB strings, start there
else if(rb.size() > br.size()){
val = rb.remove(rb.size() - 1);
}
//while there are both BR and RB strings, use them
while(br.size() > 0 && rb.size() > 0){
val += br.remove(br.size() - 1);
val += rb.remove(rb.size() - 1);
}
}
//otherwise there is only the BR string, use the max
else{
val += br.remove(br.size() - 1);
}
//add the BB and RR string lengths
val += bbLength;
val += rrLength;
return val;
}
//if there are only RB strings, use the max there
else if (rb.size() > 0){
int val = rb.remove(rb.size() - 1);
val += bbLength;
val += rrLength;
}
//else there are only BB and RR strings. Use the longest one of those
else{
return Math.max(bbLength, rrLength);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

B and R string algorithm:

Sort the strings in descending order of length in such a way that those starting and ending with B and B are first, followed by those with B and R, then R and B and finally R and R.
Let strings starting and ending with B and B be called BxxB. Similarly, BxxR, RxxB, RxxR
Now there are 16 possible cases:
N = 0 (no strings given)
Output is 0
Only strings starting and ending with B and B (BxxB)
Output is length of all strings summed up.
Only strings starting with B and ending with R (BxxR)
Output is length of the longest string
Only strings starting with R and ending with B (RxxB)
Output is length of the longest string
Only strings starting and ending with R and R (RxxR)
Output is length of all strings summed up
Only two types of strings: BxxB, BxxR
Output is total length of all BxxB + Length of longest string of type BxxR
Only two types of strings: BxxB and RxxB
Output is length of RxxB + Total Length of all BxxB
Only two types of strings: BxxB and RxxR
Output is max(total length of BxxB, total length of RxxR)
Only two types of strings: RxxB and BxxR
Output is RxxB1 + BxxR1 + RxxB2 + BxxR2 + ….
Only two types of strings:
Only three types of strings: BxxB, BxxR, RxxB
Output is total length of all BxxB + (BxxR1 + RxxB1 + BxxR2 + RxxB2 + .. till either is exhausted)
Only three types of strings: BxxR, ….. and so on

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````B and R string algorithm:

1. Sort the strings in descending order of length in such a way that those starting and ending with B and B are first, followed by those with B and R, then R and B and finally R and R.
2. Let strings starting and ending with B and B be called BxxB. Similarly, BxxR, RxxB, RxxR
3. Now there are 16 possible cases:
a. N = 0 (no strings given)
Output is 0
b. Only strings starting and ending with B and B (BxxB)
Output is length of all strings summed up.
c. Only strings starting with B and ending with R (BxxR)
Output is length of the longest string
d. Only strings starting with R and ending with B (RxxB)
Output is length of the longest string
e. Only strings starting and ending with R and R (RxxR)
Output is length of all strings summed up
f. Only two types of strings: BxxB, BxxR
Output is total length of all BxxB + Length of longest string of type BxxR
g. Only two types of strings: BxxB and RxxB
Output is length of  RxxB + Total Length of all BxxB
h. Only two types of strings: BxxB and RxxR
Output is max(total length of BxxB, total length of RxxR)
i. Only two types of strings: RxxB and BxxR
Output is RxxB1 + BxxR1 + RxxB2 + BxxR2 + ….
j. Only two types of strings:
Only three types of strings: BxxB, BxxR, RxxB
k. Output is total length of all BxxB + (BxxR1 + RxxB1 + BxxR2 + RxxB2 + .. till either is exhausted)
Only three types of strings: BxxR, ….. and so on``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.serj.data;

public class MaxPattern {

public static void main(String[] s) {
String[] data = { "R", "RBB", "BB", "BR" };
MaxPattern obj = new MaxPattern();
obj.check(data);
}

String maxStringFound = null;
private void check(String[] data) {
maxStringFound = null;
for (int i = 0; i < data.length; i++) {
check(data[i], getStringArray(data, i));
}
System.out.println("MAX STRING FOUND " + maxStringFound);

}

private void check(String string, String[] data) {
for (int i = 0; i < data.length; i++) {
if (string.endsWith("" + data[i].charAt(0))) {
if (data.length == 1) {
string = string + " " + data[i];
} else {
check(string + " " + data[i], getStringArray(data, i));
}
}
}
System.out.println(string);
String s1 = string.replaceAll("\\s", "");
if (maxStringFound == null || maxStringFound.length() < s1.length()) {
maxStringFound = s1;
}

}

private String[] getStringArray(String[] data, int index) {
String[] d = new String[data.length - 1];
int k = -1;
for (int i = 0; i < data.length; i++) {
if (i != index) {
k++;
d[k] = data[i];
}
}
return d;
}
}``````

R RBB BB BR
R RBB BR
R RBB
R
RBB BB BR R
RBB BB
RBB BR R
RBB BR
RBB
BB BR R RBB
BB BR RBB
BB BR
BB
BR R RBB BB
BR R
BR RBB BB
BR RBB
BR
MAX STRING FOUND RRBBBBBR

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.serj.data;

public class MaxPattern {

public static void main(String[] s) {
String[] data = { "R", "RBB", "BB", "BR" };
MaxPattern obj = new MaxPattern();
obj.check(data);
}

String maxStringFound = null;
private void check(String[] data) {
maxStringFound = null;
for (int i = 0; i < data.length; i++) {
check(data[i], getStringArray(data, i));
}
System.out.println("MAX STRING FOUND " + maxStringFound);

}

private void check(String string, String[] data) {
for (int i = 0; i < data.length; i++) {
if (string.endsWith("" + data[i].charAt(0))) {
if (data.length == 1) {
string = string + " " + data[i];
} else {
check(string + " " + data[i], getStringArray(data, i));
}
}
}
System.out.println(string);
String s1 = string.replaceAll("\\s", "");
if (maxStringFound == null || maxStringFound.length() < s1.length()) {
maxStringFound = s1;
}

}

private String[] getStringArray(String[] data, int index) {
String[] d = new String[data.length - 1];
int k = -1;
for (int i = 0; i < data.length; i++) {
if (i != index) {
k++;
d[k] = data[i];
}
}
return d;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MaxPattern {

public static void main(String[] s) {
String[] data = { "R", "RBB", "BB", "BR" };
MaxPattern obj = new MaxPattern();
obj.check(data);
}

String maxStringFound = null;
private void check(String[] data) {
maxStringFound = null;
for (int i = 0; i < data.length; i++) {
check(data[i], getStringArray(data, i));
}
System.out.println("MAX STRING FOUND " + maxStringFound);

}

private void check(String string, String[] data) {
for (int i = 0; i < data.length; i++) {
if (string.endsWith("" + data[i].charAt(0))) {
if (data.length == 1) {
string = string + " " + data[i];
} else {
check(string + " " + data[i], getStringArray(data, i));
}
}
}
System.out.println(string);
String s1 = string.replaceAll("\\s", "");
if (maxStringFound == null || maxStringFound.length() < s1.length()) {
maxStringFound = s1;
}

}

private String[] getStringArray(String[] data, int index) {
String[] d = new String[data.length - 1];
int k = -1;
for (int i = 0; i < data.length; i++) {
if (i != index) {
k++;
d[k] = data[i];
}
}
return d;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just using start and end characters this can be solved pretty easily,

``````private static void maxstring()
{
int op = 0;
int max1 = 0;
int max2 = 0;
foreach ( string s in arr )
{
if ( s == 'R' && s[s.Length - 1] == 'R' )
{
op = op + s.Length;
}
else if ( s == 'B' && s[s.Length - 1] == 'B' )
{
continue;
}
else if ( s == 'B' && s[s.Length - 1] == 'R' )
{
max1 = Math.Max( max1, s.Length );
}
else
{
max2 = Math.Max( max2, s.Length );
}
}
Console.WriteLine( op + max1 + max2 );
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

After sorting the string array, Dynamic programming can be applied to get the solution.
Following is a java implementation for that.

``````import java.util.Arrays;

public class RBStrings {

private int findMaxLength(String[] a)
{
if(a == null || a.length == 0)
throw new IllegalArgumentException("The array is null.");

Arrays.sort(a);

int[] DP = new int[a.length];
DP = a.length();
int max = Integer.MIN_VALUE;

for(int i = 1; i < a.length; i++)
{
DP[i] = a[i].length();

for(int j = 0; j < i; j++)
{
if(a[j].charAt(a[j].length() - 1) == a[i].charAt(0))
{
if(DP[i] + a[j].length() > DP[i])
DP[i] = DP[i] + a[j].length();

if(DP[i] > max)
max = DP[i];
}
}
}

return max;
}

public static void main(String[] args)
{
RBStrings rbs = new RBStrings();

String[] arr = {"RBR", "BBR", "RRR"};

int maxLength = rbs.findMaxLength(arr);

System.out.println("Max length = " + maxLength);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Kousik, your code doesn't work for the input {"RBR", "RBRB", "RRR"}

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code implementation : -

``````#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc1(a,b) scanf("%lld%lld",&a,&b)
#define sc2(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define pc(a) printf("%lld\n",a)
#define pc1(a) printf("%lld ",a)
const int MOD=1e9+7;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ll n;
sc(n);
vector<pair<ll,string>> br,rb;
ll ble=0,rle=0;
for(ll i=0;i<n;++i)
{
string re;
cin>>re;
if(re=='R' && re[re.size()-1]=='R')
rle+=re.size();
else if(re=='B' && re[re.size()-1]=='B')
ble+=re.size();
else if(re=='R' && re[re.size()-1]=='B')
rb.pb({re.size(),re});
else
br.pb({re.size(),re});
}
sort(rb.begin(),rb.end());
sort(br.begin(),br.end());
ll br1=br.size()-1,rb1=rb.size()-1;
ll co=0;
if(br.size()>0)
{
if(rb.size()>0)
{
if(br.size()>rb.size())
co+=br[br1--].first;
else if(rb.size()>br.size())
co+=rb[rb1--].first;
while(br1>=0 && rb1>=0)
{
co+=br[br1--].first;
co+=rb[rb1--].first;
}
}
else
co+=br[br1--].first;
co+=(rle+ble);
}
else
{
if(rb.size()>0)
{
co+=rb[rb1--].first;
co+=(rle+ble);
}
else
co=max(rle,ble);
}
cout<<co<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#simple python code
a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#simple python3 code
a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))
and``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//

``````a=int(input())
list1=[]
ans=0
for i in range(a):
list1.append(input())
for index,string in enumerate(list1):
if (((len(list1))-1)>index):
list2=[]
list3=[]
for character in string:
list2.append(character)
a=len(list2)
print(a)
print(list2)
for char in list1[index+1]:
list3.append(char)
b=len(list3)
print(list3)
print(b)
if(list2[a-1] is list3):
ans+=len(list3)
print(ans+len(list1))
//``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.