## Google Interview Question for SDE-2s

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

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

Can you explain the question giving more examples pls ?

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;
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() {
std:string str("ABCD");
find_combinations(str);

return 0;
}``````

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)
{
}
}
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;
}
}
}

return res;
}``````

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);
}
}
}``````

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"))``````

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"))``````

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<>();
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;
}
} else {
}
}
return result;
}``````

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);
}``````

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.