Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
In C++:
#include <string>
#include <iostream>
void anagram(std::string &word, int n)
{
if (n <= 0) {
std::cout << word << "\n";
return;
}
if (word[n] < 'a' or word[n] > 'z') {
anagram(word, n-1);
return;
}
int i;
for (i = n; i >= 0; --i) {
if (word[i] < 'a' or word[i] > 'z')
continue;
char tmp = word[i];
word[i] = word[n];
word[n] = tmp;
anagram(word, n-1);
}
}
void print_anagrams(const std::string &w)
{
std::string word = w;
anagram(word, word.length()-1);
}
def comp(word, i, possi):
if i == len(word) or len(possi) == 0:
print(word)
return
if word[i].isupper() or word[i].isdigit() or (not word[i].isalpha() and not word[i].isdigit()):
comp(word, i+1, possi)
else:
for s in possi:
copyWord = list(word)
copyWord[i] = s
copyWord = "".join(copyWord)
copyPossi = list(possi)
copyPossi.remove(s)
comp(copyWord, i+1, copyPossi)
word = "q1eRz"
import re
regex = re.compile('[^a-z]')
comp(word, 0, list(regex.sub('', word)))
public class question {
public static void main (String args[]){
String test = "Hi8Test(*!good";
for (int i = 0; i<test.length(); i++){
if(test.charAt(i)>= 'a' && test.charAt(i)<= 'z'){
reorderString(test, i);
}
}
}
public static void reorderString(String test, int index){
char [] temp = test.toCharArray();
for (int j = 0; j<test.length(); j++){
if(temp[j]>='a' && temp[j]<='z'){
char tempChar = temp[index];
temp[index] = temp[j];
temp[j] = tempChar;
System.out.println(new String (temp));
}
}
}
}
Not optimal in terms of run time, but a quick solution
this is a totally wrong solution, Try the sample text "Hello", and there are a lot of duplicates, what's more, "Hleol" and some other permutations never happen
// changing a bit of logic and you will get the answer
package interviews.epic;
/**
*
* @author venkatramreddykunta
*/
public class Anagram {
public static void main (String args[]){
String test = "Hi8Test(*!good";
for (int i = 0; i<test.length(); i++){
if(test.charAt(i)>= 'a' && test.charAt(i)<= 'z'){
reorderString(test, i);
}
}
}
public static void reorderString(String test, int index){
char [] temp = test.toCharArray();
for (int j = index+1; j<test.length(); j++){
if(temp[j]>='a' && temp[j]<='z'){
swap(temp, index, j);
System.out.println(new String (temp));
swap(temp, index, j);
}
}
}
public static void swap(char[] temp, int index, int j) {
char tempChar = temp[index];
temp[index] = temp[j];
temp[j] = tempChar;
}
}
/* previous answer
Hi8Test(*!good
He8Tist(*!good
Hs8Tiet(*!good
Ht8Ties(*!good
Hg8Ties(*!tood
Ho8Ties(*!tgod
Ho8Ties(*!tgod
Hd8Ties(*!tgoo
He8Tist(*!good
He8Tist(*!good
He8Tsit(*!good
He8Ttis(*!good
He8Tgis(*!tood
He8Tois(*!tgod
He8Tois(*!tgod
He8Tdis(*!tgoo
Hs8Teit(*!good
Hs8Tiet(*!good
Hs8Tiet(*!good
Hs8Tite(*!good
Hs8Tige(*!tood
Hs8Tioe(*!tgod
Hs8Tioe(*!tgod
Hs8Tide(*!tgoo
Ht8Tesi(*!good
Ht8Tise(*!good
Ht8Ties(*!good
Ht8Ties(*!good
Ht8Tieg(*!sood
Ht8Tieo(*!sgod
Ht8Tieo(*!sgod
Ht8Tied(*!sgoo
Hg8Test(*!iood
Hg8Tist(*!eood
Hg8Tiet(*!sood
Hg8Ties(*!tood
Hg8Ties(*!tood
Hg8Ties(*!otod
Hg8Ties(*!otod
Hg8Ties(*!dtoo
Ho8Test(*!giod
Ho8Tist(*!geod
Ho8Tiet(*!gsod
Ho8Ties(*!gtod
Ho8Ties(*!tgod
Ho8Ties(*!tgod
Ho8Ties(*!togd
Ho8Ties(*!tdgo
Ho8Test(*!goid
Ho8Tist(*!goed
Ho8Tiet(*!gosd
Ho8Ties(*!gotd
Ho8Ties(*!togd
Ho8Ties(*!tgod
Ho8Ties(*!tgod
Ho8Ties(*!tgdo
Hd8Test(*!gooi
Hd8Tist(*!gooe
Hd8Tiet(*!goos
Hd8Ties(*!goot
Hd8Ties(*!toog
Hd8Ties(*!tgoo
Hd8Ties(*!tgoo
Hd8Ties(*!tgoo
*/
/* updated answer
He8Tist(*!good
Hs8Teit(*!good
Ht8Tesi(*!good
Hg8Test(*!iood
Ho8Test(*!giod
Ho8Test(*!goid
Hd8Test(*!gooi
Hi8Tset(*!good
Hi8Ttse(*!good
Hi8Tgst(*!eood
Hi8Tost(*!geod
Hi8Tost(*!goed
Hi8Tdst(*!gooe
Hi8Tets(*!good
Hi8Tegt(*!sood
Hi8Teot(*!gsod
Hi8Teot(*!gosd
Hi8Tedt(*!goos
Hi8Tesg(*!tood
Hi8Teso(*!gtod
Hi8Teso(*!gotd
Hi8Tesd(*!goot
Hi8Test(*!ogod
Hi8Test(*!oogd
Hi8Test(*!doog
Hi8Test(*!good
Hi8Test(*!gdoo
Hi8Test(*!godo
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication2
{
class Anagram
{
public static ArrayList al = new ArrayList();
static void Main(string[] args)
{
string str = "q1eRz";
char[] charArry = str.ToCharArray();
permute(charArry, 0, str.Length - 1);
var uniqueList = al.ToArray().Distinct();
foreach (var item in uniqueList)
{
Console.WriteLine(item);
}
Console.ReadKey();
}
static void permute(char[] arry, int i, int n)
{
int j;
string s;
if (i == n)
{
s = new string(arry);
al.Add(s);
//Console.WriteLine(s);
}
else
{
for (j = i; j <= n; j++)
{
swap(ref arry[i], ref arry[j]);
permute(arry, i + 1, n);
swap(ref arry[i], ref arry[j]); //backtrack
}
}
}
static void swap(ref char a, ref char b)
{
if ((a >= 'a' || a >= 'A') && (a <= 'z' || a <= 'Z') && (b >= 'a' || b >= 'A') && (b <= 'z' || b <= 'Z'))
{
char tmp;
tmp = a;
a = b;
b = tmp;
}
}
}
}
#include<stdio.h>
void anagram(char*,int,int);
void swap(char *,char*);
int main(void){
char s[20]={'\0'};
int length;
printf("enter a string\n");
scanf("%s",s);
putchar('\n');
int i;
for(i=0;i<20;i++){
if(s[i]=='\0'){
length=i;
break;
}
}
anagram(s,0,length);
return 0;
}
void anagram(char*s,int i,int length){
int j;
if(i==length)
printf("%s\n",s);
if(s[i]>'z' || s[i]<'a'){
anagram(s,i+1,length);
return;
}
for(j=i;j<length;j++){
if(s[j]<='z' && s[j]>='a'){
swap(&s[i],&s[j]);
anagram(s,i+1,length);
swap(&s[i],&s[j]);
}
else
anagram(s,i+1,length);
}
}
void swap(char* a, char* b){
char c=*a;
*a=*b;
*b=c;
}
#include<stdio.h>
void anagram(char*,int,int);
void swap(char *,char*);
int main(void){
char s[20]={'\0'};
int length;
printf("enter a string\n");
scanf("%s",s);
putchar('\n');
int i;
for(i=0;i<20;i++){
if(s[i]=='\0'){
length=i;
break;
}
}
anagram(s,0,length);
return 0;
}
void anagram(char*s,int i,int length){
int j;
if(i==length)
printf("%s\n",s);
if(s[i]>'z' || s[i]<'a'){
anagram(s,i+1,length);
return;
}
for(j=i;j<length;j++){
if(s[j]<='z' && s[j]>='a'){
swap(&s[i],&s[j]);
anagram(s,i+1,length);
swap(&s[i],&s[j]);
}
else
anagram(s,i+1,length);
}
}
void swap(char* a, char* b){
char c=*a;
*a=*b;
*b=c;
}
public static void main (String args[]){
String input = "AbcDe";
reorderString(input, "");
}
public static void reorderString(String test, String res){
//char[] temp = test.toCharArray();
System.out.println(res+test);
if (test.length()==1){
System.out.println(res+test);
} else {
int i;
for (i=0;i<test.length();i++){
if ('a'<=test.charAt(i)&& test.charAt(i)<='z'){
for (int j=i+1;j<test.length();j++){
if ('a'<=test.charAt(j)&& test.charAt(j)<='z'){
char[] temp = test.toCharArray();
char tempchar = temp[i];
temp[i]=temp[j];
temp[j]= tempchar;
String newString=new String (temp);
reorderString(newString.substring(i+1,test.length()), res+newString.substring(0,i+1));
}
}
}
}
}
}
public static void main (String args[]){
String input = "AbcDe";
reorderString(input, "");
}
public static void reorderString(String test, String res){
//char[] temp = test.toCharArray();
System.out.println(res+test);
if (test.length()==1){
System.out.println(res+test);
} else {
int i;
for (i=0;i<test.length();i++){
if ('a'<=test.charAt(i)&& test.charAt(i)<='z'){
for (int j=i+1;j<test.length();j++){
if ('a'<=test.charAt(j)&& test.charAt(j)<='z'){
char[] temp = test.toCharArray();
char tempchar = temp[i];
temp[i]=temp[j];
temp[j]= tempchar;
String newString=new String (temp);
reorderString(newString.substring(i+1,test.length()), res+newString.substring(0,i+1));
}
}
}
}
}
}
def find_anagram(word):
if len(word) <= 1:
return set(word)
result = set([word])
for i in range(len(word)):
if 64 < ord(word[i]) < 91:
continue
for j in range(i+1,len(word)):
if 96 < ord(word[j]) < 123:
word_ = str(word)
t = word_[i]
word_ = word_[:i] + word_[j] + word_[i+1:]
word_ = word_[:j] + t + word_[j+1:]
inter = set([word_[:i+1]+x for x in find_anagram(word_[i+1:])])
result = result.union(inter)
return result
def find_anagram(word):
if len(word) <= 1:
return set(word)
result = set([word])
for i in range(len(word)):
if 64 < ord(word[i]) < 91:
continue
for j in range(i+1,len(word)):
if 96 < ord(word[j]) < 123:
word_ = str(word)
t = word_[i]
word_ = word_[:i] + word_[j] + word_[i+1:]
word_ = word_[:j] + t + word_[j+1:]
inter = set([word_[:i+1]+x for x in find_anagram(word_[i+1:])])
result = result.union(inter)
return result
public class PermutationOfString {
public static void main(String[] args){
String s = "q1zRe";
Set<String> output = findPermutations2(s);
for(String w: output)
{
System.out.println(w);
}
}
public static Set<String> findPermutations(String s){
Set output = new HashSet();
if(s == null){
return null;
}
else if(s.length() == 0)
{
output.add("");
return output;
}
char ch = s.charAt(0);
String remString = s.substring(1);
Set<String> remainingSet = findPermutations(remString);
for(String newString : remainingSet)
{
for(int i = 0; i <= newString.length(); i++)
{
output.add(addCharAtPosition(newString, ch, i));
}
}
return output;
}
public static String addCharAtPosition(String s, char ch, int i){
return (s.substring(0, i) + ch + s.substring(i));
}
public static Set<String> findPermutations2(String s){
Set output = new HashSet();
HashMap<Integer, Character> indices = new HashMap<Integer, Character>();
StringBuilder indexString = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
{
indices.put(i, s.charAt(i));
indexString.append(i);
}
}
int index1 = 0, index2 = 0;
char[] sArray = s.toCharArray();
Set<String> permutations = findPermutations(indexString.toString());
for(String perm : permutations){
sArray = s.toCharArray();
for(int i = 0; i<indexString.length(); i++)
{
index1 = Integer.parseInt(perm.charAt(i)+ "");
index2 = Integer.parseInt(indexString.charAt(i) + "");
sArray[index2] = indices.get(index1);
}
output.add(new String(sArray));
}
return output;
}
}
package Strings;
import java.util.ArrayList;
public class AnagramsOfLettersOnly {
public static void main(String[] args) {
String input = "Hello";
StringBuilder indexesOfLetters = new StringBuilder();
for(int i = 0; i < input.length(); i++) {
if(input.charAt(i) > 'a' && input.charAt(i) < 'z')
indexesOfLetters.append(i);
}
if(indexesOfLetters.length() == 0 || indexesOfLetters.length() == 1) {
System.out.println("No anagrams for this string");
return;
}
ArrayList<String> permutationsOfIndexes = getPermutations(indexesOfLetters.toString());
for(String eachPermutation: permutationsOfIndexes) {
StringBuilder builder = new StringBuilder(input);
for(int i = 0; i < eachPermutation.length(); i++) {
builder.setCharAt(Character.getNumericValue(indexesOfLetters.charAt(i)), input.charAt(Character.getNumericValue(eachPermutation.charAt(i))));
}
System.out.println(builder);
}
}
public static ArrayList<String> getPermutations(String str) {
ArrayList<String> permutations = new ArrayList<String>();
if(str == null)
return null;
if(str.length() == 0) {
permutations.add(str);
return permutations;
}
char currentChar = str.charAt(0);
String remainingString = str.substring(1);
ArrayList<String> words = getPermutations(remainingString);
for(String word : words) {
for(int i = 0; i <= word.length(); i++) {
String newWord = addCharAt(word, i, currentChar);
permutations.add(newWord);
}
}
return permutations;
}
public static String addCharAt(String word, int i, char currentChar) {
return word.substring(0, i) + currentChar + word.substring(i, word.length());
}
}
import java.util.*;
import java.util.Map.Entry;
class new1{
public static void main(String[] args){
anagram("a1bGc2deP*");
}
public static void anagram(String org){
if(org==null) return;
if(org.length()==0 || org.length()==1) return;
int len=org.length();
HashMap<Integer,Character> map = new HashMap<Integer,Character>();
String resort="";
for(int i=0;i<len;i++){
if(org.charAt(i)>='a' && org.charAt(i)<='z'){
resort+=org.charAt(i);
}else{
map.put(i, org.charAt(i));
}
}
String tem="";
String curr=resort;
int resort_len=resort.length();
List<String> res = new ArrayList<String>();
helper(resort,curr,resort_len,tem,res);
//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
for(String s:res){
for(Entry<Integer, Character> entry:map.entrySet()){
int i=entry.getKey();
char c=entry.getValue();
s=s.substring(0,i)+c+s.substring(i);
}
System.out.println(s);
}
}
public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
if(resort_len==0 && !tem.equals(resort)){
res.add(tem);
return;
}
for(int i=0;i<resort_len;i++){
helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
}
}
}
import java.util.*;
import java.util.Map.Entry;
class new1{
public static void main(String[] args){
anagram("a1bGc2deP*");
}
public static void anagram(String org){
if(org==null) return;
if(org.length()==0 || org.length()==1) return;
int len=org.length();
HashMap<Integer,Character> map = new HashMap<Integer,Character>();
String resort="";
for(int i=0;i<len;i++){
if(org.charAt(i)>='a' && org.charAt(i)<='z'){
resort+=org.charAt(i);
}else{
map.put(i, org.charAt(i));
}
}
String tem="";
String curr=resort;
int resort_len=resort.length();
List<String> res = new ArrayList<String>();
helper(resort,curr,resort_len,tem,res);
//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
for(String s:res){
for(Entry<Integer, Character> entry:map.entrySet()){
int i=entry.getKey();
char c=entry.getValue();
s=s.substring(0,i)+c+s.substring(i);
}
System.out.println(s);
}
}
public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
if(resort_len==0 && !tem.equals(resort)){
res.add(tem);
return;
}
for(int i=0;i<resort_len;i++){
helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
}
}
}
import java.util.*;
import java.util.Map.Entry;
class new1{
public static void main(String[] args){
anagram("a1bGc2deP*");
}
public static void anagram(String org){
if(org==null) return;
if(org.length()==0 || org.length()==1) return;
int len=org.length();
HashMap<Integer,Character> map = new HashMap<Integer,Character>();
String resort="";
for(int i=0;i<len;i++){
if(org.charAt(i)>='a' && org.charAt(i)<='z'){
resort+=org.charAt(i);
}else{
map.put(i, org.charAt(i));
}
}
String tem="";
String curr=resort;
int resort_len=resort.length();
List<String> res = new ArrayList<String>();
helper(resort,curr,resort_len,tem,res);
//Iterator<Entry<Integer, Character>> iter = map.entrySet().iterator();
for(String s:res){
for(Entry<Integer, Character> entry:map.entrySet()){
int i=entry.getKey();
char c=entry.getValue();
s=s.substring(0,i)+c+s.substring(i);
}
System.out.println(s);
}
}
public static void helper(String resort,String curr,int resort_len,String tem,List<String> res){
if(resort_len==0 && !tem.equals(resort)){
res.add(tem);
return;
}
for(int i=0;i<resort_len;i++){
helper(resort,curr.substring(0,i)+curr.substring(i+1,resort_len),resort_len-1,tem+curr.charAt(i),res);
}
}
}
select indexes of characters we can move. generate all permutations of them. replace chars in the original string for each permutation.
- GK February 06, 2015Example:
input: q1eRz
arr: [0,2,4]
possible permutations:
[0,4,2] -> q1zRe
[2,0,4] -> e1qRz
[2,4,0] -> r1zRq
etc...
if you have dictionary check if the anagram is presented in it.