## Data Structures Interview Questions

- 1of 1 vote
given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?

@Anonymous Thanks for the reply!

Please try other use cases like, only single leaf node

- 1of 1 vote
Given a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

The rectangle at lower level has more priority than at higher levels.

- 0of 0 votes
A binary tree and a number, say k are given. Print every path in the tree with sum of the nodes in the path as k.(A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree)

- 0of 0 votes
Design Amazon Recommendations Feature. Focus on designing how would you store and make it accessible fast? What would be class design like for the class which would provide list of products which people bought similar to a given product? How would you test that class?

- 1of 1 vote
Given an integer target and binary tree (not a binary search tree!) each of whose nodes contains an integer (which may be positive or negative), find the set of all subtrees whose sum equals the given target. The sum of a subtree is just the sum of the integers contained in its nodes. Note that the subtree does not have to contain all child nodes - it can be any set of connected nodes.

- 0of 0 votes
Give a large multi MB byte file in memory, a system handles delete requests for segments typically of the order of bytes. The system has a constraint that individual purge requests of byte segments are expensive, so that the no. of purges are a minimum.

Eg. a 5 MB file receives delete requests for offsets (1, 100), (250, 550),(1000, 1200), (400, 600), (800, 900), (1100, 1150)

Effective delete requests - (1, 100) , (250, 600), (800, 900), (1000, 1200)

The users of the system always go by the absolute byte ordering of the file. Eg. if byte 1 is deleted, the users of the system will reference the actual byte 2 as byte 2.

What data structure would you use to store these intervals such that the following operations are efficient 1. Looking up an interval 2. Inserting a new interval that has no overlap with existing ones 3. Inserting a new interval that has partial overlaps with existing intervals. This would involve collapsing the existing intervals with the new interval to form a single large interval. Eg. Interval cache: {(1, 100), (250, 550), (1000, 1200)} , new interval : (400, 700) -> Interval cache: {(1,100), (250, 700), (1000, 1200)}

- 2of 2 votes
Print the longest path from root to leaf in a Binary tree (Basically the nodes that lie on the height path).

- 0of 0 votes
public interface FirstCommonAncestor {

/**

* Given two nodes of a tree,

* method should return the deepest common ancestor of those nodes.

*

* A

* / \

* B C

* / \ \

* D E H

* / \

* G F

*

* commonAncestor(D, F) = B

* commonAncestor(C, G) = A

* commonAncestor(E, B) = B

*/

Node commonAncestor(Node one, Node two);

}`class Node { final Node parent; final Node left; final Node right; public Node(Node parent, Node left, Node right) { this.parent = parent; this.left = left; this.right = right; } boolean isRoot() { return parent == null; } }`

- 1of 1 vote
You are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.

- 0of 0 votes
What data structure would you use to store the entries of a sparse matrix?

- 0of 0 votes
(Priority Scheduling) In some systems, a priority is associated with each process and the CPU is allocated to the process with the highest priority (small value). Equal priority processes are scheduled in FIFO order. Define a suitable data structure, and then write a simulation program for the system described above. The program should display the following menu: 1. Add a New Process. 2. Serve a Process. 3. Display Information about Waiting Process. 4. Number of Waiting Process 5. Exit menu Hints: You have to adjust the QUEUE ADT in implementation level to be suitable for solving this problem. The process should have the following fields: process ID and priority.

- 0of 0 votes
Add a node to sorted circular linked list

- 0of 0 votes
None actually understands how garbage collection works, albeit people ask this in the interviews. Nonetheless, we are going to ask you something very similar. Here is the problem.

Take an array of bytes, perhaps 1MB in size.

Implement these two operations:`ptr_structure = alloc ( amount_of_storage ) freeed = free ( ptr_structure )`

Now, here is your problem. alloc must allocate contiguous storage. If it is not possible, you need to compact ( defragment ) memory. So, you need to implicitly write a :

`defragment() // defragments memory`

Worse is coming. Even imagining you have written a stop the world defragmenter, after you reallocate, how the ptr_structures would actually work?

Solve this whole problem.

Time allocated was 1 hour. Face to face, panel with 2 interviewers.

- 0of 0 votes
As you know, every OS comes up with this tiny application called the calculator. It is good. Now, here is our problem. If we try to implement the function

`def calculate( operand, operator, operand ) { /* Do Interviewers bidding here */ }`

I have to write if upon if upon if upon if to do for all operators. Moreover, some operators are not even binary! Take example the abs() or say the negate()!

Bigger problem persists. With the if mode, we can not even add operators as we wish to without changing code!

But that is a sin. So, what do we do? That is question 1.

In question 2, as a software tester, how do you propose to test and automate the above? Writing more if than the developer is not allowed.

- 0of 0 votes
Given a sorted (increasing order) array, write a program to create a binary tree with minimal height

- 0of 0 votes
Problem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :

Nearest meeting cell: Given any two cells - C1,C2, find the closest cell Cm that can be reached from both C1 and C2.

Note: Aim for O(Log(N)) solution.

INPUT FORMAT - First line has the number of cells N

Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.

Third line contains two cell numbers whose nearest meeting cell needs to be found. (return -1 if there is no meeting cell from the two given cells) .

OUTPUT FORMAT - Find nearest meeting cell (NMC).

- 0of 0 votes
Problem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :

find Maximum number of entry points (incoming edges) for any cell in the maze

Note: Aim for O(N) solution.

INPUT FORMAT - First line has the number of cells N

Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.

OUTPUT FORMAT - Find max entry points in any cell.

- 0of 0 votes
Problem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :

The length of the largest cycle in the maze. Return -1 if there are no cycles.

Note: Aim for O(N) solution.

INPUT FORMAT - First line has the number of cells N

Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.

OUTPUT FORMAT - length of the largest cycle.

- -2of 4 votes
Follow-up to above question:

Can you augment a BST to return the number of elements with node values in a given range?

If not, what other data structure would work?

- 0of 0 votes
The following is the design question I was asked.

Design a dash board.

Should be very realistic.

Should be scalabe .

Should have very less latency .

Can expect millions of updates per second.

Dash board should show :

for each day :

1. city name ,

2.total trips in that city for that day ,

3.total fare it could collect in that city on that day,

4. fare collected from old clients

5. fare collected from new clients (new client is the client who is having his first ride in Uber after registration)

Input : we get two strings s1 , s2.

the format of s1 : trip_id , client_id , city , datetime

the format of s2 : trip_id , fare.

Could you please suggest how to proceed for this kind of question?

- 2of 2 votes
A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35

- 0of 0 votes
Given input format, The first line has the number of employees of a company Z. The next two lines have employees to perform certain operations on. The first employee of the fourth line can be assumed to be the ceo of the company. Each line from then on has the format Employee X Employee Y where X manages Y. (and hence Y forms the child for X).

input:

6

Rajesh

Ravi

//Tree Starts here

Ram Raj

Ram Goku

Raj Rajesh

Raj Richa

Richa Ravi

Its known that each person in the company can directly line manage a maximum of 2 other employees.

For the two employees in the first two lines, find the lowest common manager.

How to construct this tree in java to eventually do an lca?

- 0of 0 votes
In a 2D(m*n) int array few cells are marked as 0(zero). Distance between each cell is 1(one). Hence diagonal from one cell to next cell in the diagonal is 2(two). For each cell find the distance from the closest 0(zero) value cell.

Input would be: length of array. width of array. count of zero in the array. followed by list of x coordinates and list of y coordinates

Example:

3

5

1

0

0

Output:

0 1 2

1 2 3

2 3 4

3 4 5

4 5 6

- 0of 0 votes
Implement a data structure to represent this

[1,[2],[[[5]]],6,7,8]. Multi level indirection with in a list

- 0of 0 votes
What is a stack? What operations can be performed on it?

Implement a stack data structure.

- 0of 0 votes
Implement a datastructure with the following APIs

void add(int) - 3,12,5,6,1

int getMin() - 1,3,5,6,12

- 2of 2 votes
Given two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.

- -1of 3 votes
Construct a Binary tree from the preorder traversal and find the distance between two nodes.

- 0of 0 votes
Find out if there is cycle in Directed graph

- -1of 1 vote
Given billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)

There is a simple way to achieve answer in O(n) by processing each rectangle sequentially, but optimize it further provided large number of Rectangle array.