Amazon Interview Question for SDE1s


Country: United States




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

so $$ will be the permutations of prefix?

- spiroso February 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only use digit which in input string and replace with charecter if input is 10$ then output is 100,101 all possible cobination by kiping digit as it is only replace charecter

- Anonymous February 25, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this how I'd solve the problem

class Scratch {
    
    private static ArrayList<Character> num;
    
    public static void main(String[] args) {
        System.out.print("Enter he number string : ");
        String input = (new Scanner(System.in)).next();
        num = new ArrayList<>();
        
        for (char c : input.toCharArray())
            if (c >= '0' && c <= '9') num.add(c);
        
        combinations(input, "", 0);
    }
    
    private static void combinations(String input, String pre, int i) {
        if (i < input.length()) {
            char c = input.charAt(i);
            
            if (c >= '0' && c <= '9')
                combinations(input, pre + c, i + 1);
            
            if (c == '$')
                for (char t : num)
                    combinations(input, pre + t, i + 1);
        }
        else System.out.println(pre);
    }
}

- PeyarTheriyaa February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Write in c

- Rising star February 26, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rewrote in c check that answer

- PeyarTheriyaa March 01, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In kotlin

fun printCombinations(s: String) {
    val chars = s.filter { c -> c.isDigit() }.toCharArray()
    val result = HashSet<String>()
    printCombinations(s, 0, 0, chars, result)
    result.forEach { t -> println(t)}
}

private fun printCombinations(s: String, index: Int, sequence: Int,
                              chars: CharArray, result: HashSet<String>) {
    if (index > s.length - 1) {
        result.add(s)
        return
    }

    if (sequence > chars.size - 1) {
        return
    }

    if (s[index].isDigit()) {
        return printCombinations(s, index + 1, sequence, chars, result)
    }

    val s1 = s.substring(0, index) + chars[sequence] +
            s.subSequence(index + 1, s.length)

    printCombinations(s1, index + 1, sequence + 1, chars, result)
    printCombinations(s1, index + 1, sequence, chars, result)
    printCombinations(s1, index + 1, 0, chars, result)
    printCombinations(s, index, sequence + 1, chars, result)
}

- slowBurner February 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In c

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

char set[10];
int end;

void combinations(char *num, char *pre, int curr, int lvl)
{
    if (curr < strlen(num))
    {
        if (num[curr] >= '0' && num[curr] <= '9')
        {
            pre[lvl] = num[curr];
            combinations(num, pre, curr + 1, lvl + 1);
        }
        else if (num[curr] == '$')
            for (int i = 0; i < end; i++)
            {
                pre[lvl] = set[i];
                combinations(num, pre, curr + 1, lvl + 1);
            }
        else
            combinations(num, pre, curr + 1, lvl);
    }
    else
    {
        pre[lvl] = '\0';
        printf("%s\n", pre);
    }
}

int main(int argc, char const *argv[])
{
    char num[20], pre[20];
    printf("Enter Number String : ");
    scanf("%s", num);

    end = 0;
    for (int i = 0; i < strlen(num); i++)
        if (num[i] >= '0' && num[i] <= '9')
        {
            bool flag = true;

            for (int j = 0; j < end; j++)
                if (set[j] == num[i])
                    flag = false;

            if (flag == true)
                set[end++] = num[i];
        }

    combinations(num, pre, 0, 0);

    return 0;
}

- PeyarTheriyaa March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in scala:

def wildcardCombination(s: String) = {
    val set = s.toArray.filter(_ != '$').toSeq
    val str = set.mkString
    val lenPattern = s.length - str.length
    set.flatMap(_ => set).combinations(lenPattern).flatMap(_.permutations).toSeq.map(c => str ++ c)
  }

- guilhebl March 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implemented as recursive DFS. Each node checks if the current 'k-th' char is '$'. If yes, the char at the 'k-th' position is replaced from digits form the digit_set and the message string with 'k+1' pointer is passed to the next node.

'''
def replace_dollar(msg):
results = []
digit_set = set(list(msg.replace('$','')))
_replace_dollar(msg, 0,results, digit_set)
return results


def _replace_dollar(msg, k, results, digit_set):
if k == len(msg):
results.append(msg)
elif msg[k] != '$':
_replace_dollar(msg, k+1, results, digit_set)
else:
for digit in digit_set:
_replace_dollar(replace_at_k(msg, k, digit), k+1, results, digit_set)

def replace_at_k(msg, k, digit):
return msg[:k] + digit + msg[k+1:]
'''

- Anonymous March 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implemented as DFS via recurrent function. Each we passe a message 'msg' and a pointer 'k'. If msg[k] is the dollar sign, this char is replaced by a digit from the 'digit_set' and the recuurent function is called with the modified message and increased pointer k+1.

The complexity of the soution is O(2^k) in time and O(n^k) in memory where k is # of dollars and n is # of digits.

def replace_dollar(msg):
    results = []
    digit_set = set(list(msg.replace('$','')))
    _replace_dollar(msg, 0,results, digit_set)
    return results


def _replace_dollar(msg, k, results, digit_set):
    if k == len(msg):
        results.append(msg)
    elif msg[k] != '$':
        _replace_dollar(msg, k+1, results, digit_set)
    else:
        for digit in digit_set:
            _replace_dollar(replace_at_k(msg, k, digit), k+1, results, digit_set)

def replace_at_k(msg, k, digit):
    return msg[:k] + digit + msg[k+1:]

- autoboli March 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
IMPLEMENTATION IN PYTHON.
CODE INSPIRED BY PeyarTheriyaa

Example 1: 
Input <- 10$
Output -> 100 and 101

Example 2: 
Input <- 1$2$
Output -> 1121, 1122, 1221, 1222

Stack Explanation for example of input 1:

Stack 0:
        numberList = ['1','0']
        c = '1'
        pre = '1'
        i = 0
        Stack 1: 
                i = 1
                c = '$'
                pre = '10'
                Stack 2: 
                        i = 2
                        c = '$'
                        pre = '101'
                        Stack 3: 
                            i = 3
                            break
                 print -> 101
                 Stack 4: 
                         i = 2
                         c = '$'
                         pre = '100'
                         Stack 5: 
                             i = 4
                              break
                 print -> 100
                        


The $ should be replaced by the each preceding digit and displayed as output. 
"""

def combinations(input,pre,i):
    if (i < len(input)):
        
        _char = input[i]
        
        if _char >= '0' and _char <= '9':
            combinations(input,pre + _char,i+1)
        
        if _char == '$':
            for j in numList:
                combinations(input,pre+j,i+1)
    else:
        print(pre)
    

input = '10$'
numList = []

# Get the numbers saved to a list 
for i in input:
    if (i >= '0' and i <= '9'):
        numList.append(i)

combinations(input,'',0)

- armaghanwa March 29, 2019 | 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