Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
I believe yes. The char is essentially the same as numbers. So the task is to output the number abcd that a<b<c<d. Here first we use their ascii order(but regardless of uppercase/lowercase) to sort the char sequences to get a candidate pool with size L. Second we generate the sequence with length from L to 1, in a way that we select a char from the candidate pool, the append a smaller one on the front.
The termination condition is when size of our sequence meet the desired length or there is no candidate to choose from the pool.
In this way we don't need to get all the permutation of the chars.
a. Generate all possible permutations using the char sequence .
public static void allPossibleCominations(String prefix , String str) {
int n = str.length();
if(n==0) {
set.add(prefix);
}
else {
// System.out.println(str);
set.add(str);
for(int i=0;i<n;i++) {
allPossibleCominations(prefix+str.charAt(i), str.substring(0,i)+str.substring(i+1,n));
}
}
b. Now , iterate through each word . Consider each character and if the ascii less than the pervious character , disqualify the woed . Else print it
why can't we just sort the sequence of characters using ASCII value(keeping in mind the upper case and lower case) and then get the combinations?
Could you please clarify the input? I am not able to understand what is the input for the given question. Number of Character Sequence???
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class WellOrderedWord {
public static void main(String[] args) {
String prefix = "";
String str= "maharaja";
Set<String> set = new TreeSet<String>();
allPossibleCominations(prefix, str,set);
printPerms(set);
}
public static void allPossibleCominations(String prefix , String str, Set<String> set) {
int n = str.length();
if(n==0) {
set.add(prefix);
}
else {
set.add(str);
for(int i=0;i<n;i++) {
String sub1 = str.substring(0,i);
String sub2 = str.substring(i+1,n);
allPossibleCominations(prefix+str.charAt(i), sub1+sub2,set);
}
}
}
public static void printPerms(Set<String> set) {
for(String word:set) {
int count =0;
for(int i=1; i <word.length(); i++) {
int wordLen = word.length()-1;
int secondChar = word.charAt(i);
int firstChar = word.charAt(i-1);
int sum = secondChar-firstChar;
if(sum>1) {
count++;
}
if(count==wordLen) {
System.out.println(word);
}
}
}
}
}
My solution. tested and it handles lower case and upper case combinations of well ordered strings
private static void getWellOrderedString(String currentString,int charsLeft)
{
recursion_count++;
if(charsLeft==0)
{
System.out.println(currentString);
stringCount++;
}
char i, j;
if(currentString.isEmpty()) {
i='a';
j = 'A';
}
else {
char lastchar = currentString.charAt(currentString.length()- 1);
if(lastchar >= 'a' && lastchar < 'z') {
i=(char) (lastchar + 1);
j = (char) (lastchar - 32 + 1) ;
}
else if(lastchar >= 'A' && lastchar < 'Z') {
j = (char) (lastchar + 1);
i = (char) (lastchar + 32 + 1);
}
else {
return;
}
}
for (;i <='z' && charsLeft > 0; i++)
{
getWellOrderedString(currentString+i, charsLeft-1);
}
for (;j <='Z' && charsLeft > 0; j++)
{
getWellOrderedString(currentString+j, charsLeft-1);
}
}
public class Permute{
public static void main(String args[]) {
permutation("", "aBIY");
/*String a= "a";
String b="b";
System.out.println(b.compareTo(a));*/
}
private static void permutation(String prefix, String str) {
int n = str.length();
String target="";
if (n == 0){
target = prefix;
}
else {
target = str;
boolean flag=true;
for(int j=1;j<target.length();j++){
String b= target.substring(j).toLowerCase();
String a= target.substring(j-1).toLowerCase();
if(b.compareTo(a)<0){
flag=false;
}
}
if(flag==true){
System.out.println(target);
}
for (int i = 0; i < n; i++){
char a=str.charAt(i);
String b = str.substring(0, i);
String c = str.substring(i+1, n);
permutation(prefix + a, b + c);
}
}
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) isWellOrdered(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
private static void isWellOrdered(String permute) {
char[] c = permute.toCharArray();
int len = c.length;
for (int i = 0; i < len; i++)
{
for (int j = i; j < len; j++)
{
if (c[j] < c[i]) return;
}
}
System.out.println(permute);
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
String str = "abcd";
System.out.println("Input char seq is"+str);
permutation(str.toLowerCase());
}
}
I have written a code which produces all ordered strings. All it takes is the total number of input characters. You can also specify the start of the string if you wish to. If you don't specify, it gives you all ordered strings of that length starting from 'a'.
public class OrderedString {
//private static int stringCount=0;
public static void getAllOrderedStrings(String currentString, int charsLeft) {
if(charsLeft==0)
{
System.out.println(currentString);
//stringCount++;
}
char i;
if(currentString.isEmpty())
i='a';
else
i=(char) (currentString.charAt(currentString.length()-1)+1);
for (;i<='z';i++)
{
getAllOrderedStrings(currentString+i, charsLeft-1);
}
}
public static void main(String args[]) {
getAllOrderedStrings("", 4);
}
}
#include<iostream>
using namespace std;
#include<string>
using std::string;
void main()
{
string s;
cin >> s;
for (string::iterator i = s.begin(); i < s.end(); i++)
{
for (string::iterator j = i+1; j < s.end(); j++)
{
if ((*i >= 97 && *j >= 97) || (*i < 97 && *j < 97))
{
if (*i > *j)
{
char tmp;
tmp = *i;
*i = *j;
*j = tmp;
}
}
else
{
if (*i >= 97 && *j < 97)
{
if ((*i - 32) > *j)
{
char tmp;
tmp = *i;
*i = *j;
*j = tmp;
}
}
else if (*i < 97 && *j >= 97)
{
if (*i>(*j - 32))
{
char tmp;
tmp = *i;
*i = *j;
*j = tmp;
}
}
}
}
}
string::iterator output = s.begin();
while (output != s.end())
{
cout << *output;
output++;
}
system("pause");
}
public static void wellorderedcom(ArrayList<String> sq){
Collections.sort(sq, String.CASE_INSENSITIVE_ORDER);
ArrayList<String>order=new ArrayList<String>();
int length=0;
for(int i=0;i<sq.size();i++){
for(int j=0;j<length;j++){
order.add(order.get(j)+sq.get(i));
}
order.add(sq.get(i));
length=order.size();
}
for(String s:order){
System.out.println(s);
}
}
public static void wellorderedcom(ArrayList<String> sq){
Collections.sort(sq, String.CASE_INSENSITIVE_ORDER);
ArrayList<String>order=new ArrayList<String>();
int length=0;
for(int i=0;i<sq.size();i++){
for(int j=0;j<length;j++){
order.add(order.get(j)+sq.get(i));
}
order.add(sq.get(i));
length=order.size();
}
for(String s:order){
System.out.println(s);
}
}
public static void wellOrderedAll(String pre, int n) {
if (n == 0) {
System.out.println(pre);
} else {
char[] chars = new char[2];
if (pre.length() != 0) {
char last = pre.charAt(pre.length() - 1);
if (last >= 'a' && last <= 'z') {
last++;
chars[0] = last;
int val = last - 32;
chars[1] = (char) val;
} else {
last++;
chars[1] = last;
int val = last + 32;
chars[0] = (char) val;
}
} else {
chars[0] = 'a';
chars[1] = 'A';
}
for (int i = 0; i < chars.length; i++) {
if (i == 0) {
for (char j = chars[i]; j <= 'c'; j++) {
wellOrderedAll(pre + j, n - 1);
}
} else {
for (char j = chars[i]; j <= 'C'; j++) {
wellOrderedAll(pre + j, n - 1);
}
}
}
}
}
Logic:
1. Get the input sequence
2. Draw combinations of the sequence
3. Permute each sequence
4. Check if the sequence is Well Ordered and output.
- Vathsan December 28, 2014/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package interviews; import java.util.List; import java.util.ArrayList; /** * * @author sreevathsan */ public class OrderedCharSeq { public static List<String> perms = new ArrayList(); public static char[] swap(char[] ch, int i, int j){ char tmp = ch[i]; ch[i] = ch[j]; ch[j] = tmp; return ch; } public static void permute(char[] ch, int i, int n){ if(i==n){ //System.out.println(ch); String res = new String(ch); //System.out.println(res); perms.add(res); return; } else{ for(int j=i;j<=n;j++){ ch = swap(ch,i,j); permute(ch, i+1, n); ch = swap(ch,i,j); } } } public static void generateCombos(String str){ for(int i=1; i<=str.length();i++){ for(int j=0; i+j<=str.length();j++){ String tmpStr = str.substring(j,j+i); //System.out.println(tmpStr); if(i>1) permute(tmpStr.toCharArray(),0,i-1); } } perms.add("$$$"); int i=0; System.out.println("Possible sequence combinations are"); while(!perms.get(i).equalsIgnoreCase("$$$")){ System.out.println(perms.get(i)); i++; } } public static boolean isOrderedSeq(String str){ char ch[] = str.toCharArray(); for(int i=0;i<str.length()-1;i++){ if(ch[i] > ch[i+1]){ return false; } } return true; } public static void computeOrderedSeq(String str){ generateCombos(str); System.out.println("Ordered Sequences are "); int i=0; while(!perms.get(i).equalsIgnoreCase("$$$")){ String seq = perms.get(i); if (isOrderedSeq(seq.toLowerCase())) { System.out.println(seq); } i++; } } public static void main(String[] args){ String str = "abcd"; System.out.println("Input char seq is"+str); computeOrderedSeq(str); } }