## Data Structures Interview Questions

- 0of 0 votes
give me the code for :

Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.

Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.

(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)

let me know the best and optimised way of writing this code.

Also i suggest people to aviod using inbuilt functions as much as possible

My Answer is as below in perl`#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";`

- 1of 1 vote
Given an array say [0,1,2,3,5,6,7,11,12,14,20]

given a number say 5.

Now find the sum of elements which sum to 5

eg:2+3=5, 0+5=5 etc.

I guess the interviewer wanted all possible combinations eg 0+2+3=5, etc

- 0of 0 votes
How to find starting of loop in a link list in case looping somewhere.

For ex: 1->2->3->4->5->3

- 0of 0 votes
Given a list with duplicate values find the first unique elements in it.

for eg: BH BH F AL HJ AL HJ PK

so answer is F

- 1of 7 votes
Given an excel column number convert it to excel column alphabet and reverse.

Example : If column number(starts from 0) = 26 : Column alpha = AA.

- 1of 1 vote
Print all paths of a binary tree from root to leaf.

Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice).

- 0of 0 votes
Compare time complexity of insert and search functions in HashMap, Array, Linked List and Queue

- 0of 0 votes
You are given a large set of integers, which are not sorted. Figure out a method to retrieve the largest 1000 elements, in O(n) time.

- -1of 3 votes
how to print this pattern

input N=4

output :

4444444

4333334

4322234

4321234

4322234

4333334

4444444

input N=3

output :

33333

32223

32123

32223

33333

- -1of 1 vote
Print the Pattern

input N=4

output :

4444444

4333334

4322234

4321234

4322234

4333334

4444444

input n=3

output :

N=3

33333

32223

32123

32223

33333

- 0of 0 votes
There is a file which contains N words. There may be M anagrams in that file, K words on each anagrams. K>=1, M>=1, N>=1. You need to write an algorithm which will create one list for each anagram with k words and group all M lists with one data structure

- 1of 1 vote
Find your own method to balance an unbalanced binary tree.(you must not use existing methods like AVL, red black or b trees)

- 0of 0 votes
Convert a sorted integer Array to balanced binary search tree. This is very simple one and I could do it in O(n) time and O(1)extra space

- 0of 0 votes
Given 2 sorted linked list , merge them into single sorted list. Change the pointers, don't copy data

- 0of 0 votes
Given a read only linked list with next and random pointer , clone the list

- -1of 1 vote
delete all the nodes from a binary tree that lie on a path whose sum from root to leaf is less than a given value K. Twist was that the node values can be any integer. It may be a negative number.

- 0of 0 votes
Data structure to push, pop and find min element in O(1) time.

- 0of 0 votes
Given a linked list like a1-a2-a3-a4-b1-b2-b3-b4. Convert it into a1-b1-a2-b2-a3-b3-a4-b4

- 0of 0 votes
program to pruning a binary tree

- 2of 2 votes
Write a function in C to create a new BST which is the mirror image of a given tree.

- -2of 2 votes
Design a meeting scheduler. The solution I came up with was to create an array of intervals for each day, so if intervals is 15 mins, then array size would be 24*4. However, if interval is small, that will substantially increase the size of the array, and that might be considered as a waste of space, though it supports O(1) look up. I was wondering if there is any other way to do this. I think we might be able to keep a sorted array of meetings sorted by start time, so look up would be O(logn). But insertion in the middle of the array would take O(n) since it requires data shifting.

- -2of 2 votes
Design a meeting scheduler. One way is to use an array to represent each interval, like every 15 mins. Although it provides O(1) look up, if interval is small, it seems like we are wasting a lot of space. Any alternative approach that can save space? If we keep a sorted array of meetings sorted by start time, look up will be O(logn), but inserting the new meeting in the middle of the array will require shifting elements, which is O(n).

- 0of 0 votes
Write a function in C to create a new BST which is the mirror image of a given tree.

- -5of 5 votes
If you have data coming in rapid succession what is the best way of dealing with redundant data?

- 2of 2 votes
I was asked a question in an interview.

On an office floor , there are e entities - Walls , Cubicles , Coffee Rooms.

In what data structure we should store this design that when a new member joins the company , the cubicle number which is empty and next closest to any coffee room should be assigned to it.

Basically , data structure DS.pop() should return that cubicle number in the most efficient way.

A Person can walk through cubicles to reach a coffee room but not through walls.

- 0of 0 votes
How you can find whether a link list contains a cycle or not?

- -1of 3 votes
Given a log file from a website which contains the user ID and the accessed URL, find the TOP "sequence" of 3 urls amongst ALL visitors of the website. The sequence of urls have to be in sequence as they are accessed.

My solution is Two hashtables and one MaxUrl object. One hashtable<String,String> userName as key and url sequence as value, where url sequence is three url contatenated by a special character like '#' (google#amazon#yahoo). This value is in FIFO manner. For each value, we check with the second hashtable and see if they exist before, if yes, increment the count, if no, insert the new sequence with count set to 0. So second hashtable<String, Integer> url sequence as key and count as value. Keep a curr_Max to store the current max count, when exceeded, updates max_urlSequence.

Any suggestion?

- 0of 0 votes
design a data structure for caching the result of "int getSmallestBiggerPrime(int)" so that the client side can reduce the trips to the server as much as possible. There are some examples in format of input->output: 1->1, 2->2, 3->3, 4->5, 5->5, 6->7, 7->7, 8->11, 9->11...

The interviewer did not say whether to use Least Recently Used (LRU) or Most Recently Used (MRU). But he gave a requirement using an example, suppose the user inputs 6 and gets 7 last time, the next time when he inputs 7, there should be no server trip to get 7 as the result.

- -1of 1 vote
The final question was just how to write a connection pool (i.e, a class that returns connections to the user, and if the user is done, returns them back to the pool)

- -1of 1 vote
How do you design a Maze and what kind of data structures you use for Maze. In addition, write a method to print the shorted path from start to end point.