Amazon Interview Question
Software Engineer InternsCountry: United States
Super cool, you can make this space efficient by using start/end pointers instead of straight up using substrings but this is good!!!!
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.
@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.
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 - 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.
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?
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);
}
}
}
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;
}
}
}
}
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);
}
}
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;
}
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));
}
}
}
}
<?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);
}
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;
}
- RW November 14, 2013