## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: In-Person

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

Solved it with a binary search tree.
O(n) runtime: Creation of tree takes O(n) time and then inorder traversal takes O(n) time.
O(n) extra space complexity.

``````class Node: #BST
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def iter_in_order(self):
if self.left:
yield from self.left.iter_in_order()
yield self.value
if self.right:
yield from self.right.iter_in_order()

def decode(arg_script):
root = Node(1)

fresh_idx = 2
I_node = root
D_node = root

for char in arg_script:
if fresh_idx > 9:
return -1 #invalid input, would force me to use digits > 9

new_node = Node(fresh_idx)
if char == "I":
I_node.right = new_node
I_node = new_node
D_node = new_node
elif char == "D":
D_node.left = new_node
D_node = new_node

fresh_idx += 1

return "".join([str(idx) for idx in root.iter_in_order()])

print(decode("DDIDDIID"))``````

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

``````package main

import (
"fmt"
"strings"
)

type PatternPart struct {
l     string
count int
}

func FindMinNum(pattern string) string {
letters := strings.Split(pattern, "")
P := []PatternPart{{letters[0], 1}}
i := 0
for j := 1; j < len(letters); j++ {
if letters[j] == P[i].l {
P[i].count++
} else {
P = append(P, PatternPart{letters[j], 1})
i++
}
}
digits := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
res := ""
for pos, p := range P {
if p.l == "D" {
if pos == 0 {
res += digits[p.count]
digits = append(digits[:p.count], digits[p.count+1:]...)
}
for j := p.count - 1; j >= 0; j-- {
res += digits[j]
}
digits = digits[p.count:]
} else {
if pos == 0 {
res = "1"
digits = digits[1:]
}
if pos == len(P)-1 {
for j := 0; j < p.count; j++ {
res += digits[j]
}
digits = digits[p.count:]
} else {
for j := 0; j < p.count-1; j++ {
res += digits[j]
}
digits = digits[p.count-1:]
res += digits[P[pos+1].count]
digits = append(digits[:P[pos+1].count], digits[P[pos+1].count+1:]...)
}
}
}
return res
}

func main() {
fmt.Println(FindMinNum("D"))        // 21
fmt.Println(FindMinNum("I"))        // 12
fmt.Println(FindMinNum("DD"))       // 321
fmt.Println(FindMinNum("II"))       // 123
fmt.Println(FindMinNum("DIDI"))     // 21435
fmt.Println(FindMinNum("IIDDD"))    // 126543
fmt.Println(FindMinNum("DDIDDIID")) // 321654798
}``````

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

package com.sample;

public class PatternMatcher {

public String getSmallestNumber(String pattern) {

char[] charArray = pattern.toCharArray();

int start = 0;
String number = null;

boolean foundI = false;
boolean foundD = false;
int beginI = -1;
int beginD = 0;
int endD = 0;
for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];

if (c == 'I') {

if (foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}

foundD = false;
foundI = false;
}

if (!foundI) {
foundI = true;
beginI = i;
}
}

if (c == 'D') {
if (!foundD) {
foundD = true;
beginD = i;
endD = i;
} else {
endD = i;
}
}
}

if (start <= charArray.length) {
System.out.println("Pending::foundD:" + foundD + "::foundI::" + foundI);

if (foundI && foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}
} else if (foundI) {
if (number == null) {
number = "";
}
for (int j = start + 1; j <= charArray.length + 1; j++) {
number += j;
}
} else if (foundD) {
if (number == null) {
number = "";
}
for (int j = charArray.length + 1; j >= start + 1; j--) {
number += j;
}
}
}
return number;
}

public static void main(String[] args) {
PatternMatcher patternMatcher = new PatternMatcher();
System.out.println(patternMatcher.getSmallestNumber("IDDIIID"));
// System.out.println(patternMatcher.getSmallestNumber("DDDI"));
// System.out.println(patternMatcher.getSmallestNumber("IIDDDI"));
// System.out.println(patternMatcher.getSmallestNumber("DDIDDIIDI"));
// System.out.println(patternMatcher.getSmallestNumber("DDDIIIDDI"));
// System.out.println(patternMatcher.getSmallestNumber("IX"));
// System.out.println(patternMatcher.getSmallestNumber("DDX"));
// System.out.println(patternMatcher.getSmallestNumber("IIX"));
// System.out.println(patternMatcher.getSmallestNumber("DIDIX"));
}
}

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

``````{
package com.sample;

public class PatternMatcher {

public String getSmallestNumber(String pattern) {

char[] charArray = pattern.toCharArray();

int start = 0;
String number = null;

boolean foundI = false;
boolean foundD = false;
int beginI = -1;
int beginD = 0;
int endD = 0;
for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];

if (c == 'I') {

if (foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}

foundD = false;
foundI = false;
}

if (!foundI) {
foundI = true;
beginI = i;
}
}

if (c == 'D') {
if (!foundD) {
foundD = true;
beginD = i;
endD = i;
} else {
endD = i;
}
}
}

if (start <= charArray.length) {
System.out.println("Pending::foundD:" + foundD + "::foundI::" + foundI);

if (foundI && foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}
} else if (foundI) {
if (number == null) {
number = "";
}
for (int j = start + 1; j <= charArray.length + 1; j++) {
number += j;
}
} else if (foundD) {
if (number == null) {
number = "";
}
for (int j = charArray.length + 1; j >= start + 1; j--) {
number += j;
}
}
}
return number;
}

public static void main(String[] args) {
PatternMatcher patternMatcher = new PatternMatcher();
System.out.println(patternMatcher.getSmallestNumber("IDDIIID"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IIDDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDIDDIIDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDIIIDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IX"));
//		System.out.println(patternMatcher.getSmallestNumber("DDX"));
//		System.out.println(patternMatcher.getSmallestNumber("IIX"));
//		System.out.println(patternMatcher.getSmallestNumber("DIDIX"));
}
}``````

}

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

``````package com.sample;

public class PatternMatcher {

public String getSmallestNumber(String pattern) {

char[] charArray = pattern.toCharArray();

int start = 0;
String number = null;

boolean foundI = false;
boolean foundD = false;
int beginI = -1;
int beginD = 0;
int endD = 0;
for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];

if (c == 'I') {

if (foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}

foundD = false;
foundI = false;
}

if (!foundI) {
foundI = true;
beginI = i;
}
}

if (c == 'D') {
if (!foundD) {
foundD = true;
beginD = i;
endD = i;
} else {
endD = i;
}
}
}

if (start <= charArray.length) {
System.out.println("Pending::foundD:" + foundD + "::foundI::" + foundI);

if (foundI && foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}
} else if (foundI) {
if (number == null) {
number = "";
}
for (int j = start + 1; j <= charArray.length + 1; j++) {
number += j;
}
} else if (foundD) {
if (number == null) {
number = "";
}
for (int j = charArray.length + 1; j >= start + 1; j--) {
number += j;
}
}
}
return number;
}

public static void main(String[] args) {
PatternMatcher patternMatcher = new PatternMatcher();
System.out.println(patternMatcher.getSmallestNumber("IDDIIID"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IIDDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDIDDIIDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDIIIDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IX"));
//		System.out.println(patternMatcher.getSmallestNumber("DDX"));
//		System.out.println(patternMatcher.getSmallestNumber("IIX"));
//		System.out.println(patternMatcher.getSmallestNumber("DIDIX"));
}``````

}

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

``````package com.sample;

public class PatternMatcher {

public String getSmallestNumber(String pattern) {

char[] charArray = pattern.toCharArray();

int start = 0;
String number = null;

boolean foundI = false;
boolean foundD = false;
int beginI = -1;
int beginD = 0;
int endD = 0;
for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];

if (c == 'I') {

if (foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}

foundD = false;
foundI = false;
}

if (!foundI) {
foundI = true;
beginI = i;
}
}

if (c == 'D') {
if (!foundD) {
foundD = true;
beginD = i;
endD = i;
} else {
endD = i;
}
}
}

if (start <= charArray.length) {
System.out.println("Pending::foundD:" + foundD + "::foundI::" + foundI);

if (foundI && foundD) {
int currentCursor = start;

if (beginI >= 0) {
if (number == null) {
number = "" + ++currentCursor;
}

for (int x = beginI; x < beginD - 1; x++) {
number += ++currentCursor;
}

currentCursor = currentCursor + (endD - beginD + 1) + 1;
number += currentCursor;
}

if (number == null) {
currentCursor = ++currentCursor + (endD - beginD) + 1;
number = "" + currentCursor;
}

start = currentCursor;

for (int x = beginD; x <= endD; x++) {
number += --currentCursor;
}
} else if (foundI) {
if (number == null) {
number = "";
}
for (int j = start + 1; j <= charArray.length + 1; j++) {
number += j;
}
} else if (foundD) {
if (number == null) {
number = "";
}
for (int j = charArray.length + 1; j >= start + 1; j--) {
number += j;
}
}
}
return number;
}

public static void main(String[] args) {
PatternMatcher patternMatcher = new PatternMatcher();
System.out.println(patternMatcher.getSmallestNumber("IDDIIID"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IIDDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDIDDIIDI"));
//		System.out.println(patternMatcher.getSmallestNumber("DDDIIIDDI"));
//		System.out.println(patternMatcher.getSmallestNumber("IX"));
//		System.out.println(patternMatcher.getSmallestNumber("DDX"));
//		System.out.println(patternMatcher.getSmallestNumber("IIX"));
//		System.out.println(patternMatcher.getSmallestNumber("DIDIX"));
}
}``````

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

``````public String getSmallestNumberV2(String pattern) {
String number = null;
pattern = getCharacterCount(pattern);
char[] charArray = pattern.toCharArray();

List<String> list = new ArrayList<String>();
for (int i = 1; i <= 9; i++) {
}

for (int i = 0; i < charArray.length; i+=2) {
char c = charArray[i];
int count = charArray[i + 1] - '0';

if (Character.toLowerCase(c) == 'd') {
if (number == null) {
number = list.remove(count);
}
for (int j = count - 1; j >= 0; j--) {
number += list.remove(j);
}
}

if (Character.toLowerCase(c) == 'i') {
if (number == null) {
number = list.remove(0);
}

if (i + 2 < charArray.length) {
for (int j = 0; j < count - 1; j++) {
number += list.remove(0);
}

char cNew = charArray[i + 2];
int countNew = charArray[i + 3] - '0';

number += list.remove(countNew);
} else {
for (int j = 0; j < count; j++) {
number += list.remove(0);
}
}
}
}
return number;
}

public String getSmallestNumberV3(String pattern) {
String number = null;
pattern = getCharacterCount(pattern);
char[] charArray = pattern.toCharArray();

int start = 1;
for (int i = 0; i < charArray.length; i+=2) {
char c = charArray[i];
int count = charArray[i + 1] - '0';

if (Character.toLowerCase(c) == 'd') {
if (number == null) {
number = "" + (count + 1);
}
for (int j = count; j > 0; j--) {
number += j;
}
start += count + 1;
}

if (Character.toLowerCase(c) == 'i') {
if (number == null) {
number = "" + start;
start++;
}

if (i + 2 < charArray.length) {
for (int j = 0; j < count - 1; j++) {
number += (start + j);
}

char cD = charArray[i + 2];
int countD = charArray[i + 3] - '0';

start += countD + count - 1;
number += (start);

for (int j = 0; j < countD; j++) {
number += start - 1 - j;
}
start++;
i+=2;
} else {
for (int j = 0; j < count; j++) {
number += (start + j);
}
start += count;
System.out.println(start);
}
}
}
return number;
}``````

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

``````int getLowest(int a[], int n)
{
for (int i=0;i<n;i++)
if (a[i]>0)
return i;
return -1;
}

int countConsecutive(string str, int start, char c)
{
int count=0;
for (unsigned int i=start;i<str.length();i++)
{
if (str[i]!=c)
break;
count++;
}
return count;

}

int transToLowestSum(string DI)
{
int resNum=0;
int avl[]={1,1,1,1,1,1,1,1,1};
for (unsigned int i=0;i<DI.length();i++)
{
int lowest = getLowest(avl,9);
if (DI[i]=='I')
{
resNum=resNum*10+lowest+1;
avl[lowest]=0;
}
else
{
int countD = countConsecutive(DI, i, 'D');
resNum=resNum*10+lowest+1+countD;
avl[lowest+countD]=0;
}
}
return resNum*10+getLowest(avl,9)+1;
}``````

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

``````int getLowest(int a[], int n)
{
for (int i=0;i<n;i++)
if (a[i]>0)
return i;
return -1;
}

int countConsecutive(string str, int start, char c)
{
int count=0;
for (unsigned int i=start;i<str.length();i++)
{
if (str[i]!='c')
break;
count++;
}
return count;

}

int transToLowestSum(string DI)
{
int resNum=0;
int avl[]={1,1,1,1,1,1,1,1,1};
for (unsigned int i=0;i<DI.length();i++)
{
int lowest = getLowest(avl,9);
if (DI[i]=='i')
{
resNum=resNum*10+lowest+1;
avl[lowest]=0;
}
else
{
int countD = countConsecutive(DI, i, 'D');
resNum=resNum*10+lowest+1+countD;
avl[lowest+countD]=0;
}
}
return resNum*10+getLowest(avl,9)+1;
}``````

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

Brute forde

``````private string reverseAString(string str, int startIndex, int length)
{
var repStr = string.Empty;
var subStr = str.Substring(startIndex, length);
foreach (var c in subStr)
repStr = c + repStr;

return str.Replace(subStr, repStr);
}

public string FindtheMinNumber(string pattern)
{
var output = string.Empty;
var startIndex = 0;
var length = 0;
var previous = '@';
for (var i = 0; i < pattern.Length + 1; i++)
{
output = output + (i + 1);
}
for (var c = 0; c < pattern.Length; c++)
{
if (previous == pattern[c])
{
if (pattern[c] == 'D')
length++;
}
else
{
if (length > 1 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
else if(length > 0 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
previous = pattern[c];
length = 1;
startIndex = c;
}

}
if(length > 0 && previous == 'D')
output = reverseAString(output, startIndex, length + 1);
Console.WriteLine(output);
return output;``````

}

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

``````static int FindMinNum(string s)
{
if (s == null || s.Length == 0 || s.Length > 9)
throw new Exception("Invalid Input");

List<int> ret = new List<int>();
Queue<int> q = new Queue<int>();
for (int i = 1; i <= 9; i++)
q.Enqueue(i);

int idx = 0;

for (int i = 0; i < s.Length && q.Count > 0; i++)
{

int nextDigit = q.Dequeue();
if (s[i] == 'D')
{
ret.Insert(idx, nextDigit);
}
else if (s[i] == 'I')
{
idx = ret.Count - 1;
}
else
{
throw new Exception("Invalid Character");
}
}

int fNumber = 0;
for (int i = 0; i < ret.Count; i++)
{
fNumber += ret[ret.Count - i - 1] * (int)Math.Pow(10, i);
}
return fNumber;
}``````

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

if (input == null || input.length() == 0)
return null;
int pre = 1;
int[] result = new int[input.length() + 1];
char[] in = input.toCharArray();
int min = pre;
int max = pre;
result[0] = 1;
for (int i = 0; i < in.length; i++) {
char flag = in[i];
if (flag == 'I') {
while (++pre <= max) {
continue;
}
max = pre;
result[i + 1] = pre;
} else if (flag == 'D') {
int j = i - 1;
while (j >= 0) {
if (in[j] == 'I')
break;
else
j--;
}
for (int k = j; k < i; k++) {
result[k + 1] += 1;
max = max > result[k + 1] ? max : result[k + 1];
}
result[i + 1] = result[i] - 1;
} else {
return null;
}
}

return Arrays.toString(result);

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

``````if (input == null || input.length() == 0)
return null;
int pre = 1;
int[] result = new int[input.length() + 1];
char[] in = input.toCharArray();
int min = pre;
int max = pre;
result[0] = 1;
for (int i = 0; i < in.length; i++) {
char flag = in[i];
if (flag == 'I') {
while (++pre <= max) {
continue;
}
max = pre;
result[i + 1] = pre;
} else if (flag == 'D') {
int j = i - 1;
while (j >= 0) {
if (in[j] == 'I')
break;
else
j--;
}
for (int k = j; k < i; k++) {
result[k + 1] += 1;
max = max > result[k + 1] ? max : result[k + 1];
}
result[i + 1] = result[i] - 1;
} else {
return null;
}
}

return Arrays.toString(result);``````

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

def decypher(s):
lower = 1
upper = len(s)
res = ''
for el in s:
if el == 'I':
res += str(lower)
lower += 1
elif el == 'D':
res += str(upper)
upper -= 1
return res

assert decypher('IDIIIDD') == '1723465'

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

Not optimal.
IDIIIDD can be "deciphered" to be 13245876 , which is smaller than 1723465

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

Not optimal.
IDIIIDD can be "deciphered" to be 13245876 , which is smaller than 1723465

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

Scala solution:

``````class Node(p: Int) {
var pos: Int = p
var left: Option[Node] = None
var right: Option[Node] = None
}

def tree(codes: String): Node = {
var position = 1
val root = new Node(position)
var left = root
var right = root
for (c <- codes) {
position += 1
val newNode = new Node(position)
if (c == 'D') {
left.left = Some(newNode)
left = newNode
} else if (c == 'I') {
right.right = Some(newNode)
right = newNode
left = newNode
}
}

root
}

def walk(node: Node): Seq[Int] = {
var seq = Seq(node.pos)
if (node.left.nonEmpty)
seq = walk(node.left.get) ++ seq
if (node.right.nonEmpty)
seq ++= walk(node.right.get)
seq
}

def build(codes: String): String = walk(tree(codes)).mkString``````

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

``````int main() {

string s;
cin >> s;

list<int> digits = { 1,2,3,4,5,6,7,8,9 };

int index = 0;

list<int> frequencies;
int count = 1;
int lastChar = s[0];
char firstChar = s[0];
for (int i = 1; i < s.length(); i++) {
if (s[i] != lastChar) {
//add segment to list:
frequencies.push_back(count);
count = 1;
lastChar = s[i];
}
else {
count++;
}
}
frequencies.push_back(count);

bool isD = firstChar == 'D';
string result = "";
bool isFirst = true;
while (!frequencies.empty()) {
if (isD) {
auto f = frequencies.front();
string digits_string = "";
for (int i = 0; i < f; i++) {
digits_string += to_string(digits.front());
digits.pop_front();
}
if (isFirst) {
digits_string += to_string(digits.front());
digits.pop_front();
isFirst = false;
}
std::reverse(digits_string.begin(), digits_string.end());
result += digits_string;
frequencies.pop_front();
isD = !isD;
}
else {
auto inc = frequencies.front();
frequencies.pop_front();
for (int i = 0; i < inc - 1; i++) {
result += to_string(digits.front());
digits.pop_front();
}
if (isFirst) {
result += to_string(digits.front());
digits.pop_front();
isFirst = false;
}
auto d = frequencies.front();
std::list<int>::iterator i = digits.begin();
result += to_string(*i);
digits.erase(i);
isD = !isD;
}
}

cout << result << endl;``````

}}

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

public static int smallestNum(String code) {
StringBuilder num = new StringBuilder();
int maxNum = 0;
for (int index = 0; index < code.length(); index++) {
char ch = code.charAt(index);
switch (ch) {
case 'I':
int nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
if (index == 0) {
num.append(String.valueOf(nextD + 1)).append(String.valueOf(nextD + 2));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
} else {
num.append(String.valueOf(nextD + maxNum + 1));
maxNum = nextD + maxNum + 1;
for (int j = 0; j < nextD; j++) {
num.append(maxNum - 1 - j);
index++;
}
}
break;
case 'D':
nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
num.append(String.valueOf(nextD + 2)).append(String.valueOf(nextD + 1));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
break;
default:
}
}
return Integer.parseInt(num.toString());
}

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

``````public static int smallestNum(String code) {
StringBuilder num = new StringBuilder();
int maxNum = 0;
for (int index = 0; index < code.length(); index++) {
char ch = code.charAt(index);
switch (ch) {
case 'I':
int nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
if (index == 0) {
num.append(String.valueOf(nextD + 1)).append(String.valueOf(nextD + 2));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
} else {
num.append(String.valueOf(nextD + maxNum + 1));
maxNum = nextD + maxNum + 1;
for (int j = 0; j < nextD; j++) {
num.append(maxNum - 1 - j);
index++;
}
}
break;
case 'D':
nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
num.append(String.valueOf(nextD + 2)).append(String.valueOf(nextD + 1));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
break;
default:
}
}
return Integer.parseInt(num.toString());
}``````

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

``````public static int smallestNum(String code) {
StringBuilder num = new StringBuilder();
int maxNum = 0;
for (int index = 0; index < code.length(); index++) {
char ch = code.charAt(index);
switch (ch) {
case 'I':
int nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
if (index == 0) {
num.append(String.valueOf(nextD + 1)).append(String.valueOf(nextD + 2));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
} else {
num.append(String.valueOf(nextD + maxNum + 1));
maxNum = nextD + maxNum + 1;
for (int j = 0; j < nextD; j++) {
num.append(maxNum - 1 - j);
index++;
}
}
break;
case 'D':
nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
num.append(String.valueOf(nextD + 2)).append(String.valueOf(nextD + 1));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
break;
default:
}
}
return Integer.parseInt(num.toString());
}``````

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

``````public static int smallestNum(String code) {
StringBuilder num = new StringBuilder();
int maxNum = 0;
for (int index = 0; index < code.length(); index++) {
char ch = code.charAt(index);
switch (ch) {
case 'I':
int nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
if (index == 0) {
num.append(String.valueOf(nextD + 1)).append(String.valueOf(nextD + 2));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
} else {
num.append(String.valueOf(nextD + maxNum + 1));
maxNum = nextD + maxNum + 1;
for (int j = 0; j < nextD; j++) {
num.append(maxNum - 1 - j);
index++;
}
}
break;
case 'D':
nextD = 0;
for (int j = index + 1; j < code.length(); j++) {
if (code.charAt(j) == 'D') {
nextD++;
} else {
break;
}
}
num.append(String.valueOf(nextD + 2)).append(String.valueOf(nextD + 1));
maxNum = nextD + 2;
for (int j = 0; j < nextD; j++) {
num.append(nextD - j);
index++;
}
break;
default:
}
}
return Integer.parseInt(num.toString());
}``````

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

I initially thought that this was really hard, but after some analysis, the solution appeared simple. You initialize your result as either 12 or 21 depending on what the first item in the pattern is. Track and update the index of the maximum number in result as you add more items.
When you encounter an I add result[max_index] + 1 to the right and set max index to the last element in the result
When you encounter a D get the insert result[max_index] + 1 at max index, shifting everything after it to the right. I have tried using a deque so that this operation can be done in constant time.

``````from collections import deque

def get_min(pattern):
if len(pattern) > 9:
raise ValueError('Invalid Pattern')
if pattern[0] == 'D':
q = deque([2, 1])
max_index, min_index = 0, 1
elif pattern[0] == 'I':
q = deque([1, 2])
max_index, min_index = 1, 0
else:
raise ValueError('Invalid Pattern')
for i in range(1, len(pattern)):
if pattern[i] == 'I':
q.append(q[max_index]+1)
max_index = len(q) - 1
elif pattern[i] == 'D':
n = q[max_index]
q.insert(max_index, n+1)
else:
raise ValueError('Invalid Pattern')
return q

print(get_min('D'))
print(get_min('I'))
print(get_min('DD'))
print(get_min('II'))
print(get_min('DIDI'))
print(get_min('IIDDD'))
print(get_min('DDIDDIID'))``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Hi online work customer service online market maile market online please me contact 8574251000

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.