## Data Structures Interview Questions

- 0of 0 votes
You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

`0 / \ 0 1 / \ / \ 0 1 1 1`

You need to write a code, which will invert given LEAF and put tree in a correct state.

- 0of 0 votes
Products are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.

- 0of 0 votes
Products are identified by alphanumeric codes. Each code is stored as a string. We have three types of products:high priority, medium priority, and low priority. Given an array of product codes, sort the array so that the highest priority products come at the beginning of the array, the medium priority products come in the middle, and the low priority customers come at the end. Within a priority group, order does not matter. You are given a priority function which, given a product code, returns 1 for high, 2 for medium and 3 for low. This array may contain a large number of product codes, so do your best to minimize additional storage.

- 0of 0 votes
Given a Matrix A,

The rules for movement are as follows :

1. Can only move Right or Down from any element

2. Can only move within the row and column of element we start from intially.

3. You can only visit or cross an element if its value is lesser than the value of element you start from.

Find total number of elements one can visit, If one starts from an element A(i,j) where i-> row and j-> column.

Note : You have to print this output for each matrix element.

Input : Matrix

1 2 3

2 3 1

3 1 2

Output:

1 1 3

1 3 1

3 1 1

- 0of 0 votes
Given a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.

Here's what your method signatures should look like (in Java):

List<Integer> store(Node root)

Node restore(List<Integer> list)

Example Tree:

5

/ \

3 2

/ / \

1 6 1

- 0of 0 votes
You are given three type of data sets.

Type 1

Data size: 4 billion

Distinct Data: 1000

Type 2

Data Size: 4 billion

Distinct Data: 2 billion

Type 3

Data Size: 1000

Each Data is of length 100 million byte

What kind of data structure would you use to answer search/insert/remove queries for each data types?

- 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.

- 1of 1 vote
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"]

- 1of 3 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.