Bank of America Interview Question


Country: United States
Interview Type: Written Test




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

public static void main(String[] args) {
		String str = "11011000";
		System.out.println(magicstr(str));
	}

	public static String magicstr(String str) {

		int n = str.length();
		int maxInd = -1;
		int maxLen = -1;
		int maxVal = -1;
		for (int i = 1; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				int mag = ismagic(str, i, j);
				if (mag > maxVal && maxVal > -1) {
					String nq = "";
					String t1 = str.substring(maxInd, maxInd + maxLen);
					String t2 = str.substring(i, j + 1);
					String pre1 = str.substring(0, maxInd);
					String po1 = str.substring(j+1, n);
					String mi1 = str.substring(maxInd + maxLen+1, i + 1);

					nq = pre1;
					nq += t2;
					nq += mi1;
					nq += t1;
					nq += po1;

					str = magicstr(nq);
				} else if (mag > maxVal && maxVal == -1) {
					maxInd = i;
					maxLen = j - i + 1;
					maxVal = mag;
					break;
				}
			}
		}
		return str;
	}

	public static int ismagic(String str, int i, int j) {
		if (i == j)
			return -1;
		String bis = str.substring(i, j+1);
		if (bis.length() == 0)
			return -1;

		int bi = Integer.parseInt(bis, 2);
		int count1 = 0;
		int count0 = 0;

		int n = bis.length()-1;
		while (n >= 0) {
			if (((bi & (1 << n)) != 0) && ( (bi & (1 << n)) == 1 || (bi & (1 << n)) % 2 == 0))
				count1++;
			else
				count0++;

			if (count1 < count0)
				return -1;
			n--;
		}
		if (count1 == count0)
			return Integer.parseInt(bis);
		return -1;
	}

- sudip.innovates October 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please explain?

- maulish October 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- sudip.innovates October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
  }
}

- Saurabh February 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What

- Anonymous March 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Dakshi October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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));
  }
}

- Anonymous February 03, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More