Amazon Interview Questions
- 0of 0 votes
AnswersGiven an array sort all the elements in even positions in ascending order and odd positions in descending order
- bcsandy.1982 February 17, 2013 in India for Kindle| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 0of 0 votes
AnswersIf A and B, two integers are given.
- Sanjay Kumar August 08, 2012 in India
compute A/B.
Ex. 2/5 --> Ans should be 0.4
225/1000 --> Ans should be 0.225
22/7 --> Ans Should be 3.(142857) where 142857 are repeating decimal| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Coding - 0of 0 votes
AnswersRemove duplicates from min-heap.
- Aashish July 13, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere is an external array of integers on which you can perform the following operations in O(1) time.
- aditya.eagle059 June 25, 2012 in United States
1. get(int i) - returns the value at the index 'i' in the external array.
2. reverse( int i, int j) - returns the reverse of the array between index positions i and j (including i and j).
example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return {3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
Write a code to sort the external array. Mention the time and space complexity for your code.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersI was given a very interesting question.
You are given two very large files each containing integers in each line followed by a line break.
Produce a file with integers that are common in both files.
Estimate the time complexity of your code block?
Any edge cases and Bottlenecks?
Assumptions?
How would you solve this.
I did a little research on this and saw that some people suggested using Radix Sort for this and trying to split on large file into subsets and then using radix sort.
Here is the link
http://stackoverflow.com/questions/6520954/produce-a-file-that-has-integers-common-to-two-large-files-containing-integers
Can someone help me write this function. I read a lot of theories a lot of places but I am really looking for a code, preferably java for this.
This is a simple implementation of the same. I got a clarification that numbers are integers but the files are large but on one disk only.
I am using an approach as In case the file is too big to fit into memory on one go, break it into parts or read n integers at a time.and then use hashmaps to look for integers.
Cpmplexity: If the partition size is p and the file size is m then and no of rows per partition in n then ----- O(m/p * n) or O(N).
- chaos June 07, 2012 in United Statesimport java.io.*; import java.util.*; import java.io.FileWriter; public class FileRead{ /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub File file1 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input1.txt"); File file2 = new File("C:\\Documents and Settings\\chaos\\Desktop\\input2.txt"); try{ Map mymap = new HashMap(); Scanner scan1 = new Scanner(file1); Scanner scan2 = new Scanner(file2); while(scan1.hasNextLine( )) { int line = scan1.nextInt(); mymap.put(line,1); } while(scan2.hasNextLine()) { int line = scan2.nextInt(); try{ int val = (Integer) mymap.get(line); if(val==1) try{ FileWriter f1 = new FileWriter("C:\\Documents and Settings\\chaos\\Desktop\\output.txt"); BufferedWriter out = new BufferedWriter(f1); out.write(line); System.out.println(line); }catch (IOException e){} }catch(NullPointerException e2){} } } catch(FileNotFoundException e){e.printStackTrace();} } }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHow would you eliminate and print duplicate elements of an array of 5 billion 32-bit signed integers
- InfiniteLoop May 31, 2012 in United States| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm - 0of 0 votes
AnswersIm sure everyones heard of this.
Matrix with rows and column sorted. Find a particular element.
I mentioned the O(m+n) solution. He asked to make it better.
Thought for a while, then told him that you start with the last element of the first row and once you find the row which might contain the element, do a binary search on that row (since its sorted).
This further brings down the complexity to O(m+logn).
He said make it even better.
So I said do a binary search on the last column and look for the row where the element in the previous row is smaller and the element in the current row is greater than or equal to the target.
So the complexity becomes O(log m + log n).
He said ok.
When I was about to code this, he said there are two ways to implement it.
1) One you implement the dual binary search method.
2) Make use of the facts that the rows and columns are sorted.
Thought this over for a while and mentioned that instead of doing two binary searches, you can do just one considering the entire matrix as a linear array and doing binary search.
The complexity would be log(m*n)=log(m) + log(n).(Same as the previous optimal solution).
There would be some logic involved in translating the indices to (row,col) pairs. I got this working, but he wanted me to return the (row,col) pair if the element was found or (-1,-1) if not found.
For this he gave me the function signature
void find(int A[][10], int m, int n, int target,int&row, int col)
which is what I couldn't figure out. Here m = number of rows and n=no of cols
Here is the solution I gave// Initially pass start as 0 and end as m*n when calling function find(int A[][10],int start,int end,int target,int cols) { int mid = (start+end)/2; if (start > end) { element not found; } int r = mid/cols; int c = mid%cols; if(A[r][c] == target) { element found; } else if (target>A[r][c]) { start = mid+1; find(A[][10],start,end,target,cols); } else { end = mid-1; find(A[][10],start,end,target,cols); } }
Can somebody tell me how i can return the (row,col) pairs (yes! return two values) using the function signature he mentioned.
- sreemana@buffalo.edu March 30, 2012 in United States
PS: Thanks for reading the whole post.. I know its kinda long. But I hope it helps someone.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersWrite 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)
- sk February 23, 2012 in United States for AWSP| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGet the top 3 frequently used words in a book. The book contents are given as a single text file.
- anon.guy January 31, 2012 in United States for Kindle
I used hashmap solution. The interviewer said its not optimal. Use a combination of two or three data struct.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays Coding Data Structures - 0of 0 votes
AnswersRound-I Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated.
- Tim December 25, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Algorithm - 0of 0 votes
Answersthere are 2 types of bricks 1*2 and 1*3, in how many ways can u build a wall of length n and height 1.
- veena May 05, 2010
i.e for wall of length 7 and height 1
ans - 223, 232, 322
for wall of size 8
ans - 2222, 233, 323, 332
given n write a function to print all possiblilies| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersu have an array A of unknown length L. The array contains numbers that are distinct and sorted ascendingly. The array is 1-indexed i.e. first element is got by A[1] and not A[0]. To help u, since L is not known, when a index out of bounds is used, then a special value of NOT_FOUND is returned.
- akash April 22, 2010
the question is to find some positive integer n such that when used as the index, the result from the array is the n itself. i.e. A[n] = n.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination.
- kanurukh March 15, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the next in order node of given node in binary tree. Write the program of same. pointer to parent node is given.
- Anonymous January 07, 2010| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersHe gave me an array of Integers, each integer allows me to make at max its value jumps. If i am at zero, i'm stuck i cannot move forword. He asked me to find the least selection to reach end of the array.
- its ME November 23, 2009
ex: 1 3 5 8 9 2 6 7 6 8 9
initially at one i have only make one jump to 3, from 3 i can jump either 1 step 0r 2 steps 0r 3 steps.
my solution is 1 to 3 to 8, 3 selection and i am done.
Device an algo for this| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven 1) an int[] array and 2) an int value, how do i find out which two elements in the array add up to the value given? What is the speed of your algorithm? Can it be done faster?
- Zefram Cochrane November 22, 2008| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 2of 2 votes
AnswersWrite a Java code that take a string of parenthesis as input and return if the string is valid or not . The input will have '(' and ')' and also '*' and * serves as wild card and can be used in place of both '(' and ')' or it can be null.
- ryanray1512 October 16, 2017 in United States
For example,the String (*)(*)(** is a valid String.
Follow up: What if '[]' and '{}' are also in the string along with '()' and * can be used in place of any of them or can be considered as null?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 3of 3 votes
AnswersHow can you design a data structure that can do the following operations in O(1) time:
- Masumbuet December 29, 2014 in United States for International expansion
Insert, Delete, Search, Max which returns the maximum number
I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 10of 10 votes
AnswersYou are given with an array of 1s and 0s. And you are given with an integer m, which signifies number of flips allowed.
- Hitman October 22, 2014 in United States
find the position of zeros which when flipped will produce maximum continuous series of 1s.
e.g.
input:
arr={1 1 0 1 1 0 0 1 1 1 } m=1
output={1 1 1 1 1 0 0 1 1 1} position=2
arr={1 1 0 1 1 0 0 1 1 1 } m=2
output={1 1 0 1 1 1 1 1 1 1} position=5,6| Report Duplicate | Flag | PURGE
Amazon Algorithm - 0of 0 votes
Answersimplement bool isFactorialDivisible( int x, int y)
- suresh June 01, 2014 in India
Return true if x! is divisible by y
else return false| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersWrite a method that takes a string, in this format "aabbaadddc". Encode the string by counting the consecutive letters. Ex: "a2b2a2d3c1"
- unicorn November 07, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Coding - 0of 0 votes
AnswersWrite a program to get shortest path between two given nodes in a binary tree.
- pirate July 18, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer C - 5of 7 votes
AnswersDelete last node from the linked list. First node pointer is not given.
- yolo July 11, 2013 in India
I told him its not possible in conventional linked list.
He asked me what if we can add some more data in node.
Data should not be a pointer to previous node i.e., it should still be singly linked list.| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 1of 3 votes
AnswersGiven a binary tree, a complete path is defined as a path from root to a leaf. The sum of all nodes on that path is defined as the sum of that path. Given a number K, you have to remove (prune the tree) nodes from the tree which lie on a path having sum less than K.
- seth June 04, 2013 in India
Note: A node can be part of multiple paths. So we have to delete it only in case when all paths from it have sum less than K.| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersFind the longest common subsequence of two string
- RXH February 27, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose there is a distance matrix which consists of n points and that gives the distance of say (a,b) = 6 , (a,c) = 5. If there are N points assume 10000, then it requires N * N matrix to store the corressponding distances.How to store the matrix in such a fashion that it gives a fast retrieval and optimized storage.
- sowmya January 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersfirst non repeating character from a given string
- suryaoe November 04, 2012 in India for payments team| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer