## Data Structures Interview Questions

- 0of 0 votes
You have been given a map which holds book name and book author. One author might have several different books. But books are unique. Now, write a function which will return you a Map which will have the author name as unique and all the books he has written as values.

`Book Map=["Java"-->"John", "C#"-->"Rob", "Ruby"-->"John", "Rails"-->"Rob"]`

This should return a Map which has the following:

`["John"-->{"Java","Ruby"} "Rob"--{"C#","Rails"}]`

- 0of 0 votes
https://codejamanalysis.wordpress.com/2017/03/18/crossover-problem-super-stack/

Any Optimized Solution to avoid TLE for 4 test cases. I have tried by implementing Stack using Doubly Linked List.

Still not able to pass test cases!!!

- 0of 0 votes
Given a BST of memory sizes. Find best fit for a memory block of size M.

- 0of 0 votes
Given a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.

Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.

- 0of 0 votes
Given a 2-d integer array, find the size of the largest connected area (number of elements connected), where two elements are connected if they are side-adjacent in matrix(up,down,left,right operations). Also there can be maximum of two different integers present in this set.

- 0of 0 votes
Given two sets of intervals such as {[1, 2], [4, 8]} and {[2, 5]}. Find their union {[1, 8]} for the two intervals.

- 0of 0 votes
Design a dictionary which words are grouped by the same characters. For example, dog and god are in the same group. And how to make it scalable to handle a huge number of words?

- 0of 0 votes
We have an array if 0's and 1's like

00010000010001001

Assume that all 1's are a person and if a new person comes and if we want to add to the array in such a way that the gap between individuals are maximum as possible.

if we add a new person, then the new array should be

000100100010001001

- 1of 1 vote
Given a string as input, return the list of all the patterns possible:

`'1' : ['A', 'B', 'C'], '2' : ['D', 'E'], '12' : ['X'] '3' : ['P', 'Q']`

Example if input is '123', then output should be [ADP, ADQ, AEP, AEQ, BDP, BDQ, BEP, BEQ, CDP, CDQ, CEP, CEQ, XP, XQ]

- 0of 0 votes
/*Coding question: The customers for a particular business, required to use a webpage to select a Browse Node.

A Browse Node, is an element in the classification structure used to classify products in the Amazon webpage.

The products are classified in 8 categories. Each category has its own sub-classification that looks like a tree with many

children per node and many levels. The UI developer has a tool to paint such tree. He requires from you (You are the backend developer)

to implement 2 interfaces for him:

Node getRoot();

List<Node> getChildren(Node node);

The data is available for you in a text file with this format:

//nodeid, parent_node_id, nodename

Example:

//nodeid, parent_node_id, nodename

10, 1, Comedy Books

20, 2, Tablets

1, -1, Books

11, 1, Novels

12, 11, Terror novels

2, -1, Electronics

-1, 0, GlobalRoot

*/

- 0of 0 votes
Given n line segments, find if any two segments intersect

http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

- 0of 0 votes
N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

- 1of 1 vote
Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9

Target number : 5

Output : 5

Target number : 11

Output : 9

Target Number : 4

Output : 5

- 0of 0 votes
Write a merger and separator for Linked List.

eg: 1->2->3->4->5

separator()

1->3->5 and 2->4

merger()

1->2->3->4->5

- 0of 0 votes
How would you design the "call logs" for a mobile phone ? Be as efficient as possible.

- 0of 0 votes
You are given a stream of numbers which represent the stock prices of a company with timestamp. You need to perform some set of operations on the stream of data efficiently as below: 1. findStockPriceAtGivenTimeStamp(Timestamp) 2. deleteAndGetMinimumStockPriceForToday() Timstamp: 1 2 3 . 4 . 5 Prices: 12 34 4 . 1 . 18

- 1of 1 vote
Explain the Data Structure which is well suited to implement UNIX commands like PWD, LS, MKDIR, CD in an imaginary OS. No code required.

- 0of 0 votes
Design a text based rpg.

- Player can enter room.

- Room has 4 walls and items

- a wall can have door

- user can enter a different room if they chose a wall which has door.

- There is also a Enemy, which walks around different rooms. If present in the same room, takes away all your items

- A player has an inventory which has list of items

- a item can be food or weapon

User should be able to start a game and be given set options(in text) of what command to execute, like pick up item in current room, walk north, east, south, or west, or undo action to return to previous state.

- 0of 0 votes
You are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.

Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png

In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.

Input :

First line is a positive integer N, number of horizontal and vertical lines.

Second line is positive integer M, number of segments removed.

Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.

Output :

Is the total number of squares in the figure with all sides along the remaining lines in the figure.

Sample Input :

4

4

H,2,1

H,3,1

V,2,2

V,2,3

Output :

5

Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.

- 0of 0 votes
// Create a numeric binary tree structure/classes that have left and right children and an integer numeric value.

// Write a function 'isBalanced' for a node that returns true if the sum of all the children on the left is equal

// to the sum of all the children on the right.

//Example:

// [12] [12].isBalanced() -> True. [3, 3]

// / \

// [3] [1] [1].isBalanced() -> True. [2, 2]

// / \

// [2] [0]

// / \

// [2] [0]

// - Part I: setup and isBalanced() function

// - Part II: implement “allBalancedNodes()” <— given a node, finds all balanced children

// allBalancedNodes(12) -> returns a list of balanced nodes: { [1], ... }

- 0of 0 votes
Given a fully connected graph with n nodes and corresponding values. One node can interact with other node at a time, to replace/ignore/add its value to other node’s value. Assuming this operation takes 1 unit of time, how much time would it take for all the nodes to have value equal to sum of all the nodes.

Examples : Given a graph with values {1,2,3,4}, find total time it takes, such that all nodes have value as 10.

I am assuming it can be done in O(N).It will take basically two traversals, one for calculating the sum of values of nodes(first traversal), other for replacing the value of the nodes(second traversal).

It will take 2*(no of nodes) time.

Are there any better ways possible ?

- 0of 0 votes
Implement a function that returns whether a string made of different bracket characters is well formed or not.

For example,

"{({})[]}" is a well formed bracket string

"{[](}" is not a well formed bracket string

Needless to say any single brackets are automatically counted as not well formed

- 0of 0 votes
Design a system that supports updating table with options to discard the updates. It should have the following functions:

`- create(String: rowName) #cannot be called until startTransaction has been called - delete(String: rowName) #cannot be called until startTransaction has been called - update(String: rowName) #cannot be called until startTransaction has been called - startTransaction() #start transaction operations( create/delete/update) - commitTransaction() #apply transaction to the actual Table( can be array-of-objects ) - discardTransaction() #discard any transaction applied thus far`

Rough impl is acceptable as long as the design is displayed correctly.

- 0of 0 votes
Given a list of employees and their bosses as a CSV file , write a function that will print out a hierarchy tree of the employees.

- 0of 0 votes
I was asked this question for the above role:

Create a fixed size cache which is fully associative. The entries are evicted based on the rank. for any entry added, the function int getEntryRank(entry) will return its rank which will not change on lookup

db_read_entry() to get the entry from db

Part 2) The rank will change on lookup`My solution was: a hashtable (unordered_set<entry>) and a priority queue <pair<int, entry> > lookup(entry) { hashtable lookup. if found, return the entry (O(1)) // otherwise (not found) if limit reached, then // evict the priority queue top, entry e = db_read_entry(); // expensive op //insert the entry into the hash set, //insert pair<int, entry>(get_entry_rank(entry), entry) into the priority queue. (O(logn)) return entry; } Part 2: The rank change on lookup Since the priority queue does not provide the key(hash key) value to be modified, and only provide access to top entry. I propose change in the associated ds for hashset, My proposal was: create an associated binary tree(std::set) with the hashmap (map of entry as key, and the iterator entry in the std::set of entries) . I used iterator to avoid look up for entry into the set during each entry lookup in the hashset. The set contains the [rank information + entry]. On look up, the entry into the set(of rank) is looked up (O(1)) and then erased, and then insert back after recaulated rank value.The iterator inrto the hash_set is also updated with this new iterator. On limit reached, the tree is searched for min value. from that min value item (the rank and the entry), the entry is looked up into the hash_set, and hence removed from there too. The rest of the process is the same as lookup as described below. I believed my slution was faor enough O(1) look up, if not found. the look up (with const rank) O(logn) + db access time. db access time dominate the O(logn) hence this logn (to insert into the priority queue,(or pop and insert into the priority) does not matter For changing rank: The binary tree lookup (O(1) since the hash_map has the iterator update of the rank, (lookup and removal of the rank entry in the binary tree O(1), and insert is O(logn). Hence each operator (lookup, evict and lookup, excluding the db access) will take O(logn) instead of O(1). I was rejected because of not optimize solution (performance is not good). I am wondering whether the solution was not good even though it was phone interview and I have to work within the time frame of 25 minutes. or the interview process is just unrealistic. Please share your solution so that I can see where I failed`

- 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