Groupon Interview Question for Developer Program Engineers


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

- Marcello Ghali June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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" ?

- Arian August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you handle : "aaaabaac"

- Arian August 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

So, what is the question ?

- Koustav Chatterjee June 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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++;

}


}

- KeLeSoV June 22, 2013 | Flag
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")

- whatevva' June 21, 2013 | Flag Reply
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.

- aka June 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- whatevva' June 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(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".

- Sunny June 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- whatevva' June 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny June 21, 2013 | Flag
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)) {
			phrases.add(s.substring(0, len2+1));
			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[0];
	int n = Integer.parseInt(args[1]);
	ArrayList<String> phrases = new ArrayList<String>();
	phrases.add("");
	phrases = partition(s, n+1, phrases);
	if(phrases == null) {
		System.out.println("no solution");
	} else {
		for(String phrase : phrases)
			System.out.println(phrase);
	}
}

- Sunny June 21, 2013 | Flag Reply
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.

- Anonymous June 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Murali Mohan June 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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??

- tamil selvi June 26, 2013 | Flag
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.children.add(newNode);
				interRoot = root;
				flag.bool = false;
			}
		}
		
	}

}

- JY July 09, 2013 | Flag Reply
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]);
                  result.Add(sb.ToString());
                  
                  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);
               result.Add(strBefore);
               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));
                  }

                  result.Add(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;
}

- Nelson July 11, 2013 | Flag Reply
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{
p.push_back(addchars(startingIndex, endingIndex, str));
}
phrasecount++;
startingIndex = endingIndex + 1;
endingIndex = endingIndex + phrasecount;
}
}

- victor October 21, 2013 | Flag Reply
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);

- victor October 21, 2013 | Flag Reply
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[0], 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)); } } }}] - lem November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char string[100];
int c = 0, count[26] = {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",,);
}
}

- Sambit Swain February 17, 2014 | Flag Reply
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[256] 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[256];    
   //Adding the first element
    phrases.add(toDecode.charAt(0));
     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);
                                phrases.add(temp);
                                 charArr[toDecode.charAt(i)]++;
                }
          }
       return phrases;
   }

- Danish Shaikh (danishshaikh556@gmail.com) May 01, 2014 | 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