N/A Interview Question Software Engineers
Country: India
Interview Type: Written Test
package salesforce;
import java.util.LinkedList;
import java.util.List;
public class Solution {
public static void main(String[] args) {
//String largestMagical = largestMagical("1100");
// String largestMagical = largestMagical("11011000");
String largestMagical = largestMagical("1101001100");
//String largestMagical = largestMagical("1101110101011000");
System.out.println(largestMagical);
}
public static String largestMagical(String str) {
List<Integer> list = new LinkedList<>();
int length = str.length();
for(int i=0; i<length; i++) {
if(str.charAt(i) == '1') {
list.add(1);
} else {
list.add(-1);
}
}
for(int i=0; i < length - 1; i++) {
WrapperIntger wrapperI = new WrapperIntger(i);
for(int j = i+1; j < length - 1; j++) {
WrapperIntger wrapperJ = new WrapperIntger(j);
WrapperIntger preFixSum = new WrapperIntger(0);
WrapperIntger suffixSum = new WrapperIntger(0);
WrapperIntger end = new WrapperIntger(-1);
boolean isPrefixMagical = checkMagical(wrapperI, wrapperJ, preFixSum, list);
boolean isSuffixMagical = checkMagical(wrapperJ, end, suffixSum, list);
if(isPrefixMagical && isSuffixMagical && suffixSum.getIntValue() > preFixSum.getIntValue()) {
StringBuilder stringBuilder = new StringBuilder();
// System.out.println("String len" + length);
//System.out.println("i=" + wrapperI.getIntValue());
//System.out.println("j=" + wrapperJ.getIntValue());
String tempStr = stringBuilder.append(str.substring(0, wrapperI.getIntValue()))
.append(str.substring(wrapperJ.getIntValue(), end.getIntValue()))
.append(str.substring(wrapperI.getIntValue(), wrapperJ.getIntValue()- 1))
.toString();
if(end.getIntValue() < length) {
tempStr = stringBuilder.append(str.substring(end.getIntValue())).toString();
}
str = tempStr;
}
}
}
return str;
}
private static boolean checkMagical(WrapperIntger start, WrapperIntger end, WrapperIntger sum, List<Integer> list) {
if(end.getIntValue() == -1) {
for(int i=start.getIntValue() +1 ; i < list.size(); i++) {
WrapperIntger tempWrapper = new WrapperIntger(i);
if(checkMagical(start, tempWrapper, sum, list)) {
end.setIntValue(i);
return true;
}
}
return false;
}
int check = 0;
int counter = end.getIntValue() - start.getIntValue();
for(int i=start.getIntValue(); i < end.getIntValue(); i++) {
check = check + list.get(i);
if(list.get(i).equals(1)) {
sum.setIntValue((int) (sum.getIntValue() + Math.pow(2, counter)));
}
counter--;
if(check < 0) {
return false;
}
}
return check == 0;
}
private static class WrapperIntger {
int intValue;
public WrapperIntger(int intValue) {
this.intValue = intValue;
}
public int getIntValue() {
return intValue;
}
public void setIntValue(int intValue) {
this.intValue = intValue;
}
}
}
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;
}
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));
}
}
def swap(array,start,end):
temp = [array[start],array[start+1]]
for i in range(start+2,end):
array[i-2] = array[i]
array[end-1] = temp[0]
array[end] = temp[1]
def getNextMS(array,start):
numZero = 0
numOne = 0
for i in range(start,len(array)):
print("i=",i)
if i < start + 2 and array[i] !='1':
return -1
if array[i] == '1':
numOne += 1
else:
numZero += 1
if numZero == numOne:
return i
return -1
binString = "11011000"
array =list(binString)
def largestMagical():
global array
for i in range(len(array)-1):
if array[i] == '0':
nextMS = getNextMS(array,i+1)
if nextMS != -1:
swap(array,i-1,nextMS)
print(array)
return array
largestMagical()
def swap(array,start,end):
temp = [array[start],array[start+1]]
for i in range(start+2,end):
array[i-2] = array[i]
array[end-1] = temp[0]
array[end] = temp[1]
def getNextMS(array,start):
numZero = 0
numOne = 0
for i in range(start,len(array)):
print("i=",i)
if i < start + 2 and array[i] !='1':
return -1
if array[i] == '1':
numOne += 1
else:
numZero += 1
if numZero == numOne:
return i
return -1
binString = "11011000"
array =list(binString)
def largestMagical():
global array
for i in range(len(array)-1):
if array[i] == '0':
nextMS = getNextMS(array,i+1)
if nextMS != -1:
swap(array,i-1,nextMS)
print(array)
return array
largestMagical()
bool magicB(vector<int> n, int strt, int & end, int & sum)
- Anonymous October 08, 2017{
if( end == -1)
{
for(int i = strt+1; i < n.size(); i++)
if(magicB(n, strt, i, sum))
{
end = i;
return true;
}
return false;
}
int chk = 0; int counter = end-strt;
for(int i = strt; i<=end;i++)
{
chk = chk + n[i];
if(n[i] == 1)
sum = sum + pow(2, counter);
counter --;
if(chk < 0) return false;
}
if (chk == 0)
return true;
return false;
}
string largestMagical(string str) {
vector<int> n ;
for(int i = 0; i<str.length();i++)
if(str[i] =='0')
n.push_back(-1);
else
n.push_back(1);
for (int idx = 0; idx < str.length()-1; idx ++)
{
for(int i = idx+1; i<str.length()-1;i++)
{
int sum1 = 0, sum2 = 0;
int end = -1;
bool c1 = magicB(n, idx, i, sum1);
bool c2 = magicB(n, i+1, end, sum2);
if(c1 && c2 && sum2>sum1)
{
str = str.substr(0, idx) + str.substr(i+1, end-i) + str.substr(idx, i-idx+1) + str.substr(end+1);
}
}
}
return str;
}