Google Interview Question for Software Engineers


Country: United States




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

The problem looked like very easy, but it was actually not so trivial recursion. Rewrite input as fork join model. Code: ideone[dot]com/pW7gAr

- shakil0302 April 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Using regular expression.
	//O(n), where n is the string length.
	//It may take up to O(2^m) time and space to compile the regular expression, where m is the size of regex.
	public static String reformat(String input) {
	    String regex = "^(.*)(\\{)(.*?)(\\})(.*)$";
		
	    Matcher matcher = Pattern.compile(regex).matcher(input);
	 
	    String result = "";
	    
	    if (matcher.find()) {
	    	String[] rep = matcher.group(3).split(",");
	    	
	    	for (int i = 0; i < rep.length; i++)
	    		rep[i] = matcher.group(1) + rep[i] + matcher.group(5);
	    	
	    	return matcher.group(2) + String.join(", ", rep) + matcher.group(4);
	    }
	    return input;
	}

- Anonymous April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Using regular expression.
	//O(n), where n is the string length.
	//It may take up to O(2^m) time and space to compile the regular expression, where m is the size of regex.
	public static String reformat(String input) {
	    String regex = "^(.*)(\\{)(.*?)(\\})(.*)$";
		
	    Matcher matcher = Pattern.compile(regex).matcher(input);
	 
	    String result = "";
	    
	    if (matcher.find()) {
	    	String[] rep = matcher.group(3).split(",");
	    	
	    	for (int i = 0; i < rep.length; i++)
	    		rep[i] = matcher.group(1) + rep[i] + matcher.group(5);
	    	
	    	return matcher.group(2) + String.join(", ", rep) + matcher.group(4);
	    }
	    return input;
	}

- Anonymous April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Duplicate. Please delete!

- Anonymous April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Help

- Anonymous April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Duplicate. Please delete!

- Anonymous April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

using recursion after creating a list of Nodes, for the example: "a{d,b,c}e", list of nodes:
Node(a,Node(dbc,Node(e)))

import java.util.LinkedList;
import java.util.List;

public class BraceExpansion {

    public static final class Node {
        private String value;

        private Node next;

        public Node(String value) {
            this.value = value;
        }

    }

    public List<String> expansion(String input) {

        int n = input.length();

        Node head = null;
        Node previous = null;

        for (int i = 0; i < n; ) {

            char c = input.charAt(i);

            Node newNode;

            if (c == '{') {
                int j = input.indexOf('}', i);
                String s = input.substring(i + 1, j).replaceAll(",", "");
                newNode = new Node(s);
                i = j + 1;
            } else {
                newNode = new Node(c + "");
                i++;
            }


            if (head == null) {
                head = newNode;
                previous = newNode;
            } else {
                previous.next = newNode;
                previous = newNode;
            }
        }

        List<String> result = new LinkedList<>();

        dfs(head, new StringBuilder(), result);

        return result;

    }

    private void dfs(Node head, StringBuilder sb, List<String> result) {

        if (head == null) {
            result.add(sb.toString());
        } else {
            for (char c: head.value.toCharArray()) {
                dfs(head.next, sb.append(c), result);
            }
        }

        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        BraceExpansion braceExpansion = new BraceExpansion();

        List<String> expansion = braceExpansion.expansion("a{d,c,b}{e,f,g}");

        System.out.println(expansion);
    }

}

- mmenezes April 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;

public class BraceExpansion {

    public static final class Node {
        private String value;

        private Node next;

        public Node(String value) {
            this.value = value;
        }

    }

    public List<String> expansion(String input) {

        int n = input.length();

        Node head = null;
        Node previous = null;

        for (int i = 0; i < n; ) {

            char c = input.charAt(i);

            Node newNode;

            if (c == '{') {
                int j = input.indexOf('}', i);
                String s = input.substring(i + 1, j).replaceAll(",", "");
                newNode = new Node(s);
                i = j + 1;
            } else {
                newNode = new Node(c + "");
                i++;
            }


            if (head == null) {
                head = newNode;
                previous = newNode;
            } else {
                previous.next = newNode;
                previous = newNode;
            }
        }

        List<String> result = new LinkedList<>();

        dfs(head, new StringBuilder(), result);

        return result;

    }

    private void dfs(Node head, StringBuilder sb, List<String> result) {

        if (head == null) {
            result.add(sb.toString());
        } else {
            for (char c: head.value.toCharArray()) {
                dfs(head.next, sb.append(c), result);
            }
        }

        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        BraceExpansion braceExpansion = new BraceExpansion();

        List<String> expansion = braceExpansion.expansion("a{d,c,b}{e,f,g}");

        System.out.println(expansion);
    }

}

- mmenezes April 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ExpandString(std::string str1)
{
	map<std::string, std::string> mapStrExpan;

	int nLength = str1.length(); 
	bool openBrace = false, closeBrace = false;
	string strTemp = "";
	for (int i = 0; i <nLength ; i++ )
	{
		strTemp = str1[i];
		if (str1[i] == '{')
		{
			mapStrExpan[strTemp] ;
			openBrace = true;
		}
		else if (str1[i] == '}')
		{
			mapStrExpan[strTemp];
			openBrace = false;
			closeBrace = true;
		}
		else
		{
			if(openBrace)
				mapStrExpan["{"] += strTemp;
			else if (closeBrace)
				mapStrExpan["last"] += strTemp;
			else
				mapStrExpan["first"] += strTemp;
		}
	}

	map<std::string, std::string>::iterator itMap; 
	map<std::string, std::string>::iterator itMapLast;

	std::string expanString = "";
	std::string strLast = "";
	//seperating first last strings from the middle and printing in combination.
	if ((itMapLast = mapStrExpan.find("first")) != mapStrExpan.end())
	{
		expanString += itMapLast->second;
	}

	if ((itMapLast = mapStrExpan.find("last")) != mapStrExpan.end())
	{
		strLast += itMapLast->second;
	}

	if ((itMapLast = mapStrExpan.find("{")) != mapStrExpan.end())
	{
		int nLeng = itMapLast->second.length();
		std::string middlestr = itMapLast->second;

		printf("Combination of Strings \r\n");
		std::string strFinal; 
		for (int i = 0; i < nLeng; i++)
		{
			if (middlestr[i] != ',')
			{
				strFinal = expanString + middlestr[i] + strLast;
				printf("%s\r\n", strFinal.c_str());
			}
		}

	}

}

int main()
{
	std::string str1 = "ahj{d,c,b,m,o,p,q}etu";

	ExpandString(str1);

	getchar();

}

- rsullad May 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package T12;

import java.util.ArrayList;

public class T12 {

	private static final String input = "a{d,c,b}e";

	public static void main(String[] args) {

		boolean first = false, second = false;
		ArrayList<String> firstS = new ArrayList<>();
		ArrayList<String> secondS = new ArrayList<>();
		ArrayList<String> thirdS = new ArrayList<>();

		for (int i = 0; i < input.length(); i++) {
			char getChar = input.charAt(i);
			switch (getChar) {
			case '{':
				first = true;
				break;
			case '}':
				second = true;
				break;
			case ',':
				break;
			default:
				if ((first == false) && (second == false)) {
					firstS.add(String.valueOf(getChar));
				} else if ((first == true) && (second == false)) {
					secondS.add(String.valueOf(getChar));
				} else if ((first == true) && (second == true)) {
					thirdS.add(String.valueOf(getChar));
				}
				break;

			}
		}

		String beforeS = new String();
		String afterS = new String();

		for (String temp : firstS) {
			beforeS += temp;
		}

		for (String temp : thirdS) {
			afterS += temp;
		}

		ArrayList<String> result = new ArrayList<>();

		for (int k = 0; k < secondS.size(); k++) {
			String temp = new String();
			String mid = secondS.get(k);

			temp = beforeS + mid + afterS;
			result.add(temp);
		}
		
		System.out.println(result);
	}
}

- mannerh1 May 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved using queues.

- Anonymous September 13, 2020 | 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