Amazon Interview Question Applications Developers
Country: United States
Interview Type: In-Person
Then you have to sort the input string first, then modify the code not to repeat previous character... A modification can be following (i write in C++)
public void
permutation(String prefix, String str) { // str must be sorted first!
int n = str.length();
if (n == 0)
System.out.println(prefix);
else
for(int i = 0;i < n;i++){
if ( i>0 and str.charAt(i) == str.charAt(i-1)) continue;
permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
}
};
// code in C++:
sort(inputStr.begin(), inputStr.end());
permutation("", inputStr);
You can maintain a hashmap for storing the output. Instead of printing the prefix you can put it into the map and return it. This will avoid duplicates..
Sorting the input and removing duplicates will alter the length of the combination. So, I think this method should be simple..
#include<iostream>
#include<string>
using namespace std;
bool swap(string& str, int i, int j){
char c = str[i];
str[i] = str[j];
str[j] = c;
return true;
}
void printAnagram(string str, int pos){
if(pos == str.length()){
cout<<str<<endl;
return;
}
for(int i = pos; i < str.length(); ++i){
//deal with duplicate
if(str[i] == str[pos] && i != pos)
continue;
swap(str, i, pos);
printAnagram(str, pos + 1);
swap(str, i, pos);
}
}
int main(){
printAnagram("aab", 0);
return 0;
}
This is a permutation problem which can be solved by backtracking.
void permute(char *str, int start, int end)
{
if (start == end)
printf("%s\n", str);
else
{
for (int i = start; i <= end; i++)
{
swap((str+start), (str+i));
permute(str, start+1, end);
swap((str+start), (str+i)); //backtrack
}
}
}
def recur(cur_list, sol):
if cur_list == []:
res.append(sol)
flag = False
for i in range(len(cur_list)):
if flag == True and cur_list[i] == cur_list[i-1]:
continue
flag = True
cur_sol = sol
cur_sol += cur_list[i]
next_list = cur_list[:i] + cur_list[i+1:]
recur(next_list, cur_sol)
res = []
str_in = "amazon"
list_in = list(str_in)
list_in.sort()
recur(list_in, "")
res.sort()
for w in res:
print w
public void allComb(String soFar , String remaining)
{
if(reamainng .lenght <=0){
System.out.println(remaining);
}
else{
for(int i = 0 ;i< reamining.lenght,i++)
{
String next = soFar + remaining.chatAt(i);
remaining = remaining.substring(0,i) + remaining.substring(i+1);
allComb(next,remaining);
}
}
ex ==allComb("","Danish");
Agree with the consensus above. Its same as finding perms of a string.
Here's working C++ code, with hashmap to remove any dups:
vector<string> findSubStr(string s){
//find all unique substr of s. Hashmap used
//to filter out the duplicates
vector<string> v (1);
vector<string> v1 (1);
char c;
int i=0;
string s1, t;
string subS;
unordered_map<string, int>m;
if(s.length() <= 1){
c = s[0];
s1.append(1, c);
v[0] = s1;
return v;
}
c = s[0];
s1.append(1,c);
v[0] = s1;
m[s1] = 1;
subS = s.substr(1, s.length()-1);
v1 = findSubStr(subS);
for(i=0; i < v1.size(); i++){
t = v1[i];
if(m[t] == 0){
v.push_back(t);
m[t] = 1;
}
t = s1 + t;
if(m[t] == 0){
v.push_back(t);
m[t] = 1;
}
}
return v;
}
#include<iostream>
#include<string>
using namespace std;
void swap(string& str, int i, int j){
char c = str[i];
str[i] = str[j];
str[j] = c;
}
void printAnagram(string str, int pos){
if(pos == str.length()){
cout<<str<<endl;
return;
}
for(int i = pos; i < str.length(); ++i){
//deal with duplicate
if(str[i] == str[pos] && i != pos)
continue;
swap(str, i, pos);
printAnagram(str, pos + 1);
swap(str, i, pos);
}
}
int main(){
printAnagram("aab", 0);
return 0;
}
class Solution {
public:
vector<string> stringAnograms( string str ) {
if( str.size()==0 ) return vector<string>();
if( str.size()==1 ) return vector<string>(1, str);
// sort the string
sort( str.begin(), str.end() );
vector<string> anagrams;
queue<pair<string, string> > strQueue;
strQueue.push( pair<string, string>("", str) );
while ( strQueue.front().second.length()!=0 ) {
const string prefix = strQueue.front().first;
const string suffix = strQueue.front().second;
strQueue.pop();
for (int i=0; i<suffix.length(); i++) {
if( i>0 && suffix[i]==suffix[i-1] ) continue;
strQueue.push( pair<string, string>(prefix+suffix[i], suffix) );
strQueue.back().second.erase(i ,1);
}
}
while ( !strQueue.empty() ) {
anagrams.push_back( strQueue.front().first );
strQueue.pop();
}
return anagrams;
}
};
the above logic is right but doesn't work for duplicate characters
I have done few corrections and below is the code
while(1)
{
k=ch[i%siz];
ch[i%siz]=ch[(i+1)%siz];
ch[(i+1)%siz]=k;
i++;
cout << ch << endl;
//cout << sh << endl;
//cin >> st;
if(!strcmp(ch, sh))
break;
count++;
}
cout << count << endl;
}
private char[] nextPermutation(char []a) {
int n = a.length;
if (n == 1) return new char[]{};
int k = n - 2;
while(a[k] >= a[k + 1]) {
k--;
if (k < 0)
return new char[]{};
}
int idx = -1;
for(int i=k+1;i<n;i++){
if (a[k] < a[i] && (idx == -1 || a[idx] > a[i])) {
idx = i;
}
}
char t = a[idx];
a[idx] = a[k];
a[k] = t;
Arrays.sort(a, k + 1, n);
return a;
}
private void run() {
char []a = next().toCharArray();
Arrays.sort(a);
while(a.length > 0) {
System.out.println(Arrays.toString(a));
a = nextPermutation(a);
}
}
// iterative version
void shift_string(CStringA *tmp,int index,int len)
{ //String, index, String Length
CStringA str = *tmp;
char c_tmp = str[index];
for(index;index<len-1;index++)
{
str.SetAt(index,str[index+1]);
}
str.SetAt(index,c_tmp);
tmp->SetString(str);
}
// swap -> shift -> swap -> shift -> ..... -> FINISH
void ts(CStringA in)
{
int x =0,y=0;
int len = in.GetLength();
int min=len-2;//it points 'len-2' index
bool exit = false;//loop escape check value;
int *index_arr = new int[len];//3,4,5,6,7~ //
memset(index_arr ,0,sizeof(int)*(len) );
char c_tmp; //swap temp value
//length range 0~2
if(len == 1)
{
printf("%s\n",in);
exit = true;
}
else if(len == 2)
{
printf("%s\n",in);
c_tmp = in[0];
in.SetAt(0,in[1]);
in.SetAt(1,c_tmp);
printf("%s\n",in);
exit = true;
}
else if(len == 0)
{
exit = true;
}
//
for(;exit == false;)
{
//basic operations ( swap last two items)
printf("%s\n",in);
c_tmp = in[min];
in.SetAt(min,in[min+1]);
in.SetAt(min+1,c_tmp);
printf("%s\n",in);
c_tmp = in[min];
in.SetAt(min,in[min+1]);
in.SetAt(min+1,c_tmp);
index_arr[0]++;
//
for(y=0;;y++)
{
if(index_arr[y] == (3+y)) //is 'index_arr[y]' reaches specific value
{
if(index_arr[y] == len)// (index_arr == len) ==> last level loop
{
exit = true;
break;
}
else
{
if(y+1 < len-1 )
{
//index carry
index_arr[y] = 0;
index_arr[y+1]++; //next value increament
}
}
shift_string(&in,len - (3+y), len);
}
else //is on progressing?
{
shift_string(&in,len -(3+y),len);
/*
CString s = "0123";
shift_string(&s,0,len);
"0123" -> "1230"
*/
break;
}
}
}
delete[] index_arr;
}
int main()
{
CStringA t("01234567");
// printf("start = %s\n",t);
ts(t);
return 0;
}
public class StringAnagrams {
public static void main(String ...args){
String str = "amz";
char []chars = str.toCharArray();
for(int i=0;i<str.length();i++){
for(int j=0;j<str.length()-1;j++){
char temp = chars[j];
chars[j] = chars[j+1];
chars[j+1] = temp;
System.out.println(chars);
}
}
}
}
yes you are right.. this wont generate permutations.. i guess i didn't fully understand the question.. thx for correcting me!
@1337.. nop.. not my account.. i guess he/she got confused with question as well..
the above logic is right but doesn't work for duplicate characters
I have done few corrections and below is the code
while(1)
{
k=ch[i%siz];
ch[i%siz]=ch[(i+1)%siz];
ch[(i+1)%siz]=k;
i++;
cout << ch << endl;
//cout << sh << endl;
//cin >> st;
if(!strcmp(ch, sh))
break;
count++;
}
cout << count << endl;
}
This is same as printing all the permutations of the string..
- arsragavan March 23, 2014public void permutation(String prefix, String str) { int n = str.length(); if (n == 0) System.out.println(prefix); else for(int i = 0;i < n;i++) permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n)); }