Google Interview Question for Software Engineers


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

- aonecoding February 13, 2018 | Flag Reply
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();
    }

- denis.zayats February 13, 2018 | Flag Reply
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();
    }

- Anonymous February 13, 2018 | Flag Reply
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;
	}

- Anonymous February 13, 2018 | Flag Reply
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;
	}

}

- Anwar Shaikh February 13, 2018 | Flag Reply
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();
    }

- Anonymous February 13, 2018 | Flag Reply
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;
}

- jgriesser February 13, 2018 | Flag Reply
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);
}

- Viv February 17, 2018 | Flag Reply
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);
	}

- Viv February 17, 2018 | Flag Reply
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;
}

- the_lobster February 18, 2018 | Flag Reply
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;
}

- the_lobster February 18, 2018 | Flag Reply
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;
}

- the_lobster February 18, 2018 | Flag Reply
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;
}

- the_lobster February 18, 2018 | Flag Reply
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
    }

- Natalia March 10, 2018 | Flag Reply
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();
    }

- Aim_Google March 30, 2018 | 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