## Microsoft Interview Question for SDE-2s

Team: C&E
Country: india
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Here's a hash based solution for this problem.
Create a structure

``````struct node
{
int* address;
bool visited;
struct node* next;
};``````

1. Create an array of 26 (alphabatic characters) node.
2. For each entry in linked list fill the hash table (based on starting character).
2.1. address - pointer to for linked list node.
2.2. visited = false
2.3. next = NULL (it will come into use when two nodes have same starting character, using the idea of chaining concept in hashing)

Now lets try to fill the given linked list in hash table:-
Pointer Value :- 0x100 0x200 0x300 0x400 0x500 0x600 0x700
Linked List :- here -> is -> ew -> long -> shut -> error -> roll

Once these pointer values are feeded into the nodes we are done with the hash table.

Now, to find the possibilities we start from first node of linked list. Let's do it one by one.

1. a. Here (search for h in hash table).
b. Since 'e' is last character of here, now search hash table for 'e'. Now we have two enteries for 'e' we will do it one at a time. Lets say we choose "ew" first time, and if we have next of "ew" != NULL, we mark "ew" as visited (i.e. "ew"->visited = true) now we proceed for 'w' and continue same ways.
c. Since after here 'e', there is one more possibility of having "error" 'e', for "ew" we have already visited (since visited flag for "ew" is true), we will go forward in that chain and continue.

In this way we can have all possiblities. Thanx

Comment hidden because of low score. Click to expand.
0
of 0 votes

There's a problem with your solution:
What if you got a word that you need to reuse, but it's already visited?
Say you have: elle->ew->ebbe

you will print:
elle->ew
elle->ebbe
but you will not print:
elle->ebbe->ew
because you already visited ew, even thou you should print it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can create a directed graph here . Each node of graph will be a word and we make a edge from node to another if the end of word of first node is start of word of another node (eg we can make an edge from "here" to "ew" and "here" to "error") . After our graph is built all we need is to do DFS from each node and print all paths.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

first we should check how to handle circle like ab->ba.
here I use a set to detect circle and only save {ab, ba}.
connect the last node to the root, then we can use a recursive function to handle all nodes.

``````class SListNode {
public:
string v;
SListNode *next;
SListNode(string s) : v(s), next(NULL) {};
};
vector<vector<string>> line(SListNode *root, vector<string> &pre, set<string> &predic) {
vector<vector<string>> res;
string &tmp = root->v;
pre.push_back(root->v);
predic.insert(root->v);
SListNode *p = root->next;
while (p != root) {
if (p->v[0] == tmp.back() && predic.find(p->v) == predic.end()) {
auto tmpres = line(p, pre, predic);
res.insert(res.end(), tmpres.begin(), tmpres.end());
}
p = p->next;
}
if (res.empty()) {
res.push_back(pre);
}
predic.erase(root->v);
pre.pop_back();
return res;
}

vector<vector<string>> line(SListNode *root) {
if (!root) return vector<vector<string>>();
SListNode *p = root;
while (p->next) p = p->next;
p->next = root;
vector<string> tmp;
set<string> tmpdic;
auto res = line(root, tmp, tmpdic);
p->next = NULL;
return res;
}``````

sample result:

``````Here    ew
Here    error   roll    long``````

another test case: ab->ba->acd->bcd
result:

``````ab      ba      acd
ab      bcd``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Algorithms steps
1) create trie of the string given in the linked list.
2) start from first node, if found first child with end char, consider that, then go unto to the point where either the string ends or it convert into to children, if you see such case, put them into the stack, and as you travel in the trie, mark the string in the list as travelled, so that when one choose next string from list, we always choose untravelled string.
3) try until the stack is empty.

In the stack you will insert the start and end node of the sequences

Complexity : O(N) time + space used by trie.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More