unknown Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
use a stack and vector and recursion
#include<iostream>
#include <vector>
#include <stack>
using namespace std;
bool printp(vector<std::pair<char, int>> s1, int s, int e)
{
if (s > e) return false;
cout << s1[s].first << s1[s].second << "," << s1[e].second << ",";
if (!printp(s1, s + 1, e - 1)) cout << "null";
cout << s1[e].first;
return true;
}
void Parse(string s)
{
std::stack<char> s1;
vector<std::pair<char, int>> t1;
int first = 1;
for (int i = 0; i < s.length(); i++)
{
t1.push_back(make_pair(s[i], i));
if (s[i] == '[')
s1.push('[');
else
{
s1.pop(); if (s1.empty()){ if (!first) cout << ","; first = 0; printp(t1, 0, t1.size() - 1); t1.clear(); }
}
}
}
int main()
{
Parse("[[]][]");
return 0;
}
public class TranslateBracketArrangement {
public static void main(String[] args) {
final String s1 = "[[]][]";
final String s2= "[][[]]";
System.out.println(process(s1, 0, s1.length() - 1));
System.out.println(process (s2, 0, s2.length()-1));
}
static String process(String s, int start, int end) {
System.out.printf("start =%d, end=%d %n", start, end);
List<String> result = new ArrayList<>();
// handle base case []
if (end == start + 1) return String.format("[%d,%d, null]", start, end);
// handle base case ""
if ( end <start+1) return "null";
// else we have [*] where * needs parsing
int p = start;
int left = 0, right = 0, p1 = p;
while (end >= p) {
switch (s.charAt(p)) {
case '[':
left++;
break;
case ']':
right++;
break;
}
p++;
if (left > 0 && right > 0 && (left == right)) {
String partial = String.format("[%d,%d,%s]", p1, p1 + left + right - 1, process(s, p1 + 1, p1 + left + right - 2));
result.add (partial);
left= right =0;
p1=p;
}
}
return result.toString();
}
}
In Kotlin, using a stack and StringBuilder.
fun main(args: Array<String>) {
val output = parse("[[]][]")
println( output )
}
fun parse( input: String ) : String{
val output = StringBuilder()
var currentPos = 0
val stx = ArrayDeque<Int>()
while( currentPos < input.length ){
if ( input[currentPos] == '[' ){
stx.push( currentPos )
} else {
val start = stx.pop()
if ( start == currentPos-1 ){
if ( start != 0 ) output.append(",")
output.append("[$start,$currentPos,null]")
} else {
if ( start != 0 ) output.prepend(",")
output.prepend("[$start,$currentPos")
output.append("]")
}
}
currentPos++
}
return output.toString()
}
fun StringBuilder.prepend( string: String ): StringBuilder{
this.insert(0, string )
return this
}
def parser(string):
stack = []
for item in enumerate(string):
if(item[1]=="["):
stack.append(item)
else:
sub = [0,item[0],None]
close = False
while(not close):
last = stack.pop()
if type(last) is list:
sub[2] = last
else:
sub[0] = last[0]
stack.append(sub)
close = True
return stack
print parser("[[[[]][]]][]")
def parser(string):
stack = []
for item in enumerate(string):
if(item[1]=="["):
stack.append(item)
else:
sub = [0,item[0],None]
close = False
while(not close):
last = stack.pop()
if type(last) is list:
sub[2] = last
else:
sub[0] = last[0]
stack.append(sub)
close = True
return stack
print parser("[[[[]][]]][]")
- Alex October 29, 2017