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

- ramibotros March 18, 2017 | Flag Reply
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
}

- dmitry.labutin March 10, 2017 | Flag Reply
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"));
}
}

- Anonymous March 10, 2017 | Flag Reply
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"));
	}
}

}

- Anonymous March 10, 2017 | Flag Reply
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"));
	}

}

- Mr. Y March 10, 2017 | Flag Reply
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"));
	}
}

- Y March 10, 2017 | Flag Reply
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++) {
			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;
	}

- Y March 11, 2017 | Flag Reply
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;
}

- elkon March 13, 2017 | Flag Reply
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;
}

- elkon March 14, 2017 | Flag Reply
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;

}

- maksymas March 14, 2017 | Flag Reply
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;
            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;
        }

- Anonymous March 15, 2017 | Flag Reply
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);

- Greedy March 17, 2017 | Flag Reply
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);

- Greedy March 17, 2017 | Flag Reply
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'

- complexity N March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ramibotros March 18, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ramibotros March 18, 2017 | Flag
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

- Sergey April 02, 2017 | Flag Reply
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();
			std::advance(i, d);
			result += to_string(*i);
			digits.erase(i);
			isD = !isD;
		}
	}

	cout << result << endl;

}}

- trevorvanloon April 09, 2017 | Flag Reply
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());
}

- Niket Arora June 11, 2017 | Flag Reply
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());
    }

- Niket Arora June 11, 2017 | Flag Reply
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());
    }

- Niket Arora June 11, 2017 | Flag Reply
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());
    }

- Niket Arora June 11, 2017 | Flag Reply
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

- haider ali March 10, 2017 | 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