Amazon Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
public String findPattern(String logicalPattern) {
String pattern = "";
int numOfIncrements = countNumOfInc(logicalPattern);
int i = 1, j = logicalPattern.length() + 1;
char[] arr = logicalPattern.toCharArray();
for(int n = 0; n < logicalPattern.length();) {
if(arr[n] == 'I') {
pattern += i;
i = setI(i,pattern,j);
n++;
--numOfIncrements;
} else {
int temp = j - numOfIncrements;
while(arr[n] == 'D') {
pattern += temp--;
n++;
}
}
}
while(pattern.length() < logicalPattern.length() + 1) {
pattern += i++;
}
return pattern;
}
private int setI(int i, String pattern, int j) {
while(pattern.contains(i+"") && i <= j) ++i;
return i;
}
private int countNumOfInc(String logicalPattern) {
int count = 0;
for(char c : logicalPattern.toCharArray()) {
if(c == 'I') ++count;
}
return count;
}
Maximum number = length of input String + 1
First number = Maximum number - no.of character "I" occurrences.
From then loop through the all numbers
public static String sol(String inputString){
if(null == inputString || inputString.isEmpty()) {
return null;
}
int maxNumber = inputString.length()+1;
int count =0;
char inputArray[] = inputString.toCharArray();
for(char input : inputArray){
if('I'==(input)){
count ++;
}
}
int number = maxNumber-count;
List<Integer> numberList = new ArrayList<Integer>();
numberList.add(number);
String output=String.valueOf(number);
for(char input : inputArray){
if(input == 'D'){
number--;
while(numberList.contains(number)){
number--;
}
}
if(input == 'I'){
number ++;
while(numberList.contains(number)){
number++;
}
}
numberList.add(number);
output = output+number;
}
return output;
}
public static String sol(String inputString){
if(null == inputString || inputString.isEmpty()) {
return null;
}
int maxNumber = inputString.length()+1;
int count =0;
char inputArray[] = inputString.toCharArray();
for(char input : inputArray){
if('I'==(input)){
count ++;
}
}
int number = maxNumber-count;
List<Integer> numberList = new ArrayList<Integer>();
numberList.add(number);
String output=String.valueOf(number);
for(char input : inputArray){
if(input == 'D'){
number--;
while(numberList.contains(number)){
number--;
}
}
if(input == 'I'){
number ++;
while(numberList.contains(number)){
number++;
}
}
numberList.add(number);
output = output+number;
}
return output;
}
//O(N) time complexity, O(N) space complexity where N is the size of the input sequence.
public int[] createSeq(String seq)throws NullPointerException
{
if(seq==null)
{
throw new NullPointerException();
}
if(seq.length()==0||seq.trim().equals(""))
{
System.out.println("Input should not be empty or consist of blank space");
return null;
}
int[] arr=seq.length+1;
for(int i=arr.length;i>=1;i--)
{
arr[arr.length-i]=i;
}
int j=arr.length-1;
for(int i=seq.length-1;i>=0;i--)
{
if(seq.charAt(i)=='I')
{
swap(j,j-1,arr);
}
j--;
}
}
private void swap(int i, int j, int[] a)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
private void deduce(String sequence) {
int[] solution = new int[sequence.length() + 1];
int iSeen = 0;
int dNext = 1;
for (int i = sequence.length() - 1; i >= 0; i--) {
char ch = sequence.charAt(i);
if (ch == 'D') {
solution[i+1] = dNext;
dNext += iSeen + 1;
}
iSeen = (ch == 'I') ? iSeen + 1 : 0;
}
solution[0] = dNext;
for (int i = 1; i < solution.length; i++) {
if (solution[i] == 0) {
solution[i] = solution[i-1] + 1;
}
}
Arrays.stream(solution).forEach(System.out::print);
System.out.println();
}
Based on the first publish I did a refactor
public string PrintNumber(string s)
{
int numDec = 0;
foreach (var c in s)
if (c == 'D')
numDec++;
var sb = new StringBuilder();
numDec = numDec + 1;
sb.Append(numDec);
int numInc = numDec + 1;
numDec--;
foreach (var c in s)
{
if (c == 'I')
{
sb.Append(numInc);
numInc++;
}
else
{
sb.Append(numDec);
numDec--;
}
}
return sb.ToString();
}
ex - "DDIIDIDI"
step 1 - if it starts with "D" add a "I" to the beginning else "D" -- the new string becomes "IDDIIDIDI"
step 2 - list all the I that come after a D [3, 6, 8]. Now we will process in batches of 0-2, 3-5, 6-7, 8-8
step 3 - set x = 1, place x++ for all the D in right to left and x++ for all the I in left to right order for each batch y-z.
position 0-2(IDD) = 321
position 3-5(IID) = 564
position 6-7(ID) = 87
position 8-8(I) = 9
Finally we go 321564879
for input ------ DDIIDIDI
I guess based on above rule IDDI should be 34215
#include <stdio.h>
int fun(char *str, int dnum, int inum, int num, int *out, int mul){
if (*str == 0) return *out = *out + num;
*out = *out + num*mul;
if (*str == 'I'){
fun(str + 1, dnum, inum + 1, inum + 1, out, mul/10);
}
else if (*str == 'D'){
fun(str + 1, dnum - 1, inum, dnum - 1, out, mul/10);
}
return *out;
}
int main(){
char *str = "IDDI";
int dcount = 1;
int mul = 1;
int out = 0;
char *temp = str;
while (*temp++){
if (*temp == 'D') dcount++;
mul *= 10;
}
printf("%d", fun(str, dcount, dcount, dcount, &out, mul));
return 0;
}
public class CreateSequence {
public static String getSequence(final String input){
if(input==null||input.length()==0){
return null;
}
int length=input.length();
int[] squence=new int[length+1];
for(int i=0;i<length+1; i++){
squence[i]=i;
}
int dcount=0;
for(char ch: input.toCharArray()){
if(ch=='D'){
dcount++;
}
}
int firstnum=dcount+1;
StringBuffer sb=new StringBuffer();
sb.append(firstnum);
squence[firstnum-1]=-1;
int current=firstnum;
for(char ch: input.toCharArray()){
if(ch=='D'){
while(squence[(current-1)]==-1){
current--;
}
sb.append(current);
squence[(current-1)]=-1;
}
if(ch=='I'){
while(squence[(current-1)]==-1){current++;}
sb.append(current);
squence[(current-1)]=-1;
}
}
return sb.toString();
}
public static void main(String[] args) {
String input="IDDI";
System.out.println(getSequence(input));
}
}
public class CreateSequence {
public static String getSequence(final String input){
if(input==null||input.length()==0){
return null;
}
int length=input.length();
int[] squence=new int[length+1];
for(int i=0;i<length+1; i++){
squence[i]=i;
}
int dcount=0;
for(char ch: input.toCharArray()){
if(ch=='D'){
dcount++;
}
}
int firstnum=dcount+1;
StringBuffer sb=new StringBuffer();
sb.append(firstnum);
squence[firstnum-1]=-1;
int current=firstnum;
for(char ch: input.toCharArray()){
if(ch=='D'){
while(squence[(current-1)]==-1){
current--;
}
sb.append(current);
squence[(current-1)]=-1;
}
if(ch=='I'){
while(squence[(current-1)]==-1){current++;}
sb.append(current);
squence[(current-1)]=-1;
}
}
return sb.toString();
}
public static void main(String[] args) {
String input="IDDI";
System.out.println(getSequence(input));
}
}
public static String getSequence(final String input){
if(input==null||input.length()==0){
return null;
}
int length=input.length();
int[] squence=new int[length+1];
for(int i=0;i<length+1; i++){
squence[i]=i;
}
int dcount=0;
for(char ch: input.toCharArray()){
if(ch=='D'){
dcount++;
}
}
int firstnum=dcount+1;
StringBuffer sb=new StringBuffer();
sb.append(firstnum);
squence[firstnum-1]=-1;
int current=firstnum;
for(char ch: input.toCharArray()){
if(ch=='D'){
while(squence[(current-1)]==-1){
current--;
}
sb.append(current);
squence[(current-1)]=-1;
}
if(ch=='I'){
while(squence[(current-1)]==-1){current++;}
sb.append(current);
squence[(current-1)]=-1;
}
}
return sb.toString();
}
public static void main(String[] args) {
String input="IDDI";
System.out.println(getSequence(input));
}
public static String getSequence(final String input){
if(input==null||input.length()==0){
return null;
}
int length=input.length();
int[] squence=new int[length+1];
for(int i=0;i<length+1; i++){
squence[i]=i;
}
int dcount=0;
for(char ch: input.toCharArray()){
if(ch=='D'){
dcount++;
}
}
int firstnum=dcount+1;
StringBuffer sb=new StringBuffer();
sb.append(firstnum);
squence[firstnum-1]=-1;
int current=firstnum;
for(char ch: input.toCharArray()){
if(ch=='D'){
while(squence[(current-1)]==-1){
current--;
}
sb.append(current);
squence[(current-1)]=-1;
}
if(ch=='I'){
while(squence[(current-1)]==-1){current++;}
sb.append(current);
squence[(current-1)]=-1;
}
}
return sb.toString();
}
public class CreateSequence {
public static String getSequence(final String input){
if(input==null||input.length()==0){
return null;
}
int length=input.length();
int[] squence=new int[length+1];
for(int i=0;i<length+1; i++){
squence[i]=i;
}
int dcount=0;
for(char ch: input.toCharArray()){
if(ch=='D'){
dcount++;
}
}
int firstnum=dcount+1;
StringBuffer sb=new StringBuffer();
sb.append(firstnum);
squence[firstnum-1]=-1;
int current=firstnum;
for(char ch: input.toCharArray()){
if(ch=='D'){
while(squence[(current-1)]==-1){
current--;
}
sb.append(current);
squence[(current-1)]=-1;
}
if(ch=='I'){
while(squence[(current-1)]==-1){current++;}
sb.append(current);
squence[(current-1)]=-1;
}
}
return sb.toString();
}
{
int[] myInt = new int[MyString.Length + 1];
for (int i = 0; i < myInt.Count(); i++)
myInt[i] = i + 1;
int left = 0;
int right = MyString.Length;
char[] myChar = MyString.ToCharArray();
for (int i = 0; i < myChar.Count(); i++)
{
if (myChar[i] == 'I')
{
right--;
}
else
{
left++;
}
}
string tempString = "";
tempString = myInt[left].ToString();
for (int i = 0; i < myChar.Count(); i++)
{
if (myChar[i] == 'I')
{
left += 1;
tempString = tempString + myInt[left];
}
else
{
right -= 1;
tempString = tempString + myInt[right];
}
}
Console.Write(tempString);
}
{
int[] myInt = new int[MyString.Length + 1];
for (int i = 0; i < myInt.Count(); i++)
myInt[i] = i + 1;
int left = 0;
int right = MyString.Length;
char[] myChar = MyString.ToCharArray();
for (int i = 0; i < myChar.Count(); i++)
{
if (myChar[i] == 'I')
{
right--;
}
else
{
left++;
}
}
string tempString = "";
tempString = myInt[left].ToString();
for (int i = 0; i < myChar.Count(); i++)
{
if (myChar[i] == 'I')
{
left += 1;
tempString = tempString + myInt[left];
}
else
{
right -= 1;
tempString = tempString + myInt[right];
}
}
Console.Write(tempString);
}
This one is easy. Idea is to find the very first number, i.e, at the index of decrement count from left to right, or increment count from right to left.
Create another array to hold numbers in increasing order, set visited index by setting -1.
Once initial index is set, now its just traversing through string and incrementing or decrementing to next available index in store.
- dreamchaser1984 February 20, 2016