Amazon Interview Question
SDE-2sTeam: Payments
Country: United States
Interview Type: In-Person
public class Main {
public static void main(String[] args) {
String s1 = "abc";
String s2 = "de";
printInterleave(s1,s2);
}
public static void printInterleave(String s1,String s2){
String soFar = "";
printInterleaveUtil(s1,s2,0,0, soFar);
}
public static void printInterleaveUtil(String s1, String s2, int l1, int l2, String soFar){
if(l1 == s1.length() && l2 == s2.length()){
System.out.println(soFar);
return;
}
if(l1 < s1.length()){
printInterleaveUtil(s1,s2,l1+1,l2,soFar+s1.charAt(l1));
}
if(l2 < s2.length()){
printInterleaveUtil(s1,s2,l1,l2+1,soFar+s2.charAt(l2));
}
}
}
public class Main {
public static void main(String[] args) {
String s1 = "abc";
String s2 = "de";
printInterleave(s1,s2);
}
public static void printInterleave(String s1,String s2){
String soFar = "";
printInterleaveUtil(s1,s2,0,0, soFar);
}
public static void printInterleaveUtil(String s1, String s2, int l1, int l2, String soFar){
if(l1 == s1.length() && l2 == s2.length()){
System.out.println(soFar);
return;
}
if(l1 < s1.length()){
printInterleaveUtil(s1,s2,l1+1,l2,soFar+s1.charAt(l1));
}
if(l2 < s2.length()){
printInterleaveUtil(s1,s2,l1,l2+1,soFar+s2.charAt(l2));
}
}
}
#include <iostream>
#include <cstring>
using namespace std;
void printPermutations(string str1,string str2,int start1,int start2,string temp)
{
if (start1==str1.length() && start2==str2.length())
{
cout<<temp<<endl;
return;
}
if(start1 < str1.length())
{
printPermutations(str1,str2,start1+1,start2,temp+str1[start1]);
}
if(start2 < str2.length())
{
printPermutations(str1,str2,start1,start2+1,temp+str2[start2]);
}
}
int main()
{
string str1="abc",str2="de";
string temp="";
printPermutations(str1,str2,0,0,temp);
return 0;
}
public class StringInterleaving {
public static void main(String argsp[]) {
String s1="abc",s2="de";
printInterleaving(s1, s2, 0);
printInterleaving(s2, s1, 0);
}
public static void printInterleaving(String s1, String s2, int index) {
System.out.println(s1.substring(0, index)+s2+s1.substring(index));
if(index+1 <= s1.length()) {
printInterleaving(s1, s2, index+1);
}
}
}
{{public class StringInterleaving {
public static void main(String argsp[]) {
String s1="abc",s2="de";
printInterleaving(s1, s2, 0);
printInterleaving(s2, s1, 0);
}
public static void printInterleaving(String s1, String s2, int index) {
System.out.println(s1.substring(0, index)+s2+s1.substring(index));
if(index+1 <= s1.length()) {
printInterleaving(s1, s2, index+1);
}
}
}
}}
/*
* InterLeavingStrs.cpp
*
* Created on: Jul 29, 2016
* Author: chandra.shekhar
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define BUFF 25
void InterLeaveStrs(char *s1, char *s2, int n, int m, char *dest, int destIdx){
if(n == strlen(s1) && m == strlen(s2) ){
cout << "String is " << dest << endl ;
return;
}
if(n < strlen(s1)){
dest[destIdx] = s1[n];
InterLeaveStrs(s1,s2,n+1, m,dest, destIdx+1);
}
if(m < strlen(s2)){
dest[destIdx] = s2[m];
InterLeaveStrs(s1,s2,n, m+1,dest, destIdx+1);
}
}
int main(){
char s1[BUFF];
char s2[BUFF];
cout << endl << "Enter String 1 " << endl ;
cin >> s1;
cout << "Enter String 2" << endl;
cin >> s2;
char dest[BUFF];
memset(dest, '\0', BUFF);
InterLeaveStrs(s1,s2,0,0,dest,0);
return 0;
}
public static void main(String[] args) {
test t = new test();
DP dp = new DP();
dp.merge("abcd","ef");
}
public void merge(String s1 , String s2){
compute(s1,s2,"", new ArrayList<>());
}
private void compute(String s1, String s2, String res , List<String>resList) {
if(s1.length() == 0)
{
System.out.println(res+s2);
}
else if(s2.length() ==0){
System.out.println(res+s1);
}
else{
compute(s1.substring(1),s2,res+s1.charAt(0),resList) ;
compute(s1,s2.substring(1),res+s2.charAt(0),resList) ;
}
}
public void merge(String s1 , String s2){
compute(s1,s2,"", new ArrayList<>());
}
private void compute(String s1, String s2, String res , List<String>resList) {
if(s1.length() == 0)
{
System.out.println(res+s2);
}
else if(s2.length() ==0){
System.out.println(res+s1);
}
else{
compute(s1.substring(1),s2,res+s1.charAt(0),resList) ;
compute(s1,s2.substring(1),res+s2.charAt(0),resList) ;
}
}
public void merge(String s1 , String s2){
compute(s1,s2,"", new ArrayList<>());
}
private void compute(String s1, String s2, String res , List<String>resList) {
if(s1.length() == 0)
{
System.out.println(res+s2);
}
else if(s2.length() ==0){
System.out.println(res+s1);
}
else{
compute(s1.substring(1),s2,res+s1.charAt(0),resList) ;
compute(s1,s2.substring(1),res+s2.charAt(0),resList) ;
}
}
if you're just interleaving, isn't it basically a DFS where you walk down the two strings?
function weaveStrings(stringSoFar, firstString, secondstring){
if(firstString === "" && secondString === ""){
console.log(stringSoFar);
} else {
if(firstString.length > 0){
weaveStrings(stringSoFar + firstString.charAt(0), firstString.subString(1), secondString);
}
if(secondString.length > 0){
weaveStrings(stringSoFar + secondString.charAt(0), firstString, secondString.subString(1))
}
}
}
function printInterweavings(firstString, secondString){
if(firstString === null || typeof(firstString) === "undefined"){
throw {
name: "argumentException",
message: "first string is null or undefined"
}
}
if(secondString === null || typeof(secondString) === "undefined"){
throw {
name: "argumentException",
message: "second string is null or undefined"
}
}
if(firstString.length > 0 || secondString.length > 0){
weaveStrings("", firstString, secondString);
}
}
public static void main(String[] args) {
printComb("ab","def",0,0,"");
}
public static void printComb(String s1,String s2,int i1,int i2, String soFar ){
if((s1 == null || s1.length() == i1) && (s2 == null || s2.length() == i2)){
System.out.println(soFar);
}
if(s1.length() > i1){
printComb(s1, s2, i1+1, i2, soFar+s1.charAt(i1));
}
if(s2.length() > i2){
printComb(s1, s2, i1, i2+1, soFar+s2.charAt(i2));
}
}
public static void main(String args[])
{
String s1="abc",s2="de";
print_inter_leave(s1,s2,0);
}
private static void print_inter_leave(String s1, String s2,int index) {
if(s2.length()==0)
return;
for(int i=0;i<=s1.length()-index;i++)
{
System.out.println(s1.substring(0, i+index)+s2+s1.substring(i+index));
print_inter_leave(s1.substring(0,i+index)+s2.substring(0,1)+s1.substring(i+index),s2.substring(1),i+2);
}
}
- Rakshith Kunchum July 26, 2016