## MVVSK

BAN USER- 0of 0 votes

AnswersA file of encoded message contains only numbers. Original message contains only lowercase letters and spaces. So character ‘a’ is mapped to 1 ‘b’ to 2 and so on till ‘z’ is mapped to 26. Given an input of numbers find out the number of ways you can decode it in original message. Eg. 123 can be decoded in 3 ways as 'abc', 'lc' or 'aw'

- MVVSK in India| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersA file of encoded message contains only numbers. Original message contains only lowercase letters and spaces. So character ‘a’ is mapped to 1 ‘b’ to 2 and so on till ‘z’ is mapped to 26. Given an input of numbers find out the number of ways you can decode it in original message. Eg. 123 can be decoded in 3 ways as ‘abc’, ‘lc’ or ‘aw'

- MVVSK in India| Report Duplicate | Flag | PURGE

Amazon Senior Software Development Engineer Algorithm

The solution is simple as they didn't say abt the "BST" is balanced or not ...

so let us take the array is sorted in ascending order

Now keep adding all the elements to the right of the nodes

eg : {1,2,3,4,5}

node(1).right->node(2).right->node(3).right->node(4).right->node(5)

all node(x).left->null

this is also a BST :-)

String input = "28/12/9999";

String[] splitArray = input.split("/");

Integer date = Integer.parseInt(splitArray[0]);

Integer month = Integer.parseInt(splitArray[1]);

Integer year = Integer.parseInt(splitArray[2]);

boolean leapYear = year%4 == 0 ? true : false;

boolean is31Days = false;

if(month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)

is31Days = true;

boolean isfeb = month == 2? true : false;

date = date+4;

if((is31Days && date > 31))

{

month +=1; date = date - 31;

}

else if(!is31Days && date > 30)

{

month +=1; date = date - 31;

}

else if ((isfeb && leapYear && date > 29 ) )

{

month +=1; date = date - 29;

}

else if (isfeb && !leapYear && date > 28 ){

month +=1; date = date - 28 ;

}

if(month == 13){

month = 1;

year +=1;

}

System.out.print((date.toString().length()==1?"0":"") + date.toString() + "/" + (month.toString().length() == 1 ? "0" : "")+month.toString()+"/"+year.toString());

I found a simple solution

Array : {1 2 7 8 9}

Assumption : Array is sorted

Output : need to construct the 2numbers from array numbers such that sum is min

Solution :

1)num1=num2=0

2)mul1=mul2=1

3)for(int i=0;i<arr.len;i++)

{

if(i%2 = 0 && arr[i] !=0)

{

num1=arr[i]*mul1 ;

mul1*=10;

}

else if(arr[i]!=0)

{

num2=arr[i]*mul2;

mul2*=10;

}

}

4)Print num1 and num2

5) So min sum is num1+num2

@suvrokroy : there are two problems if we in your approach ..

1) we can not increase the size of int array dynamically , so we can not put all the content to big array ...

2)If we want to use bubble sort we need to create a new array with content of both array , the complexity will be

N: length of first array

M length of second array

time : O((N+M)2) = O(n2)

space : O(M+N) = O(n)

The complexity of my solution is

time : O(M+N) = O(n)

space : O(M+N) = O(n)

private static int[] mergeArray(int[] array1, int[] array2) {

// TODO Auto-generated method stub

int[] output = new int[array1.length+array2.length];

int i=0,j=0 ,k=0;

while(i< array1.length && j<array2.length )

{

if(array1[i]<array2[j]){

output[k++]=array1[i++];

}

else{

output[k++]=array2[j++];

}

}

if(array1.length -1 != i){

while(i<array1.length){

output[k++]=array1[i++];

}

}

if(array2.length -1 != j){

while(j<array2.length){

output[k++]=array2[j++];

}

}

return output;

}

Hi Bevan ,

The question is : to find if to linked lists are intersecting ,if yes return the first intersecting node

Understanding question :

Consider the shape "Y" made of beads ...

Now assume each bead as node and it is pointing to the next bead to for linked list .

I mean if two linked list's are intersecting they form a shape "Y" .

Here we need to find the intersecting point ....

here we have to parts ...

1)Given two singly linked list, find if they are intersecting. Do this in single iteration.

a) traverse list1 and find the last element

b) traverse list2 and find the last element

c) check if last element of list1 == last element of list2 , if equal intersecting else not

here we have parsed the list only once :-)

2) Also find the intersecting node in O(n) time and O(1) space

here they have asked to do it in O(1) space so we need to use only one variable :-)

a) create a variable(int) diff=0

b) parse list1 and increment diff for each node

c) parse list2 and decrement diff for each node

d)if diff is > 0 list1 is bigger so push the pointer of list1 by diff times

else list2 is bigger so push the pointer of list2 by mod(diff) times

e)Now check if both the pointers are equal till we reach end

public static void main(String[] args) {

String input = "abc";

StringBuffer inputSB = new StringBuffer(input);

StringBuffer output = new StringBuffer();

printPrem(inputSB,output );

//System.out.print("dfdd");

}

private static void printPrem(StringBuffer input, StringBuffer output) {

if(input.length()==0){

System.out.println(output);

}

else{

for(int i=0;i<input.length();i++)

{

StringBuffer tempi = new StringBuffer(input.toString());

StringBuffer tempo = new StringBuffer(output.toString());

printPrem(tempi.deleteCharAt(i) , tempo.append(input.charAt(i)));

}

}

}

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

public static void main(String[] args) {

- MVVSK August 20, 2016printComb("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));

}

}