Amazon interview questions

  1. 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.
  2. What are the 4 basics of OOP?
  3. Define Data Abstraction. What is its importance?
  4. 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.
  5. Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.
  6. Given a string,find the first un-repeated character in it? Give some test cases
  7. 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.)
  8. 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.
  9. What is a C array and illustrate the how is it different from a list.
  10. What is the time and space complexities of merge sort and when is it preferred over quick sort?
  11. 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.
  12. 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.
  13. 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.
  14. Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.
  15. How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same
  16. Explain polymorphism. Provide an example.
  17. 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)
  18. 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?
  19. 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.
This entry was posted in C++, Database, General. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

12 Comments on Amazon interview questions

  1. ram
    Posted 6/18/2008 at 5:31 am | Permalink

    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)

  2. 1818merong
    Posted 6/22/2008 at 7:57 pm | Permalink

    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;

  3. NA
    Posted 7/4/2008 at 4:15 pm | Permalink

    Hi 1818merong, your solution only works if there is only 1 missing number. However, the questions is asking for missing number(s).

  4. Vishesh Garg
    Posted 7/10/2008 at 6:37 am | Permalink

    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*/

  5. Abyss
    Posted 7/19/2008 at 12:04 pm | Permalink

    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.

  6. Posted 8/11/2008 at 1:39 pm | Permalink

    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.

  7. Anon
    Posted 8/11/2008 at 1:49 pm | Permalink

    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.

  8. shiva
    Posted 10/20/2008 at 9:43 am | Permalink

    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 ;
    }

  9. Jason Wei
    Posted 1/24/2009 at 8:33 pm | Permalink

    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.

  10. Jason Wei
    Posted 1/25/2009 at 2:02 am | Permalink

    just kidding my answer to 17 isn’t correct

  11. Satya
    Posted 2/6/2009 at 8:31 pm | Permalink

    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;
    }

  12. Satya
    Posted 2/6/2009 at 8:33 pm | Permalink

    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.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*