Amazon Interview Question Software Engineer in Tests
Country: India
Interview Type: Written Test
Here is some python code, which I believe does the trick. Basically you make a list of characters from the given string and then make a list of ASCII values named 'lis'. Then you check two conditions: the length of lis should be even, and the sum of the first half should be equal to the sum of the second half. If the conditions hold, then prepend "12345" to str and return it, otherwise return it as it is:
def is_equal_sum(str):
lis = map(ord, list(str))
if((len(lis)%2 == 0) and sum(lis[:(len(lis)/2)])==sum(lis[(len(lis)/2):])):
return "12345"+str
else:
return str
is_equal_sum("678876")
returns
'12345678876'
is_equal_sum("67887")
returns
'67887'
Wait, I don't get what is meant by "TWO EQUAL PARTS"? Is it necessary for them to be the two equal halves or can they be any two subsequences of the string. If it is the former, look at my answer above, otherwise it is a special case of the "2-partition problem" and is weakly NP-complete, i.e. it can be solved in pseudo-polynomial time using DP. I'm giving a recursive solution in python here(for each element choose whether it is to be included in the first part or the second):
def any_equal_sum(str):
lis = map(lambda(x): ord(x)-ord('0'), list(str))
if(len(lis)%2 != 0 or sum(lis)%2 != 0): return str
if(is_subset_with_sum(lis, sum(lis)/2, len(lis)/2)):
return "12345"+str
else:
return str
def is_subset_with_sum(lis, s, length):
if(length>len(lis)): return False
if(length==0): return s==0
return (is_subset_with_sum(lis[:-1], s, length) or is_subset_with_sum(lis[:-1], s-lis[-1], length-1))
any_equal_sum("667788")
returns
"12345667788"
and
any_equal_sum("66788")
returns
"66788"
"TWO EQUAL PARTS" actually implies we are looking for an palindrome of even length. It is also possible to clarify whether we can consider an odd length string since "1234321" has its left and right sides equal (ignoring the pivot 4). Now, we check if the given string is a palindrome. If positive, then search for the right portion of this string in the source string (e.g., we search for the 876 in the "12345876678") and if found, then replace the remainder of the source with the given string. So, we get:
1. is "678876" palindrome? YES
2. is "876" present in "12345876678"? YES
3. Starting from the first index where 8 is encountered, replace the source string with the given string -> "12345678876".
It is an O(n) approach.
For second half of prog,Look at thss
cpy and paste in browxy site
import java.io.*;
public class Test{
public static void main(String args[]){
String Str="12345876678"
System.out.print("Return Value :" );
System.out.println(Str.replaceFirst("876678", "678876" ));
}
}
OUTPUT:
Return Value :12345678876
function(string input)
{
int number;
int sumOne;
int sumTwo;
// If string doesn't have even number of characters
// then it can't be devided in to two equal parts
if((input.Length)%2!=0)
return string.Empty;
// Get the first part of the string
String strOne = input.Substring(0,input.Length/2);
// Get the second part of the string
String strTwo = input.Substring(input.Length/2);
if(int32.TryParse(strOne,out number))
{
Sum(number(out sumOne);
}
if(int32.TryParse(strTwo,out number))
{
Sum(number(out sumTwo);
}
if (sumOne==sumTwo)
return "12345667788";
else
return input;
}
Sum(int digit, out sum) // digit = 456
{
sum = digit % 10; // sum = 6
int number = digit/10; // number = 45
while(number!=0)
{
sum = sum + number % 10; // sum = 6+5
number = number/10; // number = 4
}
}
in python
#!/usr/bin/python
s="678876"
l=len(s)
r1=[]
r2=[]
final=["12345"]
if(l%2!=0) :
print("string has odd number of digits")
else:
l2=(l/2)
i=0
while(i<l2) :
int(s[i])
r1.append(s[i])
i=i+1
j=int(l2)
while(j<l) :
int(j)
r2.append(s[j])
#print(j)
j=j+1
s1=0
s2=0
for a in r1 :
s1=s1+int(a)
for b in r2 :
s2=s2+int(b)
#print(s1)
#print(s2)
if (s1==s2) :
final.append(s)
print("".join(final))
else :
print("the sum of digits is not equal")
ruby solution -
def equal_part_sum_string str
half, i, arr_1, arr_2, sum_1, sum_2 = str.length / 2, 0, [], [], 0, 0
str.split('').each do |c|
i < half ? arr_1 << c : arr_2 << c
i += 1
end
0.upto(arr_1.size) do |i|
sum_1 += i
end
0.upto(arr_2.size) do |i|
sum_2 += i
end
if sum_1 == sum_2
str = '12345' + arr_2.join + arr_1.join
end
end
import java.util.Arrays;
public class twoequalparts {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="678876";
String []s=str.split("");
int len =str.length();
int n=len/2;
int max1 = 0,max2=0;
int []arr=new int[len];
for(int i=0;i<len;i++)
{
arr[i]=Integer.parseInt(s[i]);
}
System.out.println(Arrays.toString(arr));
for(int i=0;i<n;i++)
{
max1+=arr[i];
}
System.out.println(max1);
for(int i=len-1;i>=n;i--)
{
max2+=arr[i];
}
System.out.println(max2);
if(max1==max2)
{
String st="12345";
StringBuffer sb=new StringBuffer();
sb.append(st);
for(int i=n;i<len;i++)
{
sb.append(arr[i]);
}
for(int i=0;i<n;i++)
{
sb.append(arr[i]);
}
System.out.println(sb);
}
}}
check the string length divide it by two then sum it up...if sum is same then append 12345 in starting...It should not be this much simple....please clarify the constraints in the problem...
- Dinesh Pant September 19, 2013