SHR
BAN USER- 1of 1 vote
AnswersGiven a number print the number of combinations you can derive from the number. 1=A, 2=B, 26=Z, 0=+.
- SHR in India
For example: 1123 can be represented by 1,1,2,3 which would stand for AABC.
Another representation - 11,23 - JW
Another representation - 1,1,23 - AAW
Another representation - 11,2,3 - JBC
For number 1123, there will be 5 combinations.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersIn a binary tree, find and print the path with smallest weight.
- SHR in India
Criteria: the tree contains integer values in the nodes. It may not be balanced tree. Weight is calculated by sum of values in the nodes in that path. Write code that returns the path as well as the minweight.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
Javacode and testcase:
package dev.random;
public class BallPassProblem
{
public int getNumberOfPasses(int numberOfFriends, int jumpCount, int maxNumber)
{
int[] friends = new int[numberOfFriends];
int countInPosition=0;
friends[0]++;
countInPosition = friends[0];
int ballPosition = 0;
int maxIndexInArray = numberOfFriends - 1;
int countOfPasses=1;
jumpCount++;
while (countInPosition < maxNumber)
{
if (countInPosition % 2 == 0)
{
int tempBallPosition = ballPosition - jumpCount;
ballPosition = (tempBallPosition < 0) ? maxIndexInArray + (tempBallPosition) : tempBallPosition;
}
else
{
int tempBallPosition = ballPosition + jumpCount;
ballPosition = (tempBallPosition > maxIndexInArray) ? (tempBallPosition - maxIndexInArray) : tempBallPosition;
}
countInPosition = ++friends[ballPosition];
countOfPasses++;
}
return countOfPasses;
}
}
//testcase:
package dev.random;
import org.junit.Test;
import static junit.framework.TestCase.assertEquals;
public class BallPassProblemTest
{
@Test
public void testGetNumberOfPasses() throws Exception
{
BallPassProblem problem = new BallPassProblem();
assertEquals(10, problem.getNumberOfPasses(5,2,3));
}
}
Java code and test case:
public class LongestSubStringInLexicographyOrder
{
private String str;
public LongestSubStringInLexicographyOrder(String str)
{
this.str = str;
}
public void setStr(String str)
{
this.str = str;
}
String findLongestSubString()
{
//Null and length checks
if (this.str == null || this.str.isEmpty())
{
return "";
}
int length = this.str.length();
//Core logic starts
int from=0, to=-1;
int tempFrom=0, tempTo=-1;
for (int i=1; i<length; i++)
{
tempTo=i;
//reset tempFrom whenever you see its not in lexicographic order
if (str.charAt(i) < str.charAt(i-1))
{
tempFrom=i;
}
//keep note of the from and to index if the previous length is smaller
if (to - from < tempTo - tempFrom)
{
from=tempFrom;
to=tempTo;
}
}
return str.substring(from, to+1);
}
}
//Testcase:
import org.junit.Test;
import static org.junit.Assert.*;
public class LongestSubStringInLexicographyOrderTest
{
@Test
public void findLongestSubString() throws Exception
{
LongestSubStringInLexicographyOrder subStringInLexicographyOrder = new LongestSubStringInLexicographyOrder("abcdefghijklmnopqrstuvwxyz");
assertEquals("abcdefghijklmnopqrstuvwxyz", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr("abcdafghijklmnopqrstuvwxyz");
assertEquals("afghijklmnopqrstuvwxyz", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr("abcdafghijklmnopqrstbvwxyz");
assertEquals("afghijklmnopqrst", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr("abcdafghiajklanopqrstbvwxyz");
assertEquals("anopqrst", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr(null);
assertEquals("", subStringInLexicographyOrder.findLongestSubString());
}
}
Java Code with test cases:
public class LongestAlternatingSubsequence
{
private int array[];
LongestAlternatingSubsequence(int[] array)
{
this.array = array;
}
public void setArray(int[] array)
{
this.array = array;
}
int findLongestAlternatingSubSequence()
{
//Null and length checks
if (this.array == null)
{
return -1;
}
int length = this.array.length;
if (length == 0)
{
return -1;
}
//Core logic starts
int from=-1, to=-1;
int tempFrom=-1, tempTo=-1;
for (int i=1; i<length; i++)
{
tempTo=i;
if (i%2 == 1)
{
if (!(this.array[i-1] > this.array[i]) && tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}
}
else
{
if (!(this.array[i] > this.array[i-1]) && tempTo-tempFrom > to-from)
{
to=tempTo;
from=tempFrom;
tempFrom=i-1;
}
}
}
System.out.println("To: " +to+"From: "+from);
return to - from;
}
}
//Test Case:
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;
public class LongestAlternatingSubsequenceTest
{
@Test
public void findLongestAlternatingSubSequence() throws Exception
{
LongestAlternatingSubsequence subsequence = new LongestAlternatingSubsequence(null);
assertEquals(-1, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 45});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 50, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(10, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 70, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
subsequence.setArray(new int[]{1, 2, 51, 52, 60, 55, 54, 68, 80, 76, 75, 12, 11});
assertEquals(8, subsequence.findLongestAlternatingSubSequence());
}
}
Java code:
import java.util.Iterator;
import java.util.List;
public class WordDistanceFinder
{
List<String> strings;
public WordDistanceFinder(List<String> strings)
{
this.strings = strings;
}
public int distance(String stringFrom, String stringTo)
{
if (!(this.strings.contains(stringFrom) && this.strings.contains(stringTo)))
{
return -1;
}
if (stringFrom.equals(stringTo))
{
return 0;
}
int fromPos=-1;
int toPos=-1;
Iterator iterator = this.strings.listIterator();
int i=0;
int min = Integer.MAX_VALUE;
while(iterator.hasNext())
{
i++;
String nextString = (String) iterator.next();
if (nextString.equals(stringFrom))
{
fromPos=i;
if (min > Math.abs(fromPos - toPos) && toPos > -1)
{
min = Math.abs(fromPos - toPos);
}
}
else if (nextString.equals(stringTo))
{
toPos=i;
if (min > Math.abs(fromPos - toPos) && fromPos > -1)
{
min = Math.abs(fromPos - toPos);
}
}
}
return min;
}
}
//TestCases:
import java.util.Arrays;
import static org.junit.Assert.*;
public class WordDistanceFinderTest
{
@org.junit.Test
public void testDistance() throws Exception
{
WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick", "abcd"));
assertEquals(-1, finder.distance("123", "123"));
assertEquals(-1, finder.distance("123", "abcd"));
assertEquals(0, finder.distance("abcd", "abcd"));
assertEquals(3, finder.distance("fox","the"));
assertEquals(1, finder.distance("quick", "fox"));
}
}
Java Code without using any other DS. Complexity is O(n). Please find JUnit test case as well.
import java.util.Iterator;
import java.util.List;
public class WordDistanceFinder
{
List<String> strings;
public WordDistanceFinder(List<String> strings)
{
this.strings = strings;
}
public int distance(String stringFrom, String stringTo)
{
if (!(this.strings.contains(stringFrom) && this.strings.contains(stringTo)))
{
return -1;
}
if (stringFrom.equals(stringTo))
{
return 0;
}
int fromPos=-1;
int toPos=-1;
Iterator iterator = this.strings.listIterator();
int i=0;
int min = Integer.MAX_VALUE;
while(iterator.hasNext())
{
i++;
String nextString = (String) iterator.next();
if (nextString.equals(stringFrom))
{
fromPos=i;
if (min > Math.abs(fromPos - toPos) && toPos > -1)
{
min = Math.abs(fromPos - toPos);
}
}
else if (nextString.equals(stringTo))
{
toPos=i;
if (min > Math.abs(fromPos - toPos) && fromPos > -1)
{
min = Math.abs(fromPos - toPos);
}
}
}
return min;
}
}
Testcase:
import java.util.Arrays;
import static org.junit.Assert.*;
public class WordDistanceFinderTest
{
@org.junit.Test
public void testDistance() throws Exception
{
WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick", "abcd"));
assertEquals(-1, finder.distance("123", "123"));
assertEquals(-1, finder.distance("123", "abcd"));
assertEquals(0, finder.distance("abcd", "abcd"));
assertEquals(3, finder.distance("fox","the"));
assertEquals(1, finder.distance("quick", "fox"));
}
}
Repmendezleah216, Analyst at Bosch
Hello,everybody,I'm Leah Mendez.I want to make some friends here.I’m a woman with ambition and ...
Repcardiroy, Backend Developer at Accolite software
Hi,I am from Taxes, USA. Enthusiastic multilingual translator with years involvement with Spanish-English translations.Looking to additionally improve interpretation ...
Repnancysimms14, Backend Developer at ASAPInfosystemsPvtLtd
I am Nancy from California,Handling project development and documentation is my job. Passionate determined.Looking for an open project ...
Java Program with test cases:
Please note this program uses Java 8 BiFunction
TestCase;
- SHR April 24, 2016