Data Structures Interview Questions
- 0of 0 votes
AnswersWebsites like Pandora recommend music based on user preferences. What kind of information would you need in such a design?
- tielongs October 31, 2013 in United States| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer Intern Data Structures - -3of 3 votes
AnswersQ1. What Data structure would you use if you have to store millions of numbers.
- himanshu October 26, 2013 in India| Report Duplicate | Flag | PURGE
Nextag Software Engineer / Developer Data Structures - -1of 1 vote
AnswersGiven a catalog of books, with the following attributes
- it_code October 26, 2013 in India
Name
Author
Publisher
Publisher Year
Price
Inventory count
Implement functionality for
1. get / search all books (by author/by name/by publisher) Also need to support partial string search
2. Update catalog (book)
Features:
* Explain why you use a particular data structure.
* Free to choose any language, C/C++/C#/Java/Perl/Python.
* Need to design the classes appropriately, that can allow scalability, encapsulation.
* Need to allow search similar to that currently provided by Flipkart.
Code in around 1 hour.| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Data Structures - -1of 3 votes
AnswersGiven a Tree (not essentially a BST). Find the right most cousin of a given node.
- juilee October 22, 2013 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven two values in a Binary Tree - how do you find the lowest common ancestor?
- MarkLennartPrice October 21, 2013 in United States| Report Duplicate | Flag | PURGE
Data Structures - 8of 10 votes
AnswersComplete the below function which takes an arraylist and displays the list in the expected output
- AP October 07, 2013 in United States
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
// your code
}
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) { ... }
}
}
Example input:
List<Relation> input = newArrayList();
input.add(new Relation(“animal”, “mammal”));
input.add(new Relation(“animal”, “bird”));
input.add(new Relation(“lifeform”, “animal”));
input.add(new Relation(“cat”, “lion”));
input.add(new Relation(“mammal”, “cat”));
input.add(new Relation(“animal”, “fish”));
TreePrinter.printTree(input);
Expected output:
line 1: lifeform
line 2: animal
line 3: mammal
line 4: cat
line 5: lion
line 6: bird
line 7: fish| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHow would you assign numbers if you were AT&T, describe a data structure
- juny October 07, 2013 in United States for Azure| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Data Structures - 2of 2 votes
AnswersGiven an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b.
- vik October 07, 2013 in United States
Required complexity: O(n^2)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Arrays Data Structures Ideas Matrix - -2of 2 votes
AnswersHow do you check if a binary tree is balanced or not? Please traverse through this code and explain how the complexity is O(N).
- sivaji8 October 03, 2013 in United States
public boolean isBalanced(Node root){
if(checkHeight(root) == -1){
return false;
}else{
return true;
}
}
private int checkHeight(Node root){
if(root == null){
return 0;
}
int leftHeight = checkHeight(root.left);
if(leftHeight = -1 ){
return -1;
}
int rightHeight = checkheight(root.right);
if(rightHeight = -1){
return -1;
}
int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > 1){
return -1;
}else{
return Math.max(leftHeight, rightHeight) + 1;
}
}
Please traverse for the following tree.
A
/ \
B C
/ \ / \
D E F G
\
H| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 2of 4 votes
AnswersGiven two trees, find if tree 2 is the mirror image of tree 1.
- techpanja October 02, 2013 in United States| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Data Structures - -4of 6 votes
AnswersRotate a M*N matrix by 90 degree.
- sivaji8 October 02, 2013 in United States
Is this answer right?
public void rotateMN(int[][] input){
int i = input.length;
int j = input[0].length;
int m = j;
int n = i;
int[][] newArray = new int[m][n];
for(int j = input[0].length-1, m=0; ;i--, m++ ){
for(int i = input.length-1, n=0; i >= 0 ; i--, n++){
newArray[m][n] = input[i][j];
}
}
}
Will this also work for N*N matrix rotation by 90 degrees?
The time complexity is O(N) since it just traverse the input matrix and copy it to the new matrix. The space complexity is (MN) + (MN) = So MN.
Is it possible to do rotation for M * N matrix in space? If so please provide that answer
Whats this space and time complexity?| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersQuestion 3 / 3 (Find first unique character)
- Harjit Singh September 27, 2013 in India for TCS
Find the first unique character in a Stream. Please note that you are being provided a stream as a source for these characters.
The stream is guaranteed to eventually terminate (i.e. return false from a call to the hasNext() method), though it could be very long. You will access this stream through the provided interface methods.
A call to hasNext() will return whether the stream contains any more characters to process.
A call to getNext() will return the next character to be processed in the stream.
It is not possible to restart the stream.
If there is no unique character, then return the character '#'. # won't be any character in the character stream.
You just have to complete the function getUniqueCharacter() using the functions hasNext() and getNext() which are already defined.
Example:
Input:
aAbBABac
Output:
b
Input:
aBBa
Output:
#| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Data Structures - 1of 1 vote
AnswersIt was a pretty interesting question.
- b2010 September 25, 2013 in United States
Assume that you are given a fixed set of floating point numbers. Now given a new floating point number 'x', the goal is to efficiently find the number that is closest to 'x' from the fixed set. Question is: what data structure will you actually use for storing the fixed set of floating point numbers to achieve this?
Edit:
I missed to add. The interviewer further mentioned that I can not sort and that I can use any amount of time for creating the data structure (meaning this need not be efficient).
Since, I am not allowed to 'sort', I assumed that I can not use BST as I will have to compare numbers while populating the tree. But I didn't clarify it with him; I should have in hindsight.| Report Duplicate | Flag | PURGE
Amazon Research Scientist Data Structures - 0of 2 votes
AnswersGiven a tree (not necessary a Binary Tree) print (draw) the tree in original structure with proper formatting.
- Rahul September 20, 2013 in India| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm Data Structures - 5of 5 votes
AnswersA link list contains following elements
struct node{ int data; node* next; node* random; }
Given head of such a linked list write a function who copies such a linked list and returns the head of the new list. So if in the original list first node points to fourth node in random the copy should have the same relation. The random pointer can point to any node including itself and more than two nodes can have random pointer to the same node.
- vik September 13, 2013 in United States
Required time complexity O(n) and no extra space can be used (apart from the newly allocated memory which you will need to create the new list)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures - -2of 4 votes
AnswersWrite a thread safe data structure such that there could be only one writer at a time but there could be n readers reading the data. You can consider that incrementing or decrementing a variable is an atomic operation. If more than one threads try to write simultaneously then just select one randomly and let others wait
- vik September 13, 2013 in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures Operating System - 0of 0 votes
AnswersDesign a web crawler to dump all the pages of a given website (URL) onto disk. So basically it saves pages which is related to the website (for instance dump all pages of aws.amazon.com) and do not crawl the links outside the website
- vik September 06, 2013 in United States
I coded it in python and then they asked what is the internal structure of dict in python and why or why not it is fast| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Coding Data Structures Python - -1of 1 vote
AnswersDelete the repeated elements in a singly linked list in O(n) time complexity without using extra space. Linked list contains elements in unsorted order
- Saurabh Singhal August 22, 2013 in India
P.S. - Sorting is not allowed| Report Duplicate | Flag | PURGE
VMWare Inc Intern Coding Data Structures Linked Lists - 3of 3 votes
AnswersA standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner?
- Saurabh Singhal August 17, 2013 in India
P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8| Report Duplicate | Flag | PURGE
Goldman Sachs Intern Algorithm Coding Data Structures Trees and Graphs - 0of 0 votes
AnswersSort the array(have to implement the equals method in Cat and Dog).
- trish August 17, 2013 in United States
Cat c = new Cat("Snow Ball");
Dog d = new Dog("Max");
array = {c, d, ... };| Report Duplicate | Flag | PURGE
Symantec Principal Software Engineer Data Structures - -1of 1 vote
AnswersYou have two threads "A" and "B" and an integer "Count". "A" can increment the count up to 10(stops after that). "B" can decrements the count up to 1(stops after that). Print out the count after increment and decrements.
- trish August 17, 2013 in United States| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersCount the duplicates in the array ?
- trish August 17, 2013 in United States
array = {"IBM", "Amazon", "Google", "IBM"}
Another question from "Cracking the Code".| Report Duplicate | Flag | PURGE
Data Structures - 0of 0 votes
AnswersRemove duplicates in the array ?
- trish August 17, 2013 in United States
array = {"IBM", "Amazon", "Google", "IBM"}
Another question from "Cracking the Code".| Report Duplicate | Flag | PURGE
Data Structures - -2of 2 votes
AnswersReverse the values in the array.
- trish August 17, 2013 in United States
Here is the array = {1, 2, 4, 5, 7}| Report Duplicate | Flag | PURGE
Data Structures - -2of 8 votes
Answersits easy but still!!
find the largest subarray with equal number of 0's and 1's.
example 001010101
output:8
- viva August 14, 2013 in United Statesint subarray(int arr[],int n) { int count=0; for(int i=0;i<n;i++) { if(a[i]==0) count++; else count--; } if(count==0) return n; else { if(count>0) return n-count; else return n+count; } }
| Report Duplicate | Flag | PURGE
Groupon SDE1 Data Structures - 4of 4 votes
AnswersConsidering a stream of integers coming in. Design a datastructre to store only n of them. Insert if if does not exist in the datastructre. And if it reaches n, remove the first one inserted into the datastructure.
- anonymous August 11, 2013 in India
Datastructure should provide, addition, deletion and search all in O(1) time.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - -1of 1 vote
AnswersThe question was that you need to implement virtual directory using dynamic structure . For example :-
- ankitkumar2010@vit.ac.in August 11, 2013 in India for Zoho
VIT is the root directory then
VIT>CS
VIT>Building Science
.
.
Then each department should have its branch
VIT>CS>CSE
VIT>CS>IT
VIT>CS>MCA
Furthermore each branch will have a number of files i.e
VIT>CS>CSE>file1.txt
VIT>CS>CSE>file2.txt
VIT>CS>IT>file1.txt
Note-No need to create actual files just store the name .
Each file should have properties :-
1) RO(Read Only) or WO(Write Only)
2) Hidden or Visible etc.
List of Commands :-
1) addFile(<file name>) to add file
2) addHiddenFile(<filename>) to add hidden file
3) setReadOnly<filename> to set read only property
4) gotoDir to go to a particular directory
5) listFiles to list files
6) listAllFiles to list all files including hidden files
7) details to display all details of files
8) delete to just to mark the file as deleted but you don't need to actually delete it.
I used nested structures to implement it. Can anyone give a more proper solution with the code?| Report Duplicate | Flag | PURGE
Software Engineer / Developer Data Structures - 2of 2 votes
AnswersI have a list of several million words unsorted.
- Anon August 08, 2013 in United States
How can you find the largest and the smallest words that can be typed by a single hand on a qwerty-style keyboard? Following the rules of finger placement, a word can either be typed fully on the left-hand side of the keyboard, the right-hand side, or both. Find the largest and smallest left-hand word(s), and the largest and smallest right-hand word(s).
given: millions of words, unsorted
given: set of left-hand chars - a,s,d,f,...
given: set of right-hand chars - j,k,l...| Report Duplicate | Flag | PURGE
Google Software Engineer in Test Data Structures - 1of 3 votes
AnswersIn a Binary Tree, weight of each node is described by the value of the node multiplied by the level (i.e. for root node value is 1* value in root node), And the weight of tree is sum of all the node weights.
- prabal77 August 06, 2013 in India
Find the minimum tree weight out of all the binary trees possible from a given set of numbers.
P.S: No input and no sample data provided| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures