## Data Structures Interview Questions

- 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?

- 0of 0 votes
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.

- 0of 2 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

- -1of 1 vote
Difference between a crash and exception.

Difference between macros and inline functions.

Mfc: message maps and virtual functions.

Different calling convention.

Late n early binding...

Garbage collector algorithm. When gc will fail to clean the memory.

How to know heap size, crash dump analysis, What is a stack n how to know stack memory size.

Commands in windbg.

Questions on Critical section, mutex, semaphores. Can we use mutex in single process and how?

Working of MSIL and JIT COMPILER.

Can a C# code, use c++ code and call kernel functions like createfile.

Areas: dot net, oops, operating systems, thread synchronization.

Difference in execution steps of c++ and c# code

- 0of 0 votes
How to impliment Google map

Data Structure and algorithm.

1. Zoom in/out

2. horizontal/ vertical.

Assumtion - all the image of earth with pixel\Any other assumption is allowed

- 0of 0 votes
How google map implemented ? zoom in , zoom out, moving horizontal and moving vertically.

Give data Structure and algorithm.

Given all the data from satellite which revolve around earth in spiral way.

- 4of 4 votes
Given a Sorted integer array which is rotated N number of times. You have no idea what that N is. An element in the array can occur more for any number of time. Write a method to search the position of a given element. If there are more than one of the same element, return the position of the first element.

- 1of 3 votes
JAVA:

Given an array say of length 1000; Pick up every value from every 20th index and store it in a separate array. Make sure to loop through all the elements in the array. Example: newArray1 = {0, 20, 40, 60, ..};

newArray2 = {1, 21,41, 61, ..};

- 0of 0 votes
Given an array say of length 1000; Pick up every value from every 20th index and store it in a separate array. Make sure to loop through all the elements in the array. Example: newArray1 = {0, 20, 40, 60, ..};

newArray2 = {1, 21,41, 61, ..};