## Data Structures Interview Questions

- 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

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