Bank of America Interview Question
Country: United States
Interview Type: Written Test
@mulish
The idea is to check for magical binary sequence of any length starting from MSB to LSB, which has value less than previous. Once found swap the magical seq.
In this example 10 appears at the 7th index, while 1100 appears at 5th index. As 1100 values is greater than 10, we swap them.
public class MagicalString {
private static void swap(final char[] input, int start, int end) {
char[] temp = {input[start], input[start + 1]};
for (int i = start + 2; i <= end; i++) {
input[i - 2] = input[i];
}
input[end - 1] = temp[0];
input[end] = temp[1];
}
private static int getNextMS(final char[] input, int start) {
for (int i = start, numZero = 0, numOne = 0; i < input.length; i++) {
System.out.println("i = " + i);
if (i < start + 2 && input[i] != '1') return -1;
if (input[i] == '1') numOne++;
else numZero++;
if (numZero == numOne) return i;
}
return -1;
}
private static String largestMagical(final String binString) {
char[] input = binString.toCharArray();
for (int i = 1; i < input.length - 1; i++) {
if (input[i] == '0') {
int nextMS = getNextMS(input, i + 1);
if (nextMS != -1) swap(input, i - 1, nextMS);
}
}
return String.copyValueOf(input);
}
public static void main(String[] args) {
String binString = "11011000";
System.out.println(largestMagical(binString));
}
}
string modify_str(string s, int l1, int r1, int l2, int r2)
{
string temp;
int n=s.length();
for(int i=0;i<l1;i++)temp+=s[i];
for(int i=l2;i<=r2;i++)temp+=s[i];
for(int i=l1;i<=r1;i++)temp+=s[i];
for(int i=r2+1;i<n;i++)temp+=s[i];
return temp;
}
string doPerm(string s)
{
int n=s.length();
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
if(s[i]=='0')continue;
int l1=-1, r1=-1, l2=-1, r2=-1, sum=0;
for(int j=i;j<n;j++)
{
if(s[j]=='1')
{
if(l1==-1)l1=j;
else if(r1!=-1 && l2==-1)l2=j;
sum++;
}
else
{
if(l1==-1)continue;
if(r1!=-1 && l2==-1)
{
l1=-1, r1=-1, l2=-1, r2=-1;
continue;
}
sum--;
}
if(sum==0)
{
if(l2==-1)r1=j;
else
{
r2=j;
if(s.substr(l1, r1-l1+1)<s.substr(l2, r2-l2+1))
break;
else
{
l1=-1, r1=-1, l2=-1, r2=-1;
}
}
}
}
if(l2!=-1)
{
s=modify_str(s, l1, r1, l2, r2);
k=0;
break;
}
}
}
return s;
}
string largestMagical(string binString) {
string s=doPerm(binString);
return s;
}
string modify_str(string s, int l1, int r1, int l2, int r2)
{
string temp;
int n=s.length();
for(int i=0;i<l1;i++)temp+=s[i];
for(int i=l2;i<=r2;i++)temp+=s[i];
for(int i=l1;i<=r1;i++)temp+=s[i];
for(int i=r2+1;i<n;i++)temp+=s[i];
return temp;
}
string doPerm(string s)
{
int n=s.length();
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
if(s[i]=='0')continue;
int l1=-1, r1=-1, l2=-1, r2=-1, sum=0;
for(int j=i;j<n;j++)
{
if(s[j]=='1')
{
if(l1==-1)l1=j;
else if(r1!=-1 && l2==-1)l2=j;
sum++;
}
else
{
if(l1==-1)continue;
if(r1!=-1 && l2==-1)
{
l1=-1, r1=-1, l2=-1, r2=-1;
continue;
}
sum--;
}
if(sum==0)
{
if(l2==-1)r1=j;
else
{
r2=j;
if(s.substr(l1, r1-l1+1)<s.substr(l2, r2-l2+1))
break;
else
{
l1=-1, r1=-1, l2=-1, r2=-1;
}
}
}
}
if(l2!=-1)
{
s=modify_str(s, l1, r1, l2, r2);
k=0;
break;
}
}
}
return s;
}
string largestMagical(string binString) {
string s=doPerm(binString);
return s;
}
public class MagicalString {
private static void swap(final char[] input, int start, int end) {
char[] temp = {input[start], input[start + 1]};
for (int i = start + 2; i <= end; i++) {
input[i - 2] = input[i];
}
input[end - 1] = temp[0];
input[end] = temp[1];
}
private static int getNextMS(final char[] input, int start) {
for (int i = start, numZero = 0, numOne = 0; i < input.length; i++) {
System.out.println("i = " + i);
if (i < start + 2 && input[i] != '1') return -1;
if (input[i] == '1') numOne++;
else numZero++;
if (numZero == numOne) return i;
}
return -1;
}
private static String largestMagical(final String binString) {
char[] input = binString.toCharArray();
for (int i = 1; i < input.length - 1; i++) {
if (input[i] == '0') {
int nextMS = getNextMS(input, i + 1);
if (nextMS != -1) swap(input, i - 1, nextMS);
}
}
return String.copyValueOf(input);
}
public static void main(String[] args) {
String binString = "11011000";
System.out.println(largestMagical(binString));
}
}
public class MagicalString {
private static void swap(final char[] input, int start, int end) {
char[] temp = {input[start], input[start + 1]};
for (int i = start + 2; i <= end; i++) {
input[i - 2] = input[i];
}
input[end - 1] = temp[0];
input[end] = temp[1];
}
private static int getNextMS(final char[] input, int start) {
for (int i = start, numZero = 0, numOne = 0; i < input.length; i++) {
System.out.println("i = " + i);
if (i < start + 2 && input[i] != '1') return -1;
if (input[i] == '1') numOne++;
else numZero++;
if (numZero == numOne) return i;
}
return -1;
}
private static String largestMagical(final String binString) {
char[] input = binString.toCharArray();
for (int i = 1; i < input.length - 1; i++) {
if (input[i] == '0') {
int nextMS = getNextMS(input, i + 1);
if (nextMS != -1) swap(input, i - 1, nextMS);
}
}
return String.copyValueOf(input);
}
public static void main(String[] args) {
String binString = "11011000";
System.out.println(largestMagical(binString));
}
}
import java.util.*;
public class Main
{
public void magic_bin(int inp_bin)
{
ArrayList<Integer> x = new ArrayList<Integer>();
x.add(inp_bin);
int one_c=0, zero_c=0;
int n=x.size();
ArrayList<Integer> one = new ArrayList<Integer>();
ArrayList<Integer> zero = new ArrayList<Integer>();
for(int i=0;i<n;i++)
{
// print(x[i])
if (x.equals(1))
{
one.addAll(x);
one_c=one_c+1;
}
if (x.equals(0))
{
zero.addAll(x);
zero_c=zero_c+1;
}
if (one_c< zero_c)
{
System.out.println("Not a magic binary string") ;
break;
}
if (one_c==zero_c)
System.out.println("It is a magic binary string") ;
//print(one_c, zero_c)
}
}
public static void main(String[] args) {
System.out.println("Enter binary string");
Scanner sc =new Scanner(System.in);
int inp=sc.nextInt();
Main m = new Main();
m.magic_bin(inp);
}
}
public class MagicalString {
private static void swap(final char[] input, int start, int end) {
char[] temp = {input[start], input[start + 1]};
for (int i = start + 2; i <= end; i++) {
input[i - 2] = input[i];
}
input[end - 1] = temp[0];
input[end] = temp[1];
}
private static int getNextMS(final char[] input, int start) {
for (int i = start, numZero = 0, numOne = 0; i < input.length; i++) {
System.out.println("i = " + i);
if (i < start + 2 && input[i] != '1') return -1;
if (input[i] == '1') numOne++;
else numZero++;
if (numZero == numOne) return i;
}
return -1;
}
private static String largestMagical(final String binString) {
char[] input = binString.toCharArray();
for (int i = 1; i < input.length - 1; i++) {
if (input[i] == '0') {
int nextMS = getNextMS(input, i + 1);
if (nextMS != -1) swap(input, i - 1, nextMS);
}
}
return String.copyValueOf(input);
}
public static void main(String[] args) {
String binString = "11011000";
System.out.println(largestMagical(binString));
}
}
- sudip.innovates October 16, 2017