Data Structures Interview Questions
- 0of 2 votes
AnswersWrite a function that takes two arguments one array of integers that ranges between 0 and 9 and second the target sum(again integer). It produces all permutations strings of the input digits that equals the target sum.
- panchadi520 April 27, 2015 in India
For example, if input is array 2, 3, 5 and target sum is 10, then the output should be:
22222 because 2+2+2+2+2 = ,10
2323 as 2+3+2+3 = 10
3232
55
2233
3322
532
235
352
etc.,| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Data Structures - 1of 1 vote
AnswersDesign a data structure to keep track of top k elements out of 2 billion records.
- panda April 22, 2015 in India
Each record is numberd with a key which is 30 bit and a number which is count of how many times the customer has visited us.
Come up with an data structure so that the updation of element in 2 billion records will be faster.
Getting top k element will be faster| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 1 vote
AnswersHow can you determine if an array is pre order representation of a binary tree. I started with the logic of creating binary tree using a pre order array and failure to create the tree will mean that the array is not a pre order representation, but got stuck in middle.
- angshu1986 April 16, 2015 in India| Report Duplicate | Flag | PURGE
Symantec Java Developer Data Structures - 0of 0 votes
AnswersReturn the number of pairs of nodes which violate the binary search tree property given a root node. I was lead to the discussion of finding it by handling for different cases like ancestors, siblings, but came to know interviewer was looking for simpler solution. Not sure if it is fair to get this as make/break questions with out any other question for experienced candidate.
- Vib March 22, 2015 in India| Report Duplicate | Flag | PURGE
Bankbazaar Data Structures - 0of 0 votes
AnswersSuppose you have a huge data of students. This data is in RAM (around 48 GB). Student has following attributes:
- guptasunny158 March 20, 2015 in India
1) RollNo
2) Name
3) Address
Now I need to implement three method:
getStudentByRollNo(int rollno)
getStudentsByName(String name)
getStudentsByAddress(String address)
In what data structure I can keep these students so that these methods can return the results really fast.| Report Duplicate | Flag | PURGE
unknown Member Technical Staff Data Structures - 0of 0 votes
AnswersGiven three arrays sorted in non-decreasing order, print all common elements in these arrays.
- topCoder March 15, 2015 in India
Examples:
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80
ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Outptu: 5, 5| Report Duplicate | Flag | PURGE
Coupon Dunia SDE1 Algorithm Data Structures - 0of 0 votes
AnswersWhat are the advantages of an array over a linked list? and vice versa.
- shoryagupta1493 March 12, 2015 in United States for Amazon Fresh| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersThis was design question.
- shanushaan March 12, 2015 in United States
I have a single timer class which is running on a single port of a machine.
There are multiple clients that can send request to this timer class as follows.
request_timer (x)
where x is time in seconds.
when the timer class gets this request from a client it starts a timer object of x seconds and after x seconds are over it sends an event to the requesting client and client can handle the event the way it wants to .
The problem is if you have large number of clients then the timer class is single point of congestion and the clients may receive the event from it after a long time.
What are the good ways to scale this for a large number of clients?| Report Duplicate | Flag | PURGE
Cisco Systems Analyst Data Structures - 4of 4 votes
AnswersGive a path get it's canonical form. So for example if you have path in the form e/../../a/d/./../b/c then you should return a/b/c.
I have the solution but it's not the most optimal or the best solution. I just wanted to see what others have.
- cyb March 09, 2015 in United Statespublic String canonicalPath(String path){ if(path == null || path.isEmpty()){ throw new RuntimeException("incorrect path provided"); } String[] chunks = path.split("/"); Stack<String> s = new Stack<String>(); List<String> arr = new ArrayList<String>(); for(String chunk: chunks){ if(chunk.isEmpty() || chunk == "."){ System.out.println("skipping"); }else{ if(!s.isEmpty() && s.peek().equals("..") && !chunk.equals("..")){ while (!s.isEmpty()) { if(s.peek().equals("..")){ s.pop(); }else{ s.pop(); break; } } s.push(chunk); }else{ s.push(chunk); } } } StringBuffer sb = new StringBuffer(); List<String> list = null; if(!s.isEmpty()){ list = new ArrayList<String>(s); } if(list != null){ for(String ss : list){ sb.append("/"+ss); } } return sb.toString(); }
| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures - 6of 6 votes
AnswerPhone Interview with Collabedit.
- Sagar Shah February 11, 2015 in United States
/** Compute the value of an expression in Reverse Polish Notation. Supported operators are "+", "-", "*" and "/".
* Reverse Polish is a postfix mathematical notation in which each operator immediately follows its operands.
* Each operand may be a number or another expression.
* For example, 3 + 4 in Reverse Polish is 3 4 + and 2 * (4 + 1) would be written as 4 1 + 2 * or 2 4 1 + *
*
* @param ops a sequence of numbers and operators, in Reverse Polish Notation
* @return the result of the computation
* @throws IllegalArgumentException ops don't represent a well-formed RPN expression
* @throws ArithmeticException the computation generates an arithmetic error, such as dividing by zero
*
* <p>Some sample ops and their results:
* ["4", "1", "+", "2.5", "*"] -> ((4 + 1) * 2.5) -> 12.5
* ["5", "80", "40", "/", "+"] -> (5 + (80 / 40)) -> 7
*/| Report Duplicate | Flag | PURGE
Linkedin Android Engineer Data Structures - 1of 3 votes
Answersdesign and implement a calculater that can calculate expressions like:
- srcnaks February 02, 2015 in -
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )
(PS:all items are space delimetered.)
Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Problem Solving Stacks String Manipulation Trees and Graphs - 2of 2 votes
Answersthere are numbers in between 0-9999999999 (10-digits) which are assigened someone (does not matter which number assigned who)
- srcnaks February 02, 2015 in -
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table - 2of 2 votes
AnswersYou are given a binary search tree and a positive integer K. Return the K-th element of the tree.
- Anonymous January 27, 2015 in Israel
No pre-processing or modifying of the tree is allowed.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 1of 1 vote
AnswersYou are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).
- Anonymous January 27, 2015 in Israel
Return the number of sequences of elements (groups of consecutive elements), pointed by the array.
For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.
Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
Answerswhat are real applications of avl tree?
- ANURAG January 25, 2015 in United States| Report Duplicate | Flag | PURGE
Data Structures - 1of 1 vote
AnswersWrite a function that does an in-order traversal of a tree and prints out the contents (Assume each node has 1 piece of content which is an integer).
- americano- January 24, 2015 in United States for Cloud
Write this function without using recursion (you can assume a library that has stack/queue/list objects with some standard methods is available for use by you).
What is the maximum size your stack can grow to and what is the expected size that your data structure can grow to assuming that the tree has n nodes?| Report Duplicate | Flag | PURGE
Microsoft SDET Data Structures - 1of 1 vote
AnswersDesign a TinyURL like Service.
- R@M3$H.N January 16, 2015 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Data Structures Problem Solving System Design - 0of 0 votes
Answershow to design a relation functionality. similar to facebook , how to hold friends objects for a user profile , so that that is easily searchable . how to use cache for this?
- gopi.komanduri December 30, 2014 in India| Report Duplicate | Flag | PURGE
Adobe Computer Scientist Algorithm Coding Data Structures - 3of 3 votes
AnswersHow can you design a data structure that can do the following operations in O(1) time:
- Masumbuet December 29, 2014 in United States for International expansion
Insert, Delete, Search, Max which returns the maximum number
I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 2of 2 votes
AnswersConstructing Bridges:
- R@M3$H.N December 25, 2014 in India
A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.
Construct as many Non-Crossing Bridges as possible.
Input:
Above Bank >> 7 4 3 6 2 1 5
Below Bank >> 5 3 2 4 6 1 7
are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)
Output:
(1,1) (3,2) (4,3) (6,4) (7,5)| Report Duplicate | Flag | PURGE
StartUp SDE-2 Algorithm Data Structures - 0of 0 votes
AnswersGive a tree (any tree, can be a binary. I told the interviewer that I assume it is binary tree and he said that is fine). Print the tree content on the screen one tree level per line
- hiuhchan December 12, 2014 in United States
i.e.
if a tree is like this:
a
/ \
b c
/ /
e f
The output would be
a
bc
ef
Too bad, I was only able to make it print on one line instead of separate line. Until after the interview is over. Then I figure the final answer.| Report Duplicate | Flag | PURGE
Cloudera SDET Algorithm Data Structures - 1of 1 vote
AnswersGiven a 2^31 x 2^31 tic tac toe board, describe how you would store the state of the game to check if there is a winner.
- Algorithmy December 10, 2014 in United States| Report Duplicate | Flag | PURGE
Zillow Data Structures - 1of 1 vote
AnswersA binary tree represent an organization hierarchy. The root node is the CEO and etc. design a algorithm to print the tree level by level.
- joeyk December 06, 2014 in United States for Supply Chain| Report Duplicate | Flag | PURGE
Bloomberg LP Software Engineer / Developer Data Structures - 0of 0 votes
AnswersCheck if 2 link lists merge or not. If yes, return the 1st common node.
- Guest December 05, 2014 in India| Report Duplicate | Flag | PURGE
Monotype Senior Software Development Engineer Data Structures - 0of 0 votes
AnswersDesign Maps: You have set of [lat, long] for all famous locations. Given your position [lat, long] return all famous locations within r radius of your position.
- darklight November 27, 2014 in India| Report Duplicate | Flag | PURGE
Flipkart Software Engineer / Developer Data Structures - 1of 3 votes
AnswersImplement a vector-like data structure from scratch.
- Victor November 21, 2014 in Brazil
This question was to be done in C or C++.
Discussion topics:
1. Dealing with out of bounds accesses.
2. What happens when you need to increase the vector's size?
3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Data Structures