## Data Structures Interview Questions

- 2of 2 votes
Question : Given a set of N numbers [1,N], partition them into 2 disjoint subsets based on a set of K queries.

Each query is of the type (n1, n2) where n1 and n2 are distinct numbers from the set and n1 and n2

belong to opposite subsets.

Example:

Input:

Input:

N = 4

K = [(1, 2), (1, 3), (2, 4)]

Output:

Set 1 : (1,4)

Set 2 : (2,3)

- -2of 2 votes
word look up

- -1of 1 vote
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], ... }

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