## Data Structures Interview Questions

- 0of 0 votes
Design a data structure to keep track of top k elements out of 2 billion records.

Each record is numberd with a key which is 30 bit and a number which is count of how many times the customer has visited us.

Come up with an data structure so that the updation of element in 2 billion records will be faster.

Getting top k element will be faster

- 0of 0 votes
How can you determine if an array is pre order representation of a binary tree. I started with the logic of creating binary tree using a pre order array and failure to create the tree will mean that the array is not a pre order representation, but got stuck in middle.

- 0of 0 votes
New data structure where tree is reversed. Leaves are at the top and root at the bottom. Given two nodes in such DS find the least common ancestor in such tree.

- 0of 0 votes
Return the number of pairs of nodes which violate the binary search tree property given a root node. I was lead to the discussion of finding it by handling for different cases like ancestors, siblings, but came to know interviewer was looking for simpler solution. Not sure if it is fair to get this as make/break questions with out any other question for experienced candidate.

- 0of 0 votes
Suppose you have a huge data of students. This data is in RAM (around 48 GB). Student has following attributes:

1) RollNo

2) Name

3) Address

Now I need to implement three method:

getStudentByRollNo(int rollno)

getStudentsByName(String name)

getStudentsByAddress(String address)

In what data structure I can keep these students so that these methods can return the results really fast.

- 0of 0 votes
Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}

ar2[] = {6, 7, 20, 80, 100}

ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}

ar2[] = {3, 4, 5, 5, 10}

ar3[] = {5, 5, 10, 20}

Outptu: 5, 5

- 0of 0 votes
What are the advantages of an array over a linked list? and vice versa.

- 0of 0 votes
This was design question.

I have a single timer class which is running on a single port of a machine.

There are multiple clients that can send request to this timer class as follows.

request_timer (x)

where x is time in seconds.

when the timer class gets this request from a client it starts a timer object of x seconds and after x seconds are over it sends an event to the requesting client and client can handle the event the way it wants to .

The problem is if you have large number of clients then the timer class is single point of congestion and the clients may receive the event from it after a long time.

What are the good ways to scale this for a large number of clients?

- 0of 0 votes
Give a path get it's canonical form. So for example if you have path in the form e/../../a/d/./../b/c then you should return a/b/c.

I have the solution but it's not the most optimal or the best solution. I just wanted to see what others have.`public String canonicalPath(String path){ if(path == null || path.isEmpty()){ throw new RuntimeException("incorrect path provided"); } String[] chunks = path.split("/"); Stack<String> s = new Stack<String>(); List<String> arr = new ArrayList<String>(); for(String chunk: chunks){ if(chunk.isEmpty() || chunk == "."){ System.out.println("skipping"); }else{ if(!s.isEmpty() && s.peek().equals("..") && !chunk.equals("..")){ while (!s.isEmpty()) { if(s.peek().equals("..")){ s.pop(); }else{ s.pop(); break; } } s.push(chunk); }else{ s.push(chunk); } } } StringBuffer sb = new StringBuffer(); List<String> list = null; if(!s.isEmpty()){ list = new ArrayList<String>(s); } if(list != null){ for(String ss : list){ sb.append("/"+ss); } } return sb.toString(); }`

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