Amazon Interview Question for Software Engineer Interns


Country: United States




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

public static void permutate(String head, String tail) {
        if (tail.isEmpty()) {
            System.out.println(head);
        } else {
            Map<Character, Boolean> seen = new HashMap<Character, Boolean>();
            for (int i = 0; i < tail.length(); i++) {
                if (!seen.containsKey(tail.charAt(i))) {
                    seen.put(tail.charAt(i), true);
                    permutate(head + tail.charAt(i), tail.substring(0, i) + tail.substring(i + 1, tail.length()));
                }
            }
        }
    }

    public static void main(String[] args) {
        permutate("", "aaab");
    }

- RW November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Super cool, you can make this space efficient by using start/end pointers instead of straight up using substrings but this is good!!!!

- Aasen November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why HashMap, HashSet could be good enough to serve the purpose..

- Alok November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, but actually it's the same - HashSet is backed by HashMap. We can rewrite it without additional maps/sets but with increased complexity - tail.substring(0, i).indexOf(tail.charAt(i)) == -1 instead of seen.contains.

- RW November 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Aasen start/end pointers may actually not work because you are juggling the characters in the string for every permutate() call. start/end indices can not really specify the two parts of the string given the order of characters will change.

- nosyDeveloper November 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pretty good.
But the hasmap or mapset might be overkill.
You could use an array with size ('z'-'A'+1) and index it by ('your char'-'A'), knowing the 'char' translates the char to its ascii code.

- jpsalada November 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

jpsalada - no, main memory consumer in my solution are strings generated on each recursive call - two string for each call. There is always a trade-off between speed and memory consumption - classic solution with chars swapping (like Ajeet's one - but he has forgotten to add uniqueness check) has probably the best memory consumption, but I see no way how to make it faster when chars in given string are not unique. My solution may generate much less recursive calls but with worse memory consumption.

- RW December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could anyone please explain the logic behind this solution? I don't quite follow.

- Guy February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think I might get it now. For every position, we try every possible combination as long as the character has not been visited. Very elegant approach! What'ts the time complexity though?

- Guy February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

From O(n) for "aaaa...a" to O(n!) for "abc....z"

- Anonymous February 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

public class Permutation
{
	stringBuilder output;
	String input;
	boolean used[];

	public Permutation(String in)
	{
		this.input = in;
		output = new StringBuilder();
		used = new Booolean[n];
	}

	public void Permute(String in)
	{
		if(in.length() == output.length())
		{
			print(output.toString());
		}
		for(int i=0;i<in.length; i++)
		{
			if(used[i]) continue;

			output.append(input.charAt(i));
			used[i] = true;
			permute(in.substring(i));
			used[i] = false;
			output.setLength(output.length() - 1);
		}
	}
}

- zahidbuet106 December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have you tried to run it?

- RW December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringPermutation{
	
	public static void main(String args[])
	{
		long start = System.currentTimeMillis();
		new StringPermutation().permuteString("assdfeg");
		long end = System.currentTimeMillis();
		System.out.println("Time Consumed:"+(end-start)+"ms");
	}
	
	public void permuteString(String s)
	{
		HashMap<String,Integer> permutations = new HashMap<String,Integer>();
		char[] sor = new char[s.length()];
		for(int i=0;i<s.length();i++)
		{
			sor[i] = s.charAt(i);
		}
		permute(permutations,sor,0,s.length());
		for(String string : permutations.keySet())
			System.out.println(string);
	}

	public void permute(HashMap<String,Integer> map,char[] sor,int start,int length)
	{
		if(start == length -1)
		{
			String s = new String(sor);
			map.put(s,0);
		}
		else
		{
			for(int i = start;i<length;i++)
			{
				char temp = sor[i];
				sor[i] = sor[start];
				sor[start] = temp;
				permute(map,sor,start+1,length);
				temp = sor[i];
				sor[i] = sor[start];
				sor[start] = temp;
			}
		}
	}
}

- wenfengzhuo November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main (String args[] ) {
        permute("Peace");
    }

    public static void permute(String input) {
        int inputLength = input.length();
        boolean[] used = new boolean[inputLength];
        StringBuffer output = new StringBuffer();
        char[] in = input.toCharArray();

        permute(in, output, used, inputLength, 0);

    }

    private static void permute(char[] in, StringBuffer output, boolean[] used, int inputLength, int level) {
        // TODO Auto-generated method stub
        if (level == inputLength) {
            System.out.println(output.toString());
            return;
        }
        
        for (int i=0; i < inputLength; i++) {
            
            if (used[i]) continue;
            output.append(in[i]);
            used[i] = true;
            permute(in, output, used, inputLength, level + 1);
            used[i] = false;
            output.setLength(output.length() - 1);
        }
    }

- Anonymous November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void perm2(String s) {
           int N = s.length();
           char[] a = new char[N];
           for (int i = 0; i < N; i++)
               a[i] = s.charAt(i);
           perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
    	int n = a.length;
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    } 
    
    private static void swap(char[] a, int i, int j) {
            char c;
            c = a[i]; a[i] = a[j]; a[j] = c;
    }

- Ajeet November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.PermutationOfStrings;

import java.util.HashSet;

public class P {

/**
* @param args
*/
public static void main(String[] args) {
String name = "CareerCup";
printPermutationOfString(name);
}
static HashSet<String> permutation = new HashSet<String>();


private static void printPermutationOfString(String name) {

boolean[] count = new boolean[name.length()];
getAllPermutation (name, count, "");

}

private static void getAllPermutation(String name, boolean[] count,
String soFar) {

if (soFar != null && soFar.length() > 0) {
if (permutation.add(soFar))
System.out.println(soFar);
}
if (soFar.length() == name.length())
return;
for (int i = 0; i < name.length(); i++) {
if (!count[i]){
boolean[] c = count.clone();
c[i] = true;
getAllPermutation(name, c, soFar + name.charAt(i));
}
}

}

}

- nishant November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

class Node {
 public $str;
 public $nodes = [];
 public $char;
}

function process(Node &$node) {
 $len = strlen($node->str);
 if ($len == 0) return;

 for ($i = 0; $i < $len; $i++) {
  $char = $node->str[$i];
  if (!isset($node->nodes[$char])) {
   $new_node = new Node();
   $new_node->char = $char;
   $pos = strpos($node->str, $char);
   $new_node->str = substr($node->str, 0, $pos) . substr($node->str, $pos+1);
   $node->nodes[$char] = $new_node;
   process($new_node);
  }
 }
}

function print_node(Node &$node) {
 if (strlen($node->str) == 0) {
  print $node->char."\n";
  return true;
 }
 
 print $node->char;
 $first = reset($node->nodes);
 $key = $first->char;
 if (print_node($first)) {
  unset($node->nodes[$key]);
 }

 if (count($node->nodes) == 0) {
  return true;
 }

 return false;
}

$root = new Node();

$root->str = "123334";
$root->char = '';

process($root);

$all_deleted = false;

while (!$all_deleted) {
  $all_deleted = print_node($root);
}

- Paul November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ version. Uses O(n) space.

#include <iostream>
#include <unordered_set>

void permute(const std::string& perm, const std::string& str, std::unordered_set<std::string>& permutations) {
	if (str.empty()) {
		if (!permutations.count(perm)) {
			std::cout << perm << std::endl;
			permutations.insert(perm);
		}
		return;
	}
	
	for (size_t i = 0; i < str.size(); i++) {
		permute(perm + str[i], str.substr(0, i) + str.substr(i + 1),	permutations);
	}
}

void permute(const std::string& str) {
	std::unordered_set<std::string> permutations;
	permute("", str, permutations);
}

int main() {
	permute("aabc");
	return 0;
}

- Diego Giagio November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the worst case your set of permutations will contain n! strings.

- RW November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array. And then run next_permute algo which is as follow:

1) Scan string from right most to left side until you find char which is smaller then this char. Let that index is j.
2) Now swap(j,0). and sort the list from j-1 to 0,

- Himanshu January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use recursion and backtracking

- fReaK November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How can worst case beat n! ? (large n, almost all distinct)

- = November 14, 2013 | 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