Amazon Placement Paper Pattern

1. To write a code to simulate the memory leak.

2. One sorting algo – merge sort/heap sort/quick sort with the complexity (time & Space)

3. Write an algorithm to optimize the code to have minimum no of iteration.

4. Write a code for traversal of a node in doubly linked list

5. Code for Palindrome (ask then to write the code with minimum no of iteration & with good hash cases)

Amazon Interview questions
1. Write an algorithm to determine if 2 linked lists intersect

2. Find the 2nd-largest node in a binary tree

3. Probably the most difficult question they asked me was, he put a binary tree on the whiteboard and I had to write a function that would find if the tree was symmetrical or not. Anyone who’s familiar with data structures and recursion should be fine with this, just don’t freak out when they propose the question.

4. Find the element from the array that has odd number of occurences

5. Generate words from a n *n matrix

6. How would you, specifically, build Amazon Web Services?

1. Given the number of nodes in a complete binary tree, find out the height of the tree (assume the height of the root is 1)

2. Time complexity of different sorting algorithms

3. Given the smallest and largest elements in an array, find out the best sorting algorithm (better than quicksort) to sort this array?

4. Write a program to reverse the digits in an unsigned integer. (1234 -> 4321)

5. Count the number of words in a file

6. Is Function overloading possible in C++ differing only with return type?

7. What is a singleton class in C++?

8. Find out all the pairs of elements in an array that computes sum to k.

Some Sample Questions:

1 How will you find out the difference between Binary Trees and Binary Search Trees? They wanted to know how I will implement it? Complexity?

2. Write code to find the Kth largest element in a Binary Search Tree. I wrote the c++ function, and then was debugging it for various edge conditions..

3. Find the first occurance of an integer in an array. The best and worst cases. Write the code. I explained binary search, and wrote the function.

4. Find the width of a binary tree. I wrote the function for it.

. He asked if I had built and tested a system end-to-end,

5. Tell some details about mutithreading programming. What is semaphore? Diff between thread and process etc etc

6. How search engine make index of documents? What DS shuld you use? How do u index a database for range finding query. Etc etc….

7. Write a code to make canonical form a directory listing.

8. Design and implement LRU based hash
– discussion on data structure to use, algo, unit test, etc

9. Select K smallest integer from n integer where n is very large and k is very small.

10. OS level Q: diff between user level thread vs kernel level thread, page replacement algo, etc.
11Find the first common ancestor of two given nodes in a binay search tree.

12.using a function
int random(); //returns 0 or 1
implement a function
int rnd(int a , int b ); // which returns a random value between ‘a’ and ‘b’

13.difference between multi-processing and multi-threading.. and then he went into kernel level threads
And user level threads…
> what would i chose for implementing a webserver (multi processing, or multi threading (user level or kernel level) and why?)

> Design/architect a web portal for a library in a college:
>> What a re the types of users.. And functions that should be exposed to them
>> The overall appplication structure
>> The database schema (with the details of each table)

14. Given a sentence reverse individual words. Write code and read out.

15. Given array of n integers and an integer x, find whether there exist two elements in the array whose sum equals x.

16. Design Leaset Recently Used cache

17. Design chess game and send the class diagram to the given email address in an hour

18) An infinite array of sorted integers is given and we have to search given number from that array.

20) Design for Car Rental System
(Classes and patterns to be used)

21) How will you find whether a linked list is a palindrome or not? The given linked list is a singly-linked list of characters. Use of extra memory is not recommended.

22) Given a string say, ‘RADAR’, print ‘R2A2D1’ in return, that is, each character followed by the number of times it occurs in the string.

23) Discuss some sorting algorithms with their concept and their (worst/average) order of complexity. Which is the best sorting algorithm and why?

24. Find whether a substring exists in the given string.
bool substring(const char *string, const char *substr);

25 Write a code to determine if a given binary tree is a binary search tree or not. Binary search tree is a tree in which all elements to the left of a node are smaller and all elements to the right are bigger.

26. There is an external array of integers on which you can perform the following operations in O(1) time.

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.

27 Find whether a substring exists in the given string.
bool substring(const char *string, const char *substr);

28. Write a code to determine if a given binary tree is a binary search tree or not. Binary search tree is a tree in which all elements to the left of a node are smaller and all elements to the right are bigger.

1) Find if Binary tree is symmetrical
2) Java Generics , Primitive Data Types and Object types and comparison of Java Generics Vs C++ Template
3) How to mirror binary tree .. Write a C++ / Java code for that
4) 4 integers between range of 1 to 10 are given and write a program to find maximum number of combinations of these integers which add up to 15.
Then further asked if 4 integers have limitations e.g. like { 5,5,5,5} then it will result in only one combination 5,5,5 so how to tackle that.

Interviews can induce some stress and some headaches, but if you can expect what’s ahead, you’ll be in much better shape. I hope to help others taking the interview to prepare and to remove some stress on people’s chest.

The interview
My interviewer called, introduced himself and promptly started the interview.

* What languages have you learnt in U of T? What tools to you use to program? What platform did you develop on?

* Having first scanned my resume, he first asked about a prototyping project i worked on. And seeing it won an IBM-sponsored competition, he asked what the competition was.

* Then he asked about an operating system project I listed. He asked what I did and what I’ve learnt. He asked if we actually implemented it (hell yeah… so many sleepless nights). And he went on by asking how to debug when developing an operating system.

* What’s the project you’re most proud of? And why so? Mine was online-marking tool, found at pyre’s past project page.

* Are you familiar with TCP? I honestly said that I didn’t know much except handshaking. He said it was fine and he re-assured me I was not expected to know it.

* Are you familiar with HTTP? I said I was, having written a basic web server, which I very briefly explained. He was interested in the web server, so I gave an explanation of the basic structure of my implementation. He asked about how I dealt with concurrency issues, but I didn’t. He then asked in general how to deal with concurrency issues.

After the first part of the interview was done, he gave more clarifications as to what he does , and what exactly his group is responsible for. He talked about how this was just information gathering and there was no reason to be stressed. The second part could then begin:

* Give an algorithm that will allow you to find the Nth node from the end of a singlely linked list. We explored many solutions, ranging from the naive algorithm to using a stack to finally getting the solution which only requires one pass.

* Imagine you have a database that can only do 2,000 queries a second. Your web application gets 5,000 queries a second, what can you do to improve the situation? After asking him for some clarifications, he added: Imagine its a stock quote engine for NASDAQ and that the queries are about the top 100 stocks at closing.

* Imagine you have a big online storefront. Your webserver can only do 1,000 concurrent requests. Many people are visiting your website and you want to support 3,000 concurrent requests. What would you do? I asked for some clarifications, and he said: The limitation is computational power and not bandwidth.