## Data Structures Interview Questions

- 0of 0 votes
Given a 2 D array with m Entry points (which are on the edges) and n exit points which are on the edges give the total number of paths that are possible.

- 2of 2 votes
Phone Interview with Collabedit.

/** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/".

* Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands.

* Each operand may be a number or another expression.

* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + *

*

* @param ops a sequence of numbers and operators, in Reverse Polish Notation

* @return the result of the computation

* @throws IllegalArgumentException ops don't represent a well-formed RPN expression

* @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero

*

* <p>Some sample ops and their results:

* ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5

* ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7

*/

- 0of 0 votes
design and implement a calculater that can calculate expressions like:

+ 2 4

* 8 ( + 7 12)

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )

(PS:all items are space delimetered.)

Example answers

+ 2 4 => 2 + 4 = 6

* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152

( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148

- 1of 1 vote
there are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)

Write two methods called "getNumber" and "requestNumber" as follows

Number getNumber();

boolean requestNumber(Number number);

getNumber method should find out a number that did not assigened than marks it as assiged and return that number.

requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.

design a data sturucture to keep those numbers and implement those methods

- 1of 1 vote
You are given a binary search tree and a positive integer K. Return the K-th element of the tree.

No pre-processing or modifying of the tree is allowed.

- 0of 0 votes
You are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).

Return the number of sequences of elements (groups of consecutive elements), pointed by the array.

For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.

Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]

- 0of 0 votes
Count number of BST.

We are given N Nodes ,each having unique values in[1,N] how many different Binary search tree are possible using all of them.

- 0of 0 votes
what are real applications of avl tree?

- 1of 1 vote
Write a function that does an in-order traversal of a tree and prints out the contents (Assume each node has 1 piece of content which is an integer).

Write this function without using recursion (you can assume a library that has stack/queue/list objects with some standard methods is available for use by you).

What is the maximum size your stack can grow to and what is the expected size that your data structure can grow to assuming that the tree has n nodes?

- 0of 0 votes
Design a TinyURL like Service.

- 0of 0 votes
how to design a relation functionality. similar to facebook , how to hold friends objects for a user profile , so that that is easily searchable . how to use cache for this?

- 3of 3 votes
How can you design a data structure that can do the following operations in O(1) time:

Insert, Delete, Search, Max which returns the maximum number

I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?

- 2of 2 votes
Constructing Bridges:

A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.

Construct as many Non-Crossing Bridges as possible.

Input:

Above Bank >> 7 4 3 6 2 1 5

Below Bank >> 5 3 2 4 6 1 7

are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Output:

(1,1) (3,2) (4,3) (6,4) (7,5)

- 0of 0 votes
Give a tree (any tree, can be a binary. I told the interviewer that I assume it is binary tree and he said that is fine). Print the tree content on the screen one tree level per line

i.e.

if a tree is like this:

a

/ \

b c

/ /

e f

The output would be

a

bc

ef

Too bad, I was only able to make it print on one line instead of separate line. Until after the interview is over. Then I figure the final answer.

- 1of 1 vote
Given a 2^31 x 2^31 tic tac toe board, describe how you would store the state of the game to check if there is a winner.

- 0of 0 votes
A binary tree represent an organization hierarchy. The root node is the CEO and etc. design a algorithm to print the tree level by level.

- 0of 0 votes
Check if 2 link lists merge or not. If yes, return the 1st common node.

- 0of 0 votes
Design Maps: You have set of [lat, long] for all famous locations. Given your position [lat, long] return all famous locations within r radius of your position.

- 0of 0 votes
You have set of [lat, long] of all famous locations. Given your position [lat, long] return all famous locations within radius r of your position

- -1of 1 vote
Implement a vector-like data structure from scratch.

This question was to be done in C or C++.

Discussion topics:

1. Dealing with out of bounds accesses.

2. What happens when you need to increase the vector's size?

3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back

- 0of 0 votes
Design a queue (FIFO) structure using only stacks (LIFO).

Code is not necessary.

Follow-up: provide a complexity analysis of push and remove operations.

- 0of 0 votes
A parent array P is given where P[i] denotes the parent of the ith node in the tree(the tree is generic). Parent of root is indicated with -1. I need to find the height/depth of tree. (Best sol in O(n))

- 0of 0 votes
Given ~300k words with an average length of 7 in a file.

All words are dictionary correct words.

Print all the anagrams that are present in this list of words without repeating them.

E.g. if the list has:

ACT

BAT

CAT

TAB

TAC

print:

ACT, CAT, TAC

BAT, TAB

- 0of 0 votes
Write a function that takes a list of positive integers as an input, and returns all of the pairs of integers it contains that sum to 100. You can assume that all inputs are between 1 and 99.

- 6of 6 votes
Given a string (1-d array) , find if there is any sub-sequence that repeats itself.

Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated

2. abba <---- No, a and b follow different order

3. acbdaghfb <-------- yes there is a followed by b at two places

4. abcdacb <----- yes a followed by b twice

The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.

In the sense, it should be checked for every pair of characters in the string.

- 3of 5 votes
Write a program to implement Double Linked List from Stack with min. complexity.

- 2of 2 votes
The stepping number:

A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.

Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.

- 3of 5 votes
You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C & D are integers values in the array.

Eg: Given [3,4,7,1,2,9,8] array

The following

3+7 = 1+ 9 satisfies A+B=C+D

so print (0,2,3,5)

- 1of 1 vote
We have 'n' patients and 'm' problems. The problems are of boolean type. Eg diabetes problem would be 'T' if a patient has it or 'F' otherwise. Suggest the data structure you would store this scenario on?

Q: We have a set of problems {diabetes, liver disease, kidney disease} find all the patients who have at least the 3 problems from the set.

The number of patients can be huge (n).

The number of problems not comparatively huge (m).

Which would be the best data structure to store these kind of records, so that we have a better search time.

- -1of 1 vote
A Load Balancer has the following functions:

`getHost() addHost(String) removeHost(String)`

Implement these functions using any data structure you wish. Also indicate the average performance for each function and what you expect to be its call count in a typical system with respect to each other of the three functions. In other words, how often do you expect getHost() to be called compared to addHost(...)?

Constraints:

Hosts are unique.

getHost() returns a random host from the host group