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.
   Ex.

       3
   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.   http://www.careercup.com/question?id=13000680
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.
    Example:
    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 ?   http://puddleofriddles.blogspot.com/2012/03/you-are-given-n-types-of-coin.html
15. Given a program on fork() system call.
    

    #include <stdio .h>
    #include <unistd .h>
    int main()
    {
       fork();
       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 .  http://stackoverflow.com/questions/5502916/please-explain-morris-inorder-tree-traversal-without-using-stacks-or-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?       http://www.careercup.com/question?id=13032664
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!http://www.careercup.com/question?id=12868663
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?    http://www.careercup.com/question?id=12903663
22. Given an array of integers, find second largest element in an array.  http://www.careercup.com/question?id=12897677
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 ..http://www.careercup.com/question?id=12903687
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         http://www.careercup.com/question?id=12940668
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. http://www.careercup.com/question?id=12887674
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.  http://www.careercup.com/question?id=12960668
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.  http://www.careercup.com/question?id=12975663
31. Given a 2D array, all rows and all columns sorted. Find an integer x from the 2D array.  http://www.careercup.com/question?id=12977662
32. How do you find million smallest numbers from a file that contains billions of numbers ? http://www.careercup.com/question?id=13018675
33. Convert a sorted doubly linked list to a BST while trying to keep BST as balanced as possible   http://www.careercup.com/question?id=12778667
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.   http://www.careercup.com/question?id=12743681
35. Given a string “This is an example” –> Output: “This is an example” There should be equal number of spaces between words.  http://www.careercup.com/question?id=12781696
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? http://www.careercup.com/question?id=12765663
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.  http://www.careercup.com/question?id=12809665
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 ..http://www.careercup.com/question?id=12805664
40. Algorithm to check a linked list is palindrome or not, each node contains a single character. http://www.careercup.com/question?id=12804667
41. Find the successor of a node in inorder traversal. http://www.careercup.com/question?id=1280566
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)
    {}{}
    {{}}   http://www.careercup.com/question?id=12806664
43. Given an array of N integers with +ve & -ve numbers. Find the maxproduct of 3 numbers ? & Test Cases   http://www.careercup.com/question?id=12806693
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.  http://www.careercup.com/question?id=12849666
45. Write Program to find longest common contiguous intersection from 2 lists provided to the function.
    Example: list1: abcrfghwetf
    list2: abrfghwwetxyab   http://www.careercup.com/question?id=12862670
46. Construct a Cartesian tree from in order traversal  ..http://www.careercup.com/question?id=12715683
47. Find if two rectangles overlap in cartesian space..http://www.careercup.com/question?id=12719693
48. Given an expression tree how do you evaluate it and also how do you evaluate for n-ary operators …http://www.careercup.com/question?id=12714690
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
    140
    0 90
    0 0    http://www.careercup.com/question?id=12691679
50. Given n points in 2D space find k points nearest to origin..http://www.careercup.com/question?id=12691685
51. Print a binary tree in level by level in Zig-Zag manner …http://www.careercup.com/question?id=12688694
52. Given a binary tree return the new binary of given depth.
    Example:
    0 – 3 — Should return full binary tree from root to height 33 – 4 — Should return full binary tree from height 3 to 4   http://www.careercup.com/question?id=12642713
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)…http://www.careercup.com/question?id=12746661
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 …http://www.careercup.com/question?id=12782664
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    http://www.careercup.com/question?id=12779666
56. Convert a BST to sorted doubly linked list.     http://www.careercup.com/question?id=12778666
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.   http://www.careercup.com/question?id=12572675
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))   http://www.careercup.com/question?id=12590664
59. Write a function to convert an IPv4 Address in string format to an unsigned integer http://www.careercup.com/question?id=12651670
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              http://www.careercup.com/question?id=12650665
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)    http://www.careercup.com/question?id=12663669
62. Search an element in a 3-D sorted array without modifying the given array.   http://www.careercup.com/question?id=12666670
63. Write a program to calculate the number of occurances of letters(chars) in a string. Eg:”Test”.  http://www.careercup.com/question?id=12666683
64. Print nodes at k distance from root..http://www.geeksforgeeks.org/archives/8615
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.  http://www.careercup.com/question?id=12698674
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.http://www.careercup.com/question?id=12696671
67. Given an array, subarray size k and a number ssum, find the number of subarrays of size k that sum up to ssum. http://www.careercup.com/question?id=12697675
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 http://www.careercup.com/question?id=12705676
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] http://www.careercup.com/question?id=12705691
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 ..http://www.careercup.com/question?id=12711674
72. Find the number of nodes in a singly link list, it can be both cyclic and acyclic..http://www.careercup.com/question?id=12631663
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)   http://www.careercup.com/question?id=12570669
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.
    Example – AAAABBBCXYZEEEEPPPPPKKABC
    should be A4B3CXYZE4P5K2ABC.
    you are supposed to iterate the array only once, and modify the same input parameter, do not create any new string.   http://www.careercup.com/question?id=12514668
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 .  http://www.careercup.com/question?id=12514670
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.   http://www.careercup.com/question?id=12391700
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.  http://www.careercup.com/question?id=12527666
78. Given a robot and a Maze in a game. Following our few of the primitives:
    bool IsMazeExit();
    bool Forward();
    void RightTurn();
    Constraints:
    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  http://www.careercup.com/question?id=12549691
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).   http://www.careercup.com/question?id=12559669
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]  http://www.careercup.com/question?id=12533682
81. In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space. [Hints- D&C or swapping]  http://www.careercup.com/question?id=12549702
82. You are given a linked list which has the following structureCode:

    linkedList {
    data
    *nextLink
    *randomLink

    }
    *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]  http://www.careercup.com/question?id=12549703
83. How to build a heap from inoder traversal ?  http://www.careercup.com/question?id=9735293
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]  http://www.careercup.com/question?id=12557684
85. An array contain +ve and -ve element, find the longest contiguous sub array whose sum is 0  http://www.careercup.com/question?id=12533685
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 ?    http://www.careercup.com/question?id=12549705
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]  http://www.careercup.com/question?id=12560677
88. How you implemnt a Priority Queue using Heap.  http://www.careercup.com/question?id=12549706
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 ]  http://www.careercup.com/question?id=12549707
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).   http://www.careercup.com/question?id=12533686
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 }}  http://www.careercup.com/question?id=12560678
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?  http://www.careercup.com/question?id=12336749
93. placed two robots and a sensor on the line, write code that will be executed on both machines and make them meet. http://www.careercup.com/question?id=12337726
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  http://www.careercup.com/question?id=12364061
95. Given the number, find the immediate next (larger) palindrome   http://www.careercup.com/question?id=12382912
96. Find the nth non-repeating number given a streams of characters in the range of A-Z  ..http://www.careercup.com/question?id=12381892
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.  http://www.careercup.com/question?id=12374673
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)   http://www.careercup.com/question?id=12351270
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     http://www.careercup.com/question?id=12381347
100. compare two strings arrays and return intersection elements in a string array without using 2 for loops?  http://www.careercup.com/question?id=12402663
101. GIven a binary tree, print the tree according to the level.
     eg
     01
     0203
     04050607
     0809101112131415
     proceed further to find the mirror image of alternate level
     01
     0203
     07060504
     0809101112131415    http://www.careercup.com/question?id=12419665
102. given a million integers find the largest k elements  http://www.careercup.com/question?id=12347483
103. find common ancestor of 2 nodes in
     1. binary tree
     2. binary search tree No parent pointer is given.   http://www.careercup.com/question?id=12374681
104. Given number n, return true if n is prime otherwise false.    http://www.careercup.com/question?id=12342686
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.
     Example
     (“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) )   http://www.careercup.com/question?id=12518669
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.  http://www.careercup.com/question?id=12520661
107. Write code to traverse a binary tree and save all the elements found in a sorted order in double link list.  http://www.careercup.com/question?id=12514667
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.   http://www.careercup.com/question?id=12449679
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)  http://www.careercup.com/question?id=12419684
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 ?  http://www.careercup.com/question?id=12515668
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.   http://www.careercup.com/question?id=12426712
112. how would you design a rate limiter in a client to control the number of transactions it requests the server.  http://www.careercup.com/question?id=12322728
113. How do you check if an entered text in a textbox is a student email address (ends with edu). special case xyz@alumni.univ.edu should be rejected  http://www.careercup.com/question?id=12503676
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  http://www.careercup.com/question?id=12375726
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
     Tree;
     N
     / \
     N L
     / \
     L L  http://www.careercup.com/question?id=12477676
116. You have the post order traversal of a tree. produce the tree.
     Possible?
     If not, what other info you need?
     Ok you have that info, now produce the tree.
     Write code  http://www.careercup.com/question?id=12493668
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.   http://www.careercup.com/question?id=12480668
118. Given a binary search tree, first find the least common ancestor of two numbers and then generalize it for m numbers.   http://www.careercup.com/question?id=12480667
119. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time   http://www.careercup.com/question?id=12343736
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.  http://www.careercup.com/question?id=12469661
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.  http://www.careercup.com/question?id=12468661
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..  http://www.careercup.com/question?id=1244666
123. Till Page 7 So far in careercup..Target—till page 20