Microsoft Interview Question
Country: India
your solution won't work in case of string which are -ve number and in case of strings which are not convertable to number.
Your solution is good.
Negative (Who the hell writes -ve to mean negative) numbers don't make sense in the context of this question so obviously that isn't what's being asked. Otherwise you'd have to worry about
a = -45
b = -456
If you concatenate those strings together you get the string "-45-456" which doesn't make any god damned sense as it's not asking you what string evaluates to the highest value.
Additionally pointing out that this doesn't work if the input values aren't "convertable to number" is unnecessary.
Very smart and simple solution, Manan. Unlike other solutions, there are no multiplies or other arithmetic that you are using. So, there is no chance of overflow.
what is j here?
Will it work when numbers are like 45 450, in which case if i understand your solution, it will return any but answer should be 45450 instead of 45045
Suppose two string, stringA and stringB, are integer-convertible.
a = atoi(stringA.c_str());
b = atoi(stringB.c_str());
valA = a * power(10, stringB.size()) + b;
valB = b * power(10, stringA.size()) + a;
return valA > valB? valA : valB;
what if length of string is long? say 10 or 15
multiplication & power doesn't really work
why are you taking power? What are these?
valA = a * power(10, stringB.size()) + b;
valB = b * power(10, stringA.size()) + a;
Your comment is correct if this string is really long.(out of 64-bit can take) But if it is down to that road, the first question to answer to how to store the really large number (data structure) in computer. For instance a number is composed of 1 billion digits. For some meaningful computing some sanity checking is necessary beforehand.
You just need to calculate largest of the 2 string as integer/double and the other one you need to append it to that.
ex:
string a="150";
string b="120";
string result = (Convert.ToInt32(a)>=Convert.ToInt32(b))?string.Concat(a,b):string.Concat(b,a);
inputs are given as arguments.. e.g ./a.out 45 465
#include<stdio.h>
#include<string.h>
int main(int argc, char * argv[]){
int a, b,min,i;
char *st;
a= strlen(argv[1]);
b= strlen(argv[2]);
min= a < b ? a : b ;
for(i=0;i<min;i++){
if (argv[1][i] < argv[2][i]){
st= strcat(argv[2],argv[1]);
printf("%s",st);
return 0;
}
else if (argv[1][i] > argv[2][i]){
st= strcat(argv[1],argv[2]);
printf("%s",st);
return 0;
}
// noted equal case ignored and later taken care of..
}
// if the argv[1], argv[2] is prefix of one then this check is needed
if (a<b){
if (argv[1][0] >= argv[2][min] )
st= strcat(argv[1],argv[2]);
else
st= strcat(argv[2],argv[1]);
}
else {
if (argv[2][0] >= argv[1][min] )
st= strcat(argv[2],argv[1]);
else
st= strcat(argv[1],argv[2]);
}
printf("%s",st);
return 0;
}
String a = "45";
String b = "4545456";
String merge_to_max (String a, String b) {
if (a.length() > b.length()) {
String c = a;
a = b;
b = c;
}
for (int i=0; i<b.length(); i++) {
int mod_a = i % a.length();
if (a.charAt(i) > b.chartAt(i)) {
return a + b;
} else if (a.charAt(i) < b.charAt(i)) {
return b + a;
}
}
return a+b;
}
String a = "45";
String b = "4545456";
String merge_to_max (String a, String b) {
if (a.length() > b.length()) {
String c = a;
a = b;
b = c;
}
for (int i=0; i<b.length(); i++) {
int mod_a = i % a.length();
if (a.charAt(mod_a) > b.chartAt(i)) {
return a + b;
} else if (a.charAt(mod_a) < b.charAt(i)) {
return b + a;
}
}
return a+b;
}
There is even a more cunning method. Since the comparison of number is the same as the string/ASCII. For instance 46465 < 46546, for string it is also very true that "46465" < "46545" because the ASCII of "5" is more than "4".
So we can append these two string in difference order, the one winning on string comparison wins in integer-conversion.
// StringA and StingB input
std::string combAB = StringA + StringB;
std::string combBA = StringB + StirngA;
return combAB.compare(combBA) > 0? atio(combAB) : atio(combBA);
Now you need to port your code to a machine that uses EBCDIC. Does your approach work? If not, then re-write it so that it works on an EBCDIC machine and a non-EBCDIC machine.
It should not matter as long as the string comparison is implemented as if '4' < '5', and atio() does the same thing. Remember that we are not doing assembler.
#include <string.h>
#include <stdlib.h>
int max_sum(char *s1, char *s2)
{
char *num1,*num2;
int n1,n2;
num1 = s1;
num1 = (char*)malloc(strlen(s1) + strlen(s2) +1);
num2 = (char*)malloc(strlen(s1) + strlen(s2) +1);
memcpy(num1,s1,strlen(s1));
memcpy(num1+strlen(s1),s2,strlen(s2)+1);
memcpy(num2,s2,strlen(s2));
memcpy(num2+strlen(s2),s1,strlen(s1)+1);
n1 = atoi(num1);
n2 = atoi(num2);
free(num1);
free(num2);
if(n1 > n2)
return n1;
return n2;
}
int main()
{
max_sum("123","345");
}
Assuming powers etc are not allowed (if the string length is too large!)
WLOG, assume a.length <= b. length. For example, if a.length>b.length, define c = b and d = a. And work with c and d.
Check bit by bit if
a[i] > b[i]
string compare(string a, string b)
{
int flagcount = 1;
string result;
for (i = 0, i<a.length && flagcount =1, i++)
{
if(a[i] > b[i])
{
flagcount = 2;
result = a+b;
}
if(a[i] = b[i])
{
flagcount = 1;
}
if(a[i]<b[i])
{
flagcount =0;
result = b+a;
}
}
if (flagcount ==1)
{
string modb = b[a.length + 1 : b.length-1];
string moda = modb + a;
result = compare(moda, b);
}
return result;
}
If the integer values of s1 and s2 are all larger than 32-bit, or 64-bit integer, what will happen?
Thus I think we should handle them as strings, instead of converting them to integers.
Below is my C++ code.
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
bool isLarger(char* s1, char* s2)
{
bool flag = false;
int l1 = strlen(s1), l2 = strlen(s2), l = l1 > l2 ? l1 : l2, i = 0;
char* f1 = new char[l];
char* f2 = new char[l];
for(i = 0; i < l1; f1[i] = s1[i], i++);
for(; i < l; f1[i++] = '9');
for(i = 0; i < l2; f2[i] = s2[i], i++);
for(; i < l; f2[i++] = '9');
for(i = 0; i < l; i++)
{
if(s1[i] < s2[i])
{
flag = true;
break;
}
}
delete f1;
delete f2;
return flag;
}
char* spellNumber(char* s1, char* s2)
{
int i = 0;
char* spell = new char[strlen(s1) + strlen(s2) + 1];
if(isLarger(s1, s2))
{
for(i = 0; i < strlen(s2); i++)
{
spell[i] = s2[i];
}
for(; i < strlen(s1) + strlen(s2); i++)
{
spell[i] = s1[i - strlen(s2)];
}
}
else
{
for(i = 0; i < strlen(s1); i++)
{
spell[i] = s1[i];
}
for(; i < strlen(s1) + strlen(s2); i++)
{
spell[i] = s2[i - strlen(s1)];
}
}
spell[i] = '\0';
return spell;
}
int main()
{
char* s1 = "1243";
char* s2 = "5634";
char* spell = spellNumber(s1, s2);
cout << spell << endl;
delete spell;
return 0;
}
#include<iostream> // Author : Jeevan B.Manoj,TKMCE
#include<stdlib.h>
#include<string.h>
using namespace std;
int main()
{
char s1[60],s2[60],str1[30],str2[30];
strcpy(s1,"");
strcpy(s2,"");
int n1,n2;
cout<<"Enter S1 and S2 ";
cin>>str1>>str2;
strcat(s1,str1);
strcat(s1,str2);
n1=atoi(s1);
strcat(s2,str2);
strcat(s2,str1);
n1=atoi(s2);
if(n1>n2)
cout<<"\n"<<s1;
else
cout<<"\n"<<s2;
return 0;
}
only join the string once
public String join(String a, String b)
{
for(int i = 0; i < a.length() + b.length(); i++) {
char c1 = i < a.length() ? a.charAt(i) : b.charAt(i - a.length());
char c2 = i < b.length() ? b.charAt(i) : a.charAt(i - b.length());
if (c1 < c2)
return b + a;
else if (c1 > c2)
return a + b;
}
return b + a;
}
Here is the solution.
1. Set String one = s1+s2
2. Set String two = s2+s1
3. Now if(one > two) return one+two else return two+one
Below is the java Code
- loveCoding October 16, 2012