## Data Structures Interview Questions

- 0of 0 votes
Given an array of integers and a number. WAP to find the pairs which sum of upto given number.

I solved it. Then he asked about writing test cases for this function.

I wrote below test cases

1.) All the elements should be number.

2.) Length of array should not be 0.

3.) Array itself should not be null.

4.) Given number, arrayLength can be represented by 32bits or 64 bits.

5.) number should not be negative.

6.) Input does not has pair, It should return false

7.) Input has pair, It should return true

8.) Input has all negative values and pair exists, then function should return true

9.) Input has all negative values and pair does not exists, function should return false

He told that he is looking for more test cases. Can you guys think of some more complex test cases.

- 1of 1 vote
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 0of 0 votes
Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree.

For example:

Given tree,

1

2 3

4 5 5 4

6 6

output: trus

- 0of 0 votes
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 1of 1 vote
Write a function that accepts two character arrays each represents a floating point number and return their sum in character array.

For example function accepts "23.45" and "2.5" and return their sum "25.95".

Restriction: We cannot use predefined functions / methods or parsing. We have to go with basic operations.

- 0of 0 votes
Which structure can be used to return the lastly added node and remove it from the collection and also will allow to peek the highest valued node without removing it from the collection. What is the time and space complexity for Push, Pop and Peek actions

- 0of 0 votes
In a Formula-1 challenge, there are n teams numbered 1 to n. Each team has a car and a driver. Car’s specification are as follows:

– Top speed: (150 + 10 * i) km per hour

– Acceleration: (2 * i) meter per second square.

– Handling factor (hf) = 0.8

– Nitro : Increases the speed to double or top speed, whichever is less. Can be used only once.

Here i is the team number.

The cars line up for the race. The start line for (i + 1)th car is 200 * i meters behind the ith car.

All of them start at the same time and try to attain their top speed. A re-assessment of the positions is done every 2 seconds(So even if the car has crossed the finish line in between, you’ll get to know after 2 seconds). During this assessment, each driver checks if there is any car within 10 meters of his car, his speed reduces to: hf * (speed at that moment). Also, if the driver notices that he is the last one on the race, he uses ‘nitro’.

Taking the number of teams and length of track as the input, Calculate the final speeds and the corresponding completion times.

- -1of 1 vote
Write code to rotate a square matrix:

Input:

1 2 3

4 5 6

7 8 9

Output:

4 1 2

7 5 3

8 9 6

- 0of 0 votes
You are given two objects, Student and Course, and there exist a many to many relation between them. One student can be enrolled for more than one course and there can be many students enrolled for a single course. Design an effective data structure to store such data keeping in mind that the time complexity for search should be optimum. A search can be for the list of students enrolled for a single course, or for the list of courses a single student is enrolled.

- 0of 0 votes
Find the depth of Binary search tree without using recursion?

- 0of 0 votes
Implement a program to reverse the linear linked list in pairs. it should handle both even number of nodes and odd number of nodes. if odd number of nodes, the last node will be the last node after reversion.

Do not move the data in the nodes. Do manipulate node pointers/references. the nodes themselves need to be manipulated, not just the data in the nodes.

For example, if the initial linear linked is,

1->2->3->4->5

after reverse it should be,

2->1->4->3->5

- 0of 0 votes
Implement a function that checks if the given binary tree is binary search tree(BST). Use tree operations to solve this. do not try solving by pre-order traversal of the tree and then checking if the array is sorted.

instead, traverse the tree for checking if it is BST.

- 0of 0 votes
Write a function that takes two arguments one array of integers that ranges between 0 and 9 and second the target sum(again integer). It produces all permutations strings of the input digits that equals the target sum.

For example, if input is array 2, 3, 5 and target sum is 10, then the output should be:

22222 because 2+2+2+2+2 = ,10

2323 as 2+3+2+3 = 10

3232

55

2233

3322

532

235

352

etc.,

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