Data Structures Interview Questions
- 9of 9 votes
AnswersQ: If you have all the companies that are traded, and live inputs are coming of which company is being traded and what is the volume, how do you maintain the data, so that you can carry out operation of giving the top 10 most traded companies by volume of shares most efficiently.
- Aditya April 14, 2013 in United States
A: I juggled between Hash Map and Max Heap. I said Max Heap, since I can take out top 10 companies in a jiffy with a Max Heap. But then he asked you will need to find a company everytime there is a trade, which will take quite some time in Heap. He pointed out that in real world scenario, number of trades happening, and hence searching of the company and updating it, will be many times more than finding top 10. Which bought me to HashMap. Updations can happen in Real time, while finding top 10 can be done in O(n) or O(nlog(n)) time.
Even that wasn't optimal obviously. The interviewer was very nice and friendly type guy. He stressed that at every trade, at most, only 1 company will change in my top 10. This hit me and got me to the correct answer that we keep all actual data in HashMap, but also maintain a MinHeap of 10 most traded company.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 2of 2 votes
AnswersQ: If I give you a new book, and ask you to create the index which is found at the end of the book, how will you do it.
- Aditya April 14, 2013 in United States
A: I said for constant addition time of words (and page numbers) in the data structure, we can use Hashmap or TRIE. But since output has to be in alphabetic order, we will use a Trie DS, where at the end of each word, we simple store a list of page numbers.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 0of 2 votes
AnswersHow do you remove duplicates from a dataset that does not fit into memory?
- Romonov April 14, 2013 in United States| Report Duplicate | Flag | PURGE
Spotify Software Engineer / Developer Data Structures - 0of 2 votes
AnswersHow can you implement a Hashtable with any given data structure
- Guest SVM April 12, 2013 in United States for AWS
What is hash function
How can you resolve collisions| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Data Structures - 0of 0 votes
AnswersGiven a huge file, design a data structure to output all possible anagrams of a particular word.
- xankar April 11, 2013 in United States
For Eg the file contains: "POT, OPT, TOP"
If I query for POT, I should get back all possible anagrams contained in the file.
--| Report Duplicate | Flag | PURGE
Goldman Sachs Senior Software Development Engineer Data Structures - 0of 0 votes
AnswersClass and Data Structure Design for a "metric" system to determine the top song of a band. Two Web Service calls:
- JSDUDE April 04, 2013 in United States
void play(String bandname, String songname);
String topSong(String bandname);
CONSTRAINTS: For this exercise we should constrain the design to a single server and do NOT use a database, but in memory data structure.
SAMPLE INPUT/OUTPUT
play("Guns N Roses", "Welcome To the Jungle");
topSong("Guns N Roses") => "Welcome To the Jungle"
play("Guns N Roses", "Sweet Child of Mine");
topSong("Guns N Roses") => "Welcome To the Jungle"
play("Guns N Roses", "Sweet Child of Mine");
topSong("Guns N Roses") => "Sweet Child of Mine"
scale the architecture| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures Object Oriented Design - 0of 0 votes
AnswersThere is a class
- Anonymous March 26, 2013 in United States
class vehicle
{
int door_numbers;
obj colour;//another class has int members Red, Green,Blue
bool has_ac;
}
there is a huge list of data of vehicles, the number of doors may vary to 1-million (imaginary vehicle :) ).
there may be millions of colors.vehicle may or may not have AC. How would you save this such that any combination
(say all blue cars with ac having 6 doors) may be accessed easily.
Discuss algorithm, complexity and testing strategy| Report Duplicate | Flag | PURGE
Student student Student student Algorithm Data Structures - 1of 1 vote
AnswerYou are given the task of creating the address book application for a smart phone. There are some
- PaulDaviesC March 23, 2013 in India
of the top level features you must implement.
1.There will be 1000+ phone book entries and user must get very quick response.
2.On default screen it shows the names of all people in alphabetical ascending order.
3.Using the search option, user can search and it will show only those names starting
with those characters which are typed in the search box.
You are supposed to compare two different data structures and list down the pros and cons of each
and finally recommend the best suited data structure.| Report Duplicate | Flag | PURGE
Xurmo Intern Data Structures - 0of 0 votes
AnswersCode up a simple Bloom Filter for four letter words. Assume all words are lowercase, exactly four letters long, and only use the letters a to z. An example set of test words might be able, band, bend, card, darn, form, grab, harm, look, make, mate, peer, and team, but assume the actual list of words is much bigger.
- showell30@yahoo.com March 16, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersHow will you store a million phone numbers in a space efficient way?
- Shock March 13, 2013 in India| Report Duplicate | Flag | PURGE
Intuit Software Engineer / Developer Data Structures - 3of 3 votes
AnswersGive the algorithm and code to get the depth of the deepest odd level leaf node in a binary tree.
- tom March 04, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersThere are 2 sorted sets.Find the common elements of those sets
- anonymous February 22, 2013 in United States
e.g.
A={1,2,3,4,5,6}
B={5,6,7,8,9}
o/p C={5,6}
Complexity should ne 0(n+m) where n and m is the size of the first and second set respectively
Which data structure should be used to store the output| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm Data Structures - 0of 0 votes
AnswersImplement a set that supports insert, remove and getRandomElement() operations.
- ak February 21, 2013 in India| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersHave you heard of the data structure called heaps? What do you know about them? Where would you use heaps and why?
- roadrunner February 19, 2013 in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Data Structures - 0of 0 votes
AnswerWhat do you know about hash tables? Talk about collisions and collision handling methods. What are the cons of using chaining?
- roadrunner February 19, 2013 in United States
-- Essentially he wanted to hear about complexity and about the effects of chaining on the complexity.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Data Structures - 1of 1 vote
AnswersA tree-map is implemented using BST, the complexity of search in a tree-map is guaranteed to be O(logn). How is that case of search complexity O(n) [obtained when the BST is like a linked list from the root node, only in single side] in BST avoided in tree-map.
- Srikanth February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 2 votes
AnswersWhich data structure is preferred for performing concurrency, serialization out of BST and Hash-Table.?
- Srikanth February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersCompare the space complexity of BST and Hash-Table.
- Srikanth February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a BST and a node, write a function to find the next biggest element in the BST in preferred language.
- Srikanth February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersSuppose we are detecting fraud cheques and we found the cheques with the following list of patterns are fraud:
- zahidbuet106 February 13, 2013 in United States
111122234455
1234
22334455
11111111
234567
etc.
Now if you have a new cheque and wan to detect fraud in O(1) time what data structure you want to use?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersPinterest has access to a large volume of 'pins' say of the order of 10 million. It is now required to display the 'Top 50' pins to the users on the website.
- maytas92@yahoo.com February 11, 2013 in United States
Each pin has an associated 'score id' which is constantly updated as users 'like' the pin.
Explain the run time complexity and memory requirements of the architecture.| Report Duplicate | Flag | PURGE
Pinterest Software Engineer / Developer Data Structures - 0of 0 votes
AnswersWhat are uses of Btree, AVL and RBtree(individual applications as i explained that we use them whenever we need balanced BST and he wasnt convinced)
- vik February 09, 2013 in United States
When would you specifically use Btree over AVL tree.
Which one out of balanced BST is most efficient(for which i answered Btree for large values of n) and he asked why dont we always use Btree then?| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 3of 3 votes
AnswersDesign a phonebook dictionary which on input any characters gives names and phone number of all the matching names(prefix)
- vik February 08, 2013 in United States
For instance
Rihana 233222232
Ricky 134242444
Peter 224323423
Ron 988232323
If you give R as input it should list
Rihana Ricky and Ron which their contact numbers
If you give ri as input it should list
Rihana, Ricky which their contact numbers| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm Data Structures - 0of 0 votes
AnswersGiven a file which contains list of function with parameters and return types (Assume parameters and return type as primitives) they can be of any order
- qstforums February 07, 2013 in United States
Example: File functions.txt contains below info
int e=f1(a,b,c,d)
int c=f2(a,b,d)
f3(a,c)
float d = f4()
question follows as below
We need to implement function
execute(functions.txt,a,b,d) where functions.txt is the file which contains just functions info and a,b, d are input parameters of functions defined in the file.
Now read the file and we need to determine the order of execution of function depending on the input parameter list
we can't execute f1 first because we have only parameters a , b and d
f2 can be executed because we have a, b and d parameters, which gives parameter c
now f3 can be executed because we have parameters a and c..
so we need to find the order and execute functions as quickly as possible (can use multi threading)
so efficient order is
f2 and f4 can run parallel and then f1 and f3 can be started only after completion of f2.
What are the data structures we use here to solve this problem
Consider execute function which takes always 1st parameter as filename and the rest of parameters as dynamic (similar to ... in java for dynamic parameter list)| Report Duplicate | Flag | PURGE
Amazon Data Structures - 0of 0 votes
AnswersA spreadsheet consists of a two-dimensional array of cells, labeled A1, A2, etc. Rows are
- sandeep17199117 February 01, 2013 in United States
identified using letters, columns by numbers. Each cell contains either an integer (its value) or
an expression. Expressions contain integers, cell references, and the operators '+', '-', '*', '/'
with the usual rules of evaluation – note that the input is RPN and should be evaluated in stack
order.
Write a program (in C, C++ or Java) to read a spreadsheet from ‘stdin’, evaluate the values of
all the cells, and write the output to ‘stdout’.
The spreadsheet input is defined as follows:
• Line 1: two integers, defining the width and height of the spreadsheet (n, m)
• n*m lines each containing an expression which is the value of the corresponding cell
(cells enumerated in the order A1, A2, A<n>, B1, ...)
Your program must output its data in the same format, but each cell should be reduced to a
single floating-point value. For example, we would expect the following expect to produce the
indicated output:
Input Expected Output
3 2
A2
4 5 *
A1
A1 B2 / 2 +
3
39 B1 B2 * /
3 2
20.00000
20.00000
20.00000
8.66667
3.00000
1.50000
The above example input visually looks like:
| 1 | 2 | 3 |
--+-------------+-------+--------------+
A | A2 | 4 5 * | A1 |
--+-------------+-------+--------------+
B | A1 B2 / 2 + | 3 | 39 B1 B2 * / |
------------------------+--------------+| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersYou have given an array of Integers of size n, and a sliding window by 1 integer ,of size k <= n. you have to print minimum number in each window of size k.
- pandu.vdp January 30, 2013 in India
E.g: given array [3,9,0,3,18,6], i.e.n = 6 and window size k = 3
available windows for above array is [3,9,0] ,[9,0,3],[0,3,18], [3,18,6]
output should be : 0, 0, 0,3| Report Duplicate | Flag | PURGE
Chronus Java Developer Data Structures - -1of 1 vote
AnswersRead a file and create a a datastructure which holds all the anagrams of words conatined in the file..
- vasa.v03 January 28, 2013 in India
For e.g lets say file content is "abc bca"
we need a DS to say "abc" and "cba" are anagrams.
I told i will use a FileReader to read characters than bytes
and assing a prime number for each alphabet
say
a - 2
b - 3
c - 5
and calculate the compound ofr multiplication
say abc = 2 * 3 * 5 = 30
bca = 3 * 5 * 2 = 30
i will use the compound a key in hashmap.
like 30 = abc-> bca -> cba
Let me know for any other better solution| Report Duplicate | Flag | PURGE
Ebay Member Technical Staff Data Structures - 0of 0 votes
AnswersGiven a two dimensional matrix of booleans, there is a function that returns the number of "true regions".
A region is a group of True values aligned vertically or horizontally.T T <= 1 region T F T F <= 2 regions F T
Question 1: How would you test a function that solve this problem, but is written by another developer. How many tests cases do you see?
- hnrqbaggio January 24, 2013 in United States for Office
Question 2: Now write the code to solve this problem. What are the time and space complexities?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft Testing - 1of 1 vote
AnswersGiven two arrays of ints that are sets, create a function to merge them to create a new set.
- hnrqbaggio January 24, 2013 in United States for Office
A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft - 0of 0 votes
AnswersTell me if a array of integers is a set.
- hnrqbaggio January 24, 2013 in United States for Office
A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates
After the first solution, I was asked about time and space complexity and to create 5 test cases for my function.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft