Amazon Interview Question Software Developers
Country: United States
There are 2^(number of s's and a's in the string) outputs in total.
A simple solution would be to create a recursive function that has a result string, a position inside the original string, and whenever the letter at the current position is a or s, append all synonim elements and recurse.
Python:
def gen(s, res, pos):
if pos >= len(s):
print res
return
if s[pos] in 'as':
if s[pos] == 'a':
gen(s, res + 'a', pos + 1)
gen(s, res + '@', pos + 1)
elif s[pos] == 's':
gen(s, res + 's', pos + 1)
gen(s, res + '$', pos + 1)
else:
res += s[pos]
gen(s, res, pos + 1)
def combinations(s):
if s:
ind_s = index_of(s, 's')
ind_a = index_of(s, 'a')
i = ind_a
if ind_s != -1:
i = ind_s
if ind_a != -1:
i = min(ind_s, ind_a)
if i != -1:
combs = combinations(s[i + 1:])
return [s] + [s[:i] + rep[s[i]] + c for c in combs]
return [s]
return []
def index_of(s, ch):
try:
return s.index(ch)
except:
return -1
def gen(word,index,char):
word = word[:index] + char + word[index + 1:]
return word
word='Password'
print (word)
print (gen(word,3,"$"))
print (gen(word,2,"$"))
print (gen(gen(word,2,"$"),3,"$"))
print (gen(word,1,"@"))
print (gen(gen(word,1,"@"),3,"$"))
print (gen(gen(word,1,"@"),2,"$"))
print (gen(gen(gen(word,1,"@"),2,"$"),3,"$"))
def change_password(password):
passwords = set()
sub_strings = []
change_characters = {'s': '$', 'a': '@'}
sub_strings.append(password)
passwords.add(password)
for index in range(len(password)):
char = password[index]
if char in ('s', 'a'):
new_password = password[:index] + change_characters[char] + password[index+1:]
passwords.add(new_password)
for sub_string in sub_strings:
alternative_password = sub_string[:index] + change_characters[char] + sub_string[index+1:]
passwords.add(alternative_password)
sub_strings.append(new_password)
return passwords
def change_password(password):
passwords = set()
sub_strings = []
change_characters = {'s': '$', 'a': '@'}
sub_strings.append(password)
passwords.add(password)
for index in range(len(password)):
char = password[index]
if char in ('s', 'a'):
new_password = password[:index] + change_characters[char] + password[index+1:]
passwords.add(new_password)
for sub_string in sub_strings:
alternative_password = sub_string[:index] + change_characters[char] + sub_string[index+1:]
passwords.add(alternative_password)
sub_strings.append(new_password)
return passwords
public static List<String> passwordSuggestions(String password){
List<String> suggestions = new ArrayList<>();
List<Integer> positions = new ArrayList<>();
for (int i = 0; i < password.length(); i++) {
if (password.charAt(i) == 'a' || password.charAt(i) == 's') {
positions.add(i);
}
}
int cantSuggestions = 2 << (positions.size() - 1);
for(int i=0;i<cantSuggestions;i++){
suggestions.add(changeCharacters(password.toCharArray(), positions, i));
}
return suggestions;
}
public static String changeCharacters(char[] text, List<Integer> positions, int actualPos){
boolean isChange = false;
for(int i=0;i<positions.size();i++){
int cycle = 2 << i;
if(actualPos<cycle){
isChange = (actualPos>=cycle/2);
}else{
int numberCicyle = actualPos/cycle;
isChange = (actualPos - numberCicyle*cycle >= cycle/2);
}
if(isChange){
if(text[positions.get(i)]=='a'){
text[positions.get(i)] = '@';
}else{
text[positions.get(i)] = '$';
}
}
}
return String.copyValueOf(text);
}
public class PasswordPossibilities {
public static void main(String[] args){
Set<String> possiblities = new HashSet<>();
String str ="Password";
possiblities(str,"",possiblities);
for(int i=0;i<str.length();i++){
if(str.charAt(i) == 's'){
possiblities(str.substring(0,i)+"$"+str.substring(i+1),"",possiblities);
} else if(str.charAt(0) == 'a') {
possiblities(str.substring(0,i)+"@"+str.substring(i+1),"",possiblities);
}
}
System.out.println(possiblities);
}
private static void possiblities(String rest, String prefix, Set<String> possiblities) {
if(rest.length()==0){
return;
}
possiblities.add(prefix+rest);
if(rest.charAt(0) == 's'){
possiblities(rest.substring(1),prefix+"$",possiblities);
} else if(rest.charAt(0) == 'a') {
possiblities(rest.substring(1),prefix+"@",possiblities);
} else{
possiblities(rest.substring(1),prefix+rest.charAt(0),possiblities);
}
}
}
public class PasswordPossibilities {
public static void main(String[] args){
Set<String> possiblities = new HashSet<>();
String str ="Password";
possiblities(str,"",possiblities);
for(int i=0;i<str.length();i++){
if(str.charAt(i) == 's'){
possiblities(str.substring(0,i)+"$"+str.substring(i+1),"",possiblities);
} else if(str.charAt(0) == 'a') {
possiblities(str.substring(0,i)+"@"+str.substring(i+1),"",possiblities);
}
}
System.out.println(possiblities);
}
private static void possiblities(String rest, String prefix, Set<String> possiblities) {
if(rest.length()==0){
return;
}
possiblities.add(prefix+rest);
if(rest.charAt(0) == 's'){
possiblities(rest.substring(1),prefix+"$",possiblities);
} else if(rest.charAt(0) == 'a') {
possiblities(rest.substring(1),prefix+"@",possiblities);
} else{
possiblities(rest.substring(1),prefix+rest.charAt(0),possiblities);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test_aws
{
/*
*
* Password Suggestor: Replace s with $ and a with @ and produce all password suggestions.
* For Example: Password : P@ssword, P@$$word,pas$word etc..
*/
class Password_suggestor
{
List<string> all = new List<string>();
public Password_suggestor()
{
passwordGen("password");
foreach(string i in all)
{
Console.WriteLine(i);
}
}
public void passwordGen(string s)
{
int n = s.Length;
if (n > 0) {
if (s.Contains('a') || s.Contains('s'))
{
for (int j = 0; j < n; j++)
{
if (s[j] == 'a')
{
var ss = s;
var update = ss.Substring(0, j) + "@" + ss.Substring(j + 1, n-(j+1));
if (!all.Contains(update))
{
all.Add(update);
}
passwordGen(update);
}
if (s[j] == 's')
{
var ss1 = s;
var update1 = ss1.Substring(0, j) + "$" + ss1.Substring(j + 1, n - (j+1));
if (!all.Contains(update1))
{
all.Add(update1);
}
passwordGen(update1);
}
}
}
}
}
}
}
import java.util.*;
public class GeneratePasswords
{
public static void main(String args[])
{
GeneratePasswords g = new GeneratePasswords();
System.out.println(g.generate("Password"));
}
public Set generate(String s)
{
Set<String> set = new HashSet<>();
helper(s, 0, set);
return set;
}
private void helper(String s, int index, Set<String> set)
{
if(index>=s.length())
{
set.add(s);
return;
}
if(s.charAt(index)=='a')
{
helper(s.substring(0,index)+"@"+s.substring(index+1), index+1, set);
helper(s, index+1, set);
}
else if(s.charAt(index)=='s')
{
helper(s.substring(0,index)+"$"+s.substring(index+1), index+1, set);
helper(s, index+1, set);
}
else
{
helper(s, index+1, set);
}
}
}
- TakeItForATestDrive June 29, 2017import java.util.*; public class Sustitutions{ static HashSet<String> possibilities = new HashSet<String>(); public static void main(String args[]){ String toUpdate="password"; getSust("",toUpdate); System.out.println(possibilities); } public static void getSust(String prefix, String rest){ if(rest.length()>0){ // System.out.println(prefix+"-"+rest); THIS PRINTS DUPLICATES possibilities.add(prefix+rest); if(rest.charAt(0) == 's'){ getSust(prefix+"$", rest.substring(1)); } if(rest.charAt(0) == 'a'){ getSust(prefix+"@", rest.substring(1)); } getSust(prefix+rest.charAt(0), rest.substring(1) ); } } }