Data Structures Interview Questions
- -1of 3 votes
AnswersGiven a log file from a website which contains the user ID and the accessed URL, find the TOP "sequence" of 3 urls amongst ALL visitors of the website. The sequence of urls have to be in sequence as they are accessed.
- Guy January 24, 2014 in United States
My solution is Two hashtables and one MaxUrl object. One hashtable<String,String> userName as key and url sequence as value, where url sequence is three url contatenated by a special character like '#' (google#amazon#yahoo). This value is in FIFO manner. For each value, we check with the second hashtable and see if they exist before, if yes, increment the count, if no, insert the new sequence with count set to 0. So second hashtable<String, Integer> url sequence as key and count as value. Keep a curr_Max to store the current max count, when exceeded, updates max_urlSequence.
Any suggestion?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
Answersdesign a data structure for caching the result of "int getSmallestBiggerPrime(int)" so that the client side can reduce the trips to the server as much as possible. There are some examples in format of input->output: 1->1, 2->2, 3->3, 4->5, 5->5, 6->7, 7->7, 8->11, 9->11...
- jiangok2006 January 23, 2014 in United States
The interviewer did not say whether to use Least Recently Used (LRU) or Most Recently Used (MRU). But he gave a requirement using an example, suppose the user inputs 6 and gets 7 last time, the next time when he inputs 7, there should be no server trip to get 7 as the result.| Report Duplicate | Flag | PURGE
Data Structures - 0of 2 votes
AnswersThe final question was just how to write a connection pool (i.e, a class that returns connections to the user, and if the user is done, returns them back to the pool)
- Guy January 19, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 2 votes
AnswersHow do you design a Maze and what kind of data structures you use for Maze. In addition, write a method to print the shorted path from start to end point.
- Guy January 18, 2014 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - -2of 2 votes
AnswersDesign question to find the most frequent sequence of web page views from a log file of all the web pages viewed. Say the sequence is 4.
- Guy January 16, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - -2of 2 votes
AnswersArranging file system in the form of a binary tree. I think the interviewer meant B-Tree. She had a huge accent.
- Guy January 16, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersSecond Question is to Encode a String
- lks January 09, 2014 in United States
aaaabbccdd -> a4b2c2d2
In minimun space and time complexity| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersFirst question is You have two numbers represented by a linked list, where each node contains a single digit. Write a function that adds the two numbers and returns the sum as a linked list
- lks January 09, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 2 votes
AnswersDesign a Logging mechanism. Should be thread safe.
- R@M3$H.N January 07, 2014 in India
Initially i came up with Command Pattern, and write into a File. Was asked how i will synchronize multiple threads writing into Same File?
Later he gave hint about Aspect-oriented Programming(AOP). And also he gave a hint of Not always writing into the File, can also be a Mail,etc..| Report Duplicate | Flag | PURGE
Microsoft SDE-2 Data Structures Problem Solving System Design Threads Unix - 0of 0 votes
AnswersHow would you represent a graph with million nodes ?
- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersGiven a collection of 3-set sequences, where a 3-set sequence is defined as a list of 3 different pages (for example: mouse-keyboard-printer is a 3-set sequence, while printer-mouse-keyboard is another) accessed sequentially on amazon.com, find the most common 3-set sequence with minimum space and time complexity
- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 1 vote
AnswersWrite a function to remove all redundant characters in a given string with minimum space and time complexity
- lks January 06, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 2of 4 votes
AnswersGiven a sorted array of integers, write a function that will return the number with the biggest number of repetitions.
- GeorgyBoy December 30, 2013 in Israel
(Asked to refine the solution to be more efficient)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm Arrays Coding Data Structures Problem Solving Sorting - -1of 1 vote
AnswersTwo array with integers.Find the value in both of them with out using set.Find the time complexity?
- HadoopUser December 28, 2013 in India| Report Duplicate | Flag | PURGE
Expedia Java Developer Data Structures - 0of 0 votes
AnswersAmazon has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff.
- pulkit.mehra.001 December 26, 2013 in India
Make an efficient data structure for storing 3 days of information of all those customers who have visited site exactly two different days and searched more than 3 unique pages of the site in those 2 days.
So whoever visited site exactly two days out of these three days and visited more then 3 unique pages should be in the contact list.
What's the efficient approach to solve these kinds of problems??| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersFind duplicates in a unsorted array and keep the order of integers as it is.
- HadoopUser December 25, 2013 in India| Report Duplicate | Flag | PURGE
Expedia Principal Software Engineer Data Structures - 0of 0 votes
AnswersQ: Pretend I'm a Dog breeder and you are an SDE. Design a solution for tracking my dog's pedigrees.
- vickykansal December 19, 2013 in United States
Followup - pedigree may also be hybrid. need a data structure which can lookup by pedigree to see if dog exists. also should be able to search by pedigree and some characters of dog.| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 0of 0 votes
AnswersHow to add a more memory dynamically to an array without deleting the old memory, means, expanding an aray without deleting the old one?
- jais.ashish December 05, 2013 in India| Report Duplicate | Flag | PURGE
Morgan Stanley Data Structures - 0of 0 votes
AnswersI have an unordered array of nodes. Each node has an id and parent_id. I want to pretty print out the nodes in an expanded format.
Assumptions:
There is only one root node in the array.
Don't worry about the white space.
Node has a toString() method.
All the ids are arbitrary and unique.
This is a tree and not a graph.
For example:
Sample input:
[{parentId: F, id:G}, {parentId: E, id: F}, {parentId: A, id: B}...]A (parent_id = null) B (parent_id = A) C (parent_id = B) D (parent_id = C) H (parent_id = B) E (parent_id = A) F (parent_id = E) G (parent_id = F)
Sample output:
- anonymous November 26, 2013 in United States
ABCDHEFG
Please write a more optimized solution and tell me the complexity.| Report Duplicate | Flag | PURGE
unknown Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a Binary Search Tree, Replace each node with sum of this node and sum of all nodes greater than this node.
- OTR November 23, 2013 in India| Report Duplicate | Flag | PURGE
iLabs Tech Lead Algorithm Data Structures - 0of 0 votes
AnswersWe maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?
- nosyDeveloper November 22, 2013 in United States
My solution was to maintain a max-heap and a map that maps ticker to the corresponding node in the heap. At every update, we look-up the node and update the value, but also note if it is an increase or decrease in value. If increase, we do a sift-up, if decrease, we do a sift-down on the heap for that node. For giving the top five values at any point of time, we don't want to disturb the order in the heap so we would copy the top five levels to a different memory and then perform 5 extract and heapifies on it.| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Data Structures - 0of 0 votes
AnswersWe maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?
- nosyDeveloper November 22, 2013 in United States| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Data Structures - 3of 3 votes
AnswersSuppose you are supplied with a file containing a list of words like ABC, BCD , CAB ( say each word in new line ). now you have to suggest algorithm for this problem -
- ajitpec November 21, 2013 in India
When a user type some character, we have to suggest him next character and basis of suggestion is that the character you are going to suggest should have maximum occurrence at that position among all these words.
For example , Let's say words are
ABC
BCD
CBA
Now if user types 'A' we have to suggest him 'B' as next character because if you see at second position in all words 'B' is occurring most number of times ( 2 times ).
similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index all words have same occurrence but 'C' comes first.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 2of 4 votes
AnswersImplement HashTable in java , especially hash function that should take care of any type of keys. The key may be integer or String or Object. But based on that the hash function should find index in the hashArray
- sivaji8 November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - -4of 4 votes
AnswersImplement Array Class in java.
- sivaji8 November 15, 2013 in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures - 0of 0 votes
AnswersCreate the mirror image of a binary tree.
- ootah November 14, 2013 in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Data Structures - -6of 6 votes
Answersplease tell me about a good website data structure in c++???
- 12024156-061@uog.edu.pk November 13, 2013 in India| Report Duplicate | Flag | PURGE
CareerCup Developer Program Engineer Data Structures - 4of 4 votes
AnswersGiven two (dictionary) words as Strings, determine if they are isomorphic. Two words are called isomorphic
- yashas.mavinkere November 07, 2013 in United States for Application
if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all
occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters
may map to the same letter, but a letter may map to itself.
Example:
given "foo", "app"; returns true
we can map 'f' -> 'a' and 'o' -> 'p'
given "bar", "foo"; returns false
we can't map both 'a' and 'r' to 'o'
given "turtle", "tletur"; returns true
we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r'
given "ab", "ca"; returns true
we can map 'a' -> 'c', 'b'| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Data Structures - 4of 4 votes
AnswersSuppose you have to maintain the stock values of various companies during various periods and return minimum stock value of a particular company over a given period of time.what data structure is best for this.
- nishu November 07, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Intern Data Structures - -4of 4 votes
Answersin this i have to improve the enqueue function
- Sarvesh November 02, 2013 in United States
enqueue returns the queue after adding the element but the original queue is not to be changed
and same is for dequeue function
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class PersistentQueue<E>{
private List<E> queue;
public PersistantQueue<E>(){
queue=new ArrayList<E>();
}
private PersistentQueue(List<E> queue){
this.queue=queue;
}
public PersistantQueue<E> enqueue(E e){
/*
Returns the queue that adds an item into tail of this queue without modifying this queue ( how to return without cloning ??)
*/
if(e==null){
throw new IllegalArgumentException();
}
List<E> clone = new ArrayList<E>(queue);
clone.add(e);
return new PersistantQueue<E>(clone);
}
public PersistantQueue<E> dequeue(){
/*
Returns the queue that removes the object at the head of this queue without modifying this queue ( here also how to do instead of clone as it it slow ??)
*/
if(queue.isEmpty()){
throw new NoSuchElementException();
}
List<E> clone = new ArrayList<E>(queue);
clone.remove(0);
return new PersistantQueue<E>(clone);
}
public E peek(){
if(queue.isEmpty()){
throw new NoSuchElementException();
}
return queue.get(0);
}
public int size(){
return queue.size();
}
}| Report Duplicate | Flag | PURGE
Data Structures