## Data Structures Interview Questions

- 0of 0 votes
Red black trees versus AVL trees. Which one is better ?

- 0of 0 votes
A new species has been discovered and we are trying to understand their form of communication. So, we start by identifying their alphabet. Tough Mr. Brown managed to steal a vocabulary that has words in it in ascending order and a team already identified the letters. So, we have now ordered words as sequences of numbers, print every letter once in ascending order.

[3,2]

[4,3,2]

[4,1,1]

[1, 2]

[1, 1]

alphabet: [3, 4, 2, 1]

- 0of 0 votes
How would you store very large numbers that can't be store in a regular Integer or BigInteger, and make calculations

- 0of 0 votes
There is a tree of nodes . each node is of type either place, area name, city, district , state, country

they are in tree like order like country contains multiple states ,states contain multiple cities ...so on

i want define the node structure and define the strategy to print the address of any node given from parent to all the child address of the node`package com.girish.sample; import java.util.ArrayList; import java.util.List; public class Node { private String name; private Node parent; private List<Node> childNodes; private String nodeType; public Node(String name,String nodeType){ this.name = name; this.nodeType = nodeType; } /** * @return the name */ public String getName() { return name; } /** * @param name * the name to set */ public void setName(String name) { this.name = name; } /** * @return the parent */ public Node getParent() { return parent; } /** * @param parent * the parent to set */ public void setParent(Node parent) { this.parent = parent; } /** * @return the childNodes */ public List<Node> getChildNodes() { return childNodes; } /** * @param childNodes * the childNodes to set */ public void setChildNodes(List<Node> childNodes) { this.childNodes = childNodes; } /** * @return the nodeType */ public String getNodeType() { return nodeType; } /** * @param nodeType * the nodeType to set */ public void setNodeType(String nodeType) { this.nodeType = nodeType; } public String getAddress() { return getparentAddress(); } public String getparentAddress() { if (parent == null) return ""; return parent.getparentAddress().concat("," + this.nodeType + ": " + this.name); } public List<String> getchildAddress() { List<String> childAddress = new ArrayList(); for (Node node : childNodes) { childAddress.add(node.getchildAddress()); } return null; } }`

- 0of 0 votes
First asked how you can write a tree in a file?

Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d

- 0of 0 votes
Implement circular buffer with read & write functions

- 0of 0 votes
Designing a data-structure for following functions

Insert X : Insert an element X into the set.

Delete X : Delete an element X from the set. It is guaranteed that such X always exist in the data structure.

Mean : Report Mean of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.

Mode : Report Mode of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.

Median : Report Median of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.

- 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)}