Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
public ArrayList<ArrayList<ArrayList<Integer>>> allCombs(int[] arr)
{
if(arr==null||arr.length==0)
{
return null;
}
ArrayList<ArrayList<ArrayList<Integer>>> ls=new ArrayList<ArrayList<ArrayList<Integer>>>();
ArrayList<ArrayList<Integer>> initial=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> l=new ArrayList<Integer>();
l.add(arr[0]);
initial.add(l);
ls.add(l);
for(int i=1;i<arr.length;i++)
{
ArrayList<ArrayList<ArrayList<Integer>>> updated=new ArrayList<ArrayList<ArrayList<Integer>>>();
Iterator<ArrayList<ArrayList<Integer>>> it=ls.iterator();
ArrayList<Integer> elem=new ArrayList<Integer>();
elem.add(arr[i]);
while(it.hasNext())
{
ArrayList<ArrayList<Integer>> curr=it.next();
ArrayList<ArrayList<Integer>> next=new ArrayList<ArrayList<Integer>>();
next.addAll(curr);
next.add(elem);
updated.add(next);
curr.get(curr.size()-1).add(arr[i]);
updated.add(curr);
it.remove();
}
ls=updated;
}
return ls;
}
//Time Complexity: O(2^N) where N is the input array size. Space: O(2^N)
public static void print(String originalElements, int start, String stringTillNow)
{
if(start == originalElements.length()) {
System.out.println(stringTillNow);
return; }
for(int i = start; i<originalElements.length(); i ++)
{
print(originalElements, i+1, stringTillNow + "(" + originalElements.substring(start,i+1) + ")" );
}
return;
}
O(2^N) time and space:
private LinkedList<StringBuilder> getInOrderCombs(int[] arr, int i) {
// Recursion base case.
if (i == 0) {
LinkedList<StringBuilder> baseResult = new LinkedList<>();
baseResult.add(new StringBuilder("(").append(arr[i]).append(")"));
return baseResult;
}
List<StringBuilder> list = new LinkedList<>();
// Get previous result.
LinkedList<StringBuilder> result = getInOrderCombs(arr, i - 1);
for (StringBuilder sb : result) {
// Copy each result and add current element with parens (use a separate list for that).
list.add(new StringBuilder(sb).append("(").append(arr[i]).append(")"));
// Append the current element (inside the parens) to each result.
sb.insert(sb.length() - 1, arr[i]);
}
result.addAll(list);
// At the end remove the first element because it's not a combination.
if (i == arr.length - 1) {
result.removeFirst();
}
return result;
}
Call example: getInOrderCombs(new int[]{1, 2, 3, 4}, 3);
C++, implementation
void printArrayCombination(vector<int>& arr, vector<int>& com) {
int i, j, k;
for (i = 0, k = 0; i < com.size() - 1; i++) {
cout << "(";
for (j = 0; j < com[i]; j++, k++) {
cout << arr[k];
}
cout << ")";
}
cout << "\n";
}
void solve(vector<int>& arr) {
vector<int> com;
queue<vector<int>> q;
int i, e, c;
com.push_back((int)arr.size());
q.push(com);
while (!q.empty()) {
com = q.front();
q.pop();
e = (int)com.size() - 1;
if (com[e] == 0) {
printArrayCombination(arr, com);
continue;
}
c = com[e];
com.push_back(0);
for (i = 1; i <= c; i++) {
com[e] = i;
com[e + 1] = c - i;
q.push(com);
}
}
}
def PrintCombo(arr, n=0):
if not arr:
return None
if len(arr) == n:
return arr
for i in xrange(n, len(arr)):
print("(" + ''.join(arr[0:n]) + ')' + '(' + ''.join(arr[n:i + 1]) + ')' + '(' + ''.join(arr[i + 1:]) + ')')
return PrintCombo(arr, n=n + 1)
if __name__ == "__main__":
PrintCombo(['1', '2', '3', '4'])
def PrintCombo(arr, n=0):
if not arr:
return None
if len(arr) == n:
return arr
for i in xrange(n, len(arr)):
print("(" + ''.join(arr[0:n]) + ')' + '(' + ''.join(arr[n:i + 1]) + ')' + '(' + ''.join(arr[i + 1:]) + ')')
return PrintCombo(arr, n=n + 1)
if __name__ == "__main__":
PrintCombo(['1', '2', '3', '4'])
void partition(int[] nums, int pos, List<Integer> res) {
if (nums.length == pos) {
int set = -1;
int i = 0;
String str = "";
for (Integer j : res) {
if (j != set) {
if (set != -1)
System.out.print(")");
set = j;
System.out.print("(");
}
System.out.print(nums[i] +"");
System.out.print(str +"");
i++;
}
System.out.print(")");
System.out.println();
}
else {
int s = pos == 0? 1:res.get(pos - 1);
int t = pos == 0?1:s+1;
for (int i = s; i <= t; i++) {
res.add(i);
partition(nums, pos + 1, res);
res.remove(res.size() - 1);
}
}
}
ArrayList<Integer> res = new ArrayList<Integer>();
gp.partition(new int[]{1,2,3,4}, 0, res);
Recursion will be good solution for this.
public class NonOverLappingPairs {
static String remaining(int[] arr, int start, int end){
if(start<end){
StringBuilder sb=new StringBuilder(arr.length-start);
for(;start<end;start++){
sb.append(arr[start]);
}
return sb.toString();
}
return "";
}
static int[] subArray(int[] arr, int i){
if(i < (arr.length - 1) ){
int[] newArr=new int[arr.length-i];
int j=0;
for(;i<arr.length;i++){
newArr[j++]=arr[i];
}
return newArr;
}
return null;
}
static void pairs(String prefix, int[] arr ){
if(arr==null){
return;
}
for(int i=0;i<arr.length-1;i++){
String firstPart = "("+remaining(arr,0,i+1)+")";
System.out.print(prefix+firstPart+"("+remaining(arr,i+1, arr.length)+")");
System.out.println();
pairs(prefix+firstPart,subArray(arr,i+1));
}
}
static void generatePairs(int[] arr){
System.out.println("("+remaining(arr,0, arr.length)+")");
pairs("",new int[]{1,2,3,4});
}
public static void main(String[] args) {
generatePairs(new int[]{1,2,3,4});
}
}
Recursion is the good solution for this.
public class NonOverLappingPairs {
static String remaining(int[] arr, int start, int end){
if(start<end){
StringBuilder sb=new StringBuilder(arr.length-start);
for(;start<end;start++){
sb.append(arr[start]);
}
return sb.toString();
}
return "";
}
static int[] subArray(int[] arr, int i){
if(i < (arr.length - 1) ){
int[] newArr=new int[arr.length-i];
int j=0;
for(;i<arr.length;i++){
newArr[j++]=arr[i];
}
return newArr;
}
return null;
}
static void pairs(String prefix, int[] arr ){
if(arr==null){
return;
}
for(int i=0;i<arr.length-1;i++){
String firstPart = "("+remaining(arr,0,i+1)+")";
System.out.print(prefix+firstPart+"("+remaining(arr,i+1, arr.length)+")");
System.out.println();
pairs(prefix+firstPart,subArray(arr,i+1));
}
}
static void generatePairs(int[] arr){
System.out.println("("+remaining(arr,0, arr.length)+")");
pairs("",new int[]{1,2,3,4});
}
public static void main(String[] args) {
generatePairs(new int[]{1,2,3,4});
}
}
void print_segments(std::vector<int>& v, std::vector<bool>& breaks)
{
std::cout << "(";
for (int i = 0; i < v.size(); i++) {
std::cout << i;
if (breaks[i] == true) {
std::cout << ")(";
}
}
std::cout << ")" << std::endl;
}
/*
* The core of the solution
* Keep a break vector "breaks"
* If breaks[i] is true, a split is needed at v[i]
*/
void print_vec(std::vector<int>& v, std::vector<bool>& breaks, int start_offset)
{
if (start_offset < breaks.size()) {
breaks[start_offset] = false;
print_vec(v, breaks, start_offset + 1);
breaks[start_offset] = true;
print_vec(v, breaks, start_offset + 1);
} else {
print_segments(v, breaks);
}
}
void print_non_overlapping_pairs(std::vector<int>& v)
{
std::vector<bool> breaks(v.size() - 1, false); // breaks used for segmenting
print_vec(v, breaks, 0);
}
void print_segments(std::vector<int>& v, std::vector<bool>& breaks)
{
std::cout << "(";
for (int i = 0; i < v.size(); i++) {
std::cout << i;
if (breaks[i] == true) {
std::cout << ")(";
}
}
std::cout << ")" << std::endl;
}
/*
* The core of the solution
* Keep a break vector "breaks"
* If breaks[i] is true, a split is needed at v[i]
*/
void print_vec(std::vector<int>& v, std::vector<bool>& breaks, int start_offset)
{
if (start_offset < breaks.size()) {
breaks[start_offset] = false;
print_vec(v, breaks, start_offset + 1);
breaks[start_offset] = true;
print_vec(v, breaks, start_offset + 1);
} else {
print_segments(v, breaks);
}
}
void print_non_overlapping_pairs(std::vector<int>& v)
{
std::vector<bool> breaks(v.size() - 1, false); // breaks used for segmenting
print_vec(v, breaks, 0);
}
#include <iostream>
#include <vector>
#include <set>
#include <string>
typedef unsigned int uint;
std::vector<uint> E = { 1,2,3,4 };
std::set<std::string> S;
inline bool test(uint A, uint pos) {
return (A & (1u << pos));
}
void construct(uint A, uint N) {
bool conjunctive_1 = false;
bool conjunctive_0 = false;
std::string str;
for(uint i = 0; i < N; i++) {
if(test(A, i)) {
if(conjunctive_0) {
str += ')';
conjunctive_0 = false;
}
if(!conjunctive_1) {
str += '(';
str += E[i] + '0';
conjunctive_1 = true;
} else {
str += E[i] + '0';
}
} else {
if(conjunctive_1) {
str += ')';
conjunctive_1 = false;
}
if(!conjunctive_0) {
str += '(';
str += E[i] + '0';
conjunctive_0 = true;
} else {
str += E[i] + '0';
}
}
}
str += ')';
if(!S.count(str)) {
S.emplace(str);
}
}
void brackets(uint N) {
for(uint i = 0; i < (1u << N)-1; i++) {
construct(i, N);
}
for(auto& a : S)
std::cout << a << std::endl;
}
int main() {
brackets(E.size());
return 0;
}
In Perl
#!/usr/bin/perl -W
use strict;
use boolean;
my @values = (1,2,3,4);
# Kick off recursion, which results a list. Stick a line break on the end of
# each array element.
print STDOUT map {$_."\n"} split_list(@values, true);
# Base case
print STDOUT join('', map {'('.$_.')'} @values)."\n";
sub split_list
{
my @segment = @_; #array of all params
my $recurse = pop @segment;
my @results = ('('.join('', @segment).')');
return @results if ! $recurse;
for (my $i = 0 ; $i < (scalar @segment) - 1; $i++)
{
if (scalar @segment % 2) # Without this stage, output lines 3 and 4 are swapped
{
my @left = split_list(@segment[0 .. $#segment - 1 - $i], false); # No recusion on even length
my $right = '('.join('', @segment[$#segment - $i .. $#segment]).')';
push(@results, map {$_.$right} @left);
}
else
{
my $left = '('.join('', @segment[0 .. $i]).')';
my @right = split_list(@segment[$i + 1 .. $#segment], true);
push(@results, map {$left.$_} @right);
}
}
return @results;
}
private static ArrayList<ArrayList<int[]>> pattern(int arr[]){
ArrayList<ArrayList<int[]>> result = new ArrayList();
if(arr.length==1){
ArrayList<int[]> subList = new ArrayList<>();
subList.add(arr);
result.add(subList);
}
else{
int[] prefix,suffix;
for(int i=0;i<arr.length;i++){
prefix = new int[i+1];
suffix = new int[arr.length-i-1];
for(int j=0;j<=i;j++){
prefix[j] = arr[j];
}
for(int j=i+1,k=0;j<arr.length;j++,k++){
suffix[k] = arr[j];
}
ArrayList<ArrayList<int[]>> temp = pattern(suffix);
for(int j=0;j<temp.size();j++){
temp.get(j).add(0,prefix);
result.add(temp.get(j));
}
if(temp.size()==0){
ArrayList<int[]> subList = new ArrayList<>();
subList.add(prefix);
result.add(subList);
}
}
}
return result;
}
#include "stdafx.h"
#include <vector>
void printPair(std::vector<int> & stops, int number){
int k = 0;
for (auto iter = stops.begin(); iter < stops.end(); ++iter){
if (k < *iter){
printf("(");
for (; k < *iter; ++k){
printf("%d", k+1);
}
printf(")");
}
}
printf("(");
for (; k < number; ++k){
printf("%d", k+1);
}
printf(")\n");
}
void calculateStops(std::vector<int> & stops, int number, int start) {
if (start == number){
return;
}
if (start == 0){
printPair(stops, number);
calculateStops(stops, number, start + 1);
return;
}
for (int i = start; i < number; ++i){
stops.push_back(i);
printPair(stops, number);
calculateStops(stops, number, i + 1);
stops.pop_back();
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int number;
scanf_s("%d", &number);
std::vector<int> stops;
calculateStops(stops, number, 0);
getchar();
getchar();
return 0;
}
// orderedpair.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
void printPair(std::vector<int> & stops, int number){
int k = 0;
for (auto iter = stops.begin(); iter < stops.end(); ++iter){
if (k < *iter){
printf("(");
for (; k < *iter; ++k){
printf("%d", k+1);
}
printf(")");
}
}
printf("(");
for (; k < number; ++k){
printf("%d", k+1);
}
printf(")\n");
}
void calculateStops(std::vector<int> & stops, int number, int start) {
if (start == number){
return;
}
if (start == 0){
printPair(stops, number);
calculateStops(stops, number, start + 1);
return;
}
for (int i = start; i < number; ++i){
stops.push_back(i);
printPair(stops, number);
calculateStops(stops, number, i + 1);
stops.pop_back();
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int number;
scanf_s("%d", &number);
std::vector<int> stops;
calculateStops(stops, number, 0);
getchar();
getchar();
return 0;
}
My solution is written by Java. My idea is translate this problem to new problem: presenting all cases how to separate an integer number to sum of all smaller integers.
Ex: input 4, output: 4; 1+3; 1+1+2; 1+2+1; 2+2; 2+1+1; 3+1; 1+1+1+1
After that we can easy come back our problem.
INPUT: {1,2,3,4}
OUTPUT :
(1,2,3,4)
(1,2,3)(4)
(1,2)(3,4)
(1,2)(3)(4)
(1)(2,3,4)
(1)(2,3)(4)
(1)(2)(3,4)
(1)(2)(3)(4)
public class NonOverLappingPair {
public static void main(String[] args) {
int[] input = new int[] { 1, 2, 3, 4 };
print(input);
}
private static void print(int[] input) {
int n = input.length;
int[] arr = new int[n + 1];
arr[0] = 0;
printPair(input, arr, n, 1, n);
}
private static void printPair(int[] input, int[] arr, int length, int n, int remain) {
if (n > length + 1) {
return;
}
if (remain == 0) {
int sum = 0;
StringBuilder builder = new StringBuilder();
int run = 0;
for (int i = 1; i <= length; i++) {
if (sum == length) {
arr[i] = 0;
} else
sum = sum + arr[i];
// builder string
int temp = arr[i];
if (temp > 0) {
builder.append("(");
}
while (temp > 0) {
builder.append(input[run++]);
if (temp > 1)
builder.append(",");
temp--;
}
if (arr[i] > 0) {
builder.append(")");
}
}
System.out.println(builder.toString());
return;
}
for (int i = remain; i > 0; i--) {
arr[n] = i;
printPair(input, arr, length, n + 1, remain - i);
}
}
}
My idea uses recursion, and sending the smaller string to subsequent recursion, while chunking strings of length 1,2,3 .. till maximum length for that particular recursive function on stack:
public static void printOrdered(String test){
printUtil(test, new StringBuilder());
}
public static void printUtil(String current,StringBuilder temp){
if(current == null || current.length()==0){
System.out.println(temp.toString());
return;
}
int currentLength = current.length();
int i=0;
for(int len=1;len<=currentLength;len++){
// for(int i=0;i<currentLength-len+1;i++){
int j=i+len;
temp.append("(");
String pair = current.substring(i,j);
temp.append(pair).append(")");
printUtil(current.substring(j), temp);
temp.setLength(temp.length()-pair.length()-2);
// }
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {1,2,3,4};
String test = "1234";
printOrdered(test);
}
public static void printOrdered(String test){
printUtil(test, new StringBuilder());
}
public static void printUtil(String current,StringBuilder temp){
if(current == null || current.length()==0){
System.out.println(temp.toString());
return;
}
int currentLength = current.length();
int i=0;
for(int len=1;len<=currentLength;len++){
// for(int i=0;i<currentLength-len+1;i++){
int j=i+len;
temp.append("(");
String pair = current.substring(i,j);
temp.append(pair).append(")");
printUtil(current.substring(j), temp);
temp.setLength(temp.length()-pair.length()-2);
// }
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = {1,2,3,4};
String test = "1234";
printOrdered(test);
}
public static void printNonOverlapping (String number) {
printNonOverlapping (number, "");
}
public static void printNonOverlapping (String number, String prefix) {
System.out.println (prefix + "(" + number + ")");
for (int i=1; i<number.length(); i++) {
String newPrefix = prefix + "(" + number.substring(0,i) + ")";
printNonOverlapping (number.substring (i, number.length()), newPrefix);
}
Invoke from main() as follows:
printNonOverlapping ("1234");
public List<List<List<Integer>>> nonOverLapCombination(int[] arr) {
List<List<List<Integer>>> result = new ArrayList<>();
List<List<Integer>> current = new ArrayList<>();
backtrack(arr, 0, current, result);
return result;
}
private void backtrack(int[] arr, int start, List<List<Integer>> current, List<List<List<Integer>>> result) {
if (start == arr.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < arr.length; i++) {
List<Integer> c = new ArrayList<>();
for (int j = start; j <= i; j++) {
c.add(arr[j]);
}
current.add(c);
backtrack(arr, i + 1, current, result);
current.remove(current.size() - 1);
}
}
The above solution doesn't give the desired output. check the one below.
void getNonOverLappingUtil(string prevPrefix,string s, map<string,bool> &stringMap){
long strLen = s.length();
for(int indx=1; indx<=strLen; indx++){
string commonPrefix = s.substr(0,indx);
commonPrefix = "("+commonPrefix+")";
string leftOutSuffix = s.substr(indx,strLen);
getNonOverLappingUtil(prevPrefix + commonPrefix,leftOutSuffix,stringMap);
if(leftOutSuffix.length() > 0){
leftOutSuffix = "("+leftOutSuffix+")";
}
if (stringMap.find(prevPrefix + commonPrefix + leftOutSuffix) == stringMap.end()) {
stringMap[prevPrefix + commonPrefix + leftOutSuffix] = true;
}
}
}
void printNonOverLapping(string s){
map<string,bool> stringMap;
getNonOverLappingUtil("",s,stringMap);
map<string,bool>::iterator it;
for(it = stringMap.begin();it!=stringMap.end();it++){
cout<<(*it).first<<endl;
}
}
If you want to avoid recursion, you can loop through the 2 to the power of (array.length -1) cases. The following code is written in java.
public <E> void findCombination(E[] array) {
int gapNumber = array.length - 1;
boolean[] gaps = new boolean[gapNumber];
for (int i = 0; i < Math.pow(2, gapNumber); i++) {
for (int gapIndex = 0; gapIndex < gaps.length; gapIndex++) {
//reset value
gaps[gapIndex] = false;
}
for (int gapIndex = 0; gapIndex < gapNumber; gapIndex++) {
if (getBit(i, gapIndex) > 0) {
gaps[gapIndex] = true;
}
}
printCombination(array, gaps);
}
}
private <E> void printCombination(E[] array, boolean[] gaps) {
System.out.print("(");
for (int i = 0; i < array.length; i++) {
if (i < gaps.length && gaps[i] == true) {
System.out.print(array[i]);
System.out.print(")(");
} else {
System.out.print(array[i]);
}
}
System.out.print(")\n");
}
public int getBit(int n, int k) {
return (n >> k) & 1;
}
@Test
public void testPrintCombination() {
Integer[] data = {1, 2, 3, 4};
findCombination(data);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] nums = {1,2,3,4,5,6,7,8,9,10};
ArrayList<int[]> res = new ArrayList<int[]>();
//The way to think about this is the degrees of freedom
//Here you can imagine the inner parentheses as the degrees of freedom
//We might have "0", "1", ... , "n-1" number of parentheses.
//So we loop over them. As a matter of fact there exist summation(nCk) for k = 0 --> n possible outcomes (= 2^(n-1) )
for (int count = 0; count < nums.length; count++) {
int [] start = new int [count+2];
//Count = number of parentheses, start = location of the parantheses, nums = list of numbers given by user
//res = output, 0 goes for the minimum possible location and nums.length-2 the maximum possible location
res = printOrder(nums, res, start, 1, count, 0, nums.length-2);
}
}
public static ArrayList<int[]> printOrder (int [] orig, ArrayList<int[]> locs, int [] start, int pos, int count, int min, int max) {
//base case only printing out in a nice way using parentheses
if (count == 0) {
start[0] = -1;
start[start.length-1] = orig.length-1;
locs.add(start); //Here is the important thing if you want to keep track and memory
//Printing the substring could be done differently (depends on the data type)
for (int j = 1; j < start.length; j++) {
System.out.print("(");
for (int r = start[j-1]+1; r <= start[j]; r++) {
System.out.print(orig[r]);
}
System.out.print(")");
}
System.out.println("");
return locs;
}
//Recursion step
else {
for (int k = min; k <= max; k++) {
start[pos] = k;
locs = printOrder(orig, locs, start, pos+1, count-1, start[pos]+1, max);
}
}
return locs;
}
Simplified version of the code for strings
public static void main(String[] args) {
String nums = "1234";
for (int count = 0; count < nums.length(); count++) { //loop over th degrees of freedom (inner parantheses)
int [] start = new int [count+2];
start[0] = -1; //this is loc the outer parentheses always fixed (...
start[start.length-1] = nums.length()-1; //this is the loc outer parentheses always fixed ...)
printOrder(nums, start, 1, count, 0, nums.length()-2); //count = number of inner parantheses
}
}
public static void printOrder (String orig, int [] start, int pos, int count, int min, int max) {
if (count == 0) { //base case (print)
for (int j = 1; j < start.length; j++) { //insert the parentheses at the right location
System.out.print("(" + orig.substring(start[j-1]+1,start[j]+1) + ")");
}
System.out.println("");
}
else { //Recursion step for the current inner parentheses (goes between position min to max)
for (int k = min; k <= max-count+1; k++) {
start[pos] = k; //update the location of the parentheses
printOrder(orig, start, pos+1, count-1, start[pos]+1, max); //move to the next parentheses
}
}
}
public static void main(String[] args) {
String nums = "1234";
for (int count = 0; count < nums.length(); count++) { //loop over th degrees of freedom (inner parantheses)
int [] start = new int [count+2];
start[0] = -1; //this is loc the outer parentheses always fixed (...
start[start.length-1] = nums.length()-1; //this is the loc outer parentheses always fixed ...)
printOrder(nums, start, 1, count, 0, nums.length()-2); //count = number of inner parantheses
}
}
public static void printOrder (String orig, int [] start, int pos, int count, int min, int max) {
if (count == 0) { //base case (print)
for (int j = 1; j < start.length; j++) { //insert the parentheses at the right location
System.out.print("(" + orig.substring(start[j-1]+1,start[j]+1) + ")");
}
System.out.println("");
}
else { //Recursion step for the current inner parentheses (goes between position min to max)
for (int k = min; k <= max-count+1; k++) {
start[pos] = k; //update the location of the parentheses
printOrder(orig, start, pos+1, count-1, start[pos]+1, max); //move to the next parentheses
}
}
}
Here is a recursive solution.
void print_nonoverlap(int a[], unsigned int n) {
if (n == 0)
return;
unsigned int *b = (unsigned int *) calloc(n, sizeof(unsigned int));
if (b == NULL) {
printf("Failed to allocate memory.");
return;
}
print_no_intern(a, n, b, 0);
free(b);
}
void print_no_intern(int a[], unsigned int n, unsigned int b[], unsigned int m) {
unsigned int i;
if (n == 0) {
unsigned int start = 0, j;
for (i = 0; i < m; i++) {
printf("(");
for (j = 0; j < b[i]; j ++)
printf("%d", a[start ++]);
printf(")");
}
printf("\n");
}
for (i = 1; i <= n; i ++) {
b[m] = i;
print_no_intern(a + i, n - i, b, m + 1);
}
}
Implemented in C++.
Python version, as well as my solution comment:
https://github.com/jimmythefung/archive/tree/master/EPI_Problems/overlapPairs
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
string AtoS(vector<string> A){
string s;
for(string c:A){
s=s+c;
}
return s;
}
deque<deque<string>> overlap(vector<string> A, unordered_map<string, deque<deque<string>>> &cache){
deque<string> q;
deque<deque<string>> Qin, Qout;
vector<string> v(A.begin()+1, A.end());
if(A.size()==1){
q.push_back(A[0]);
Qout.push_back(q);
return Qout;
}
else if (cache.count(AtoS(A))!=0){
return cache[AtoS(A)];
}
Qin = overlap(v, cache);
q.push_front(AtoS(A));
Qout.push_front(q);
for(auto it=Qin.begin(); it!=Qin.end(); it++){
q = *it;
q.push_front(A[0]);
Qout.push_front(q);
}
cache[AtoS(A)] = Qout;
return Qout;
}
deque<deque<string>> helper(vector<string> A){
string firstLetters;
deque<deque<string>> Qin, Qout;
unordered_map<string, deque<deque<string>>> cache;
int i=0;
while(i<A.size()-1){ // split A into L, R: A=[abcd] vL=[a] vR=[bcd], each loop move 1 letter to vL from vR
vector<string> vL(A.begin(), A.begin()+1+i);
vector<string> vR(A.begin()+1+i, A.end());
firstLetters = AtoS(vL);
Qin = overlap(vR, cache); //firstLetters=(a), Qin=[ (bcd), (b,cd), (b,c,d) ] and so on
for(auto q=Qin.begin(); q!=Qin.end(); q++){
(*q).push_front(firstLetters); //(a)(bcd), (a)(b,cd), (a)(b,c,d)
Qout.push_back(*q);
}
i++;
}
return Qout;
}
int main(){
vector<string> A = {"1", "2", "3", "4"};
deque<deque<string>> Q = helper(A);
for(auto q=Q.begin(); q!=Q.end(); q++){
for(auto e:(*q)){
cout << "(" << e << ")";
}
cout << endl;
}
return 0;
}
public static void main(String[] args){
String input = "ABCD";
Set<String> patterns = getPatterns(input.length()-1);
for (String pattern : patterns){
System.out.print(input.charAt(0));
char last = '0';
for (int i=1; i< input.length(); i++){
if (pattern.charAt(i-1) == last){
System.out.print(input.charAt(i));
}else{
System.out.print(" ");
System.out.print(input.charAt(i));
}
}
System.out.println();
}
}
private static Set<String> getPatterns(int length){
String[] patterns = {"0", "1"};
Set<String> output = new TreeSet<>();
if (length <= 1){
for (String pattern : patterns){
output.add(pattern);
}
}else{
for (String s :getPatterns(length -1) ){
for (String pattern : patterns)
output.add(pattern + s);
}
}
return output;
}
public class Pairy {
public static void main(String... args) {
int[] a = {1,2,3,4};
find(a, "(", 0);
}
static void find(int[] a, String s, int i) {
if (i == a.length) {
System.out.println(s + ")");
return;
}
find(a, s + a[i], i+1);
if (i + 1 < a.length)
find(a, s + a[i] + ")(", i+1);
}
}
public class Pairy {
public static void main(String... args) {
int[] a = {1,2,3,4};
find(a, "(", 0);
}
static void find(int[] a, String s, int i) {
if (i == a.length) {
System.out.println(s + ")");
return;
}
find(a, s + a[i], i+1);
if (i + 1 < a.length)
find(a, s + a[i] + ")(", i+1);
}
}
void printPermutation(int per, vector<int> & vec) {
cout << "(";
cout << vec[0];
for (uint32_t i = 1; i < vec.size(); i++) {
if (per & (1 << (i-1)))
cout << ")(";
cout << vec[i];
}
cout << ")\n";
}
uint32_t _tmain()
{
vector<int> vec = { 1,2,3,4 };
for (uint32_t i = 0; i < (1 << (vec.size() - 1)); i++)
printPermutation(i, vec);
}
void printPermutation(int per, vector<int> & vec) {
cout << "(";
cout << vec[0];
for (uint32_t i = 1; i < vec.size(); i++) {
if (per & (1 << (i-1)))
cout << ")(";
cout << vec[i];
}
cout << ")\n";
}
uint32_t _tmain()
{
vector<int> vec = { 1,2,3,4 };
for (uint32_t i = 0; i < (1 << (vec.size() - 1)); i++)
printPermutation(i, vec);
}
Here's my recursive solution using Python.
class Solution(object):
def overlapPairs(self, A):
def pairsHelp(A, start):
if start == len(A)-1:
return ['(' + str(A[start]) + ')']
strArr = pairsHelp(A, start + 1)
ret = []
for s in strArr:
curr = str(A[start])
ret.append('(' + curr +')' + s) # outside
ret.append('(' + curr + s[1:]) # inside
return ret
return pairsHelp(A, 0)
Sample input:
[1,2,3,4,5]
output:
['(1)(2)(3)(4)(5)', '(12)(3)(4)(5)', '(1)(23)(4)(5)', '(123)(4)(5)', '(1)(2)(34)(5)', '(12)(34)(5)', '(1)(234)(5)', '(1234)(5)', '(1)(2)(3)(45)', '(12)(3)(45)', '(1)(23)(45)', '(123)(45)', '(1)(2)(345)', '(12)(345)', '(1)(2345)', '(12345)']
Here's my recursive solution using Python.
class Solution(object):
def overlapPairs(self, A):
def pairsHelp(A, start):
if start == len(A)-1:
return ['(' + str(A[start]) + ')']
strArr = pairsHelp(A, start + 1)
ret = []
for s in strArr:
curr = str(A[start])
ret.append('(' + curr +')' + s) # outside
ret.append('(' + curr + s[1:]) # inside
return ret
return pairsHelp(A, 0)
Sample input:
[1,2,3,4,5]
output:
['(1)(2)(3)(4)(5)', '(12)(3)(4)(5)', '(1)(23)(4)(5)', '(123)(4)(5)', '(1)(2)(34)(5)', '(12)(34)(5)', '(1)(234)(5)', '(1234)(5)', '(1)(2)(3)(45)', '(12)(3)(45)', '(1)(23)(45)', '(123)(45)', '(1)(2)(345)', '(12)(345)', '(1)(2345)', '(12345)']
public static void printNonOverlapping (String number) { printNonOverlapping (number, ""); } public static void printNonOverlapping (String number, String prefix) { System.out.println (prefix + "(" + number + ")"); for (int i=1; i<number.length(); i++) { String newPrefix = prefix + "(" + number.substring(0,i) + ")"; printNonOverlapping (number.substring (i, number.length()), newPrefix); } }Invoke from main() as :
- raknair07 June 12, 2016printNonOverlapping ("1234");