## 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?

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

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

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

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

Write in c

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

rewrote in c check that answer

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

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

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

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:]
'''

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:]

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)

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.

### 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.