Adobe Interview Question




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

class StringPermutation {
    
    /**
    * @param args
    */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String input = "abb";
        permutation(input, "");
    }
    
    private static void permutation(String input, String sofar) {
        // TODO Auto-generated method stub
        
        if (input.equals("")) {
            System.out.printf("%s,", sofar);
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (input.indexOf(c, i + 1) != -1)
            continue;
            permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
        }
    }
    
}

- MaYanK on July 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one!

- sushbis on August 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please use comments :D

And repost this..

- very nice one on September 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

# include <stdio.h>
# include <conio.h>


void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}


void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
}
}


int main()
{

char a[] = "ABC";
permute(a, 0, 2);
getchar();
return 0;
}

- Alok on January 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Working Python Code As below....

def dp_per(x,y):
    #print x,y
    if len(y)==1:
        print x+y
        global count
        count=count+1
    else:
        cache=[]
        dp_per(x+y[0],y[1:])
        cache.append(y[0])
        for i in range(1,len(y)):
            if y[i] not in cache:
                cache.append(y[i])
                dp_per(x+y[i],y[1:i]+y[0]+y[i+1:])
print 'enter your String !!!!'
x=raw_input()
count=0
print 'Ans as below:'
dp_per('',x)
print 'Total Ans['+str(count)+']:'

- dutta.dipankar08 on February 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <hash_set>

void PrintAnagrams(char * str,
         size_t offset = 0, size_t * pLen = NULL)
{
   if (!offset) pLen = new size_t(strlen(str));

   if (offset == *pLen - 1)
      std::cout << str << std::endl;
   else {
      stdext::hash_set<char> distinct;
      distinct.insert(str[offset]);
      PrintAnagrams(str, offset + 1, pLen);

      for (int i = offset + 1; i < *pLen; ++i)
         if (distinct.find(str[i]) == distinct.end()) {
            distinct.insert(str[i]);
            std::swap(str[offset], str[i]);
            PrintAnagrams(str, offset + 1, pLen);
            std::swap(str[offset], str[i]);
         }
      }

   if (!offset) delete pLen;
}

- fiddler.g on July 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can do without the hash set.

- Anonymous on July 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How give the code

- Anonymous on July 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sort the array at first.
the time complexity (O(n)) is far less than the time complexity for permutation (O(n!))

- anonymous on July 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do it iteratively .....

- Anonymous on July 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="c++" line="1" title="CodeMonkey30135" class="run-this">#include<iostream>
#include<stdio.h>
#include<string>
#include<set>

using namespace std;


void permute(set<string> &repo,string constructed, string remaining) {
if(remaining.length() == 0) {
//printf("%s\n",constructed);
repo.insert(constructed);
return;
}
for(int i=0;i<remaining.length();++i) {
permute(repo,
constructed+remaining[i],
string(remaining,0,i)+string(remaining,i+1,remaining.length()-i-1));
}
}

void print_anagrams(string input) {
set<string> repo;
permute(repo,string(""),input);
set<string>::iterator i=repo.begin();
printf("Printing permutations..\n");
while(++i!=repo.end())
printf("%s\n",i->c_str());
}


//Program to print all permutations of a string without repetition
int main(int argc, char **argv) {
string a("abad");
print_anagrams(a);
return 0;
}</pre><pre title="CodeMonkey30135" input="yes">
</pre>

- Anonymous on July 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All the above solutions are not scalable (aka. inefficient). Number of possible permutations are very large. So if it needs to check (either manually or using STL like set), it is not desirable approach.

I remember in Rosen's discrete mathematics book there is an iterative solution that uniquely generate the permutations w/o any check (when the given string has repeated char like "ABCDABCABA". Anyone has any idea?

- anonymous on July 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. Find the last character smaller than the one that follows it.
2. Swap it with the last character larger than it.
3. Reverse the string forward of the swap point.

- Anonymous on July 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Really nice solution.

Short but really hard to understand but finally i got it.

- nitin on August 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void permute(string str, string rem)
{
int len = rem.size();
if(len == 0)
{
printf("%s\n", str.c_str());
return;
}
int i = str.size() - len;
for(int x=0; x<len; x++)
{
str[i] = rem[x];
string r = rem;
r.erase(x, 1);
permute(str, r);
}
}

void printall_perm(string x)
{
permute(x,x);
}

- i.shahin on September 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hello

- Anonymous on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ArrayList<String> getPerms(String s) {
   ArrayList<String> permutations = new ArrayList<String>();
   if (s == null) { // error case
     return null;
   } else if (s.length() == 0) { // base case
     permutations.add(“”);
     return permutations;
   }
   char first = s.charAt(0); // get the first character
   String remainder = s.substring(1); // remove the first character
   ArrayList<String> words = getPerms(remainder);
   for (String word : words) {
     for (int j = 0; j <= word.length(); j++) {
       permutations.add(insertCharAt(word, first, j));
     }
   }
   return permutations;
 }
 public static String insertCharAt(String word, char c, int i) {
   String start = word.substring(0, i);
   String end = word.substring(i);
   return start + c + end;
 }

- bicepjai on August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What would be the complexity of your solution?

- Mandy on October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n!)

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> on December 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

anagrams("Hello",0,5);

public static void print anagrams(String str, int start, int n)
{
	if(start == n)
	{
		System.out.println(str);
	}else{
		for(int i = start; i < n ; i++)
		{
			swap(str,start,i);
			anagrams(str,start+1,n)
			swap(str,start,i);
			
		}
	}

}

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> on December 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void swap(char str[],int i, int j){
	char tmp = str[i];
	str[i] = str[j];
	str[j] = tmp;
}

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> on December 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I prefer using char[] than String so I little change

public static void print anagrams(char str[], int start, int n)

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> on December 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <set>
#include <string>

using namespace std;

void printPermut(string s, string prefix = "") {
    if (s.empty()) {
        if (!prefix.empty()) {
            cout << prefix << endl;
        }
    }
    set<char> visited;
    string cpy;
    for (int i = 0; i < s.length(); ++i) {
        if (visited.find(s[i]) == visited.end()) {
            visited.insert(s[i]);
            cpy = string(s);
            cpy.erase(i, 1);
            printPermut(cpy, prefix + s[i]);
        }
    }
}

int main(int argc, char **argv) {
    if (argc == 2) {
        printPermut(string(argv[1]));
    }
}

- Thomas on February 14, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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