Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 13 vote

static void ListCombination(String str){
		if(str != null && str.length()!=0)
			RecCombine("",str);
	}
	
	static void RecCombine(String prefix,String rest){
		if(rest.length() == 0)
			System.out.print(prefix + " ");
		else{
			RecCombine(prefix + rest.charAt(0),rest.substring(1));
			RecCombine(prefix,rest.substring(1));
			
		}
	}

- loveCoding January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this will return the EMPTY set (i.e. "") which should be skipped according to the example above

- GKalchev March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

also will not work with "abababab"
it will duplicate the results

- GKalchev March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guess it was posted after the question was updated to say order doesn't matter, otherwise the vote wouldn't be so high.

- Sunny December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about this?

public static void Combinations(char[] arr, List<string> wordList, string pre, int idx)
        {
            for (int i = idx; i < arr.Length; i++)
            {
                string currWord = pre + arr[i];
                if (!wordList.Contains(currWord))
                {
                    wordList.Add(currWord);
                    Console.WriteLine(currWord);
                    Combinations(arr, wordList, currWord, i + 1);
                }
            }
        }

        static void Main(string[] args)
        {

            Combinations(new char[] { 'a', 'b', 'a', 'b', 'a', 'b' /*'c' */}, new List<string>(), string.Empty, 0);

            Console.Read();
        }

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static List<String> getSubStrings(String word) {
		List<String> allSubStrings = new ArrayList<String>();
		int max = 1 << word.length(); 
		for (int index = 1; index < max; index++) {
			StringBuffer subString = new StringBuffer();
			int bits = index;
			int _index = 0;
			while (bits > 0) {
				if ((bits & 1) > 0) {
					subString.append(word.charAt(_index));
				}
				bits >>= 1;
				_index++;
			}
			allSubStrings.add(subString.toString());
		}
		return allSubStrings;
	}
	
	public static void main(String[] args) {
		String word = "abc";
		System.out.println(getSubStrings(word));
		
		String word1 = "abababab";
		System.out.println(getSubStrings(word1));
	}

- Adnan Ahmad September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
7
of 9 vote

Well, think of each possible substring of the original string is a array of the same size of original string, if the character is included in the substring , the corresponding digit is 1, else is 0 for example, string "abcd" substring "ad" then binary form is 1001 ,print all the possible (2^n) binary array with function recursion, each postion in the binary array there are onyl 2 possibilties.

- T-racer February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is the non-recursive implementation in C++.

void print_all_substrings_iterative(const std::string& str)
{
    const size_t size = str.size();
    for (size_t i = 1; i < std::pow(2.0, (double)size); ++i) {
        for (size_t j = 0; j < size; ++j) {
            if (i & (1 << j)) {
                std::cout << str[j];
            }
        }
        std::cout << ' ';
    }
    std::cout << std::endl;
}

- artakbegnazaryan February 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Input String: bb
You Output: {b, b, bb}
Correct Output: {b, bb}

- Alva0930 February 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution in Python:

def generate(A):
  n = len(A)
  bitset = 2 ** n
  for i in xrange(1, bitset):
    s = []
    j = 0
    while i > 0:
      if i & 1 == 1 :
        s.append(A[j])
      i = i >> 1
      j = j + 1
    print("".join(s))

generate("abc")

- yaojingguo December 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public ArrayList<String> permutations(String s){
		if(s == null){
			return null;
		}
		ArrayList<String> result = new ArrayList<String>();
		if(s.length()==1){
			result.add(s);
			return result;
		}
		
		String firstTwo = s.substring(0,2);
		result.add(firstTwo);
		result.add(""+s.charAt(1)+s.charAt(0));
		//System.out.println(""+s.charAt(1)+s.charAt(0));
		
		for(int i = 2; i<s.length();i++){
			char c = s.charAt(i);
			result = insertChar(c,result); 			
		}
		
		Iterator<String> it = result.iterator();
		while(it.hasNext())
		{
			System.out.print(it.next()+"  ");
		}
		
		return result;
	}
	
	private ArrayList<String> insertChar(char c,ArrayList<String> list){
		ArrayList<String> tempResult = new ArrayList<String>();
		Iterator<String> it = list.iterator();
		while(it.hasNext()){
			String temp = it.next();
			for(int i = 0; i<=temp.length(); i++){
				String toBeAdded = temp.substring(0, i)+c+temp.substring(i);
				tempResult.add(toBeAdded);
			}	
		}
		return tempResult;
	}

- Learner May 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think we should consider the scenario that there are duplicated characters. (Ex. "abcc")
My idea is:
(1) count the number of distinct characters (3: a,b,c)
(2) count the occurence of each characters (a: 1, b: 1, c: 2)
(3) each character could be chosen [0 ~ occurence] times (a: 0~1, b:0~1, c:0~2)
The following is my implementation together with some simple tests:

import java.util.*;

class G210
{
 public static ArrayList<String> allSubstring(String input)
 {
  ArrayList<String> list = new ArrayList<String>();
  if (null == input) {return list;}
  if (0 == input.length()) {return list;}
  // count the number of distinct characters
  char[] chars = input.toCharArray();
  Arrays.sort(chars);
  int type = 1;
  char last = chars[0];
  for (int i = 1; i < chars.length; i++) if (chars[i] != last)
  {
   type++;
   last = chars[i];
  }
  // count the occurence of each characters
  char[] candidates = new char[type];
  int[] limits = new int[type];
  type = 0; last = chars[0];
  int count = 1;
  for (int i = 1; i < chars.length; i++)
  {
   if (chars[i] != last)
   {
    candidates[type] = last;
    limits[type] = count;
    type++;
    last = chars[i];
    count = 1;
   }
   else {count++;}
  }
  candidates[type] = last;
  limits[type] = count;
  // each character could be chosen [0 ~ occurence] times
  int[] counts = new int[limits.length];
  while (next(counts, limits))
  {
   StringBuffer sb = new StringBuffer();
   for (int i = 0; i < candidates.length; i++)
   for (int j = 0; j < counts[i]; j++)
   {
    sb.append(candidates[i]);
   }
   list.add(sb.toString());
  }
  return list;
 }

 private static boolean next(int[] counts, int[] limits)
 {
  for (int i = counts.length - 1; i >= 0; i--)
  {
   counts[i]++;
   if (counts[i] <= limits[i]) {return true;}
   counts[i] = 0;
  }
  return false;
 }

 public static void main(String[] args)
 {
  System.out.println("set1 = " + allSubstring("abc"));
  System.out.println("set2 = " + allSubstring("abcd"));
  System.out.println("set3 = " + allSubstring("abcc"));
 }
}

- Alva0930 February 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static List<String> getSubStrings(String word) {
		List<String> allSubStrings = new ArrayList<String>();
		int max = 1 << word.length(); 
		for (int index = 1; index < max; index++) {
			StringBuffer subString = new StringBuffer();
			int bits = index;
			int _index = 0;
			while (bits > 0) {
				if ((bits & 1) > 0) {
					subString.append(word.charAt(_index));
				}
				bits >>= 1;
				_index++;
			}
			allSubStrings.add(subString.toString());
		}
		return allSubStrings;
	}
	
	public static void main(String[] args) {
		String word = "abc";
		System.out.println(getSubStrings(word));
	}

- Adnan Ahmad September 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static Set<String> subStrs(String str, int from, int to){
		if(from == to){
			Set<String> ret = new HashSet<String>();
			ret.add("");
			ret.add(String.valueOf(str.charAt(from)));
			return ret;
		}
		
		Set<String> ret1 = subStrs(str, from + 1, to);
		Set<String> ret2 = new HashSet<String>();
		Iterator<String> iter = ret1.iterator();
		while(iter.hasNext()){
			String tmp = iter.next();
			iter.remove();
			String tmp1 = tmp + str.substring(from, from + 1);
			if(from == 0){
				if(tmp != "")
					ret2.add(tmp);
			}else{
				ret2.add(tmp);
			}
			ret2.add(tmp1);
			
		}
		
		return ret2;
	}

- Daniel November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code won't include the empty string and can tackle the situation where same characer occurs multiple times in a string.

- Anonymous November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.List;




public class SubstringGenerator {
	
	public SubstringGenerator(String str) {
		super();
		this.str = str;
	}

	private final String str;
	
	
	public List<String> generate(){
		
		List<String> allSubstrings = new ArrayList<>();
		
		for( int index = 0; index < str.length(); index++ ){
			allSubstrings.addAll( generateRight(str, "", index) );
		}
		
		return allSubstrings;
	}
	
	private List<String> generateRight(String base, String prefix, int fromIndex){
		
		String curPrefix = prefix + base.charAt(fromIndex);
		
		List<String> substrings = new ArrayList<String>();
		
		substrings.add( curPrefix );
		
		for( int offset = fromIndex+1; offset < base.length(); offset++ ){
			substrings.addAll( generateRight(base, curPrefix, offset));
		}
		
		return substrings;
	}

}

- m@}{ January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void allsubstrings(string str,int st_index,int end_index, vector<string>& strvector)
{
string st1,st2;
vector<string> tempvector;
vector<string>::iterator it;
if(st_index == end_index)
{
st1.push_back(str[st_index]);
strvector.push_back(st1);
}
else
{
allsubstrings(str,st_index+1,end_index,strvector);
for(it = strvector.begin(); it != strvector.end(); ++it)
{
st2 = *it;
st2 += str[st_index];
tempvector.push_back(st2);
st2.clear();
}
st1.push_back(str[st_index]);
tempvector.push_back(st1);
strvector.insert( strvector.end(), tempvector.begin(), tempvector.end() );

}
}

strvector contains all the substrings of the string str

- sai January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

View the input as a bit vector. Then, it is about enumerating a bit vector of size n.

Idea:

Input: "cab"

1. Recursively call the function each time trimming one character (trim c, then a)
2. When the length of the string reaches 1, return an empty string and one length character. Like ("", "b")
3. For each of the item returned from the recursion, create two items: 1. same item 2. add the trimmed character

Like: ("", "a", "b", "ab")

4. At the end, we will have all the combinations.

Here is the python code:

1 #! /usr/bin/env python
  2 import sys
  3 
  4 def generateCombination(inp):
  5     if len(inp) == 1:
  6         return [[],[inp[0]]]
  7 
  8     myContrib = inp[0]
  9     rest = generateCombination(inp[1:])
 10     result = []
 11     for aCombination in rest:
 12         s = aCombination[:]
 13         t = aCombination[:]
 14         t.append(myContrib)
 15         result.append(s)
 16         result.append(t)
 17 
 18     return result
 19 
 20 if __name__ == '__main__':
 21     inp = map(lambda x : int(x), sys.argv[1].split(" "))
 22     result = generateCombination(inp)
 23     for anItem in result:
 24         print anItem

- sachin January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

On using Python's map:
You don't have to use a lambda there.
inp = map(int, sys.argv[1].split(" ")) would suffice.

- Anonymous February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class Solution2
{
public static void main(String arg[])
{
Vector result=new Vector();
String data="abc";
for(int i=0;i<data.length();i++)
{
for(int j=i;j<=data.length();j++)
{
if(!result.contains(data.substring(i,j)))
result.add(data.substring(i,j));
}
}
for(int i=0;i<result.size();i++)
System.out.print((String)result.elementAt(i) + " ");
}

}

- durai January 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what would be the best possible worst case complexity of this operation?

- Anonymous January 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should be O(2^n) .. since overall there will be 2^n such substrings

- P January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count = 0;

int substring( string prefix, string rest )
{
	if( rest.length() == 0 )
	{
		cout<<prefix<<endl;
		++count;
	}
	else 
	{
		char c = rest[0];
		rest = rest.substr(1);
		substring( prefix , rest );
		
		prefix.push_back(c);
		substring( prefix , rest );
	}
	return count;
}

- koukou January 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
void printSubStrings(char *s,int len){
int i,j;
int end=1<<len;

for(i=1; i<end; i++){
for(j=0; j<len; j++){
if(i & (1<<j)) printf("%c",s[j]);
}
printf("\n");
}
}
}

- Anonymous January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
// Prints substrings of a given string
// note: take care of integer overflow for calculating end
void printSubStrings(char *s,int len){
int i,j;
int end=1<<len;

for(i=1; i<end; i++){
for(j=0; j<len; j++){
if(i & (1<<j)) printf("%c",s[j]);
}
printf("\n");
}
}
}

- Prashant Ranjan January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
    if(stIndex > endIndex)
    {
        if(outlen != 0)
        {
            std::cout<<"\n";
            for(int index = 0; index < outlen; index++)
            {
                std::cout<<output[index]<<"  ";
            }
        }
        return;
    }
    output[outlen] = input[stIndex];
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}

- racseism January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
    if(stIndex > endIndex)
    {
        if(outlen != 0)
        {
            std::cout<<"\n";
            for(int index = 0; index < outlen; index++)
            {
                std::cout<<output[index]<<"  ";
            }
        }
        return;
    }
    output[outlen] = input[stIndex];
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}

- racseism January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
    if(stIndex > endIndex)
    {
        if(outlen != 0)
        {
            std::cout<<"\n";
            for(int index = 0; index < outlen; index++)
            {
                std::cout<<output[index]<<"  ";
            }
        }
        return;
    }
    output[outlen] = input[stIndex];
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}

- racseism January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
    if(stIndex > endIndex)
    {
        if(outlen != 0)
        {
            std::cout<<"\n";
            for(int index = 0; index < outlen; index++)
            {
                std::cout<<output[index]<<"  ";
            }
        }
        return;
    }
    output[outlen] = input[stIndex];
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
    PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}

- racseism January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import qualified Data.List as L
     
     myF :: [a] -> [[a]]
     myF = subsequences

- Anonymous January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.Math;

class Permutations
{
  public static void main (String args[])
  {
    if (args.length != 1)
    {
      System.out.println ("Enter one string");
      return;
    }

    String str = args[0];
    int pow = str.length();

    int max = (int)Math.pow (2, pow);

    for (int i=0; i< max; i++)
    {
      StringBuilder builder = new StringBuilder();
      int mask = 1;
      for (int j=0; j<str.length(); j++)
      {
        if ( (i & mask) != 0)
        {
          builder.append (str.charAt(j));
        }
        mask = mask << 1;
      }

      System.out.println (builder.toString());
    }
  }
}

- someone January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The substring of the given string matchs below numbers
0 0 1 -- a
0 1 0 -- b
0 1 1 -- ab
1 0 0 -- c
1 0 1 -- ac
1 1 0 -- bc
1 1 1 -- abc
/// C++ code below
void print(char * str, int s)
{
int one = 1;
int i = 0, len = strlen(str);
for(i = 0; i < len; i ++)
{
if(s & (one << i)) cout<<str[i];
}
cout<<endl;
}

int generate_substring(char * str)
{
if(NULL == str) return -1;
int s = 1, len = strlen(str);
while(len)
{
s *= 2;
len --;
}
s -= 1;

while(s)
{
print(str, s);
s --;
}


return 0;
}

- zombie January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

?without questioning question itself.
ac is not a substring of "abc"

- wrong answer/questions? February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static String generateSubstrings(String input)
	{
		 String output = "{ ";
	     
	      
	      for(int x = 1; x <= input.length(); x++)
	      {
	    	  for(int y = 0; y+x <= input.length(); y++)
	    	  {
	    		  output += (input.substring(y, y+x) + ", ");

	    	  }
	      }
	      
	      //remove last ', '
	      output = output.substring(0, output.length()-2);
	      output += " }";
	      
	      return output;
	}

- Graham February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static final String[] generateSubsets(String input) {
int length = input.length();
int size = (int) Math.pow(2, length);
BitSet[] sets = new BitSet[size];
String[] output = new String[size];

for (int i=0; i<size; i++) {
BitSet set = new BitSet(size);
StringBuilder builder = new StringBuilder();
if (i>0) {
for (int j=length-1; j>=0; j--) {
if (j==length-1) {
if (i%2!=0) set.set(j, true);
} else {
boolean prev = sets[i-1].get(j);
boolean next = true;
for (int k=j+1; k<length; k++) {
next = next && sets[i-1].get(k);
}
if (next) prev = !prev;
set.set(j, prev);
}
if (set.get(j)) builder.append(input.charAt(j));
}
}
sets[i] = set;
output[i] = builder.toString();
}

return output;
}

- phishman3579 February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static final String[] generateSubsets(String input) {
        int length = input.length();
        int size = (int) Math.pow(2, length);
        BitSet[] sets = new BitSet[size];
        String[] output = new String[size];
        
        for (int i=0; i<size; i++) {
            BitSet set = new BitSet(size);
            StringBuilder builder = new StringBuilder();
            if (i>0) {
                for (int j=length-1; j>=0; j--) {
                    if (j==length-1) {
                        if (i%2!=0) set.set(j, true);
                    } else {
                        boolean prev = sets[i-1].get(j);
                        boolean next = true;
                        for (int k=j+1; k<length; k++) {
                            next = next && sets[i-1].get(k);
                        }
                        if (next) prev = !prev;
                        set.set(j, prev);
                    }
                    if (set.get(j)) builder.append(input.charAt(j));
                }
            }
            sets[i] = set;
            output[i] = builder.toString();
        }

        return output;   
    }

- Justin February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

;; Code
(define (subsets lst)
  (cond
    ((null? lst) (list null))
    (else
     (append
      (map (lambda (x) (cons (car lst) x)) (subsets (cdr lst))) (subsets (cdr lst))))))

;; Test
(map list->string (subsets (string->list "abc")))

- haluk February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

----------------Recursive Solution----------------------
recFindSubSets("", "abc");
public static ArrayList<String> recFindSubSets(String str1, String str2){
ArrayList<String> subSets = new ArrayList<String>();
if(str2.length() == 0){
subSets.add(str1);
return subSets;
}
ArrayList<String> subSets1 = recFindSubSets(str1 + str2.substring(0, 1), str2.substring(1, str2.length()));
ArrayList<String> subSets2 = recFindSubSets(str1, str2.substring(1, str2.length()));
subSets.addAll(subSets1);
subSets.addAll(subSets2);
return subSets;
}

------------Non Recursive Solution-----------------
nonRecFindSubSets("abc");
public static ArrayList<String> nonRecFindSubSets(String str){
ArrayList<String> subSets = new ArrayList<String>();
int len = str.length();
int totalSets = (int) Math.pow(2, len) - 1;

StringBuilder str1 = new StringBuilder();
for(int i=totalSets; i>=0; i--){
str1.delete(0, str1.length());
int bitmask = (int) Math.pow(2, len-1);
for(int j=0;j<len; j++) {
if((i & bitmask) > 0){
str1.append(str.charAt(j));
}
bitmask = bitmask >> 1;
}
subSets.add(str1.toString());
}
return subSets;
}

- swapsmagic February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void GenSubstrings(string input)
{
int len = 0;
Console.Write("{");

//Iterate through all letters of the input string
for (int i = 0; i < input.Length; i++)
{
len = input.Length - i;
//If the current letter not the last letter of the input string
if (i != input.Length - 1) {
//Generate all substring combinations starting with the letter
for (int j = 1; j <= len; j++) {
Console.Write(input.Substring(i, j) + ",");
}
} else {
Console.Write(input.Substring(i, 1));
}
}
Console.Write("}");
}

- Vladimir February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No one for a suffix array ?

- thegeekin February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void listStrings(byte[] x, int num, int sb_index, StringBuffer sb)
{
	if( num >= x.length )
	{
		return;
	}
	sb.append((char)x[num]);
	System.out.println(sb.toString());
	for(int i=num+1;i<x.length;i++)
	{
		listStrings(x,i,sb_index+1,sb);
	}
	sb.setLength(sb_index);
}
public static void main(String[] arg)
{
	byte x[] = "abc".getBytes();
	StringBuffer sb = new StringBuffer();
	for(int i=0;i<x.length;i++)
	{
		listStrings(x,i,0,sb);
	}
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Combination
{
	public static void main(String[] args)
	{
		String input = "ABC";
		StringBuffer sb = new StringBuffer();
		combination(input.toCharArray(), 0, input.length() - 1, sb);
	}

	public static void combination(char[] arr, int a, int b, StringBuffer sb)
	{
		for (int i = a; i <= b; i++)
		{
			sb.append(arr[i]);
			System.out.println(sb);
			combination(arr,i+1, b, sb);
			sb.setLength(sb.length()-1);
		}
	}
}

- Ted May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test
{
	public static void main(String[] args)
	{
		printAll("ABC", 0, new StringBuffer());
//		Outputs
//		---------
//		A
//		AB
//		ABC
//		AC
//		B
//		BC
//		C
	}

	private static void printAll(String str,int start, StringBuffer sb)
	{
		for(int i=start; i< str.length(); i++)
		{
			sb.append(str.charAt(i));
			System.out.println(sb);
			printAll(str, i+1, sb);
			sb.setLength(sb.length()-1);
		}
	}
}

- Ted June 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

pls tell me its mechanism after abc has been printed doesnt the start =3
and the next recursion loop shouldnt get executed
ty

- sheeredmaze January 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>

struct node
{
	char c;
	struct node* next;
	struct node* prev;
};

struct node* addnode(struct node* head,char data)
{
	if(!head)
	{
		head=(struct node*)malloc(sizeof(struct node));
		if(!head)
			return NULL;
		head->c=data;
		head->next=head;
		head->prev=head;
	}
	else
	{
		struct node* tmp=head;
		struct node* tmp1=head;
		struct node* newn;
		
		while(tmp->next!=tmp1) tmp=tmp->next;

		newn=(struct node*)malloc(sizeof(struct node));
		if(!newn)
			return NULL;
		tmp->next=newn;
		newn->c=data;
		newn->next=tmp1;
		newn->prev=tmp;
		tmp1->prev=newn;
	}

	return head;
}

void printnode(struct node* head)
{
	struct node* tmp=head;
	struct node* tmp1=head;


	do
	{
		printf("%c->",tmp->c);
		tmp=tmp->next;
	}while(tmp!=tmp1);


	tmp=head;
	tmp1=head;

	do
	{
		printf("%c->",tmp->c);
		tmp=tmp->prev;
	}while(tmp!=tmp1);
	
	printf("\n");

}


int main()
{
	char* name="abcd";
	struct node* head=NULL;

	while(*name!='\0')
	{
		head=addnode(head,*name);
		name++;
	}

	//printnode(head);

	struct node* t1=head;
	struct node* t2=head;
	struct node* t3=head;

	do
	{
		do
		{
			do
			{
				printf("%c",t2->c);
				t2=t2->next;
			}while(t2!=t3);
			printf(",");
			t2=t1;
			t3=t3->prev;
		}while(t3!=t1->next);

		t3=t1;
		do
		{
			do
			{
				printf("%c",t2->c);
				t2=t2->prev;
			}while(t2!=t3);
			printf(",");
			t2=t1;
			t3=t3->next;
		}while(t3!=t1);

		t1=t1->next;
		t2=t1;
		t3=t1;
		
	}while(t1!=head);

	printf("\n");
	
	return 0;
}

- okaysh July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems to me that a non-recursive solution is better because:
a) easily avoid extra substring calls (which creates extra copies of string)
b) avoid printing or storing of duplicate result. I don't see a good way to avoid duplicate calls when doing it recursively

def allsubstrshelper(s, startindex):
print s[startindex]
for i in range(startindex + 1, len(s)):
print(s[startindex:i+1])

def allsubstrs(s):
for i in range(len(s)):
allsubstrshelper(s, i)

allsubstrs("abcd") prints:
a
ab
abc
abcd
b
bc
bcd
c
cd
d

- ep August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[]="anonymous";
int i,j,k,n=strlen(str);
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
for(k=i;k<=j;k++)
printf("%c",str[k]);
printf("\n");
}
printf("\n");
}
getch();
}

- Anonymous September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Backtracking problem similar to Permutation. In this problem we will print all combinations.

- Andy2000 September 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<string> permutation (string str)
{
    int len = str.length();

vector<bool> used;

used.assign(len, false);

vector<string> result;

string current =””;

addNext (current, used, str, result);   
}

void addNext (string current, vector<bool> used, string candidates, vector<string> & result)
{
    if(current.size > 0)
    result.push_back(current);
    int size = used.size();
    for (int i = 0; i< size; i++)
    {
        if (used[i])
        continue;
        used[i] = true;
        addNext(current+candidates, used, candidates, result);
        used[i] = false;
    }
}

- lixulehigh September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		char[] c = "abcb".toCharArray();
		System.out.println(getAllSubstrings(c, 0, ""));
	}

	private static Set<MyString> getAllSubstrings(char[] c, int i, String prefix) {
		Set<MyString> s = new HashSet<MyString>();
		if (i < c.length) {
			s.add(new MyString(prefix + c[i]));
			s.addAll(getAllSubstrings(c, i + 1, "" + c[i]));
			s.addAll(getAllSubstrings(c, i + 1, prefix + c[i]));
		}
		s.add(new MyString(prefix));
		return s;
	}

	static class MyString {

		private final String s;
		private final String sortedS;

		public MyString(String s) {
			super();
			this.s = s;
			char[] c = s.toCharArray();
			Arrays.sort(c);
			sortedS = new String(c);
		}

		public String getS() {
			return s;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result
					+ ((sortedS == null) ? 0 : sortedS.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			MyString other = (MyString) obj;
			if (sortedS == null) {
				if (other.sortedS != null)
					return false;
			} else if (!sortedS.equals(other.sortedS))
				return false;
			return true;
		}

		@Override
		public String toString() {
			return s;
		}
	}

- A March 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since "ac", is not a substring of "abc", just confirming if you meant all possible subsets of a given set, and not substrings?

- April February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is the implementation in Java.
Iterative:

public static Set<String> getSubStringsIter(String input) {
		Set<String> res = new HashSet<>();
		if (input == null || input.isEmpty()) {
			return res;
		}
		res.add("");
		for (char c : input.toCharArray()) {
			Set<String> resCopy = new HashSet<>();
			for (String string : res) {				
				resCopy.add(string + c);
			}
			res.addAll(resCopy);
		}
		res.remove("");
		return res;
	}

Recursive Approach:

public static Set<String> getSubStringsRecursive(String input) {
		if(input == null) {
			return null;
		} 
		Set<String> res = getSubStringsRecursiveHelper(input);
		res.remove("");
		return res;
	}
	
	public static Set<String> getSubStringsRecursiveHelper(String input) {
		if (input.isEmpty()) {
			return new HashSet<>(Arrays.asList(input));
		}
		Set<String> mergeResult = merge(input.substring(0,1), getSubStringsRecursiveHelper(input.substring(1)));
		return mergeResult;
	}

	private static Set<String> merge(String substring, Set<String> res) {
		Set<String> copy = new HashSet<>();
		for (String string : res) {
			copy.add(substring + string);
		}
		res.addAll(copy);
		return res;
	}

JUnit:

@Test
	public void test_getSubStrings() {
		String input = "abc";
		Set<String> expectedRes = new HashSet<>(Arrays.asList("a","b","c","ab", "ac", "bc", "abc"));
		
		Set<String> subStringsIter = InterviewQuestions.getSubStringsIter(input);
		Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsIter.size());
		Assert.assertEquals(expectedRes, subStringsIter);
		
		Set<String> subStringsRecursiveRes = InterviewQuestions.getSubStringsRecursive(input);
		Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsRecursiveRes.size());
		Assert.assertEquals(expectedRes, subStringsRecursiveRes);
	}

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

int main(){
    int n;
    int q;
    cin >> n >> q;
    string s;
    cin >> s;
    for(int a0 = 0; a0 < q; a0++){
        int left;
        int right;
        cin >> left >> right;
        set<string> insignificant;
            for(int i = left; i <= right; i++){
                string temp;
                for (int j = i; j <= right; ++j){
                     temp += s[j];
                 set< string >::iterator it = insignificant.find(temp);
                 if (it == insignificant.end())
                     insignificant.insert(temp);
                 }
             } 
        cout<<insignificant.size()<<endl;
         for (set<string>::iterator it = insignificant.begin(); it != insignificant.end(); it++)
            cout<<*it<<" ";
    }
    return 0;
}

- kirubstkp March 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive C solution for the same

#include <stdio.h>

char Arr[] = "abcde";
int n = 5; //length of above string

void printforward(char fromPrev[6], int start, int position){
for(int i = start; i<n;i++){
fromPrev[position] = Arr[i];
fromPrev[position+1] = '\0';
printf("%s\n", fromPrev);
printforward(fromPrev, i+1, position+1);
}
}

int main(void) {

for(int i=0; i<n;i++){
char fromPrev[6];
printf("%c\n",Arr[i]);
fromPrev[0] = Arr[i];
printforward(fromPrev,i+1,1);
}

return 0;
}

P.S.: I know Arr and its length should not be declared global.

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

Let’s assume a given string S represented by the letters A1, A2, A3, ... , An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list
Now, the code to do this:

public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) { // error case
return null;
} else if (s.length() == 0) { // base case
permutations.add(“”);
return permutations;
}

char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
permutations.add(insertCharAt(word, first, j));
}
}
return permutations;
}

public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}
This solution takes O(n!) time, since there are n! permutations.

- Ali_BABA January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guess you are returning all the permutations, when that is not what is asked. So, bc <=> cb., and so on for others.

And, I guess there should be total of 2^n strings. not n!

- P January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dont claim CC's work as yours alibaba. This is the same code as given in CC book.

- Anonymous January 24, 2012 | Flag


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