Data Structures Interview Questions
- 0of 0 votes
AnswerWhen and where would you use the following data structures within the context of a virtual world? (array, linked list, hash table, binary tree).
- Anonymous May 27, 2010| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersRemove intersections of two single linked list and make one linked list. operations should be recursive.
- Sambit Sarkar May 27, 2010| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 1of 1 vote
AnswersRound-3-Qn-2)
- Arang May 26, 2010
- You are given two 4 digits prime numbers N1 and N2,
- You can change only one digit of N1 at a time.
- Resultant of changing a digit of N1 should also be a prime number.
How many number of digit changes (minimum) are required to convert N1 to N2?
Example:
Assume (8785, 8787, 8887, 9887, 9897) are prime numbers.
Lets say N1=8785 and N2 = 9897 then
change-1: 8785 => 8787
change-2: 8787 => 8887
change-3: 8887 => 9887
change-4: 9887 => 9897
So 4 digit changes are require to convert N1 to N2.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-2-Qn-2) Implement a data structure such that it provides push(), pop() and GetMax() operations and running time of all operations should be constant O(1).
- Arang May 26, 2010
Note: GetMax need not remove the max from the data structure.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-1-Qn-2) Given a binary tree, we need to create a matrix.
Example:
- Arang May 26, 2010A / \ B C / \ / \ D E F G |A|B|C|D|E|F|G| ------------------ A| B|1 (B is child of A) C|1 (C is child of A) D|1 1 (D is child of A & B) E|1 1 (E is child of A & B) F|1 1 (F is child of A & C) G|1 1 (G is child of A & C)
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-1-Qn-1) Find vertical sum of given binary tree.
Example:1 / \ 2 3 / \ / \ 4 5 6 7
The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
- Arang May 26, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersWritten-Qn-3) Given a binary tree and a number N, check is there any path exists in the tree such sum of the nodes in the path equals to N.
bool isPathExists(Node *root, int N)
Note: We can assume that node contains only positive integers
Example:1 / \ 2 3 / \ / \ 4 5 6 7
if N = 8, return TRUE
- Arang May 26, 2010
if N = 9, return FALSE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersWritten-Qn-2) Write complete working code (only the function) to traverse a binary tree in ZigZag order
void printTree(Node *root)
Example:1 / \ 2 3 / \ / \ 4 5 6 7
O/P: 1 3 2 4 5 6 7
- Arang May 26, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersWritten-Qn-1) Write complete working code (only the function) to check whether the given char sequence is valid.
- Arang May 26, 2010
bool isValid(char *str)
Example:
I/P: ()()().... O/P: Valid.
I/P: ())()(.... O/P: Invalid.
* We can assume that the input will have only squence of '(' and ')' chars.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersGiven an array with 100 balls (each ball is to be imagined as an element in the array). 99 are of same weight only 1 is not. Identify the ball.
- mr.anonymous May 25, 2010
Use the given scale function:
int scale(array_name, start_index, mid_index, end_index)
returns: -1 if the left portion is heavier
1 if the right portion is heavier
0 if both left and right portions are equal.
assumptions: left portion: array[start] to array[mid]
right portion: array[mid+1] to array[end]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
Answers0,1
- Anonymous May 25, 2010
2 - ABC
3- DEF
4- GHI
5-JKL
6-MNO
7- PQR
8- STU
9- VWXYZ
Each number represents the set of variables and When we input a number . it should be replaced by all possible string values corresponding. eg : if we enter 27190000.
It should output.
APV
APW
APX
APY
APZ| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Data Structures - 0of 0 votes
AnswersIn a company , there are three categories.A,B,C.
- Anonymous May 25, 2010
They want to give an increment.So if category C gets N% as increment. category B gets 2N% as increment and category A gets 3N% as increment.But the increment should be atleast 1% and The total updated salary should not exceed $50,000.
Print the increment and the total updated salary for a particular employee.
Assume all the required variables.| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Data Structures - 0of 0 votes
AnswersThere is a security keypad at the entrance of a building. It has 9 numbers 1 - 9 in a 3x3 matrix format.
- Anonymous May 25, 2010
1 2 3
4 5 6
7 8 9
The security has decided to allow one digit error for a person but that digit should be horizontal or vertical. Example: for 5 the user is allowed to enter 2, 4, 6, 8 or for 4 the user is allowed to enter 1, 5, 7. IF the security code to enter is 1478 and if the user enters 1178 he should be allowed. Write a function to take security code from the user and print out if he should be allowed or not| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Data Structures - 0of 0 votes
AnswersTake the user gives a set of numbers as input.Stop taking the input when he enters 0. Display the maximum odd integer and minimum even integer.See that the user inputs correct values as input.
- Anonymous May 25, 2010| Report Duplicate | Flag | PURGE
Epic Systems Software Engineer / Developer Data Structures - 0of 0 votes
AnswersQ)Which data structure would you suggest for auto completion feature in text typing like an application in iPhone?
- Optimistic May 21, 2010
A) I have no clue, initially I told him I can use a Binary Tree but I could not convince him why I would use that. then I told Hash tables.
Q) What is the disadvantage in using Hash tables?
A) Memory I told him. I don't know if that is a wrong answer.
Q) Difference between LinkedList and ArrayList
A) I told this correctly. this is an easy one.
Q) OK. I have two large files (10 MB) each how do you compare them and remove common elements in a file.
A) I told him split the files into 1 MB each and do an intersection on them get the result in another file and concatenate them back. But he asked me what datastructure I would use.
I was bowled. (This is the result of lack of proper preparation!!)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersRemove tail recursion from recursive inorder traversal in a BST. Also perform an iterative in order traversal.
- Anonymous April 28, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
Answerspros and cons of any two data structures of your choice (not allowed to choose linked list and arrays)
- dnivra March 26, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou have a tree with root 1. left of 1 is 2, right of 1 is 3. left of 2 is 4 and right of 2 is 5. left of 3 is 6 and right of 3 is 7.
- Anonymous March 25, 2010
Level is defined as: Level 1: 4
Level 2: 2
level 3 : 1,5,6
level 3: 3
level 7: 7
Print the sum of each level.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersDesign an algorithm to implement google like smart calculator. No button in the calculator. Just enter something like "98F to C" and it should convert 98 degree fahrenheit to celsius.
- Anonymous March 24, 2010
Calculation part is easy. Design the algorithm to understand what operation needs to be done, whether its temperature conversion or simple mathematics or length conversion| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
Answersfind head of Linklist
- aa March 23, 2010
An array of linked list nodes are given and act as pool of nodes.
A list use a free node from array to make new node.
When list want to free a node it just changes pointer.
Case 1: No initialization of nodes happen.
Case 2: Initialization of nodes happen. means next pointer is set to NULL.
Now look at array of nodes and find the head of linked list. Can you find it. Why or why not.
How to find optimally. Tell for both cases.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
Answers#1. Implement (in C++ or C#) a function that removes the nth element of a single linked list.
- abhays.1984 March 19, 2010
C++:
class Node
{
char* value;
Node* next;
};
Node** RemoveNth (Node** list, int n)
{
}
C#:
class Node
{
string value;
Node next;
}
Node RemoveNth(Node list, int n)
{
}
#2. Using the following table provide at least 5 test cases to test the function implemented in the previous part.
Node n Expected Result
~~~~ ~~~ ~~~~~~~~~~~~~~~~~| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Coding Data Structures Testing - 0of 0 votes
AnswersHow would you store pictures from Google's street view? (assume massive amounts of high quality pictures)
- Anonymous March 10, 2010| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
Answerswhy maps have constant time for retrieval, adding and deleting.. internally what happens?
- clrs March 04, 2010
explain how hash function in maps work..
how to handle collision of hash values?
what are tree maps?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures