## Groupon Interview Question for Developer Program Engineers

• -2

Country: United States
Interview Type: Phone Interview

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

The easiest way is to create a prefix tree. For instance, given a T="aababcabcd" you'll have one root with 2 nodes: "empty string" and "a", in turn "a" will have "b" as a child and "b" will have "c" as a child and "c" will have "d" as a child. Once you build a tree you can match it with your T, which gives you O(n) solution. See more more info about Suffix trees, Tries, Prefix trees

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

Would you please clarify your solution ? I guess creating a trie for only one word will result a string of nodes ! how could it be used to solve the problem ? what do you mean by "match it with your T" ?

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

How would you handle : "aaaabaac"

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

So, what is the question ?

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

public static void main(String[] args) {
Scanner keyboard=new Scanner(System.in);

System.out.println("Enter of string value:");
String k=keyboard.next();

long boyut=k.length();
long m=boyut/2;
if(boyut%2==1){
m=m+1;
}
int b=1,a=0;

for (int i= 0; i <m+1; i++) {
System.out.println(k.substring(a+i, a+i+b));
a+=i;
b++;

}

}

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

Following is the code in python. "phrase_list" is the list of phrases that the string is partitioned into. We start with the current phrase "cur_phrase" equal to the character pointed to by index. If the "cur_phrase" (single character) does not exist in the accumulated "phrase_list", we add it to the phrase list since p0 is given as empty. However, if the "cur_phrase" (single character) exists in the "phrase_list", we keep adding subsequent characters to the "cur_phrase" until it doesnt exist in phrase_list. After adding "cur_phrase", we reset "cur_phrase" from the next character and continue iterating.

``````def partition_string(my_str):
phrase_list = []
index = 0

while index < len(my_str):
cur_phrase = my_str[index]

while (index+1 < len(my_str)) and (cur_phrase in phrase_list):
cur_phrase += my_str[index+1]
index += 1

phrase_list.append(cur_phrase)
index += 1

return phrase_list

## MAIN
print partition_string("aababcabcd")``````

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

Just a try:
Sum of arithmetic progression is n/2(2*a+(n-1)*d)

So we know the total sum for the series i.e. in the below case which is 10:
aababcabcd = a + ab + abc + abcd

10 = n/2(2*a+(n-1)*d);
20=n(2*a+(n-1))

Try different values for n and you will see that it for all the number except 4 it is giving a fraction number.Once we get n then it is easy to check if the arithmetic pattern is as we want or not i.e. between two consecutive pattern(p1 and p2) there should be a difference of 1 character and likewise for p2 and p3.

I don't know this will work for all cases or not but suggestions are most welcome.

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

you are assuming that the progression will always increase which is not necessarily the case (atleast in my interpretation of the question). So, working out the series wouldn't help.

For example, if the given string is "aababcXabcd", the partition would be (a, ab, abc, X, abcd) .. this doesnt follow a progression

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

(a, ab, abc, X, abcd) won't work because X is not a concatenation of some string before it plus a character. But yeah had it been "aababcababcd" then the partition would be (a, ab, abc, ab, abcd) - the 2nd ab is acceptable because it's a+b and we are only requiring each phrase to be the concatentation of SOME previous phrase plus a character. In this case that previous phrase is "a".

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

Sunny, in the question p0 = '' (empty string). That is why (a, ab, abc, X, abcd) should work since X is a concatenation of p0 + X.

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

Hmm I did miss the p0 = (empty string). Having said that, then I believe the method is supposed to take a parameter n that restricts how many phrases you can have. Otherwise you can simply have each phrase being a character and that would always satisfy the condition of pi = p0 + c.
That's a slightly different question than what I assumed the question to be, which is to partition the string into phrases without letting p0 = (empty string) and always requiring p1 to be the first letter.

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

Use backtracking. At each point we have a string to partition as well as a list of phrases we have so far. If the string is empty & the number of phrases equals N (required number of phrases), then we have found a partition. Otherwise, for each phrase we have, we check if the string starts with this phrase and if so, recurse by adding this phrase to the list and checking on the remaining substring.

The code below is not optimal because I could have stopped checking once the list size is larger than N.

``````static ArrayList<String> partition(String s, int n, ArrayList<String> phrases) {
int len = s.length();
if(len == 0 && phrases.size() == n)
return phrases;
int numPhrases = phrases.size();
for(int i=0; i<numPhrases; i++) {
String phrase = phrases.get(i);
int len2 = phrase.length();
if(len > len2 && s.startsWith(phrase)) {
ArrayList<String> result = partition(s.substring(len2+1), n, phrases);
if(result != null)
return result;
else phrases.remove(phrases.size()-1);
}
}
return null;
}

public static void main(String[] args) {
String s = args;
int n = Integer.parseInt(args);
ArrayList<String> phrases = new ArrayList<String>();
phrases = partition(s, n+1, phrases);
if(phrases == null) {
System.out.println("no solution");
} else {
for(String phrase : phrases)
System.out.println(phrase);
}
}``````

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

I asked the interviewer for another example and this is how it goes :

T = aabeabcabcd

p0 = " "
p1 = p0+a = a
p2 = p1+b = ab
p3 = p0+e = e
p4 = p2+c = abc
p5 = p4+d = abcd

I was not able to write the code for it, but I want to know to do it.

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

@Anonymous

Is this an optimization question where you need to minimize the number of phrases? Otherwise, there is always this trivial solution of splitting the n-character string into n phrases where each phrase pi = p0 + ith character

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

if input is like this means...
i/p:abcabc
o/p:p0=""
p1=p0abc or p1=p0a
p2=p0b like this???
and if i/p is aaaaaa
then o/p
p0=""
p1=a
p2=p1a??

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

The code below is based on the tree idea proposed by the guy above me~

``````package tphrasePartition;
import java.util.*;

class Node<T>{
public T data;
public List<Node<T>> children;

public Node(){
super();
}

public Node(T data){
this();
this.data = data;
}

public Node<T> Exist(T data, Bool bool)
{
for(int i=0; i<this.children.size(); i++)
{
if(this.children.get(i).data.equals(data))
{
bool.bool = true;
return this.children.get(i);
}
}
bool.bool = false;
return this;
}
}

//Since there is no pointer in java, I write a Bool class
class Bool {
public boolean bool;
public Bool()
{
bool = false;
}
public Bool(boolean b){
bool = b;
}
}

public class TphrasePartition {

/**
* @param args
*/

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter of String value:");
String t = keyboard.next();

Node<String> root = new Node("");
root.children = new ArrayList();

Bool flag = new Bool(false);
Node<String> tmpRoot = new Node();
Node<String> interRoot = new Node();
interRoot = root;

System.out.println(t.length());
for(int i=0; i<t.length();i++)
{
String c =t.substring(i, i+1);
//			System.out.println(c);
tmpRoot = interRoot.Exist(c,flag);
if(flag.bool==true){
System.out.print(t.charAt(i));
interRoot = tmpRoot;
}else{
if(i!=t.length()-1)
System.out.print(t.charAt(i)+"+");
else
System.out.print(t.charAt(i));
Node<String> newNode = new Node(c);
newNode.children = new ArrayList();
interRoot = root;
flag.bool = false;
}
}

}

}``````

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

This would be solution with the assumption that the string has been sanitized and validated that it is expected. So based on that assumption you don't need to read each char so I only read the new ones added in each phrase.

I could also to a substring reading the actual characters which is another option. In that way you could probably validate but again my assumption is that it is valid.
This in C#

``````ICollection<string> PartitionPhrases(string t)
{
if(t == null)
{
throw new ArgumentNullException("t");
}

List<string> result = new List<string>();
int current = 0;
int i = 1
int length = t.Length;
StringBuilder sb = new StringBuild();

while(current < length)
{
sb.Append(t[current]);

i++;
current = current + i;
}

return result;
}``````

Here is the solution using substring where I could validate the input as it constructs the string.

``````ICollection<string> PartitionPhrases(string t)
{
if(t == null)
{
throw new ArgumentNullException("t");
}

List<string> result = new List<string>();

if(t == string.Empty)
{
return result;
}

// Initiating parameters as an interation happen so we can have a value
// for the strBefore in order to compare and validate for errors.
string strBefore = t.SubString(0, 1);
int start = 1;
int i = 2
int length = t.Length;

while((start + i) < length)
{
string strCurrent = t.SubString(start, i);
if(strCurrent.SubString(0, strCurrent -1) != strBefore)
{
throw new ArgumentException(
"t",
string.Format(
"The string t does not contain valid phrases." +
"\nBefore:{0}\nAfter{1} ",
strBefore,
strCurrent));
}

start += i;
i++;

strBefore = strCurrent;
}

if(start != length)
{
throw new ArgumentException(
"t",
"The string t does not left incomplete phrase at the end.\nPhare:" +
t.SubString(start, length -start));
}

return result;
}``````

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

The question looks confusing. I solved this with the assumption, the char count is incremented with every phrase count. Here is my implementation in c++. let me know your comments.

string addchars(int s, int e, string str){
string substr="";
while (s <= e){
substr = substr + str[s];
s++;
}
return substr;
}

void createPhrase(string str){
int startingIndex = 0;
int endingIndex = 0;
int length = str.length();
int phrasecount = 1;
vector<string> p;
while (endingIndex <= length)
{
if (startingIndex == endingIndex){
//vector does not allow char to be aded since it is declared as string.
//So convert char to string before adding to vector
stringstream ss;
string s;
char c = str[startingIndex];
ss << c;
ss >> s;
p.push_back(s);
}
else{
}
phrasecount++;
startingIndex = endingIndex + 1;
endingIndex = endingIndex + phrasecount;
}
}

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

To call it from main use this
//given a str "aabbcabcd" return a, ab, abc,abcd
str = "aababcabcd";
createPhrase(str);

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ List<string> phrase_list = new List<string>(); void partition(string fullString) { if (string.IsNullOrWhiteSpace(fullString)) { return; } int nextIndex = fullString.IndexOf(fullString, 1); string phrase = ""; if (nextIndex < 0) { phrase = fullString.Substring(0, fullString.Length); } else { phrase = fullString.Substring(0, nextIndex); } if (phrase_list.Count == 0 || // Check PJ + C phrase_list[phrase_list.Count - 1] == phrase.Substring(0, phrase.Length - 1)) { phrase_list.Add(phrase); } if (nextIndex >= 0) { partition(fullString.Substring(nextIndex)); } } }}]
Comment hidden because of low score. Click to expand.
0
of 0 vote

char string;
int c = 0, count = {0};
cout<<"Enter a string :"<<endl;
cin>>string;
char *p;
p = string;
while ( *p != '\0' )
{
if ( *p >= 'a' && *p <= 'z' )
{
count[*p -'a']++;
}
p++;
}

for ( c = 0 ; c < 26 ; c++ )
{
if( count[c] != 0 )
{
std::cout.put(97+c);
cout<<count[c]<<" ";
// printf("%c occurs %d times in the entered string.\n",,);
}
}

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

Some of the solutions are so complex above .Heres the easiest O(n) solution.Just create a int array and check if the ascii value at that index is 1 if not it is a new word and increment its ascii value count by 1;

``````public ArrayList<Strings>Phrases(String toDecode)
{
ArrayList<String>phrases = new ArrayList<String>();
int[] charArr                          = new int;
charArr[toDecode.charAt(0)]++;
for(int i=1;i<toDecode.length;i++)
{
if(    charArr[toDecode.charAt(i)] ==0)
{
String temp = phrases.get(phrases.length-1) + toDecode.charAt(i);
charArr[toDecode.charAt(i)]++;
}
}
return phrases;
}``````

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.