Google Interview Question for SDE-2s


Team: AdsWorld
Country: India
Interview Type: Phone Interview




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

# I assume you want to know all unique combinations where k characters 
# are replaced by the integer value k in a string. Thereby you can replace 
# multiple times some character but the integers placed into the string has to 
# to be separated by at least a single character...
# for simplicity I assume the initial text doesn't contain numbers (0..9)
# the recursion, assumed the word does not contain numeric values
#   g(text) = toString(k) + substring(text, k, k + 1) ** g(substring(text, k + 1, n - 1)), for all 0 < k < n - 1, n = length of text
#             ++ substring(text, 1, 1) ** g(substring(text, 1, n - 1))
#   **: every result of g is prefixed with toString(k) + substring ... 
#   ++: the two list are concatenated
def anotateWithNumCharacterPlaceholder(text):
    n = len(text)
    if n <= 0: return [""]
    result = [str(n)]
    for k in range(1, n - 1):
        pfx = str(k) + text[k : k + 1]
        for sfx in anotateWithNumCharacterPlaceholder(text[k + 1 :]):
            result.append(pfx + sfx)
    
    pfx = text[:1]
    for sfx in anotateWithNumCharacterPlaceholder(text[1:]):
        result.append(pfx + sfx)
    return result

print(anotateWithNumCharacterPlaceholder("ABCD")) 
# output
# ['4', '1B2', '1BC1', '1BCD', '2C1', '2CD', 'A3', 'A1C1', 'A1CD', 'AB2', 'ABC1', 'ABCD']

edited: of course memoization would avoid repetition of work (different prefix same suffix) and speed up things

- Chris June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain the question giving more examples pls ?

- koustav.adorable June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep the already parsed characters in the vector, and print if all characters from string are read into the vector.

#include <iostream>
using namespace std;
#include <unordered_map>
#include<list>
#include <string>
#include <vector>
#include <cassert>
#include <sstream>
#include <cctype>

void print_comb(const string &s, int index, int max_index, vector<char> st) {
    if (index == max_index) {
       for(vector<char>::iterator it = st.begin(); it != st.end(); ++it) {
         cout << *it;           
       } 
       cout <<"\n";
       return;
    }
    
    st.push_back(s[index]);
    print_comb(s, index+1, max_index, st);
    st.pop_back(); // remove current
    
    int count = 1;
    // now add the number
    if (!st.empty()) {
        if (isdigit(st.back())) {
            // get the digit and increase the count. 
            count += (int)(st.back() - '0');
            st.pop_back();
        }

    }
    char to_print = (char)(count + '0');
    st.push_back(to_print);
    print_comb(s, index+1, max_index, st);
    
}

void find_combinations(std::string s) {
    if (!s.length()) {
        return;
    }
    vector<char> st;
    print_comb(s, 0, s.length(), st);
}
int main() {
	// your code goes here
    std:string str("ABCD");
    find_combinations(str);
	
	return 0;
}

- ali.kheam June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<string> abbreviations(string s)
        {
            if (string.IsNullOrEmpty(s) || s.Length == 0) { return null; }
            if (s.Length == 1)
            {
                return new List<string>() { "1" };
            }
            List<string> ret = abbreviationsActual(s);
            ret.Remove(s);
            return ret;
        }
        private static List<string> abbreviationsActual(string s)
        {
            List<string> thislist = new List<string>() { s.Substring(0,1), "1" };
            if (s.Length == 1)
            {
                return thislist;
            }
            List<string> abbrlist = abbreviationsActual(s.Substring(1));
            List<string> result = new List<string>();
            foreach (string a in thislist)
            {
                foreach (string b in abbrlist)
                {
                    result.Add(a + b);
                }
            }
            return removeconsecutivedigits(result);
        }
        private static List<string> removeconsecutivedigits(List<string> l)
        {
            List<string> res = new List<string>() ;
            for (int index = 0; index<l.Count; index++)
            {
                string s = l[index];
                string result = string.Empty;
                for (int i = 0; i < s.Length; i++)
                {
                    char schar = s[i];
                    char rchar = result == "" ? '0' : result[result.Length - 1];
                    if (result == string.Empty)
                    {
                        result = result + schar;
                    }
                    else if (Char.IsDigit(schar) && Char.IsDigit(rchar))
                    {
                        int sum = Int32.Parse(rchar.ToString()) + Int32.Parse(schar.ToString());
                        result = result.Substring(0,result.Length - 1) + sum.ToString();
                    } else
                    {
                        result = result + schar;
                    }
                }
                res.Add(result);
            }
            
            return res;
        }

- Anonymous June 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void PrintAbbreviations(string const &s, string const abbr = "", int idx = 0)
{
	if (idx >= s.size()) {
		if (!abbr.empty() &&
			abbr != s)
		{
			cout << abbr << "\n";
		}
		return;
	}

	PrintAbbreviations(s, abbr + s[idx], idx + 1);

	bool prev_digit = !abbr.empty() && isdigit(abbr.back()) ? true : false;
	if (!prev_digit) {
		for (int i = idx; i < s.size(); ++i) {
			PrintAbbreviations(s, abbr + to_string(i - idx + 1), i + 1);
		}
	}
}

- Alex June 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def abbreviations(s):
    
    retList = []
    def abbreviations(s, prefix = ""):
        
        if not s:
            return
        
        for i in range(len(s)):
            
            retList.append(prefix + str(len(s[:i+1])) + s[i+1:])
            abbreviations(s[i+1:], prefix + s[i])

    abbreviations(s)
    return retList

print(abbreviations("ABC"))

- sreera June 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def abbreviations(s):
    
    retList = []
    def abbreviations(s, prefix = ""):
        
        if not s:
            return
        
        for i in range(len(s)):
            
            retList.append(prefix + str(len(s[:i+1])) + s[i+1:])
            abbreviations(s[i+1:], prefix + s[i])

    abbreviations(s)
    return retList

print(abbreviations("ABC"))

- sreera June 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in Java:

public ArrayList<String> abbreviation(String s) {
        return rec(s);
    }

    private ArrayList<String> rec(String s) {
        if (s.length() == 1) {
            ArrayList<String> res = new ArrayList<>();
            res.add("1");
            res.add(s);
            return res;
        }
        char curr = s.charAt(0);
        ArrayList<String> prev = rec(s.substring(1));
        ArrayList<String> result = new ArrayList<>();
        for (String p : prev) {
            char first = p.charAt(0);
            if (first >= '0' && first <= '9') { // it's a number
                if (first < '9') {
                    Integer newNr = Integer.valueOf(first + "") + 1;
                    result.add(newNr + p.substring(1));
                }
                result.add(curr + p);
            } else {
                result.add(curr + p);
                result.add("1" + p);
            }
        }
        return result;
    }

- niki July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String args[]) throws Exception {
		encryptString("abcd", "", 0);
	}

	private static void encryptString(String str, String result, int start) {
		if (start >= str.length()) {
			p(result);
			return;
		}
		int lastDigit = -1;
		if (result != null && result.length() > 0 && Character.isDigit(result.toCharArray()[result.length() - 1])) {
			lastDigit = result.toCharArray()[result.length() - 1];
		}
		if (lastDigit != -1) {
			char elem[] = result.toCharArray();
			elem[elem.length - 1] = (char) ((int) elem[elem.length - 1] + 1);
			encryptString(str, new String(elem), start + 1);
		} else {
			encryptString(str, result + 1, start + 1);
		}
		encryptString(str, result + str.toCharArray()[start], start + 1);
	}

	public static void p(String str) {
		System.out.println(str);
	}

- koustav.adorable July 25, 2017 | 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