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

0 comments:

Post a Comment