CodeBuster
BAN USER- 2of 2 votes
AnswersYou have a LinkList with each node having Next node and Other node and Data.
- CodeBuster in United States
i.e. Class Node
{
Node Next;
Node Other;
int Data;
}
Next pointer always points to next node and Other node can point to any other node in the list or can be pointing to null/nothing or can point to self.
Write program to copy this link list to a new list with proper Next and Other pointers.| Report Duplicate | Flag | PURGE
Expedia Software Engineer in Test - 0of 0 votes
AnswersYou have a book will billion pages. Each Page P has L lines and each lines has W number of words. Design a search algorithm which gives me best match search results. Best match is when all the words given by user exactly matches.
- CodeBuster in United States for Bing| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersYou came to a parking lot which is like a long road, which goes till very large length(say infinite length). Car parked on both sides of that road. You parked your car somewhere and forgot where is it. Write algirithm and then code to search your car. Note that- you dont know length of parking lot and you cant assume its length, you dont know where is your car, you are in middle of somewhere and your car might be in any side of the road
- CodeBuster in United States for Bing| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer
Create tree with parent child relationship.
Node class something like this:
public class tNode
{
public List<tNode> Children { get; set; }
public string Name { get; set; }
Insert something like this:
Insert(tNode current, string parentName, string childName)
{
if (current == null) //do not insert if parent not found
return;
if(current.Name == parentName) //parent found, insert child here
{
current.Children.Add(new tNode(childName));
}
else
{
foreach(tNode child in current.Children)
{
Insert(child, parentName, childName);
}
}
Search something like this:
List<tNode> GetChildren(tNode current, string parentName)
{
Queue<tNode> q = new Queue<tNode>();
if (current == null)
return null;
q.Enqueue(current);
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
if (tmp.Name == parentName) //found
return tmp.Children;
else
{
foreach (tNode child in tmp.Children)
{
q.Enqueue(child);
}
}
}
return null;
}
Count all children under a node like this:
public int CountNumberOfDescendents(string nodeName)
{
List<tNode> children = GetChildren(nodeName);
Queue<tNode> q = new Queue<tNode>();
int count = 0;
foreach(tNode child in children)
{
q.Enqueue(child);
count++;
}
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
foreach(tNode child in tmp.Children)
{
q.Enqueue(child);
count++;
}
}
return count;
}
If this is your algorithm, then how does your code look like? Just kidding :P
- CodeBuster November 20, 2014
1. Insert all numbers from one of the list(say List1) to a HashTable/Map/Dictionary
- CodeBuster September 02, 20162. Iterate through other List
a. n= target - list(i)
b. if hashTable.ContainsKey(n), then you found that pair
Complexity:
Space: O(n)
Time : since HashTable has constant time complexity in look up, it O(1)
If extra space is not allowed, then probably time complexity would be )(n2)