Linkedin Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: In-Person




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

setup a DAG and use bfs to from the shortest path

- Scott September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Preprocessing Step: Basically the dictionary of words is converted into multiple graphs. Each graph is constructed from words of particular size. The graph nodes have an edge if their edit distance (only replacement) is 1. Once you constructed this graph, then the problem is simple. Shortest path from given node to destination node. You can use BFS. The graph is undirected.

- docomp September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think it can be achieved in 4 steps.

cat --> cot --> dot--> dog

- Krish September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a bloom filter and force a swap for each character in the string.

If none of them form words, begin with the first character and do a random swap until a word is formed (if any), continue with the second character. And so forth. At each step try to naively switch the characters to save time.

- messophet September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Building up a graph dynamically and returning when target word is found

{
            Queue<Tuple<string,int>> grph = new Queue<Tuple<string,int>>();
            HashSet<string> words = new HashSet<string>() {"cat","bat","bet","bot","bog","dog","cot","dot","dog"};
            HashSet<string> visited = new HashSet<string>();
            string allEnglishCharacters = "abcdefghijklmnopqrstuvwxyz";
            string start = Console.ReadLine();
            string end = Console.ReadLine();
            grph.Enqueue( new Tuple<string,int>( start, 1 ));
            int level = -1;
            while(grph.Count > 0)
            {
                var target = grph.Dequeue();
                string src = target.Item1;
                for ( int i = 0; i < src.Length; i++ )
                {
                    foreach(char c in allEnglishCharacters)
                    {
                        string res = src.Substring( 0, i ) + c + src.Substring( i+1 );
                        //Optimization to reduce unnecessary checks
                        if ( visited.Contains( res ) )
                        {
                            continue;
                        }
                        else
                        {
                            visited.Add( res );
                        }
                        // if target word found exit
                        if ( res == end )
                        {
                            level = target.Item2 + 1;
                            break;
                        }
                        // if found in dictionary add
                        if(words.Contains(res))
                        {
                            grph.Enqueue(new Tuple<string,int> (res, target.Item2 + 1 ));
                        }
                    }
                    if ( level != -1 )
                        break;
                }
                if ( level != -1 )
                    break;
            }
            Console.WriteLine( level );
        }

- c.prashanth85 September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how can you know which words are "valid dictionary words", are you provided a list of valid words?

- bitly September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you can assume that you have a function like Dictionary.isValid(String s). This returns true if 's' is a valid dictionary word.

- Anonymous October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets start with all possible children nodes for cat and make a tree out of it with maintaning parent pointer.

Keep track of the already existing parent words and don't repeat in children. Maintain this in a hashset.

For example:
cat - {(bat, eat, fat, hat, mat, oat, pat, rat, sat, tat), (cot, cut), (cab, cad, cam, can, cap, car)}

Now for each of these words, get all possible valid words which we have not seen before. Add these words to the hashset.

So you will be building a big tree with all unique nodes with 3 letter words

As soon as you see dog, just stop and trace to the parent to the root and count the number of levels. Or we can maintain level info for each node.

- dhirendra.sinha January 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findPathLength(String start, String end){
// put start in queue
// put all the children of start in a queue

ObjectLevel o = new ObjectLevel(start, 0);

	Queue<ObjectLevel> q= new LinkedList<ObjectLevel>
	q.enque(o);
	HashSet<ObjectLevel> allWords = new HashSet<ObjectLevel>();

	while (!q.isEmpty()){
		// find the valid words children and add
		ObjectLevel a= q.dequeue();
		boolean isEnd = getValidChildren(a, end, Set<ObjectLevel> s);
		if(isEnd) {
			return a.level + 1; 
		}
		s.removeAll(allWords);
		enqueSet(q, s);
		allWords.addAll(s);

	}
}

boolean getValidChildren(ObjectLevel a, String end, Set<ObjectLevel>){
	// Get all valid permutations of the a.text and check isValidWord against it
	…
	//check if the children contain the end word
	if(children.contains(end))
	return true;
}

class ObjectLevel {
	String text;
	int level;

	ObjectLevel(String t, int l){
		this.text = t;
		this.level =l;
	}
}

- dhirendra.sinha January 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't you use dynamic programming and try every possibility and return the min?

- Sachin May 08, 2016 | Flag Reply


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