Sunday, January 19, 2014

Amazon Questions - Set 1

  1. Write code to find Nth last node in a linked list. Solution
  2. Given a binary tree build a vertical sum array.    Solution
  3. Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution
  4. Given two lists of strings return a list of strings that is an intersection of both of the lists.
    Analyze running time and space complexity.
    Give Test Case scenarios.
  5. There is n node graph, each node having only one root. All nodes are labeled in a random order from int 0 to n-1. The graph is represented in a array format such that the value in the array at index equal to child node label is root node label.
    For root assume the value is -1.
    4   1     2
       0 5
    the array is
    value : 1, 3, 3, -1, 3, 1
    Index : 0, 1, 2, 3, 4, 5
    Find the height of graph. careercup
  6. Given a node in a binary tree, how will you find out if left and right subtrees are mirror images of each other?  Solution
  7. Given a binary tree and a number N, print all paths that start from root and add up to N.
  8. Find the biggest BST in a given binary tree.
  9. Given an array A, build another array B in which each element is the product of all elements in A other than the element at the same position. Write code that does this with and without division.
  10. Find the position of first ’1′ in a sorted array that contains only 0-s and 1-s.
  11. In a dial pad(similar to phone dial pad) where if 2 corresponds to ‘abc’ and 3 corresponds to ‘def’ etc. Write a program to form all possible and meaningful words for the given number.
    if 2 is pressed possible words are a,b,c. But ‘a’ is only meaningful word. Hence print ‘a’ and
    if 23 is pressed. The possible words are going to be ad,ae,af,bd,be,bf,cd,ce,cf there is no meaningful word.So,dont print anything.
  12. Given a binary tree which is huge and can not be placed in memory, how do you check if the tree is a mirror image.
  13. Given a book containing 100′s of words., If a word is repeated, delete it. Process such that there are no repetitive words.
  14.  Given coins of denomination 4, 5 and 7. How can you make up 13 ?
  15. Given a program on fork() system call.
    #include <stdio .h>
    #include <unistd .h>
    int main()
       fork() && fork() || fork();
       fork(); printf(“forked\n”);
       return 0;

    How many processes will be spawned after executing the above program?
  16. Do in-order traversal of tree without using recursion .
  17. 1. There is a web URL which contains %20 in place of space, how will your replace every %20 with space3. Let’s say, on the file there are only 5% URL which contains this %20, how will your replace with space in most efficient way?
  18. Longest Palindrome in a input string
  19. How do you find million smallest numbers from a file that contains billions of numbers ?
  20. Given a binary tree, every node has a int value, return the root node of subtree with the largest sum up value. Java is more preferable. Caution: the return should be a node, not a integer!
  21. Let’s say you have a simple function (fibonacci/factorial) that you need to run constantly. The largest number that you will receive as input will be 1,000. How can you improve the performance of this function call?I said not use recursion and cache the results using a data structure (i.e. a Map)
    What else could you do to improve the performance?
  22. Given an array of integers, find second largest element in an array.
  23. Write a function convert a string to an integer. example convert String “1750″ to int 1750. Using Java, not allow use the default function ..
  24. Write a function convert a integer from 0 to 1000 to Roman numerals.
    1: I 5: V 10: X 50: L 100: C 500: D 1000: M
    Test Cases:
    XI 11, IX 9, XXX 30, DC 600, CM 900, XCVIII 98
  25. Given an array. Find pairs of numbers that add up to a given value ‘x’. with time complexity less than O(n2) and use no additional space.
  26. Write Code: Find an integer array’s maximum value. Trace code. Use Try/catch instead of return.
  27. Given a spreadhseet, what data structure you will use to store it. What will you use for dynamic updation of of Spreadsheet formulas.
  28. Count number of set bits in an Integer
  29. Find first unique character in an array.
  30. Given 2 Arrays A and B, find the intersection of two arrays. Initially without using any other data structure. Later with using additional data structure.
  31. Given a 2D array, all rows and all columns sorted. Find an integer x from the 2D array.
  32. How do you find million smallest numbers from a file that contains billions of numbers ?
  33. Convert a sorted doubly linked list to a BST while trying to keep BST as balanced as possible
  34. i got this as an interview question. i was given 2 linked lists of unequal lengths,containing a single digited number in each of their nodes. i was asked to build a 3rd linked list which contains the sum of the two linked lists, again in the form of 1 digit in a node. ex: linked list 1 is 4-7-9-6 linked list 2 is 5-7 then the 3rd linked list would be 4-8-5-3 can someone suggest me Java answer.
  35. Given a string “This is an example” –> Output: “This is an example” There should be equal number of spaces between words.
  36. each of 100 students in a school has a unique ranking 1-100. I will select 50 students randomly .
    Of the 50 randomly selected student i will select a boy, say ranking 40, and wish to know his relative ranking among the 50 students selected. How do you do this efficiently?
  37. What data structure you will use if you have to implement google map like utility, you will be able to search the city, you will be able to find shortest path between two nodes. And you have to implement one more feature of auto suggestion which means if user type “Na” then you should show all the cities starting with letter Na in a list. And algo should be very efficient because it should update things as soon as user changes the typed character.
  38. Given two nodes of a tree, find the first common ancestor of these node.
  39. How to store a binary tree in a file so that we can re construct the same tree with that file ..
  40. Algorithm to check a linked list is palindrome or not, each node contains a single character.
  41. Find the successor of a node in inorder traversal.
  42. print all possible combination of given n parentheses. Eg: if n=2 then all possible combinations are: (n stands for number of parentheses pair open-close)
  43. Given an array of N integers with +ve & -ve numbers. Find the maxproduct of 3 numbers ? & Test Cases
  44. Given an n-by-n matrix of 0′s and 1′s where all 1′s in each row come before all 0′s, find the most efficient way to return the row with the maximum number of 0′s.
  45. Write Program to find longest common contiguous intersection from 2 lists provided to the function.
    Example: list1: abcrfghwetf
    list2: abrfghwwetxyab
  46. Construct a Cartesian tree from in order traversal  ..
  47. Find if two rectangles overlap in cartesian space..
  48. Given an expression tree how do you evaluate it and also how do you evaluate for n-ary operators …
  49. The root node in the tree is equal to sum of its all descendants and the leafs are assigned value 0, so if your tree is something like 1020 30 40 50
    output will be
    0 90
    0 0
  50. Given n points in 2D space find k points nearest to origin..
  51. Print a binary tree in level by level in Zig-Zag manner …
  52. Given a binary tree return the new binary of given depth.
    0 – 3 — Should return full binary tree from root to height 33 – 4 — Should return full binary tree from height 3 to 4
  53. IMP—-Write a method to create new tree with same structure but the values of each node will be sum of their descendents (sub tree). The leaf nodes will become 0. So if the tree is 50 30 10 40 60 55 75 (PreOrder) then new tree should be 270 50 0 0 130 0 0(PreOrder)…
  54. write a function which takes a string S and a pattern string P and an integer i , and returns the i’th occurrence of P in S.
    example S = “abcabcefgabc ” , P = “abc” , i =3 , ..returns 10 …
  55. given an array A which has only 0′s and 1′s in sorted order , find the occurrence of first ’1′ in A.
    example : A [] = 00001111 , returns 5
  56. Convert a BST to sorted doubly linked list.
  57. implement “fill with paint” function which fill the screen(2d array) with respect to a given point and color,fill until border of screen or same color is met.
  58. You are given a linked list. Apart from the normal “Next” pointer, there is one more pointer(random ptr) in each node which points to some random node of the list. How will you create a clone of such a list? (In less than O(n^2))
  59. Write a function to convert an IPv4 Address in string format to an unsigned integer
  60. Given a set of unique numbers from 1 to 1000, propose a data structure that allows you to perform the following operations in constant time.
    1- Insertion,
    2- Deletion,
    3- Searching,
    4- Get any random numbe    
  61. Given a String – aaaabbbbcc, convert the given string in to a4b4c2 without using extra memory. ( Note that every character appears more than once in input string and the repeated characters are contiguous)
  62. Search an element in a 3-D sorted array without modifying the given array.
  63. Write a program to calculate the number of occurances of letters(chars) in a string. Eg:”Test”.
  64. Print nodes at k distance from root..
  65. Given references to roots of two binary trees, how do you short circuit determine whether the sequences of the leaf elements of both the trees are same ? The structure of two BTs may be different. Short circuit : for ex. If the very first leaf element of each tree is different, the algorithm should stop immediately returning false instead of checking all the leaf elements of both trees.
  66. Given two nodes of a BST and all elements in BST are distinct, write code to determine the shortest distance between the two nodes. (unit distance between two adjacent nodes). Nodes dont have parent pointer.
  67. Given an array, subarray size k and a number ssum, find the number of subarrays of size k that sum up to ssum.
  68. one unsorted array is given.Find out the index i and j ,j> i for which a[j] – a[i] is maximum.perform in linear time complexity
  69. Why data members are private when we can access them through getter/setters?. Why can’t we just make them public.[ How will you convince the interviewer]
  70. Given two linked lists. Find their intersection point.
  71. Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space ..
  72. Find the number of nodes in a singly link list, it can be both cyclic and acyclic..
  73. you have given 2n+1 numbers in which 2n numbers are repeated means every number is having duplicate value.find that non repeating number in constant space and o(n) time.i told him using XOR.
    then he gave me 2n+2 numbers in which 2n numbers are repeating like above now you have 2 different number.find both number in constant space and o(n) time.(f2f 4th round)
  74. Write function compress(char* strSource)
    it should do the following .
    repeating chars in sequence should be replaced with char & count, in case count is 1 no need to add any integer.
    should be A4B3CXYZE4P5K2ABC.
    you are supposed to iterate the array only once, and modify the same input parameter, do not create any new string.
  75. You have given two polynomials .. You have to choose a data structure which will be used for addition of both polynomials :-
    Condition :-
    polynomials are very huge ..(n is very big)
    a + bx +cx2 +…… +nxn ..
    c + dx +ex2+…… +nxn ..
    you have to store the polynomial after sum .
  76. Get the top 3 frequently used words in a book. The book contents are given as a single text file.
    I used hashmap solution. The interviewer said its not optimal. Use a combination of two or three data struct.
  77. You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.
  78. Given a robot and a Maze in a game. Following our few of the primitives:
    bool IsMazeExit();
    bool Forward();
    void RightTurn();
    Every room in the maze is a square. Each room has 2 doors. Robot can call IsExitMaze() when in a room and identify the exit. Forward moves the Robot forward few steps and if it finds a wall it returns to its position. Right turn turns the robot right 90 degrees.
    Write a method to find the exit
  79. Given numbers 1 to 1000, suggest a data structure to store them such that following operations can be executed in constant time:
    1- insertion,
    2- deletion,
    3- searching,
    4- get_any_number (means return any number if present in the data-structure otherwise return -1).
  80. Given a root and a node of a BST tree, write a function which print all the nodes which are a ‘k’ distance from the given nodes in sorted order. (distance can be upwards and downwards) [Hints -Recursion]
  81. In given array of elements like [a1,a2,a3,,b1,b2,b3,,c1,c2,c3,] Write a program to merge them like [a1,b1,c1,a2,b2,c2,,bn,cn]. We have to do it in O(1) extra space. [Hints- D&C or swapping]
  82. You are given a linked list which has the following structureCode:
    linkedList {
    *nextLink will always point to next node in the linked list
    *randomLink will point to any random node node it the list (or NULL)Now given a list L write an algorithm to create replica of the list( say L’) in O(n) time and O(n) space. [Hints- Need Double Pass/Hashing]
  83. How to build a heap from inoder traversal ?
  84. Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it’s parameter. Every node has an extra pointer “next” , which is intialized to null, fill next with node pointers which represent Inorder Successor. [Hints -Recursion/Stack/DP]
  85. An array contain +ve and -ve element, find the longest contiguous sub array whose sum is 0
  86. Given a matrix pxq, You start from top left and have to reach the bottom right. Can only traverse right or bottom. How many ways are there to reach at the bottom right?. So If I allow all 4 way move is possible what will be the ans ? . What happened if i make some Restricted Move ?
  87. Given A Binary Tree of size n , Find Out a Matrix M[n][n], where M[i][j]=1 if i is predecessor of j, else M[i][j]=0. [Hints DP]
  88. How you implemnt a Priority Queue using Heap.
  89. Given a Cache of n String Having length of k each, on Alphabet ALPHA where |ALPHA|=t, Find out number of 2k-length string constructable from the cache, where all sub-string of Resultant sub-string are also in cache ? What Data-structure should you use to Lookup cache? Design an Algorithm to find the count Efficiently? Calculate the Time/Space complexity of the technique. [Hints -Tries ]
  90. Given a Cache of k-length Strings of size n,. Given a String X, We can to convert to another String Y using the following two Rules:
    R1:you can change only one character at a Time in stepwise Transformation
    R2: All intermediate String in the transformation must be also in cache.Cache has also an API : Called Is_Transformable(X,Y) return Ture if it is possible to transform X to Y, without violating the Above rule. Assume that Cache is fixed size and there is a sequence of Query of Checking the possibility of Transformation is coming to The API of Cache.
    the Question is : What Data-Structure U can use to implement Cache ? It might need some Initial Complexity to Organize the data , for efficient lookup, and provide service to APIs.
    How can u implement the API in O(1).
    Suppose we add one more API which calculate minimum number of Steps required to transform X to Y, How do u solve this problem in O(1).
  91. Suppose, Amazon have a Logging system Like This:They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
    In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days. We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
    Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.
    {Hints:- Double Hashing/ {Hashing +Tries/BST }}
  92. Find the character that has maximum frequency in an array of characters. If n is small and dealing with unicode char-space, extra space for hashtable is overhead, can you avoid?
  93. placed two robots and a sensor on the line, write code that will be executed on both machines and make them meet.
  94. String represented as as singly Linked list with one letter on each Node. Need to check whether it is a paliandrome or not. Can use only one String variable other than the Linkedlist
  95. Given the number, find the immediate next (larger) palindrome
  96. Find the nth non-repeating number given a streams of characters in the range of A-Z  ..
  97. What is the complexity of an algorithm to check whether a binary tree is symetric or not. No need to check the data only the structure needs to be verified.
  98. Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray.
    For e.g.
    Array: 2,2,13,4,7,3,8,12,9,1,5
    Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1]
    Could this be done with a complexity better than O(n^3)
  99. given a linked list of objects.Print the objects in reverse order. I gave a recursive solution as well the normal one.
    But he wanted a solution where no recursion is used and no manipulation of any pointers in linked list.
    You can use any algorithm…any space and any time complexity…but remember linked list is dynamic.
    Could not answer this q
  100. compare two strings arrays and return intersection elements in a string array without using 2 for loops?
  101. GIven a binary tree, print the tree according to the level.
    proceed further to find the mirror image of alternate level
  102. given a million integers find the largest k elements
  103. find common ancestor of 2 nodes in
    1. binary tree
    2. binary search tree No parent pointer is given.
  104. Given number n, return true if n is prime otherwise false.
  105. write a function strRemove(char *source, char *remove )
    This function will delete all the chars that exist in string remove from array source, number of iteration should be only 1. Make the searching efficient.
    (“amazon development center”, “aenr”)
    “mzo dvlpmt ct”.
    Criteria – First parameter should be modified , no need to create an extra string.
    (Answer – Put the second array in a hash table, like array of 256 chars, to search which are the chars needed to be removed with complexity o(1) )
  106. you have two BST , they contain the same amount of elements “N” but there structure is different. how will you cross check that the trees are identical with complexity O(N). Also how will you do the same in case its only Binary tree and not a Binary search tree.
  107. Write code to traverse a binary tree and save all the elements found in a sorted order in double link list.
  108. You have a table which contains huge data may be crores of records and a cache which can contain only 1000 records. Query is done on the basis of some unique ID. When any query happens data should be copied to the cache, but the records which are used least amount of time should be removed and should be occupied with newly added records from table.
    Cache should provide two mechanism , search for record(s) on the basis of a unique id & remove the records which used least amount of time. Cache can contain max 1000 records, and record should be available in cache even after your query is done. So records in cache is refreshed only when new query is done and new record arrives which do not exist in the cache.
  109. You are given a paragraph , which contain n number of words, you are given m threads. What you need to do is , each thread should print one word and give the control to next thread … this way each thread will keep on printing one word , in case last thread come, it iwill invoke the first thread … procedure will repeat until all the words are printed in paragraph. Finally all the thread should exit gracefully. What kind of synchronization will use ? Answer only the logic to implement (not complete code)
  110. you have 100 elements from 1 to 100 but my mistake one of those number overlapped another by repeating itself.
    Ex. in 1—-98,99,100 …. 99 overwrite 2 , so the array becomes … 1,99,3,4,—-99,100 .. Array is not in sorted format , how to find the repeating number ?
  111. Right a program which will perform the following task ->
    In a binary tree , if a root is greater then the sum of two child nodes , then the new value of same root will be sum of child nodes , else the right // left child should reinit to such a value, so that the sum of the child nodes will be equal to the value of root node.
    (I asked him the answer , he told u need to do manipulation twice, 1) while parsing the nodes 2)while unwinding i.e. again recheck the values.
  112. how would you design a rate limiter in a client to control the number of transactions it requests the server.
  113. How do you check if an entered text in a textbox is a student email address (ends with edu). special case should be rejected
  114. Write code for the following problem:
    find the element in the array that appears consecutively in the array max number of times. Should be O(N)
    eg. 1113333244111 ans. 3
  115. Given pre order traversal of a tree. It has only 2 type of nodes, N & L (non-leaf, leaf).. Also, every node either has zero or two children.
    Produce the tree. Eg: Pre-order NNLLL
    / \
    N L
    / \
    L L
  116. You have the post order traversal of a tree. produce the tree.
    If not, what other info you need?
    Ok you have that info, now produce the tree.
    Write code
  117. Given a Singly Linked lists, write the function that takes as arguments the head of list and a number and then deletes all the nodes with that number.
  118. Given a binary search tree, first find the least common ancestor of two numbers and then generalize it for m numbers.
  119. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time
  120. There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.
  121. For an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.
  122. How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array..
  123. Till Page 7 So far in careercup..Target—till page 20



Post a Comment