Amazon Interview Question SDE-3s
Country: United States
Interview Type: In-Person
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
}
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"));
}
}
{
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"));
}
}
}
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"));
}
}
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"));
}
}
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++) {
list.add("" + 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;
}
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;
}
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;
}
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;
}
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;
ret.Add(q.Dequeue());
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')
{
ret.Add(nextDigit);
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;
}
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);
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);
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'
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
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();
std::advance(i, d);
result += to_string(*i);
digits.erase(i);
isD = !isD;
}
}
cout << result << endl;
}}
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());
}
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());
}
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());
}
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());
}
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'))
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.
- ramibotros March 18, 2017class 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"))