Amazon Interview Question for Software Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
3
of 5 vote

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.

void PrintNumbers(string str) {
    if (str.length() == 0) {
        return;
    }
    int dCount = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == 'D') {
            dCount++;
        }
    }
    vector<int> nums;
    for (int i = 0; i <= str.length(); i++) {
        nums.push_back(i+1);
    }
    
    cout << endl << nums[dCount] << " ";
    nums[dCount] = -1;
    int iCount = dCount+1;
    dCount--;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == 'I') {
            cout << nums[iCount] << " ";
            nums[iCount++] = -1;
        }
        else {
            cout << nums[dCount] << " ";
            nums[dCount--] = -1;
        }
    }
    cout << endl;
}

- dreamchaser1984 February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

count no. of D's
start that number as D+1

- vikram nanavare February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Asif Garhi February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- varun February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- varun February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

- divm01986 February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- vh.vahan February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
  }

- dd February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- hnatsu February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hrushikesh.iitb February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- praveen pandit March 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

}

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

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));
}

}

- IDDI should be 34215 May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

- IDDI should be 34215 May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();


}

- IDDI should be 34215 May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- IDDI should be 34215 May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the number should be least according to 3rd condition
so the answer for "IDDI" must be = 24315

- Nishant August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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);
}

- Anonymous September 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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);
}

- Jerry September 16, 2016 | 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