Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    7
    Answers

    Two words are friends if they have a Levenshtein distance of 1 (For details see http://en.wikipedia.org/wiki/Levenshtein_distance). That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word 'hello' is, using this word list https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt
    Input

    Your program should accept as its first argument a path to a filename.The input file contains the word list. This list is also available at https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt.
    Output

    Print out how big the social network for the word 'hello' is. e.g. The social network for the word 'abcde' is 4846.

    - vran.freelancer on May 09, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm

Country: India
Interview Type: Written Test


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

As a preprocessing step, we need to any way build the complete social graph from the wordlist in O(N^2) time. Two nodes in the social graph would be connected if the corresponding words are separated by a Levenshtein distance of 1.

Once the graph is constructed, we can fire a query to get the largest connected subgraph for any word , that would internally execute as a DFS starting at the queried word.

The Levenshtein distance or edit distance between any two words can be computed using Dynamic Programming (Refer to the problem of computing edit distances between two words. Feeling lazy to google the resource out on the web)

- random on May 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Take a HashMap<String, Boolean> put all the word in the wordlist into this HashMap with initial default value true.
Start from the given word put it in a Queue and then find all its friends by calling a method editdistance to find all the words from the wordlist that are at editdistance 1 and putting them int the Queue. Mark the found words in HashMap as false.

Do this till the Queue is empty or all words are exhausted in the wordlist present in HashMap.

- Anonymous on May 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

<?php

class Levenshtein {
    
    public function LevenshteinDist( $srcStr, $tarStr) {
        $srcLen = strlen($srcStr);
        $tarLen = strlen($tarStr);
        
        $disrArr = array();
        
        for ( $i = 1; $i < $srcLen; ++$i) $disrArr[$i][0] = $i;
        for ( $j = 1; $j < $tarLen; ++$j) $disrArr[0][$j] = $j;
        
        for ( $j = 1; $j < $tarLen; ++$j) {
            for ( $i = 1; $i < $srcLen; ++$i) {
                if( $srcStr[$i] == $tarStr[$j] )    $disrArr[$i][$j] = $disrArr[$i - 1][$j - 1]; // no operation required
                else    $disrArr[$i][$j] = min($disrArr[$i - 1][$j] + 1, $disrArr[$i][$j - 1] + 1, $disrArr[$i - 1][$j - 1] + 1); //deletion, insertion, substitution repectively 
            }
        }
        
        //print_r($disrArr);
        return $disrArr[$srcLen - 1][$tarLen - 1] + 1;
    }
}

$obj = new Levenshtein();
echo $obj->LevenshteinDist( 'kitten', 'sitting');
?>

- Vishnu Agarwal on May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a trie of given list of words. It will take exactly o(n).
Now for the given word search for all the words whose distance is 1. As for the word "hello", first substitue each letter from 'a' to 'z' except that letter.
e.g aello, bello, ...hallo, hbllo, etc. and keep searching in the trie. if found increment the count.
Do the same after deleting & adding the one letter in each position of the given word. Count will be the answer.

- Akash Jain on May 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well the above suggested algorithm does work but it takes a lot of time. Is their anyway i could improve upon that. I want to get this completed within 5 seconds or so. Below is my code.

public class Main {

	private static Queue<String> qAlreadyVisited = new LinkedList<String>();
	public static void main (String[] args) {

		/*assume that the file is having the list of all words against which i check the distance*/
		File file = new File("../CodeEval_Copy/src/levenshtein_Distance/Test");
		BufferedReader in = null;
		try {
			in = new BufferedReader(new FileReader(file));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		String line;
		ArrayList<String> listOfWords = new ArrayList<String>();
		Queue<String> qFriends = new LinkedList<String>();
		String socialNetworkForWord = "abcde";
		try {
			while ((line = in.readLine()) != null) {
				if(line.trim() != null && line.trim() != "")
					listOfWords.add(line);
				if (!(Math.abs((line.length() - socialNetworkForWord.length())) > 2)){
					if ((levenshteinDistance(socialNetworkForWord, line)) == 1){
						//System.out.println(line);
						qFriends.add(line);
					}
				}
			}
			test(qFriends, listOfWords);
		} catch (IOException e) {
			e.printStackTrace();
		}
		System.out.println(qAlreadyVisited.size());
	}
	
	public static void test (Queue<String> qFriends, ArrayList<String> listOfWords){
		while (!qFriends.isEmpty()){
			getAllFriends(qFriends, listOfWords);
		}
		
	}
	public static void getAllFriends(Queue<String> qFriends, ArrayList<String> listOfWords){
		String findFriendFor = qFriends.poll();
		qAlreadyVisited.add(findFriendFor);
		for (int i = 0; i< listOfWords.size(); i++){
			String str = listOfWords.get(i);
			if (!(str.length() - findFriendFor.length() > 2)){
				if ((levenshteinDistance(findFriendFor, str) == 1)){
					if (!(qFriends.contains(str)) && !(qAlreadyVisited.contains(str))){
						qFriends.add(str);
					}
				}
			}
			
		}		
	}
	public static int levenshteinDistance(String s, String t){

		// for all i and j, d[i,j] will hold the Levenshtein distance between
		// the first i characters of s and the first j characters of t;
		// note that d has (m+1)*(n+1) values
		int[][] arr = new int[s.length()+1][t.length()+1];



		// source prefixes can be transformed into empty string by
		// dropping all characters
		for (int i=1; i<= s.length(); i++){
			arr[i][0] = i;
		}

		// target prefixes can be reached from empty source prefix
		// by inserting every characters
		for (int i=1; i<= t.length(); i++){
			arr[0][i] = i;
		}
		
		arr[0][0] = 0;

		for (int i=1; i<= s.length(); i++){
			for (int j=1; j<= t.length(); j++){
				if (s.charAt(i-1)== t.charAt(j-1)){
					arr[i][j] = arr[i-1][j-1];
				}

				else{
					arr[i][j] = Math.min(Math.min(arr[i-1][j] + 1, arr[i][j-1] + 1),
							arr[i-1][j-1] + 1);
				}
			}
		}

		return arr[s.length()][t.length()];
	}
}

- Madhuir Mehta on June 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This was a problem on a recent coding competition. The competition's over though, so no worries.

- eugene.yarovoi on May 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why all the downvotes? What I said is true. Forgive me if I want to alert people to the fact that it's not from a real interview.

Of course, this problem is simple enough that it could have appeared on an interview. It's just that I recognized the exact text of the problem statement.

- eugene.yarovoi on September 15, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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