Amazon Interview Question for SDE1s


Country: India
Interview Type: Phone Interview




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

Java approach. Takes O(n!):

{

public static void permutations(String word, String perm){
        if(word.equals("")){
            System.out.println(perm);
            return;
        }
        
        for(int i = 0; i < word.length(); i++){
            StringBuffer word_util = new StringBuffer(word);
            word_util.deleteCharAt(i);
            
            String perm_util = perm;
            perm_util += word.charAt(i);
            
            permutations(word_util.toString(), perm_util);
        }
        
    }

}

- NL June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it takes O(e*n!)

- Ievgen June 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Please correct me if I am wrong.

public static int permute(String prefix,String s)
{
        int n=s.length();
        if(n==0)
        {
             System.out.println(prefix+"\t");
        }
        for(int i=0;i<n;i++)
        {
            permute(prefix+s.charAt(i),s.substring(0,i)+s.substring(i+1,n)); 
        }
        
}

- wolfengineer June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you need change from "public static int " to "public static void"

- yqin5678 January 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void Amazone10()
{
	string s("451");
	cout << "Initial: " << s << endl;

	sort(s.begin(), s.end());
	cout << "Sorted: " << s << endl;

	do
	{
		cout << "Perm: " << s << endl;
	}	while(next_permutation(s.begin(), s.end()));
}

- Anonymous June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#define MAX 100

void swap(char *c1, char c2 *);
void printStringPermutation(char *str, int i, int len);

int main(int argc, char **argv)
{
  char str[MAX]={0};
  unsigned int len = 0;
  printf("\nEnter string:");
  scanf("%s", str);
  len = strlen(str);
  len --;
  printStringPermutation(str, 0, len);
  return 0;  
}
void swap(char *c1, char *c2)
{
  char temp;
  temp = *c1;
  *c1 = *c2;
  *c2 = temp;
}
void printStringPermutation(char *str, int i, int len)
{
  if (i == len)
    printf("\n%s", str);
  else
    for (j = i; j <= len; j++)
      {
         swap(str[i], str[j]);
         printStringPermutation(str, (i+1), len))
         swap(str[i], str[j]);//this backtrack to previous combination
      }
}

Would take O(!n*n)

- Baij June 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not iterative

- Sugarcane_farmer June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Sugarcane yeah ..its not iterative...question doesn't mention about the approach which should be taken

- Baij June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it takes O(!n*1.7)

- Ievgen June 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Unless you do it wrong, I don't think Dynamic Programming will help you gain anything. This would take exponential time.

- Anonymous June 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the problem is printing all perm DP will not help. The search space is n! hence computation time will be O(n!), unless some more constraint set is included

- Rajib Banerjee June 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void CombString(string strValue)
        {
            // Print the initial string
            Console.WriteLine(strValue);
            char[] array = strValue.ToCharArray();
            int n = array.Length;
            int[] permutationnInts = new int[n]; // Index control array initially all zeros
            int i = 1;
            while (i < n)
            {
                if (permutationnInts[i] < i)
                {
                    int j = ((i%2) == 0) ? 0 : permutationnInts[i];
                    char temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    strValue = new string(array);
                    Console.WriteLine(strValue); // Print the string
                    permutationnInts[i]++;
                    i = 1;
                }
                else
                {
                    permutationnInts[i] = 0;
                    i++;
                }
            }
        }

- Ram June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;
#include <cstring>
#include <string> 
#include <unordered_map>
#include<stdlib.h>
#include<stdio.h>
#include <deque>
#include <vector>

void permu(deque<char> &i, deque<char> &o) {
        if (i.empty()) {
            // print the o list
            for(int k =0; k <o.size(); k++) {
                cout << o[k];
            }
            cout <<"\n";
            return;
        }
        
        for(int it = 0; it  < i.size(); it++) {
            // pick one and insert into the out queue
            o.push_back(i.front());
            i.pop_front();
            
            permu(i, o);
            i.push_back(o.back());
            o.pop_back();
            
        }
        
}


void permutation_do(char *s) {
    int slength = strlen(s);
    deque<char> in;
    deque<char> out;
    for(int i = 0; i < slength; i++) {
        in.push_back(s[i]);
    }
    
    permu(in, out);
}

int main() {
	// your code goes here
	char a[] = {"ABCD"};
	permutation_do(a);
	return 0;
}

- Anonymous May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;
#include <cstring>
#include <string> 
#include <unordered_map>
#include<stdlib.h>
#include<stdio.h>
#include <deque>
#include <vector>

void permu(deque<char> &i, deque<char> &o) {
        if (i.empty()) {
            // print the o list
            for(int k =0; k <o.size(); k++) {
                cout << o[k];
            }
            cout <<"\n";
            return;
        }
        
        for(int it = 0; it  < i.size(); it++) {
            // pick one and insert into the out queue
            o.push_back(i.front());
            i.pop_front();
            
            permu(i, o);
            i.push_back(o.back());
            o.pop_back();
            
        }
        
}


void permutation_do(char *s) {
    int slength = strlen(s);
    deque<char> in;
    deque<char> out;
    for(int i = 0; i < slength; i++) {
        in.push_back(s[i]);
    }
    
    permu(in, out);
}

int main() {
	// your code goes here
	char a[] = {"ABCD"};
	permutation_do(a);
	return 0;
}

- ali.kheam May 01, 2017 | 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