unknown Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
const open = "[";
const closed = "]";
function findContentsBetweenBrackets(str){
let substring = "";
let openCount = 1;
let closedCount = 0;
for(let i=1; i<str.length; i++){
current = str[i];
if(current == open){
openCount++;
}
else if(current == closed){
closedCount++;
}
if(openCount == closedCount){
break;
}
else {
substring += current;
}
}
return substring;
}
function expanded(str){
let retVal = "";
let i=0;
while(i<str.length){
current = str[i];
if(Number.isInteger(parseInt(current))){
let number = parseInt(current);
i++;
let contentsBetweenBrackets = findContentsBetweenBrackets(str.substring(i));
i += contentsBetweenBrackets.length + 1;//for the closing backet
for(let x=0; x<number; x++){
retVal += expanded(contentsBetweenBrackets);
}
}
else {
retVal += current;
}
i++;
}
return retVal;
}
const open = "[";
const closed = "]";
function findContentsBetweenBrackets(str){
let substring = "";
let openCount = 1;
let closedCount = 0;
for(let i=1; i<str.length; i++){
current = str[i];
if(current == open){
openCount++;
}
else if(current == closed){
closedCount++;
}
if(openCount == closedCount){
break;
}
else {
substring += current;
}
}
return substring;
}
function expanded(str){
let retVal = "";
let i=0;
while(i<str.length){
current = str[i];
if(Number.isInteger(parseInt(current))){
let number = parseInt(current);
i++;
let contentsBetweenBrackets = findContentsBetweenBrackets(str.substring(i));
i += contentsBetweenBrackets.length + 1;//for the closing backet
for(let x=0; x<number; x++){
retVal += expanded(contentsBetweenBrackets);
}
}
else {
retVal += current;
}
i++;
}
return retVal;
}
Suppose all digit mean the times of following string in bracket. "abc2a" is invalid.
string inner_expand(string str, int& site){
string ret = "";
while (site < str.size()){
if (str[site] >= '0' && str[site] <='9'){
int times = 0;
while (str[site] != '['){
times = times * 10 + str[site++] - '0';
}
++site;
string sub_ret = inner_expand(str, site);
for(int i = 0; i < times; ++i){
ret += sub_ret;
}
}
else if (str[site] == ']'){
++site;
return ret;
}
else{
ret += str[site++];
}
}
return ret;
}
string expand(string str){
int site = 0;
return inner_expand(str, site);
}
C++
#include <string>
#include <locale>
#include <iostream>
std::locale loc("C");
std::string::const_iterator expanded(const std::string &str, std::string::const_iterator start, std::string &out) {
while (start != str.end()) {
if (std::isalpha(*start, loc))
out.push_back(*start++);
else if (std::isdigit(*start)) {
char *end = nullptr;
auto cnt = std::strtol(&*start, &end, 10);
if (cnt == 0 || *end != '[')
return str.end();
start += end - &*start + 1;
std::string::const_iterator ret;
for (; cnt > 0; --cnt)
ret = expanded(str, start, out);
start = ret;
}
else if (*start == ']')
return start + 1;
}
return start;
}
std::string expanded(const std::string &str)
{
std::string res;
expanded(str, str.begin(), res);
return res;
}
int main() {
auto r = expanded("a2[bc2[c]]d");
auto expected = "abcccbcccd";
std::cout << "\"" << r << "\" == \"" << expected << "\" is " << std::boolalpha << (r == expected) << std::endl;
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
System.out.println(expandedString("sa2[bc2[c]]d2[f]"));
}
public static String expandedString(String s){
StringBuffer sb = new StringBuffer();
String temp = "";
int no = 0;
String real = "";
Stack<String> stack = new Stack<String>();
for(int i = 0; i < s.length(); i++){
temp = "";
real = "";
if(s.charAt(i) == ']'){
int j = i;
for(;j >= 0;j--){
String c = stack.pop();
if(c.equals("[")){
break;
}else{
temp = c + temp;
}
}
no = Integer.valueOf(stack.pop());
for(int k = 1; k <= no;k++){
real = real + temp;
}
stack.push(real);
}else{
stack.push(String.valueOf(s.charAt(i)));
}
}
Iterator<String> itr = stack.iterator();
real = "";
while(itr.hasNext()){
real = real + itr.next();
}
return real;
}
}
public static String expand(String s){
System.out.println(" Expanding String --> "+s);
Map<Integer,Integer> bracesPairIdxs = new HashMap<Integer,Integer>();
Stack<Integer> lastOpenBraceIndx = new Stack<Integer>();
int indx = 0;
for(char ch : s.toCharArray()){
if(ch == '['){
lastOpenBraceIndx.push(indx);
}else if(ch == ']'){
bracesPairIdxs.put(lastOpenBraceIndx.pop(),indx);
}
indx++;
}
System.out.println("bracesPairIdxs --> "+bracesPairIdxs);
return expandInternal(s,0,s.length()-1,bracesPairIdxs);
}
public static String expandInternal(String s,int start,int end, Map<Integer,Integer> bracesPairIdxs){
StringBuffer output = new StringBuffer();
int numRepeatToken = 0;
int indx = start;
while(indx <= end){
char ch = s.charAt(indx);
if(isNumber(ch)){
numRepeatToken = numRepeatToken*10 + ch - '0';
}else{
if(ch == '['){
String expandedToken = expandInternal(s,indx+1,bracesPairIdxs.get(indx)-1,bracesPairIdxs);
int count = 0;
while (count < numRepeatToken ){
output.append(expandedToken);
count++;
}
indx = bracesPairIdxs.get(indx)+1;
numRepeatToken = 0;
continue;
}else if(ch == ']'){
// we should not hit this condition
}else{
output.append(ch);
}
}
indx++;
}
return output.toString();
}
import java.util.*;
public class Solution {
public static String expanded(String str) {
return expanded(new StringBuilder(str), 0).toString();
}
public static StringBuilder expanded(StringBuilder str, int start) {
StringBuilder retVal = new StringBuilder();
int i = 0;
int repeted = 0;
while (i < str.length()) {
if (Character.isDigit(str.charAt(i))) {
repeted = str.charAt(i) - '0';
i++;
StringBuilder interStr = getInterString(str, i+1);
i += interStr.length();
for (int j = 0; j < repeted; j++ ) {
retVal.append(expanded(interStr, i));
}
} else {
if (str.charAt(i) != ']') retVal.append(str.charAt(i));
}
i++;
}
return retVal;
}
private static StringBuilder getInterString(StringBuilder str, int i) {
StringBuilder subStr = new StringBuilder();
int lBricket = 1, rBricket = 0;
for (; i < str.length(); i++) {
if (str.charAt(i) == '[') lBricket++;
else if (str.charAt(i) == ']') rBricket++;
if (lBricket == rBricket) break;
else subStr.append(str.charAt(i));
}
return subStr;
}
public static void main(String[] args) {
System.out.println(Solution.expanded("a2[bc2[c]]d"));
}
}
static HashMap<Integer, Integer> bracketPair = new HashMap<>();
String decodeString(String str) {
if (str == null || str.length() <= 2) return str;
Stack<Integer> stack = new Stack<>();
int length = str.length();
for (int i = 0; i < length; i++) {
char ch = str.charAt(i);
if (ch == '[') {
stack.push(i);
} else if (ch == ']') {
int start = stack.pop();
bracketPair.put(start, i);
}
}
return helper(str, 0, length-1);
}
private String helper(String str, int sI, int eI) {
StringBuilder ret = new StringBuilder();
for (int i = sI; i <= eI; ) {
char ch = str.charAt(i);
if (ch >= '0' && ch <= '9') {
int num = 0;
while (ch != '[') {
int x = ch - '0';
num *= 10;
num += x;
i++;
ch = str.charAt(i);
}
int last = bracketPair.get(i);
String temp = helper(str, i+1, last-1);
int rep = num;
for (int j = 0; j < rep; j++) {
ret.append(temp);
}
i = last+1;
} else {
ret.append(ch);
i++;
}
}
return ret.toString();
}
def expand(str):
from collections import deque
char_read_list = deque()
char_multiply_list = deque()
for char in str:
if char == ']':
current_char = char_read_list.pop()
while current_char.isdigit() == False:
if current_char != '[':
char_multiply_list.appendleft(current_char)
current_char = char_read_list.pop()
if current_char.isdigit() == True:
num_to_repeat = int(current_char)
l = list(char_multiply_list)
l[:] = l * num_to_repeat
for item in l:
char_read_list.append(item)
char_multiply_list.clear()
else:
char_read_list.append(char)
str_to_return = "".join(list(char_read_list))
return str_to_return
- TimothyRHuertas January 08, 2018const open = "["; const closed = "]"; function findContentsBetweenBrackets(str){ let substring = ""; let openCount = 1; let closedCount = 0; for(let i=1; i<str.length; i++){ current = str[i]; if(current == open){ openCount++; } else if(current == closed){ closedCount++; } if(openCount == closedCount){ break; } else { substring += current; } } return substring; } function expanded(str){ let retVal = ""; let i=0; while(i<str.length){ current = str[i]; if(Number.isInteger(parseInt(current))){ let number = parseInt(current); i++; let contentsBetweenBrackets = findContentsBetweenBrackets(str.substring(i)); i += contentsBetweenBrackets.length + 1;//for the closing backet for(let x=0; x<number; x++){ retVal += expanded(contentsBetweenBrackets); } } else { retVal += current; } i++; } return retVal; }