Walmart Labs Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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{
br.add(str.length());
}
}
else{
if(str.charAt(str.length() - 1) == 'B'){
rb.add(str.length());
}
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);
}
}
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
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
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
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;
}
}
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;
}
}
Just using start and end characters this can be solved pretty easily,
private static void maxstring()
{
string[] arr = Console.ReadLine().Split();
int op = 0;
int max1 = 0;
int max2 = 0;
foreach ( string s in arr )
{
if ( s[0] == 'R' && s[s.Length - 1] == 'R' )
{
op = op + s.Length;
}
else if ( s[0] == 'B' && s[s.Length - 1] == 'B' )
{
continue;
}
else if ( s[0] == 'B' && s[s.Length - 1] == 'R' )
{
max1 = Math.Max( max1, s.Length );
}
else
{
max2 = Math.Max( max2, s.Length );
}
}
Console.WriteLine( op + max1 + max2 );
}
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[0] = a[0].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);
}
}
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[0]=='R' && re[re.size()-1]=='R')
rle+=re.size();
else if(re[0]=='B' && re[re.size()-1]=='B')
ble+=re.size();
else if(re[0]=='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;
}
#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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
#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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
and
{
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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
}
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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
//
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[0]):
ans+=len(list3)
print(ans+len(list1[0]))
//
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.
- linteanm September 10, 2015strings = ['RRRR', 'BBB', 'R', 'BBB', 'RBBBB', 'RRB', 'BRBR', 'RBBB', 'BR'] RR = 0 BB = 0 RB = [] BR = [] for s in strings: if s[0] + s[-1] == 'BB': BB += len(s) elif s[0] + s[-1] == 'RR': RR += len(s) elif s[0] == '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