Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
public static int rank(int[] X)
{
TreeSet<Integer> smaller_count_set = new TreeSet();
int smaller_count[X.length];
smaller_count_set.put(X[X.length-1]);
smaller_count[X.length-1] = 0;
for(int i=X.length-2; i>=0; i--)
{
smaller_count_set.put(X[i]);
smaller_count[i] = smaller_count_set.headSet(X[i]).size();
}
int factorial[X.length];
factorial[0] = 1;
factorial[1] = 1;
for(int i=2; i<X.length; i++)
factorial[i] = factorial[i-2] + factorial[i-1];
int rank =1;
for(int i=0; i< X.length; i++)
{
rank+=smaller_count[i]*factorial[X.length-i-1];
}
return rank;
}
Complexity of this algorithm is O(nlgn)
The idea would be to
1. Generate all the permutations of the array element
2. Sort the generated permutations
3. Search in the sorted list for the index
To generate all possible permutations of the array elements
1. Usually string can be easily sub stringed and manipulated so generate a single string of all the elements of the array.
2. So in this case, the output string for array element would become "415".
Now permutations of the string can be generated as follows
3. If String has single character say 4 and you add 1 additional character to it say 1, it can go before 4 and after 4. So the result would be 14 and 41
4. Now if we add last character 5 to it, 5 can go in every position (First, middle and last) in the existing string like 514, 154 and 145.
5. Same would go with string 41. When we add 5 to it, 5 can go in every possible position, 541, 451 and 415.
Here is the code in java for the same
{{
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class AllCombinationOfArrayElements {
private static int[] input = { 4, 1, 5 };
public static void main(String[] args) {
String searchString = "451";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < input.length; i++) {
sb.append(input[i]);
}
List<String> list = permutations(sb.toString());
//Sort output List
Collections.sort(list);
System.out.println("Sorted permutation = " + list);
//Binary Search in the list
int zeroIndex = Collections.binarySearch(list, searchString);
System.out.println("Index of " + searchString + " in the generated permutation is = " + ++zeroIndex);
}
//Generate the permutation of the array elements
private static List<String> permutations(String input) {
ArrayList<String> inputList = new ArrayList<String> ();
if (input.length() == 1) {
inputList.add(input);
return inputList;
}
List<String> result = permutations(input.substring(0, input.length() - 1));
ArrayList<String> updatedResult = new ArrayList<String>();
for (int i = 0; i < result.size(); i++) {
String currentString = (String) result.get(i);
//Add last character at the start
updatedResult.add(input.charAt(input.length() - 1) + currentString);
//Add last character in the middle
for (int j = 1; j < currentString.length(); j++) {
updatedResult.add(currentString.substring(0, j)
+ input.charAt(input.length() - 1)
+ currentString.substring(j, currentString.length()));
}
//Add last character at the end
updatedResult.add(currentString + input.charAt(input.length() - 1));
}
return updatedResult;
}
}
}}
lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
C++ approach. O(nlog(n)) time complexity:
{
int factorial(int n)
{
if(n == 1)
return 1;
return n * factorial(n - 1);
}
void getPermutations(string word, string perm, int * permutations, int & j)
{
if(word.empty())
{
permutations[j] = stoi(perm);
j++;
return;
}
for(int i = 0; i < word.length(); i++)
{
string word_util = word;
word_util.erase(i, 1);
string perm_util = perm;
perm_util += word[i];
getPermutations(word_util, perm_util, permutations, j);
}
}
int binarySearch(int * arr, int value, int left, int right)
{
if(left > right)
return -1;
int mid = (left + right) / 2;
if(value == arr[mid])
return mid;
else if(value < arr[mid])
return binarySearch(arr, value, left, mid - 1);
else
return binarySearch(arr, value, mid + 1, right);
}
int numberRank(int * arr, int length, int x)
{
string aux = "";
for(int i = 0; i < length; i++)
aux += to_string(arr[i]);
int fact = factorial(length);
int * permutations = new int[fact];
int j = 0;
getPermutations(aux, "", permutations, j);
sort(permutations, permutations + fact);
return binarySearch(permutations, x, 0, fact - 1) + 1;
}
int main(int argc, const char * argv[])
{
int arr[] = {4, 1, 5};
int x = 541;
cout << numberRank(arr, sizeof(arr) / sizeof(int), x) << endl;
//returns : 4
}
}
I used Arrays.sort function, because everyone knows how sorting can be done.
public class NumberDictionary {
public int findRank(char[] arr, String number) {
sort(arr);
int length = arr.length;
int rank = 0;
int count = length - 1;
for (int i = 0; i < length; i++) {
char chr = number.charAt(i);
for (int j = 0; j < arr.length; j++) {
if (arr[j] == chr) {
rank = rank + j * factorial(count);
arr = remove(arr, chr);
count--;
break;
}
}
}
return rank + 1;
}
private char[] remove(char[] arr, char chr) {
char[] newArr = new char[arr.length - 1];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (chr != arr[i]) {
newArr[index] = arr[i];
index++;
}
}
return newArr;
}
private int factorial(int i) {
if (i <= 1) {
return 1;
}
return factorial(i - 1) * i;
}
private void sort(char[] arr) {
Arrays.sort(arr);
}
}
This is the test cases :
public class NumberDictionaryTest {
private NumberDictionary numberDictionary;
@Before
public void setup() {
numberDictionary = new NumberDictionary();
}
@Test
public void test() {
assertEquals(1, numberDictionary.findRank(getArr('a'), "a"));
assertEquals(1, numberDictionary.findRank(getArr('a', 'b'), "ab"));
assertEquals(1, numberDictionary.findRank(getArr('b', 'a'), "ab"));
assertEquals(2, numberDictionary.findRank(getArr('b', 'a'), "ba"));
assertEquals(6, numberDictionary.findRank(getArr('a', 'b', 'c'), "cba"));
assertEquals(14, numberDictionary.findRank(getArr('a', 'd', 'c', 'b'), "cadb"));
assertEquals(2, numberDictionary.findRank(getArr('a', 'd', 'c', 'b'), "abdc"));
assertEquals(24, numberDictionary.findRank(getArr('a', 'd', 'c', 'b'), "dcba"));
assertEquals(10, numberDictionary.findRank(getArr('a', 'd', 'c', 'b'), "bcda"));
}
private char[] getArr(char... arrs) {
return arrs;
}
}
public class FindingRank {
private static int fact(int x){
int product=1;
for(int i=2;i<=x;i++){
product = product*i;
}
return product;
}
public static void main(String[] args) {
int arr[]={4,5,1};
int num = 514;
int i=0;
int sum=0;
while(num!=0){
arr[arr.length-1-i]=num%10;
num=num/10;
i++;
}
for(i=0;i<arr.length-1;i++){
int counter=0;
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
counter++;
}
}
sum=sum+(counter*fact(arr.length-1-i));
}
System.out.println(sum+1);
}
}
Time:O(n^2)
Space: O(n)
import java.util.ArrayList;
import java.util.List;
public class Rank {
public long findRank(int[] dictionary, int x) {
List<Integer> numberIndex = new ArrayList<>();
for (int index = 0; index < dictionary.length; index++)
numberIndex.add(dictionary[index]);
return 1 + findRank(getDigits(x), 0, numberIndex);
}
private long findRank(int digits[], int position, List<Integer> indexes) {
if (position >= digits.length)
return 0;
int digit = digits[position];
int index = getIndex(indexes, digit);
int n = indexes.size();
// Remove the index from the list
indexes.remove(index);
// rank(abc) => rank(a) + rank(bc);
// rank(a) => index(a)*(n-1)!
return index * factorial(n - 1) + findRank(digits, position + 1, indexes);
}
private int getIndex(List<Integer> indexes, int value) {
for (int index = 0; index < indexes.size(); index++)
if (indexes.get(index) == value)
return index;
return -1;
}
private int[] getDigits(int x) {
int size = 1 + (int) Math.floor(Math.log10(x));
int[] digits = new int[size];
int divider = 1;
int index;
for (index = 1; index < size; index++)
divider *= 10;
index = 0;
while (x > 0) {
digits[index] = x / divider;
x -= digits[index] * divider;
divider /= 10;
index++;
}
return digits;
}
private long factorial(int n) {
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
public static void main(String[] args) {
int[] dictionary = { 1, 2, 3, 4 };
Rank r = new Rank();
System.out.println(r.findRank(dictionary, 4321));
}
}
Assuming that all numbers in the dictionary are unique, let us first sort the dictionary - {1, 4, 5}.
In the dictionary {1, 4, 5} :
Is number 451 starting from 1 (in dictionary)? No - so the number starting from 1 are 2! = 2. ----> n1
Is the number 451 starting from 4(in dictionary)? Yes - Remove 4 from dictionary
Mark 4 in 451 as processed and now start from 5 and follow the below procedure :
In the dictionary {1, 5}:
(number is 51 as 4 has been marked processed)
Is the number 51 starting from 1(in dictionary)? No, so all numbers starting with 41 are 1! = 1 ---> n2
Is the number 51 starting from 5(in dictionary)? Yes, remove 5 from dictionary
Mark 5 as processed in 451 and follow the below procedure :
In the dictionary {1} :
(number is 1 in below as 5 has been marked as processed)
Is the number 1 starting from 1(in dictionary)? Yes, remove 1 from dictionary
Mark 1 as processed
In the dictionary {} :
Dictionary is empty now, so return 1 + n1 + n2 (see n1, n2 above)
Assuming that all numbers in the dictionary are unique, let us first sort the dictionary - {1, 4, 5}.
In the dictionary {1, 4, 5} :
Is number 451 starting from 1 (in dictionary)? No - so the number starting from 1 are 2! = 2. ----> n1
Is the number 451 starting from 4(in dictionary)? Yes - Remove 4 from dictionary
Mark 4 in 451 as processed and now start from 5 and follow the below procedure :
In the dictionary {1, 5}:
(number is 51 as 4 has been marked processed)
Is the number 51 starting from 1(in dictionary)? No, so all numbers starting with 41 are 1! = 1 ---> n2
Is the number 51 starting from 5(in dictionary)? Yes, remove 5 from dictionary
Mark 5 as processed in 451 and follow the below procedure :
In the dictionary {1} :
(number is 1 in below as 5 has been marked as processed)
Is the number 1 starting from 1(in dictionary)? Yes, remove 1 from dictionary
Mark 1 as processed
In the dictionary {} :
Dictionary is empty now, so return 1 + n1 + n2 (see n1, n2 above) which is 1 + 2 + 1 = 4. So, rank of 451 is 4.
package zhang.juanyong.interview.amazon;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import org.apache.commons.lang.ArrayUtils;
/**
* Provided a number dictionary and a number, x , which is formed from the
* number dictionary. Find the rank of the number x? Rank is defined as the
* position of the number x when all the number formed from the dictionary are
* sorted.
*
* Example Input :{4,1,5} X : 451
*
* Output : 4
*
* (145,154,415,451,514,541). 451 comes at 4th position
*
* @author Juanyong
*
*/
public class NumberDictionary2 {
public static void main(String[] args) {
NumberDictionary2 nd2 = new NumberDictionary2();
nd2.permutations(new Integer[] { 4, 1, 5 }, 0);
Object find = 451;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.addAll(nd2.unique);
Object[] ary = nd2.unique.toArray();
Arrays.sort(ary);
System.out.println(Arrays.toString(ary));
System.out.println(ArrayUtils.indexOf(ary, find)+1+"th");
}
Set<Integer> unique = new HashSet<Integer>();
private void permutations(Integer[] args, int start) {
// System.out.println(Arrays.toString(args));
for (int i = start; i < args.length; i++) {
for (int j = i; j < args.length; j++) {
if (i != j) {
swap(args, i, j);
System.out.println(Arrays.toString(args));
unique.add(sum(args));
permutations(args, start + 1);
swap(args, j, i);
}
}
}
}
private Integer sum(Integer[] args) {
String value = "";
for (Integer digi : args) {
value += digi;
}
return Integer.valueOf(value);
}
private static void swap(Integer[] args, int i, int j) {
if (i == j)
return;
Integer tmp = args[i];
args[i] = args[j];
args[j] = tmp;
}
}
this is more mathematical problem then coding prob.The main concept is
1)At any position u have to figure out how many smaller no is present in the left of current position,it mean u have to go for that many permutation first to reach that particular position.
2) perform this check for all the position any for every position find the permutation and add to other location.run this for all the position then ur desire rank is sum of all permutation +1.
public static void main(String[] args) {
int[] newArr = new int[]{4, 1, 5};
int X = 451;
System.out.println(findRank(newArr, X));
}
public static int findRank(int[] numDic, int X) {
//Sort the dictionary
Arrays.sort(numDic);
//Start computing words until you hit X, then stop
int inputLength = numDic.length;
boolean[] used = new boolean[inputLength];
StringBuffer outputString = new StringBuffer();
char[] inChars = creatingStringFromIntArr(numDic);
ArrayList<String> foundWords = new ArrayList<String>();
getPermutations(inChars, outputString, used, inputLength, X, foundWords, 0);
//Position of x is length of ArrayList
return foundWords.size();
}
private static char[] creatingStringFromIntArr(int[] intArr) {
char[] newChars = new char[intArr.length];
for (int i=0; i<intArr.length; i++) {
newChars[i] = Character.forDigit(intArr[i], 10);
}
return newChars;
}
private static boolean foundWord;
private static void getPermutations(char[] inChars, StringBuffer outputString,
boolean[] used, int inputLength, int x, ArrayList<String> foundWords, int level) {
if (level == inputLength) {
foundWords.add(outputString.toString());
if (outputString.toString().equals(Integer.toString(x))) foundWord = true;
return;
}
for (int i=0; i<inputLength; i++) {
if (used[i]) continue;
if (outputString.equals(x)) return;
outputString.append(inChars[i]);
used[i] = true;
getPermutations(inChars, outputString, used, inputLength, x, foundWords, level + 1);
if (foundWord) return;
used[i] = false;
outputString.setLength(outputString.length() - 1);
}
}
The idea would be to
1. Generate all the permutations of the array element
2. Sort the generated permutations
3. Search in the sorted list for the index
To generate all possible permutations of the array elements
1. Usually string can be easily sub stringed and manipulated so generate a single string of all the elements of the array.
2. So in this case, the output string for array element would become "415".
Now permutations of the string can be generated as follows
3. If String has single character say 4 and you add 1 additional character to it say 1, it can go before 4 and after 4. So the result would be 14 and 41
4. Now if we add last character 5 to it, 5 can go in every position (First, middle and last) in the existing string like 514, 154 and 145.
5. Same would go with string 41. When we add 5 to it, 5 can go in every possible position, 541, 451 and 415.
Here is the code in java for the same
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class AllCombinationOfArrayElements {
private static int[] input = { 4, 1, 5 };
public static void main(String[] args) {
String searchString = "451";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < input.length; i++) {
sb.append(input[i]);
}
List<String> list = permutations(sb.toString());
//Sort output List
Collections.sort(list);
System.out.println("Sorted permutation = " + list);
//Binary Search in the list
int zeroIndex = Collections.binarySearch(list, searchString);
System.out.println("Index of " + searchString + " in the generated permutation is = " + ++zeroIndex);
}
//Generate the permutation of the array elements
private static List<String> permutations(String input) {
ArrayList<String> inputList = new ArrayList<String> ();
if (input.length() == 1) {
inputList.add(input);
return inputList;
}
List<String> result = permutations(input.substring(0, input.length() - 1));
ArrayList<String> updatedResult = new ArrayList<String>();
for (int i = 0; i < result.size(); i++) {
String currentString = (String) result.get(i);
//Add last character at the start
updatedResult.add(input.charAt(input.length() - 1) + currentString);
//Add last character in the middle
for (int j = 1; j < currentString.length(); j++) {
updatedResult.add(currentString.substring(0, j)
+ input.charAt(input.length() - 1)
+ currentString.substring(j, currentString.length()));
}
//Add last character at the end
updatedResult.add(currentString + input.charAt(input.length() - 1));
}
return updatedResult;
}
}
Ouput of this program:
Sorted permutation = [145, 154, 415, 451, 514, 541]
Index of 451 in the generated permutation is = 4
lets do it efficiently.
Input :{4,1,5}
X = 451.
Lets rank=1
If we want to fix 4 at position 0 then we need to increase the rank by number of permutations of {4, 1, 5} starting with an element less than 4. We have only 1 such element i.e. {1}. With 1 at position 0 we can have 2! permutations.
so, rank += 1X2! = 1+2 = 3
Let's fix 4 at position 0 and move our focus to position 1 with remaining elements {1, 5}. In order to fix 5 at position one we need to increase rank by number of permutations of {1, 5} starting with an element less than 5. Again {1} is such an element. With 4 fixed at position 0 and 1 at position 1 we have 1! permutations.
so, rank += 1X1! = 3+1 = 4
Lets fix 5 at position 1 and focus on position 2 with remaining elements {1}. In order to fix 1 in position 3 we need to increase rank by number of permutations starting with less than 1. We have no such element. So, with 45 fixed at first two positions and 1 at position 3 we have : 0! permutations
so, rank+=0X0! = 4+0 = 4.
Complexity of this algorithm is O(nlgn)
- zahidbuet106 May 18, 2014