Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
def solution(S):
stack = Stack()
i = 0
while i < len(S):
if S[i] == "(":
stack.push(i)
elif S[i] == ")" and stack.isEmpty() == False:
S = S[:i] + "1" + S[i+1:]
j = stack.pop()
S = S[:j] + "0" + S[j + 1:]
elif S[i] == ")" and stack.isEmpty() == True:
S = S[:i] + "-1" + S[i+1:]
i += 1
while stack.isEmpty() == False:
j = stack.pop()
S = S[:j] + "-1" + S[j+1:]
return S
public String findUnmatched(String input) {
int openCount = 0;
StringBuilder sb= new StringBuilder();
for (char c : input.toCharArray()) {
if (c == '(') {
openCount++;
sb.append('0');
} else if (c == ')') {
openCount--;
sb.append(openCount < 0 ? '-1' : '1');
} else {
sb.append(c);
}
}
return sb.toString();
}
/** Prints which parenthesis are unmatched */
String getUnmatchedParenthesisPattern(String text) {
int count1 = 0;
StringBuilder ret = new StringBuilder();
// Iterate over the string
for (int i = 0; i < text.length(); i++) {
char letter1 = text.charAt(i);
// In case it finds an opening parenthesis
if (letter1 == '(') {
int count2 = 1;
count1++;
// Goes looking for a closing parenthesis
for (int j = i + 1; j < text.length(); j++) {
char letter2 = text.charAt(j);
if (letter2 == ')') count2--;
if (letter2 == '(') count2++;
if (count2 == 0) break;
}
// Returns 0 if its properly closed or -1 if it wasnt
ret.append(count2 == 0 ? "0" : "-1");
// In case it finds a closing parenthesis
} else if (letter1 == ')') {
count1--;
// If it closes an opening parenthesis print 1 or if there were none opened -1
ret.append(count1 >= 0 ? "1" : "-1");
// For any other characters just print it
} else {
ret.append(letter1);
}
}
// Returns
return ret.toString();
}
word='(((abc))((d)))))'
open_track=[]
close_track=[]
for i in range(0,len(word)):
if word[i] == '(':
open_track.append(i)
elif word[i] == ')':
if not open_track:
close_track.append(i)
else:
open_track.pop()
res=[]
k=0
print(word)
print(open_track)
print(close_track)
for i in range(0,len(word)):
if i in (open_track or close_track):
res.append('-1')
elif word[i] == '(':
res.append('0')
elif word[i] == ')':
res.append('1')
else:
res.append(word[i])
print("".join(res))
word='(((abc))((d)))))'
open_track=[]
close_track=[]
for i in range(0,len(word)):
if word[i] == '(':
open_track.append(i)
elif word[i] == ')':
if not open_track:
close_track.append(i)
else:
open_track.pop()
res=[]
k=0
print(word)
print(open_track)
print(close_track)
for i in range(0,len(word)):
if i in (open_track or close_track):
res.append('-1')
elif word[i] == '(':
res.append('0')
elif word[i] == ')':
res.append('1')
else:
res.append(word[i])
print("".join(res))
word='(((abc))((d)))))'
open_track=[]
close_track=[]
for i in range(0,len(word)):
if word[i] == '(':
open_track.append(i)
elif word[i] == ')':
if not open_track:
close_track.append(i)
else:
open_track.pop()
res=[]
k=0
print(word)
print(open_track)
print(close_track)
for i in range(0,len(word)):
if i in (open_track or close_track):
res.append('-1')
elif word[i] == '(':
res.append('0')
elif word[i] == ')':
res.append('1')
else:
res.append(word[i])
print("".join(res))
public static void main(String[] args) {
String str = "(((abc))((d)))))";
unmatched(str);
}
/**
* ((a) -> -10a1 (a)) -> 0a1-1 (((abc))((d))))) -> 000abc1100d111-1-1
*
*
*/
public static void unmatched(String str) {
char[] carr = str.toCharArray();
int n = carr.length;
int i = 0;
StringBuffer sb = new StringBuffer();
String d = "";
Stack<Character> stack = new Stack<>();
int c = 0;
while (i < n) {
if(i > 0 && carr[i] == '(' && carr[i-1] == ')')
c = 1;
if (carr[i] == '(') {
stack.push(carr[i]);
d += sb.toString();
sb = new StringBuffer();
c++;
} else if (carr[i] == ')') {
c--;
if (!stack.isEmpty()) {
stack.pop();
String s = sb.toString();
if(c == 0){
s = d+s;
d = "";
}
if (s.length() > 0)
sb = new StringBuffer("0" + s + "1");
} else {
sb.append("-1");
}
} else {
sb.append(carr[i]);
}
i++;
}
String p = sb.toString();
sb = new StringBuffer(d + p);
while (!stack.isEmpty()) {
char t = stack.pop();
if (t == ')')
sb.append("-1");
else {
String s = sb.toString();
sb = new StringBuffer("-1" + s);
}
}
System.out.println(sb.toString());
}
Java Solution using the algo mentioned by Anonymous above in C++. Pretty cool algo!
static void printSummary(String s) {
Stack<Integer> stack = new Stack<Integer>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else if (chars[i] == ')') {
if (stack.isEmpty()) {
chars[i] = '^';
} else {
int openingIndex = stack.pop();
chars[openingIndex] = '0';
chars[i] = '1';
}
}
}
while (!stack.isEmpty()) {
chars[stack.pop()] = '^';
}
System.out.println("Summary: " + new String(chars).replace("^", "-1"));
}
static void printSummary(String s) {
Stack<Integer> stack = new Stack<Integer>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else if (chars[i] == ')') {
if (stack.isEmpty()) {
chars[i] = '^';
} else {
int openingIndex = stack.pop();
chars[openingIndex] = '0';
chars[i] = '1';
}
}
}
while (!stack.isEmpty()) {
chars[stack.pop()] = '^';
}
System.out.println("Summary: " + new String(chars).replace("^", "-1"));
}
It is the Java version of the C++ solution above. Brilliant Algo From Anonymous indeed.
static void printSummary(String s) {
Stack<Integer> stack = new Stack<Integer>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else if (chars[i] == ')') {
if (stack.isEmpty()) {
chars[i] = '^';
} else {
int openingIndex = stack.pop();
chars[openingIndex] = '0';
chars[i] = '1';
}
}
}
while (!stack.isEmpty()) {
chars[stack.pop()] = '^';
}
System.out.println("Summary: " + new String(chars).replace("^", "-1"));
}
public String decode(final String input) {
if (input == null || input.length() == 0) {
return null;
}
int balance = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
balance++;
} else if (c == ')') {
balance--;
}
}
StringBuilder result = new StringBuilder(input.length());
int currentBracketBalance = 0;
for (char c : input.toCharArray()) {
if (c == '(') {
currentBracketBalance++;
if (balance > 0) {
result.append(-1);
balance--;
} else {
result.append(0);
}
} else if (c == ')') {
if (currentBracketBalance > 0) {
result.append(1);
} else {
result.append(-1);
}
--currentBracketBalance;
} else {
result.append(c);
}
}
return result.toString();
}
string Transform(string const &s)
{
string out;
int open = 0;
for (char c : s) {
switch (c) {
case '(':
++open;
out += '0';
break;
case ')':
if (open > 0) {
--open;
out += '1';
} else {
out += "-1";
}
break;
default:
out += c;
break;
}
}
if (open > 0) {
string prefix;
for (int i = 0; i < open; ++i) {
prefix += "-1";
}
out = prefix + out.substr(open, out.size() - open);
}
return out;
}
static String paraValidation(String str)
{
if(str==null || str.length()<1)
return null;
if(str.length()==1)
return "-1";
StringBuilder strb=new StringBuilder();
char[] ch=str.toCharArray();
for(int i=0;i<ch.length;i++){
if(ch[i]=='('){
strb.append(ch[i]);
}else if(ch[i]==')'){
int j=i-1;
boolean t=false;
while(j>=0){
if(strb.charAt(j)=='('){
strb.replace(j, j+1, "0");
strb.replace(i, i+1, "1");
t=true;
break;
}
j--;
}
if(!t)
strb.append(ch[i]);
}else{
strb.append(ch[i]);
}
}
return strb.toString().replaceAll("\\(", "-1").replaceAll("\\)", "-1");
}
public static String solve(String input) {
StringBuilder sb = new StringBuilder();
Stack<Integer> parentheses = new Stack<>();
int index;
for (index = 0; index < input.length(); index++) {
if (input.charAt(index) == '(') {
parentheses.push(index);
sb.append('0');
} else if (input.charAt(index) == ')') {
if (!parentheses.isEmpty() && input.charAt(parentheses.peek()) == '(') {
parentheses.pop();
} else {
parentheses.push(index);
}
sb.append('1');
} else {
sb.append(input.charAt(index));
}
}
while (!parentheses.isEmpty()) {
index = parentheses.pop();
sb.setCharAt(index, '1');
sb.insert(index, '-');
}
return sb.toString();
} //end
- Anonymous November 19, 2017string a="(a))"; cout<< a<<" -> "; stack<int> st; for(int i=0;i<a.length();i++){ if(a[i]=='('){ st.push(i); }else if(a[i]==')'){ if(st.empty()){ a.replace(i, 1, "-1"); }else{ a.replace(i, 1, "1"); a.replace(st.top(), 1, "0"); st.pop(); } } } while(!st.empty()){ a.replace(st.top(), 1, "-1"); st.pop(); } cout<<a<<endl;