Google Interview Question for Software Engineers

• 4

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Looking for coaching on interview preparation?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews

Ace G, U, FB, Amazon, LinkedIn, MS and other top-tier interviews in weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

``````decompress("((x){3}(y){2}z){2}", 0)

def decompress(s, i):
res = ""
while i < len(s):
if s[i] == '(':
i += 1
word, i, r = decompress(s, i) # word is the decompressed string in (), r is the number of repetitions
res += word * r
elif s[i] == ')':
if i == len(s) - 1 or s[i + 1] != '{': # in case of strings like "(a(b))" where {} is omitted
return res, i + 1, 1
else:
close = s.find("}", i)
return res, close + 1, int(s[i + 2: close])
else:
res += s[i]
i += 1
return res``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution:
Find more interesting articled on ITARRAY.NET
Tested with:
"abccbccd" -> "a(b(c){2}){2}d"
"xxxyyzxxxyyz" -> "((x){3}(y){2}z){2}"
"xaxaxaxaxaxaxaxaxaxayyzxaxaxaxaxaxaxaxaxaxayyz" -> "((xa){10}(y){2}z){2}"

``````public String decompress(String str) {
int leftEdgeIndex = 0;
for (int i = 0; i < str.length() - 1; i++) {
//Search for the last ( bracket before the pattern is found
if (str.charAt(i) == '(') {
leftEdgeIndex = i;
}
if (str.charAt(i) == ')' && str.charAt(i + 1) == '{') {
String leftPart = str.substring(0, leftEdgeIndex);
String rightPart = str.substring(i + 2, str.length());
int rightEdgeIndex = 0;
for (int r = i + 2; r < str.length(); r ++) {
if (str.charAt(r) == '}') {
rightEdgeIndex = r;
rightPart = str.substring(rightEdgeIndex + 1, str.length());
break;
}
}
String[] parts = str.substring(leftEdgeIndex + 1, rightEdgeIndex).split("\\)\\{");
String part = repeatString( parts[0], Integer.parseInt(parts[1]));
return decompress(leftPart + part + rightPart);
}
}

return str;
}

private String repeatString(String str, int repeatTimes) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < repeatTimes; i++) {
builder.append(str);
}

return builder.toString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String decompress(String string) {

Stack<String> stack = new Stack<>();
StringBuilder result = new StringBuilder();

for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (c != ')' && c != '}') {
stack.push(String.valueOf(c));
} else if (c == ')') {
StringBuilder tmp = new StringBuilder();
String poped;
while (!(poped = stack.pop()).equals("(")) {
tmp.insert(0, poped);
}
stack.push(tmp.toString());
} else {
StringBuilder tmp = new StringBuilder();
String poped;
while (!(poped = stack.pop()).equals("{")) {
tmp.insert(0, poped);
}
int copies = Integer.valueOf(tmp.toString());
String str = stack.pop();
tmp = new StringBuilder();
for (int j = 1; j <= copies; j++) {
tmp.append(str);
}
stack.push(tmp.toString());
}
}

Iterator<String> it = stack.iterator();
while (it.hasNext()) {
result.append(it.next());
}
return result.toString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using stack to solve the problem?

``````public static void pushStringToStack(String str)
{
for(int index = 0; index < str.length(); index++)
{
char indexChar = str.charAt(index);
characterStack.push(indexChar);
}
}

public static String getInbraceString()
{
String inBraceString = "";
Character c = null;
do {
c = characterStack.pop();
if(!(c.compareTo(')') == 0 || c.compareTo('(') == 0))
{inBraceString = c + inBraceString;}
}
while(c != '(');
return inBraceString;
}

public static String decompress(String compressedString)
{
String decompressedString  = "";
for(int index = 0; index < compressedString.length(); index++)
{
char indexChar = compressedString.charAt(index);
if(indexChar == '{' || indexChar == '}') { /*ignore*/ }
else if( Character.isDigit(indexChar))
{
int replicationCount = Character.getNumericValue(indexChar);

//1. pop the string till opening brace
String inBraceString = getInbraceString();

//2. Replicate the number of times
for(int replicationIndex = 0; replicationIndex < replicationCount; replicationIndex++)
{
pushStringToStack(inBraceString);
}
}
else { characterStack.push(indexChar);}
}

while(!characterStack.isEmpty())
{
decompressedString = characterStack.pop() + decompressedString;
}

return decompressedString;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using stack to solve the problem?

``````public class StringDecompressor {

static Stack<Character> characterStack = new Stack<Character>();

public static void main(String[] args) {
// TODO Auto-generated method stub
String compressedString = "((x){3}(y){2}z){2}";
//compressedString = "(a){2}";
compressedString="a(b(c){2}){2}d";
System.out.println(decompress(compressedString));
}

public static void pushStringToStack(String str)
{
for(int index = 0; index < str.length(); index++)
{
char indexChar = str.charAt(index);
characterStack.push(indexChar);
}
}

public static String getInbraceString() {
String inBraceString = "";
Character c = null;
do {
c = characterStack.pop();
if(!(c.compareTo(')') == 0 || c.compareTo('(') == 0))
{inBraceString = c + inBraceString;}
}
while(c != '(');
return inBraceString;
}

public static String decompress(String compressedString)
{
String decompressedString  = "";
for(int index = 0; index < compressedString.length(); index++)
{
char indexChar = compressedString.charAt(index);
if(indexChar == '{' || indexChar == '}') { /*ignore*/ }
else if( Character.isDigit(indexChar))
{
int replicationCount = Character.getNumericValue(indexChar);

//1. pop the string till opening brace
String inBraceString = getInbraceString();

//2. Replicate the number of times
for(int replicationIndex = 0; replicationIndex < replicationCount; replicationIndex++)
{
pushStringToStack(inBraceString);
}
}
else { characterStack.push(indexChar);}
}

while(!characterStack.isEmpty())
{
decompressedString = characterStack.pop() + decompressedString;
}

return decompressedString;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String decompress(String string) {

Stack<String> stack = new Stack<>();
StringBuilder result = new StringBuilder();

for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (c != ')' && c != '}') {
stack.push(String.valueOf(c));
} else if (c == ')') {
StringBuilder tmp = new StringBuilder();
String poped;
while (!(poped = stack.pop()).equals("(")) {
tmp.insert(0, poped);
}
stack.push(tmp.toString());
} else {
StringBuilder tmp = new StringBuilder();
String poped;
while (!(poped = stack.pop()).equals("{")) {
tmp.insert(0, poped);
}
int copies = Integer.valueOf(tmp.toString());
String str = stack.pop();
tmp = new StringBuilder();
for (int j = 1; j <= copies; j++) {
tmp.append(str);
}
stack.push(tmp.toString());
}
}

Iterator<String> it = stack.iterator();
while (it.hasNext()) {
result.append(it.next());
}
return result.toString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static class StringAndIndex {
public String s;
public int idx;

StringAndIndex(String s, int idx) {
this.s = s;
this.idx = idx;
}
}

public static String decompress(String str) {
return decompress(str, 0).s;
}

public static StringAndIndex decompress(String str, int idx) {
StringAndIndex decompressed = new StringAndIndex("", idx);

for (int i = idx; i < str.length(); i++) {
char c = str.charAt(i);

if (c == '(') {
StringAndIndex strIdx = decompress(str, i + 1);
decompressed.s += strIdx.s;
i = strIdx.idx;
} else if (c == ')') {
if (i + 1 < str.length() && str.charAt(i + 1) == '{') {
int bracketIdx = str.indexOf('}', i + 2);
int count = Integer.parseInt(str.substring(i + 2, bracketIdx));
String toReplicate = decompressed.s;

while (--count > 0) {
decompressed.s += toReplicate;
}

i = bracketIdx;
}

decompressed.idx = i;
return decompressed;
} else {
decompressed.s += c;
}
}

return decompressed;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public String decompress(String input) {
boolean startNew = false;
Stack<String> stack = new Stack<String>();

for (int i = 0; i < input.length(); i++) {
Character ch = input.charAt(i);
if (ch == '(') {
startNew = true;
} else if (ch == ')') {
int nextIndex = input.indexOf('}', i);
int count = Integer.parseInt(input.substring(i + 2, nextIndex));
String prevStr = stack.pop();
String repStr = "";
while (count-- > 0)
repStr += prevStr;
if (stack.isEmpty())
stack.push(repStr);
else
stack.push(stack.pop() + repStr);
i = nextIndex;
} else {
if (startNew || stack.isEmpty()) {
stack.push(ch.toString());
startNew = false;
} else
stack.push(stack.pop() + ch);
}
}
String output = stack.toString();
return output.substring(1, output.length() - 1);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String decompress(String input) {
boolean startNew = false;
Stack<String> stack = new Stack<String>();

for (int i = 0; i < input.length(); i++) {
Character ch = input.charAt(i);
if (ch == '(') {
startNew = true;
} else if (ch == ')') {
int nextIndex = input.indexOf('}', i);
int count = Integer.parseInt(input.substring(i + 2, nextIndex));
String prevStr = stack.pop();
String repStr = "";
while (count-- > 0)
repStr += prevStr;
if (stack.isEmpty())
stack.push(repStr);
else
stack.push(stack.pop() + repStr);
i = nextIndex;
} else {
if (startNew || stack.isEmpty()) {
stack.push(ch.toString());
startNew = false;
} else
stack.push(stack.pop() + ch);
}
}
String output = stack.toString();
return output.substring(1, output.length() - 1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution using stacks:

``````#include <iostream>
#include <string>
#include <stack>
#include <vector>

using std::string;

template <typename T>
using VecStack = std::stack<T, std::vector<T>>;

void Decompress(string &a) {
if (a.empty()) {
return;
}

VecStack<size_t> indices;

size_t currIdx = 0;

while(currIdx < a.size()) {
char c = a[currIdx];

if (c == '(') {
indices.push(currIdx);
++currIdx;
}
else if (c == ')') {
auto prevIdx = indices.top();
indices.pop();

auto subStr = a.substr(prevIdx + 1, currIdx - (prevIdx + 1));

// Count repetitions
auto newIdx = currIdx + 2; // we are on the first digit here after “{“

string repStr;
while(a[newIdx] != '}') {
repStr.append(1, a[newIdx]);
++newIdx;
}

a.erase(prevIdx, newIdx - prevIdx + 1);

auto repsNum = std::stoul(repStr);
auto subStrLen = subStr.size();
for (size_t i = 0; i < repsNum; ++i) {
a.insert(prevIdx + (i * subStrLen), subStr);
}

currIdx = prevIdx + (subStrLen * repsNum);
}
else {
++currIdx;
}
}
}

int main () {
string compressed = "a(b(c){2}){2}d";

Decompress(compressed);

std::cout << compressed << "\n";

compressed = "((x){3}(y){2}z){2}";

Decompress(compressed);

std::cout << compressed << "\n";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ version using stacks:

``````#include <iostream>
#include <string>
#include <stack>
#include <vector>

using std::string;

template <typename T>
using VecStack = std::stack<T, std::vector<T>>;

void Decompress(string &a) {
if (a.empty()) {
return;
}

VecStack<size_t> indices;

size_t currIdx = 0;

while(currIdx < a.size()) {
char c = a[currIdx];

if (c == '(') {
indices.push(currIdx);
++currIdx;
}
else if (c == ')') {
auto prevIdx = indices.top();
indices.pop();

auto subStr = a.substr(prevIdx + 1, currIdx - (prevIdx + 1));

// Count repetitions
auto newIdx = currIdx + 2; // we are on the first digit here after “{“

string repStr;
while(a[newIdx] != '}') {
repStr.append(1, a[newIdx]);
++newIdx;
}

a.erase(prevIdx, newIdx - prevIdx + 1);

auto repsNum = std::stoul(repStr);
auto subStrLen = subStr.size();
for (size_t i = 0; i < repsNum; ++i) {
a.insert(prevIdx + (i * subStrLen), subStr);
}

currIdx = prevIdx + (subStrLen * repsNum);
}
else {
++currIdx;
}
}
}

int main () {
string compressed = "a(b(c){2}){2}d";

Decompress(compressed);

std::cout << compressed << "\n";

compressed = "((x){3}(y){2}z){2}";

Decompress(compressed);

std::cout << compressed << "\n";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ version with stack:

``````#include <iostream>
#include <string>
#include <stack>
#include <vector>

using std::string;

template <typename T>
using VecStack = std::stack<T, std::vector<T>>;

void Decompress(string &a) {
if (a.empty()) {
return;
}

VecStack<size_t> indices;

size_t currIdx = 0;

while(currIdx < a.size()) {
char c = a[currIdx];

if (c == '(') {
indices.push(currIdx);
++currIdx;
}
else if (c == ')') {
auto prevIdx = indices.top();
indices.pop();

auto subStr = a.substr(prevIdx + 1, currIdx - (prevIdx + 1));

// Count repetitions
auto newIdx = currIdx + 2; // we are on the first digit here after “{“

string repStr;
while(a[newIdx] != '}') {
repStr.append(1, a[newIdx]);
++newIdx;
}

a.erase(prevIdx, newIdx - prevIdx + 1);

auto repsNum = std::stoul(repStr);
auto subStrLen = subStr.size();
for (size_t i = 0; i < repsNum; ++i) {
a.insert(prevIdx + (i * subStrLen), subStr);
}

currIdx = prevIdx + (subStrLen * repsNum);
}
else {
++currIdx;
}
}
}

int main () {
string compressed = "a(b(c){2}){2}d";

Decompress(compressed);

std::cout << compressed << "\n";

compressed = "((x){3}(y){2}z){2}";

Decompress(compressed);

std::cout << compressed << "\n";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ version with stacks:

``````#include <iostream>
#include <string>
#include <stack>
#include <vector>

using std::string;

template <typename T>
using VecStack = std::stack<T, std::vector<T>>;

void Decompress(string &a) {
if (a.empty()) {
return;
}

VecStack<size_t> indices;

size_t currIdx = 0;

while(currIdx < a.size()) {
char c = a[currIdx];

if (c == '(') {
indices.push(currIdx);
++currIdx;
}
else if (c == ')') {
auto prevIdx = indices.top();
indices.pop();

auto subStr = a.substr(prevIdx + 1, currIdx - (prevIdx + 1));

// Count repetitions
auto newIdx = currIdx + 2; // we are on the first digit here after “{“

string repStr;
while(a[newIdx] != '}') {
repStr.append(1, a[newIdx]);
++newIdx;
}

a.erase(prevIdx, newIdx - prevIdx + 1);

auto repsNum = std::stoul(repStr);
auto subStrLen = subStr.size();
for (size_t i = 0; i < repsNum; ++i) {
a.insert(prevIdx + (i * subStrLen), subStr);
}

currIdx = prevIdx + (subStrLen * repsNum);
}
else {
++currIdx;
}
}
}

int main () {
string compressed = "a(b(c){2}){2}d";

Decompress(compressed);

std::cout << compressed << "\n";

compressed = "((x){3}(y){2}z){2}";

Decompress(compressed);

std::cout << compressed << "\n";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private final static String START_STR_CONTAINER = '('
private final static String END_STR_CONTAINER = ')'
private final static String START_NMB_CONTAINER = '{'
private final static String END_NMB_CONTAINER = '}'

String function(String inputStr) {
if (inputStr == null || inputStr.isEmpty())
return ''

StringBuilder str = new StringBuilder(inputStr)
int outsideIterator = -1,
openParenthese = -1,
closeParenthese = -1,
openBrace = -1,
closeBrace = -1

for (int i = outsideIterator; i < str.length(); i++) {

switch (str[i]) {
case START_STR_CONTAINER:
openParenthese = i
if (outsideIterator == -1)
outsideIterator = i
break
case END_STR_CONTAINER:
closeParenthese = i
break
case START_NMB_CONTAINER:
openBrace = i
break
case END_NMB_CONTAINER:
closeBrace = i
break
}

if (openParenthese != -1 && closeParenthese != -1 && openBrace != -1 && closeBrace != -1) {
if (openParenthese > closeParenthese || openBrace > closeBrace
|| openParenthese + 1 == closeParenthese || openBrace + 1 == closeBrace)
throw new Exception("Provided srtring \"\$inputStr\" is invalid")

String oldString = str.substring(openParenthese + 1, closeParenthese)
Integer repeatNumber = str.substring(openBrace + 1, closeBrace).toInteger()
StringBuilder newString = new StringBuilder()

repeatNumber.times {
newString.append(oldString)
}

str.replace(openParenthese, closeBrace + 1, newString.toString())

if (outsideIterator == openParenthese)
outsideIterator += newString.length()
openParenthese = closeParenthese = openBrace = closeBrace = -1
i = outsideIterator - 1

println(str)
}
}
if (openParenthese != -1 || closeParenthese != -1 || openBrace != -1 || closeBrace != -1)
throw new Exception("Provided srtring \"\$inputStr\" is invalid")
str
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String decompress(String str) {
if (str == null || str.length() == 0) return "";
int len = str.length();
HashMap<Integer, Integer> bracketPair = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; i++) {
char ch = str.charAt(i);
if (ch == '(') {
stack.push(i);
} else if (ch == ')') {
int prev = stack.pop();
bracketPair.put(prev, i);
}
}
return generateHelper(str, 0, len-1, bracketPair);
}
private static String generateHelper(String str, int sI, int eI, HashMap<Integer, Integer> bracketPair) {
StringBuilder builder = new StringBuilder();
int i = sI;
while (i <= eI) {
char ch = str.charAt(i);
if (ch != '(') {
builder.append(ch + "");
i++;
} else {
int end = bracketPair.get(i);
String temp = generateHelper(str, i+1, end-1, bracketPair);
int rep = 0;
i = end+2;
while (i <= eI) {
char ch2 = str.charAt(i);
if (ch2 == '}') break;
i++;
}
rep = Integer.valueOf(str.substring(end+2, i));
i++;
for (int r = 0; r < rep; r++) {
builder.append(temp);
}
}
}
return builder.toString();
}``````

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.

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.