Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can’t pass the value k to any function also.
What are the 4 basics of OOP?
Define Data Abstraction. What is its importance?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.
Given a string,find the first un-repeated character in it? Give some test cases
You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
Given a cube of size n*n*n (i.e made up of n^3 smaller cubes), find the number of smaller cubes on the surface. Extend this to k-dimension.
What is a C array and illustrate the how is it different from a list.
What is the time and space complexities of merge sort and when is it preferred over quick sort?
Write a function which takes as parameters one regular expression(only ? and * are the special characters) and a string and returns whether the string matched the regular expression.
Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that.
Find the second largest element in an array with minimum no of comparisons and give the minimum no of comparisons needed on an array of size N to do the same.
Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
Explain polymorphism. Provide an example.
Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?
Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.
Q Given n red balls and m blue balls and some containers..
A lets say you have ‘x’ containers
put 1 red ball in ‘x -1′ containers, and the rest with the ‘m’ blue balls.
There probability of selecting a red ball in this case is :1-(1/x)*(n-x-1/m)
For the same Q of finding missing nos. in array of size n a possible soln is
input[n]
int output[n];
for(int i=0;i<n;i++)
output[input[i]]++;
for(int i=0;i<n;i++)
if(output[i]==0)
printf(”%d”,i);
/* The printed numbers will be the missing nos*/
hi 1818meron.. As NA says you solution would work only for 1 missing number and also only if the numbers in that range occured exactly once . But in the original question it is mentioned atleast once so garg sol should work fine.
Q. You’re given a dictionary of all valid words. You are allowed to perform 3 operations on a word i.e insert a char,delete a char and replace a char with another. Find the min no. of operations it takes to convert 1 word to another.
A: Its simply a breadth-first-search on a graph with the words as nodes. This can be done by declaring a n*n array for a n word dictionary and if there is an operation which converts word i to word j then array[i][j] = 1 otherwise 0. Determining whether a word is related to another is simply a matter of parsing both words : if both are of equal length and differ by only 1 char or if 1 is longer than the other and both have the same prefix and suffix save 1 char then the words are interconvertible.
Q. Given a string, find its first non-repeating character.
A: Declare an array of flags initialized to 0 for the 128 chars and increment each flag when the corresponding char is parsed in the string. If the corresponding flag is still 0 when a char is parsed then mark the pos of the char (which would be its first occurence in the string) in a separate table. Now search the table for an entry whose flag value is 1 and the first occurence is minimal i.e the leftmost char of the non-repeating chars.
17. Since they are all positive integers and you cannot add two adjacent ones, all you need to do is compare two values: one that is the sum of all of the even indexed integers (assuming that the array index starts at 0) and then the sum of all of the odd indexed integers (so starting from index 1 of the array). Whichever one is larger gives you the maximum.
18. Can you use a combination of the greedy algorithm and recursion? For example, you are given the total sum of the coins, and since you want to minimize the number of coins used, subtract from the total the largest denomination amongst the coins and call that function with this new value. Continuing this, whenever the result upon subtracting the value of the largest denomination is negative, then return to the previous stack and instead subtract the denomination of the second largest. If it is still negative continue to subtract decreasing sized denominations, either until the difference is exactly 0 or until we saturate all of the possible denominations, in which case we return to the previous stack and etc.
Iterate over all chars in the string. For each iteration copy the character to a temp array. If the character already exists in the temp array, move the characters in the temp array so that they overwrite the current char in it. If we reach the end of the string, the first character in the temp array is the first un repeated character.
12 Comments on Amazon interview questions
Q Given n red balls and m blue balls and some containers..
A lets say you have ‘x’ containers
put 1 red ball in ‘x -1′ containers, and the rest with the ‘m’ blue balls.
There probability of selecting a red ball in this case is :1-(1/x)*(n-x-1/m)
Q. Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.
A. Input array[n]
int sum = n * (n + 1) /2;
int answer;
for(i=0; i<n; i++)
sum -= array[i];
answer = sum;
Hi 1818merong, your solution only works if there is only 1 missing number. However, the questions is asking for missing number(s).
For the same Q of finding missing nos. in array of size n a possible soln is
input[n]
int output[n];
for(int i=0;i<n;i++)
output[input[i]]++;
for(int i=0;i<n;i++)
if(output[i]==0)
printf(”%d”,i);
/* The printed numbers will be the missing nos*/
hi 1818meron.. As NA says you solution would work only for 1 missing number and also only if the numbers in that range occured exactly once . But in the original question it is mentioned atleast once so garg sol should work fine.
Q. You’re given a dictionary of all valid words. You are allowed to perform 3 operations on a word i.e insert a char,delete a char and replace a char with another. Find the min no. of operations it takes to convert 1 word to another.
A: Its simply a breadth-first-search on a graph with the words as nodes. This can be done by declaring a n*n array for a n word dictionary and if there is an operation which converts word i to word j then array[i][j] = 1 otherwise 0. Determining whether a word is related to another is simply a matter of parsing both words : if both are of equal length and differ by only 1 char or if 1 is longer than the other and both have the same prefix and suffix save 1 char then the words are interconvertible.
Q. Given a string, find its first non-repeating character.
A: Declare an array of flags initialized to 0 for the 128 chars and increment each flag when the corresponding char is parsed in the string. If the corresponding flag is still 0 when a char is parsed then mark the pos of the char (which would be its first occurence in the string) in a separate table. Now search the table for an entry whose flag value is 1 and the first occurence is minimal i.e the leftmost char of the non-repeating chars.
Q How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
A: Pass the Number and base to the function below. It would print the value in the Base mentioned(works with bases 2, 8, 10, 16)
void dec_bin1(int number, int base)
{
int value = 0;
char szPrintChar = ‘A’;
if(number >= base)
{
value = number % base;
number = number / base;
dec_bin1(number, base);
if(base== 16 && value > 9)
printf(”%c”, szPrintChar + value - 10);
else
printf(”%d”, value);
}
else
{
if(base == 16 && number > 9)
printf(”%c”, szPrintChar + value - 10);
else
printf(”%d”, number);
}
return ;
}
17. Since they are all positive integers and you cannot add two adjacent ones, all you need to do is compare two values: one that is the sum of all of the even indexed integers (assuming that the array index starts at 0) and then the sum of all of the odd indexed integers (so starting from index 1 of the array). Whichever one is larger gives you the maximum.
18. Can you use a combination of the greedy algorithm and recursion? For example, you are given the total sum of the coins, and since you want to minimize the number of coins used, subtract from the total the largest denomination amongst the coins and call that function with this new value. Continuing this, whenever the result upon subtracting the value of the largest denomination is negative, then return to the previous stack and instead subtract the denomination of the second largest. If it is still negative continue to subtract decreasing sized denominations, either until the difference is exactly 0 or until we saturate all of the possible denominations, in which case we return to the previous stack and etc.
just kidding my answer to 17 isn’t correct
Convert decimal to hexadecimal.
void converttohex(int num) {
char hexstring[100];
char tmp[100];
int x,y;
x = num;
while (x >= 16) {
y = x % 16;
if (y >=10 && y <=15) {
sprintf(tmp, “%c”, ‘A’ + (y % 10));
strcat(hexstring, tmp);
} else if (y < 10) {
sprintf(tmp, “%d”, y);
strcat (hexstring, tmp);
}
x = x / 16;
printf(”x=%d\n”, x);
}
sprintf(tmp, “%d”, x);
strcat(hexstring, tmp);
printf(”%s\n”, (hexstring));
reverse(hexstring);
printf(”%s\n”, hexstring);
}
void reverse(char *str) {
int i = 0;
char *tmpstr = str;
int len = strlen(str) - 1;
while (i < len) {
swap(&tmpstr[i], &tmpstr[len]);
i++; len–;
}
}
void swap(char *str1, char *str2) {
char tmp;
tmp = *str1;
*str1 = *str2;
*str2 = tmp;
}
first un repeated char in a string:
Iterate over all chars in the string. For each iteration copy the character to a temp array. If the character already exists in the temp array, move the characters in the temp array so that they overwrite the current char in it. If we reach the end of the string, the first character in the temp array is the first un repeated character.