Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

1. Override is replacing a method in a subclass with the same signature as a virtual method in the parent class. When called it invokes the subclass's version of the method instead of the parent class. Overload is when you modify the method signature but keep the name to support variants of the same procedure, its a form of parametric polymorphism.

2. Abstract is a partially implemented class that is meant for derivation. It provides base functionality but leaves key implementation details to the user of the class. It is typically used in template-method patterns where the core algorithm does not change but the details of how to get the data are context sensitive.

3. An interface is a completely unimplemented class that serves as a contract for how this abstract type will communicate with other objects. It provides a set of methods with signatures determining what calls this type supports.

4. An array is a block of memory with fast random-access times due to its mechanic for traversing the array (offsetting a pointer from the first element in the array). A linked list is a set of pairs where one element of the pair is a piece of data and the other is either a null link or a link to the next pair. Linked lists do not provide a good way of randomly accessing elements but they excel at insertions and deletions from any point in the list.

5. A tree is an abstract data type that contains elements. It has properties that make it desirable for scenarios where you want to look up data quickly but only if certain properties are maintained. Properties are: the tree must be balanced, all nodes must be ordered such that every subtree to the left is less than or equal to the root. All nodes to the right of the root must be greater than the root.

6. A map or a dictionary is a data structure that connects arbitrary pieces of data together via a fast lookup mechanism. They are typically implemented with hash-tables but sometimes a balanced binary search tree like Red Black Trees or AVL Trees are used.

7. Implement an AVL tree and make sure that its keys and values can support any type, if its a dynamically typed language then no problem just implement the logic behind rotations, insertions, deletions, etc. If its a statically typed language with a meta-programming mechanism then use that to generate AVL[Int,String] AVL[String, Int] etc...

- Anonymous April 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Override is replacing a method in a subclass with the same signature as a virtual method in the parent class. When called it invokes the subclass's version of the method instead of the parent class. Overload is when you modify the method signature but keep the name to support variants of the same procedure, its a form of parametric polymorphism.

2. Abstract is a partially implemented class that is meant for derivation. It provides base functionality but leaves key implementation details to the user of the class. It is typically used in template-method patterns where the core algorithm does not change but the details of how to get the data are context sensitive.

3. An interface is a completely unimplemented class that serves as a contract for how this abstract type will communicate with other objects. It provides a set of methods with signatures determining what calls this type supports.

4. An array is a block of memory with fast random-access times due to its mechanic for traversing the array (offsetting a pointer from the first element in the array). A linked list is a set of pairs where one element of the pair is a piece of data and the other is either a null link or a link to the next pair. Linked lists do not provide a good way of randomly accessing elements but they excel at insertions and deletions from any point in the list.

5. A tree is an abstract data type that contains elements. It has properties that make it desirable for scenarios where you want to look up data quickly but only if certain properties are maintained. Properties are: the tree must be balanced, all nodes must be ordered such that every subtree to the left is less than or equal to the root. All nodes to the right of the root must be greater than the root.

6. A map or a dictionary is a data structure that connects arbitrary pieces of data together via a fast lookup mechanism. They are typically implemented with hash-tables but sometimes a balanced binary search tree like Red Black Trees or AVL Trees are used.

7. Implement an AVL tree and make sure that its keys and values can support any type, if its a dynamically typed language then no problem just implement the logic behind rotations, insertions, deletions, etc. If its a statically typed language with a meta-programming mechanism then use that to generate AVL[Int,String] AVL[String, Int] etc...

- Anonymous April 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hooray OOP questions

1. What is difference between override and overload

Override: When a class inherits from another class, any method or value in the superclass that shares a name with the subclass will be overriden, meaning it will be ignored in favor of the subclass's definitions. If superclass contains a method

public int add_val(int a, int b){return a+b;}

and subclass contains a method

public int add_val(int a, int b){return a*b;}

calling subclass.add_val(5,5) will give a value of 25, whilst calling superclass.add_val(5,5) will give a value of 10.

Overloading: When any method has more than one possible set of input parameters, this is a huge part of polymorphic designs. Say I have two methods, add_val:

public void add_val(int a, int b){
   System.out.printf("%d\n", a+b);
}

public void add_val(String a, String b){
   System.out.println(a + " " + b);
}

calling

object.add_val(1,2);

prints "3"
whilst calling

object.add_val("Hello,", "World!");

prints "Hello, World!"

2. abstract. when will u use abstract

An abstract class is any class, at leastin the java definition, which contains an abstract method, such as

abstract int add_val();

Abstract methods have no implementation, they are meant to be implemented by a subclass.

Abstract classes can contain implemented methods and declared/initialized variables as well. If it only contains abstract methods, it should just be called an interface. This is good for the polymorphic usage of having a type of class you wish to have multiple other classes inherit from, all of which must have some common traits but which can (or must) define certain characteristics separately. Any subclass which doesn't implement one of the abstract methods from the superclass must also be called abstract, since it implicitly carries an abstract method through inheritance.

Say that I wanted to create a series of printers. They all have common traits,

abstract class Printer{
   int power;
   int speed;
   abstract void boot_sequence();
   abstract void call_in_warranty();
   public String print_paper(String s){
       //some code printing s onto paper
   }
}

Now, we have the requirements for something to be a printer (from an IT standpoint, warranty and whatnot). I could specify a hundred different brands of printer, each inheriting from the superclass. Since architecture is not going to be the same between all of them, they all have slightly different boot sequences, so boot_sequence() is left abstract until a subclass defines it. Anyone who has tried to call in a warranty on a printer or any hardware knows each company is different with how they handle it, somewhat. So, again, it should be defined by the company, not the printer. However, all printers must print onto paper, and while you could do it slightly different from others, it's easier to give a default behavior, then let someone override that if they want to do a different behavior (that's their own risk, see how many customers they get if their printer just eats paper and prints pictures of bananas all day)

3. what is an interface

An interface is similar to an abstract class, but all methods in it are implicitly abstract. These are not so much functional as they are useful for programmers. When we want to create something to fit into a functioning system, a new class, and want it to work in a certain area of the system just as easily as currently implemented classes, we have it inherit the interface, then implement what the interface gives us. Think of it as instructions about what must be included. Since all methods in interfaces are abstract, if you wish to use your new class, you have no choice but to implement all the methods inherited.


4. what is difference between array and link list

An array is a fixed-sized allocation of memory addresses of a specific type defined by the programmer. You can modify the values inside the array, but you cannot grow or shrink it. Good for when you know exactly how many things you will be working with (think a college class where you have 70 students and no one can drop or enroll, now you use a 70-element array to store their test score averages)

A linked list is a data structure consistent of nodes, each node points to another node, usually referred to as "next". Each node also has some data it carries. You create a list by linked one node to another, and that node to another, and that one to another, and so on, think

node 1 ---> node 2 ---> node 3 ---> node 4 ---> null

the node with a null next is the end of the list. Unlike arrays, these lists can change in size, shrinking or growing as needed. Traversing them must be done one node at a time, which means lookups are O(n), even if you know exactly which node you want to lookup, whereas in arrays, lookup time is O(1) when you know which index you want to access.

Linked lists are used for stacks, so, let's say you are doing some work on a compiler, you want it to check to make sure all scopes are resolved correctly, (for each {, there is a }, for each [, there is a ], for each (, there is a ), etc). You would create a linked list, where each time you saw an open bracket (a {,[, or ( in this case) you add a new element to the front of the list containing a char of that bracket type. Whenever you see a closing bracket, if the bracket at the front of the list is the same type, you remove it from the list. If, by the end of the program, you have an empty list, each open bracket had a closing bracket and you are good to go.

5. what is a tree

A tree is a structure in which nodes have one OR MORE next nodes (referred to as children). Where linked lists only have one next per node, trees can have as many as they want (the standard is one or two). We use these for a variety of purposes, but the most commonly seen is the Binary Search Tree, in which each node is sorted upon input to the tree such that doing an in order (reading each node left to right as it appears if they all were collapsed into a line) reads ordered numbers. This is done by adding a new value, looking at the root, and doing something like

if (new.val < curr.val){ 
  if(curr.left == null) curr.left = new;
  else traverse to curr.left and repeat from top
}
else if (new.val > curr.val){
  if(curr.right == null) curr.right = new;
  else traverse to curr.right and repeat from top
}
else, same val as current node, just ignore and continue to next input

Insert time is O(log n), lookup time is O(log n), and deletion time is O(log n), in the average case, for BST's.

6. what is a map\dictionary

A map, often referred to as a hashtable in data structures, is a array of keys with values assigned to them. A key is the index identifier, i.e. in a dictionary this would be the word, like aardvark or quotation, and the value is a adjustable associated input, in the case of a dictionary, the definition of the word.

The entries are sorted based on a hashing function before being input, so they know where to be put such that anytime you look at the map/dictionary, in ideal circumstances, you will see everything in order.

7. Explain (orally) how would you implement a dictionary via a tree

In an ugly manner, but okay. Each node in the tree has 26 possible children (we will pretend we only use alphabetical characters and case doesn't matter).

Each child's name is the alphabetical entry its index cooresponds to. 1st child = "a", 2nd = "b", etc. Each node carries a string value. When you traverse to a child, you append the character from its name onto the current string, and that becomes the child's string value.

So, traversing from a node with string "App" to child "l" gives that child node a string value of "Appl", now if you traversed from there to "e", you would havea node with "apple", a traversal to "i" would give you "appli", etc.

When we start with a empty root, we add a word as input, it will look at first character, go to that child (well, first it will initialize the child), then look at the next letter, go to that hcild, and so on.

This is roughshod and not the best design, a Trie would have worked well here.

- Javeed October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

It is a java question rather than C++ question.

- Zhangquan1987 May 17, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More