amazon interview questions

Shortest path in Binary Search Tree

Introduction Another interview question for the most interesting data structure called BST (Binary Search Tree). To know more about BSTs check my previous post. Problem Statement : Given a Binary Search Tree, keyed on positive integers. The task is to find the Shortest path in Binary Search Tree which adds up to the number K. If no such path exists, return a message accordingly. Understanding the problem A node in a binary search tree always has a higher key at its right child compared to its left child. There are many path running from the roots to the leaves. When we add up the key val...
Read More

Binary Tree Linking Neighbors

Introduction Problem Statement : Given a regular binary tree with left, right and peer node pointers. The left and the right pointers are already populated. We need to make the peer pointer point to the next right neighbor on the same level. Understanding the problem Here is a diagram to explain what is needed. The red peer pointer points to the immediate right neighbor if the neighbor exists. Approach 1 The first solution which comes in mind is to do a custom, level order traversal as done in the post. And, in each iteration of the inner loop, just link each of the node to the next in ...
Read More

Linked List Batch Reversing

Introduction As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList. Understanding the problem statement Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same. For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed. Approach We need to use our reverse linked list func...
Read More

Topological Ordering for Graphs

Introduction The topological ordering for graphs get many applications where the nature of the problem is ordered sequential processing. Few of the problems in this category are as follows: Dynamic Linking/Loading of programs while building and execution. Deciding the pre-requisites in a course structure. Job Scheduling in Processors or Assembly Line Processing. Building an Alien Dictionary from given words. There are many more but I am sure you got the idea. When we say topological ordering of graph, we are necessarily talking about the ordering of the vertices of the graph. Un...
Read More

Matrix Transformation to make rows and columns zero

Introduction Another interview question about matrices. Matrices have been of great interest in programming and Linear Algebra and a matter of study for most of the programmers. The problem statement follows: "Given a matrix A of size M * N where M is the number of rows and N is the number of columns and each of its cell A[i][j] is populated with either zero or one. Transform the matrix such that if there exists a cell A[i][j] = 0 then the row i and column j is zero in the resultant matrix". You must not use extra space and try to solve it in lowest possible running time. Understanding...
Read More