Alternate Print
You have two strings “A” and “B”. Your task is to print these two strings in an alternative fashion according to indices i.e. first character of “A”, the first character of “B”, the second character of “A”, the second character of “B” and so on.

Note:

If all characters of one string are printed and some characters of other string are remaining, then you have to print the remaining characters of the other string at the end of the resulting string.

Follow Up :

Can you solve the problem in O(N) time complexity and O(1) space complexity?

For Example:

A = “abc” B = “fdh” then answer will be afbdch.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test contains two space-separated strings “A” and “B”.

Output format :

For each test case, print a single line containing these two strings in an alternative fashion according to indices.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Alternate Print

You have two strings “A” and “B”. Your task is to print these two strings in an alternative fashion according to indices i.e. first character of “A”, the first character of “B”, the second character of “A”, the second character of “B” and so on.

Note:

If all characters of one string are printed and some characters of other string are remaining, then you have to print the remaining characters of the other string at the end of the resulting string.

Follow Up :

Can you solve the problem in O(N) time complexity and O(1) space complexity?

For Example:

A = “abc” B = “fdh” then answer will be afbdch.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test contains two space-separated strings “A” and “B”.

Output format :

For each test case, print a single line containing these two strings in an alternative fashion according to indices.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10    
1 <= |A|, |B| <= 10^5 
A and B contains only lower case English characters

Time Limit: 1sec

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Accepted Answer

I followed brute force approach
Step 1 : Take a result string
Step 2 : One by one append characters of both given strings in alternate style.
Step 3 : Iterate loop from i=0 to iStep 4 : Choose ith character of the first string it exists
result+=s1[i];
Step 5 : Choose ith character of the second string if it exists
result+=s2[i];
Step 6 : End loop
Step 7 : Print the result

Accepted Answer

Recursive Approach

The idea here is to use recursion and append characters one by one from A and B using a variable turn. If turn equals 0 then append character from A and if turn equals 1 then append character from B to answer. If we have appended all characters from one string, then append the remaining characters of the other string to answer.

Steps :

Declare an empty string to store the alternative print order, say the answer.
Declare few variables such as turn, to know whether we need to append character from A or B and indexOfA, indexOfB to get indices of A and B respectively.
Declare a function alter to get alternative print order and store it in answer.
Finally, return the answer.

alter(answer, A, B, indexOfA, indexOfB, turn):

If turn = 0 then the following two cases will occur:
- If indexOfA >= size of A then appends the remaining characters of B to answer and break the recursion.
- Else append A[indexOfA] to answer and change turn to 1,add 1 to indexOfA for next recursive call i.e. call alter(answer, A, B, indexOfA + 1, indexOfB, 1).
If turn = 1 then the following two cases will occur:
- If indexOfB >= size of B then appends the remaining characters of A to answer and break the recursion.
- Else append B[indexOfB] to answer and change turn to 0, add 1 to indexOfB for next recursive call i.e. call alter(answer, A, B, indexOfA , indexOfB + 1, 0).

Space Complexity: O(n)Explanation:

O(N+M), where N and M are the length of string A and B respectively.

In the worst case, we need O(N+M) recursion calls. Hence the overall complexity will be O(N+M).

Time Complexity: O(n)Explanation:

O(N+M), where N and M are the length of string A and B respectively.

In the worst case, we are appending each character from A and B which takes O(N+M) time. Hence the overall time complexity will be O(N+M)

Accepted Answer

Iterative Approach

The idea here is to run a loop and append characters from A and B one by one until both of them are not empty, then append the remaining characters of the non-empty string to answer.

Steps :

Declare an empty string to store the alternative print order, say the answer.
Run a loop from index = 0 to a minimum of size of A and size of B, and do:
- Append A[index] to answer then append B[index] to answer.
After running the loop if the size of A is greater than the size of B then append the remaining characters of A to answer, else append the remaining characters of B to answer.
Finally, return the answer.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a constant space is required.

Time Complexity: O(n)Explanation:

O(N+M), where N and M are the length of strings A and B respectively.

In the worst case, we are appending each character from A and B which takes O(N+M) time. Hence the overall time complexity will be O(N+M).

You have two strings “A” and “B”. Your task is to print these two strings in an alternative fashion according to indices i.e. first character of “A”, the first character of “B”, the second character of “A”, the second character of “B” and so on.

Note:

Follow Up :

For Example:

Input format :

Output format :

Note:

Constraints :

Note:

Top Bank of America Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Bank of America Software Developer