## Data Structures Interview Questions

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

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

- 1of 1 vote
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.

- 4of 4 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)

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

- -1of 1 vote
package jp.co.worksap.global;

import java.util.NoSuchElementException;

/**

* The Queue class represents an immutable first-in-first-out (FIFO) queue of objects.

* @param <E>

*/

public class ImmutableQueue<E> {

/**

* requires default constructor.

*/

public ImmutableQueue() {

// modify this constructor if necessary, but do not remove default constructor

}

// add other constructors if necessary

/**

* Returns the queue that adds an item into the tail of this queue without modifying this queue.

* <pre>

* e.g.

* When this queue represents the queue (2, 1, 2, 2, 6) and we enqueue the value 4 into this queue,

* this method returns a new queue (2, 1, 2, 2, 6, 4)

* and this object still represents the queue (2, 1, 2, 2, 6) .

* </pre>

* If the element e is null, throws IllegalArgumentException.

* @param e

* @return

* @throws IllegalArgumentException

*/

public ImmutableQueue<E> enqueue(E e) {

return null;

}

/**

* Returns the queue that removes the object at the head of this queue without modifying this queue.

* <pre>

* e.g.

* When this queue represents the queue (7, 1, 3, 3, 5, 1) ,

* this method returns a new queue (1, 3, 3, 5, 1)

* and this object still represents the queue (7, 1, 3, 3, 5, 1) .

* </pre>

* If this queue is empty, throws java.util.NoSuchElementException.

* @return

* @throws java.util.NoSuchElementException

*/

public ImmutableQueue<E> dequeue() {

return null;

}

/**

* Looks at the object which is the head of this queue without removing it from the queue.

* <pre>

* e.g.

* When this queue represents the queue (7, 1, 3, 3, 5, 1),

* this method returns 7 and this object still represents the queue (7, 1, 3, 3, 5, 1)

* </pre>

* If the queue is empty, throws java.util.NoSuchElementException.

* @return

* @throws java.util.NoSuchElementException

*/

public E peek() {

return null;

}

/**

* Returns the number of objects in this queue.

* @return

*/

public int size() {

return -1;

}

}

- 0of 0 votes
How will you design, and what data structure will you use for a contact list in a cell Phone. It should support insert/modify/delete/search functionality like that provided in a cell phone.

Suppose some of the entries are

Aman

Amazon

Neha Aman

and we type 'ama'

then the result should show all the above three enteries.

Also it should be possible to search using phone numbers.

- 0of 0 votes
Given an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.

For example, "2,1,1,2", you can get (2+1)*(2+1)=9.

Follow up, if the number may be negative , how to solve it ?

- 0of 0 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- 0of 0 votes
Design a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.

- 1of 1 vote
How to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.

- 1of 1 vote
Design a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.

later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.

- 0of 0 votes
Can anyone provide implementation of Suffix tree and trie?

- 3of 3 votes
Given a complete binary tree, Find a Max element

- 0of 0 votes
Write a java program to find out 5000th number in the fibonacci series.?

For example:

5th number is 5.

6th number is 8.

10th number is 55.

5000th number is ????.

- -1of 1 vote
Write code to read from a file and build datastructure that helps you query products based on their category, title, author etc.

ItemNo , Product No (unique), Title, Author, Category

1 , 00000001, Cracking Coding Interview, Gayle Laakmann McDowell , Books > Business, Finance & Law > Careers > Job Hunting

2 , 000002, The Art of Captaincy, Robert James, Books > Biography > Sport > Cricket

- 1of 1 vote
Write a program to return minimum number of swaps required to convert this binary tree into a BST.

- -1of 1 vote
Draw a graph as a graph. Assume there is graphics library to draw lines and all. Just tell how will you order the vertices such that the edges don't intersect and they seem ordered.

- -1of 1 vote
struct st{

int a;

char *ptr;

}obj;

assign : a=10;

ptr="Hello world";

- 3of 3 votes
Create the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.

(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is

2, 7, 4, 9, 1, 5, 8, 3, 6

then the median is 5.)

Model the data structure for a component that would have these two methods:`@interface SampleHandler { - (void)addNumber:(NSNumber*)number; - (NSNumber*)median; }`

Justify your decisions. Calculate the complexity of each method.