## Data Structures Interview Questions

- 0of 0 votes
Perform an efficient DeepCopy of a linked list whose node is like below:

`public class Node { public int Value {get;set;} public Node Next{get;set;} public Node Random{get;set;} }`

The Random field points to any random node in the list.

- 0of 0 votes
Given the following set of strings, write a function that stores this information.

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/Computers/Graphics Cards

// /Electronics/Computers/SSDs

// /Electronics/TVs

// /Electronics/Computers/Graphics Cards

// /Electronics/TVs

// /Electronics/TVs

// /Garden

// /Automotive/Parts

Your datastructure should be able to provide information as such:

// / = 11

// /Electronics = 9

// /Electronics/Computers = 6

// /Electronics/Computers/Graphics Cards = 4

// /Electronics/TVs = 3

// etc

// ["/Electronics/Computers/Graphics Cards", "/Garden"]

- 0of 2 votes
Given array of length n, having element 0 to n-1.

you are allowed to swap adjacent element only if Absolute difference of two element is equal to 1.

Is it possible to sort array.

If yes print sorted output.

- 0of 0 votes
Implement a stack that in addition to push and pop has a function that returns the min value of the stack.

I came up with a O(logn) solution, but he wanted a O(1) for the whole algorithm.

- 0of 0 votes
Design a data structure to support following operation:

Insert, delete, search and min difference

Time complexity of finding min Difference should be less than O(log n).

- -1of 1 vote
There is an island surrounded by oil mines. You will be given n companies and m oil mines having values. You have to distribute the mines to "n" companies in fair manner. Remember the companies can have oil mines adjacent to each other and not in between of each others.After distributing them compute the differnce of oil mines from the company getting highest and company getting lowest. This number should be minimum.(then only the distribution can be termed as fair).

Example

Input

2

2 4

6 13 10 2

2 4

6 10 13 2

output

5

1

- 0of 0 votes
Write findMin, findNext of BST tree node has parent pointer also. http://www.geeksforgeeks.org/find-the-minimum-element-in-a-binary-search-tree/

http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/

- 0of 0 votes
We have a List of FlightRoute

`public static class FlightRoute { String from; String to; int time; .... }`

and write a function to find Shortest Path: findShorestPath(String start, String end, List<FlightRoute>routes)

- 1of 1 vote
1. Difference between arrays and link list

1.1 How to prepend each of the above with extra data

2. Hash-table. What datastructure to use to create one. How to resolve collision

- 0of 0 votes
`import java.time.Duration; import java.time.LocalTime; import java.util.List; import java.util.Map; // Your goal is to write business logic for a very simple Restaurant booking system // You are encouraged to refactor exisiting code, create other classes, write helper methods etc // You also need to make sure that the implementation works correctly class Reservation { public String name; public int partySize; public LocalTime startTime; } class Table { public int tableNumber; public int maxPartySize; } class Restaurant { public List<Table> tables; public LocalTime openTime; public LocalTime closeTime; public Map<Integer, Duration> reservationDurationsPerPartySize; // Returns a Table if Reservation could be booked, null otherwise // Booking rules: // 1) Reservation could be made only when the Restaurant is open. // 2) Only one Reservation can be seatted a Table at any time. // 3) Reservation can be seatted only at a Table of the same or a bigger size. // 4) Reservation should stay on the same Table for the whole Duration. // 5) Reservation Duration is determined by PartySize. public Table bookReservation(Reservation reservation) { //TODO: } }`

- 0of 0 votes
Given set of N number of points/Co-ordinates[(x1,y1),(x2,y2), (x3,y3), (x4,y4), (x5,y5), etc] find if any of them form square.

- 2of 2 votes
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.

- -1of 5 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?