Flipkart Interview Question SDE1s
Country: India
Interview Type: Phone Interview
A blind DFS search should be relatively fast given the amount of content. I would expect a maximum computation of O(2^n) (2 because you must add or subtract each value). This could potentially be paired down by precomputing the maximum and minimum values that could be had at each position (an optimization but not necessarily one that would drop the time to something less than O(2^n). so you could execute early termination as appropriate.
public static void printSums(int target, int[] vals){
class Worker{
String[] signs;
int sum = 0;
int target;
int[] vals;
int[] min;
int[] max;
public Worker(int target, int[] vals){
this.target = target;
this.signs = new String(this.target.length);
//compute the short circuits
this.computeMinMax();
}
private void computeMinMax(){
this.min = new int[this.vals.length];
this.max = new int[this.vals.length];
int val = Math.abs(this.vals[i]);
this.min[this.vals.length-1] = -val;
this.max[this.vals.lenth-1] = val;
for(int i = this.vals.length-2; i >= 0; i--){
int val = Math.abs(this.vals[i]);
this.min[i] = this.min[i+1] - val;
this.max[i] = this.max[i+1] + val;
}
}
private void work(int index){
if(index == vals.length && this.sum == this.target){
this.printSolution();
}
else{
//if it's impossible to get the remaining value from this, don't attempt
int remaining = this.target - this.sum;
if(remaining < this.min[index] || remaining > this.max[index]){
return;
}
this.sum += this.vals[index];
this.signs[index] = "+";
this.work(index++);
this.sum -= (this.vals[index] << 1);
this.signs[index] = " - ";
this.work(index++);
this.sum += this.vals[index];
}
}
private void printSolution(){
StringBuilder line = new StringBuilder();
for(int i = 0; i < this.vals.length; i++){
line.append(this.signs[i]);
line.append(Integer.toString(this.vals[i]));
}
java.lang.System.out.println(line.toString());
}
}
Worker worker = new Worker(target, vals);
worker.work();
}
Cleaned it up some (it will run now):
public static void printSums(int target, int[] vals){
class Worker{
String[] signs;
int sum = 0;
int target;
int[] vals;
int[] min;
int[] max;
public Worker(int target, int[] vals){
this.target = target;
this.vals = vals;
this.signs = new String[this.vals.length];
//compute the short circuits
this.computeMinMax();
}
private void computeMinMax(){
this.min = new int[this.vals.length];
this.max = new int[this.vals.length];
int val = Math.abs(this.vals[this.vals.length-1]);
this.min[this.vals.length-1] = -val;
this.max[this.vals.length-1] = val;
for(int i = this.vals.length-2; i >= 0; i--){
val = Math.abs(this.vals[i]);
this.min[i] = this.min[i+1] - val;
this.max[i] = this.max[i+1] + val;
}
}
private void work(int index){
if(index == this.vals.length){
if(this.sum == this.target){
this.printSolution();
}
}
else{
//if it's impossible to get the remaining value from this, don't attempt
int remaining = this.target - this.sum;
if(remaining < this.min[index] || remaining > this.max[index]){
return;
}
this.sum += this.vals[index];
this.signs[index] = " + ";
this.work(index+1);
this.sum -= (this.vals[index] << 1);
this.signs[index] = " - ";
this.work(index+1);
this.sum += this.vals[index];
}
}
private void printSolution(){
StringBuilder line = new StringBuilder();
for(int i = 0; i < this.vals.length; i++){
line.append(this.signs[i]);
line.append(Integer.toString(this.vals[i]));
}
java.lang.System.out.println(line.toString());
}
}
Worker worker = new Worker(target, vals);
worker.work(0);
}
Working recursive example:
public static void printSumExp(int[] nums,int target){
if(nums.length == 0) return;
pseRecurse(nums,target-nums[0],String.valueOf(nums[0]),1);
}
public static void pseRecurse(int[] nums,int target,String s, int idx){
if(idx == nums.length){
if(target == 0){
System.out.println(s);
}
return;
}
pseRecurse(nums,target-nums[idx],s+" + "+nums[idx],idx+1);
pseRecurse(nums,target+nums[idx],s+" - "+nums[idx],idx+1);
}
TEST:
printSumExp(new int[]{1,9,1,2,1,2,3,6},9);
OUTPUT:
1 + 9 + 1 + 2 + 1 - 2 + 3 - 6
1 + 9 + 1 - 2 + 1 + 2 + 3 - 6
1 + 9 + 1 - 2 - 1 - 2 - 3 + 6
1 + 9 - 1 + 2 - 1 + 2 + 3 - 6
1 + 9 - 1 - 2 + 1 - 2 - 3 + 6
TEST (per example in question):
printSumExp(new int[]{1,9,1,2},9);
OUTPUT:
1 + 9 + 1 - 2
char [] opt = {'+', '-'} ;
public List<List<String>> GenerateSeq (int target , int [] array){
List<List<String>> rst = new ArrayList<List<String>>();
if (array == null || array.length == 0 || array.length == 1) {
return rst ;
}
List<String> curr = new ArrayList<> ();
curr.add(String.valueOf(array[0])) ;
generate (target, array[0], array, curr, rst, 1);
return rst ;
}
private void generate(int target , int sum , int [] array, List<String> curr, List<List<String>> rst , int index){
if (index >= array.length) {
return ;
}
if (index == array.length - 1) {
for (char c : opt) {
curr.add(String.valueOf(c)) ;
int val = cal (sum, array[index] , c) ;
if (val == target) {
curr.add(String.valueOf(array[index])) ;
rst.add(new ArrayList<String> (curr)) ;
curr.remove(curr.size() - 1) ;
}
curr.remove(curr.size() - 1) ;
}
return ;
}
for (char c : opt) {
curr.add(String.valueOf(c)) ;
curr.add(String.valueOf(array[index])) ;
int val = cal (sum, array[index] , c) ;
generate (target , val, array, curr, rst ,index + 1);
curr.remove(curr.size() - 1) ;
curr.remove(curr.size() - 1) ;
}
}
private int cal (int a , int b , char opt){
if (opt == '+') {
return a + b ;
} else {
return a - b ;
}
}
make a binary tree where left child edge is (-) and right child edge is (+). so say for 1 ,9, 1, 2 we would have binary tree something like:
1
(-) / \(+)
9 9
(-)/ \(+) (-)/ \(+)
1 1 1 1
and so on.
Now at the leaf node, we have final number (i.e. if we start from root and apply operator on edge to each internal node). Search in leaf node for the result required (R) and print the path as output.
Can you explain how did you get this tree ?It's not clear what would be the root and node value .Only confirms is that we have to use - , + in left ,right respectively .
@xyz,
There are two recursive examples in these answers that implement this go left(-), go right(+), tree approach. Mine a few above and nasim's right below. Likewise, several of the iterative approaches do the same. It's naturally a tree as the root node is array element 0 and there are two paths to each of the subsequent elements.
This will print :
+1+9+1-2
-1+9-1+2
public class arithPrint {
private static void findArith(int[] nums, int index, int target , String s){
if(index == nums.length && target == 0)
System.out.println(s);
else if(index<nums.length)
{
findArith(nums ,index+1, target-nums[index] , s+"+"+nums[index]);
findArith(nums ,index+1, target+nums[index] , s+"-"+nums[index]);
}
}
public static void main(String[] args){
int[] nums = {1,9,1,2};
int target = 9;
findArith(nums ,0 , target , "");
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class BackTrack {
private List<Integer> list ;
private List<Integer> tmp_list;
private int target_no =0;
private List<String> ResultOut;
public BackTrack(List<Integer> tmp_l , int k){
tmp_list = new ArrayList<Integer>(tmp_l);
target_no = k;
}
public void startOP(){
//System.out.println("In startop");
int i =0;
int index=0;
int curr_index=0;
ListIterator<Integer> it = tmp_list.listIterator();
list = new ArrayList<Integer>();
while(it.hasNext()){
i = it.next();
curr_index=it.nextIndex();
//System.out.println("cur index and value :" + curr_index + " " + i);
if(list.isEmpty()){
list.add(0, (Integer)i);
//index = index + 2^curr_index;
}else {
int l_size = list.size();
//System.out.println("list size and index :" + l_size + " " + index);
for(int l = index ; l < l_size; l++){
int f_val = list.get(l) + i;
int s_val = list.get(l) - i;
list.add(f_val);
list.add(s_val);
//System.out.println(list);
if(curr_index == tmp_list.size()){
boolean f_flag = resultCheck(f_val);
boolean s_flag = resultCheck(s_val);
if(f_flag)
printResult(true,list.size()-2,curr_index);
if(s_flag)
printResult(false,list.size()-1,curr_index);
}
}
index = index + (int)Math.pow(2, curr_index -2);
}
}
}
private void printResult(boolean b,int idx,int cur_ind) {
// TODO Auto-generated method stub
//System.out.println("In print Result");
List<String> result = new ArrayList<String>();
//result.add(tmp_list.get(cur_ind-1).toString());
result.add(list.get(idx).toString());
if(b)
result.add("+");
else
result.add("-");
int root_ind = idx;
root_ind = findParent(root_ind);
while(root_ind >= 0){
if(root_ind %2 != 0){
result.add(list.get(root_ind).toString());
result.add("+");
}
else{
result.add(list.get(root_ind).toString());
if(root_ind != 0)
result.add("-");
}
root_ind = findParent(root_ind);
}
correctOrder(result);
}
private void correctOrder(List<String> result) {
//System.out.println("In correctOrder");
System.out.println("Output : " + result);
ListIterator<String> lst = result.listIterator(result.size());
List<String> out_Result = new ArrayList<String>();
while(lst.hasPrevious()){
out_Result.add(lst.previous());
}
ResultOut = new ArrayList<String>();
ResultOut.add(out_Result.get(0).toString());
for(int i = 0 ; i < out_Result.size()-2; i=i+2){
int f_ele = Integer.parseInt(out_Result.get(i));
int s_ele = Integer.parseInt(out_Result.get(i+2));
String op = out_Result.get(i+1);
if(op.equals("+")){
ResultOut.add("+");
Integer res = s_ele - f_ele;
ResultOut.add(res.toString());
}
else {
ResultOut.add("-");
Integer res = f_ele - s_ele;
ResultOut.add(res.toString());
}
}
System.out.println("Final Result is : " + ResultOut);
}
private int findParent(int idx) {
// TODO Auto-generated method stub
//System.out.println("In find parent");
if(idx%2 !=0)
return (idx-1)/2;
else
return (idx-2)/2;
}
private boolean resultCheck(int val) {
//System.out.println("In result check");
if (val == target_no)
return true;
else
return false;
}
public static void main(String[] args) {
List<Integer> ll = new ArrayList<Integer>();
ll.add(8);
ll.add(7);
ll.add(3);
ll.add(4);
ll.add(5);
BackTrack b1 = new BackTrack(ll, 5);
b1.startOP();
}
}
- Navdeep Gupta May 20, 2015import java.util.ArrayList; import java.util.List; import java.util.ListIterator; public class BackTrack { private List<Integer> list ; private List<Integer> tmp_list; private int target_no =0; private List<String> ResultOut; public BackTrack(List<Integer> tmp_l , int k){ tmp_list = new ArrayList<Integer>(tmp_l); target_no = k; } public void startOP(){ //System.out.println("In startop"); int i =0; int index=0; int curr_index=0; ListIterator<Integer> it = tmp_list.listIterator(); list = new ArrayList<Integer>(); while(it.hasNext()){ i = it.next(); curr_index=it.nextIndex(); //System.out.println("cur index and value :" + curr_index + " " + i); if(list.isEmpty()){ list.add(0, (Integer)i); //index = index + 2^curr_index; }else { int l_size = list.size(); //System.out.println("list size and index :" + l_size + " " + index); for(int l = index ; l < l_size; l++){ int f_val = list.get(l) + i; int s_val = list.get(l) - i; list.add(f_val); list.add(s_val); //System.out.println(list); if(curr_index == tmp_list.size()){ boolean f_flag = resultCheck(f_val); boolean s_flag = resultCheck(s_val); if(f_flag) printResult(true,list.size()-2,curr_index); if(s_flag) printResult(false,list.size()-1,curr_index); } } index = index + (int)Math.pow(2, curr_index -2); } } } private void printResult(boolean b,int idx,int cur_ind) { // TODO Auto-generated method stub //System.out.println("In print Result"); List<String> result = new ArrayList<String>(); //result.add(tmp_list.get(cur_ind-1).toString()); result.add(list.get(idx).toString()); if(b) result.add("+"); else result.add("-"); int root_ind = idx; root_ind = findParent(root_ind); while(root_ind >= 0){ if(root_ind %2 != 0){ result.add(list.get(root_ind).toString()); result.add("+"); } else{ result.add(list.get(root_ind).toString()); if(root_ind != 0) result.add("-"); } root_ind = findParent(root_ind); } correctOrder(result); } private void correctOrder(List<String> result) { //System.out.println("In correctOrder"); System.out.println("Output : " + result); ListIterator<String> lst = result.listIterator(result.size()); List<String> out_Result = new ArrayList<String>(); while(lst.hasPrevious()){ out_Result.add(lst.previous()); } ResultOut = new ArrayList<String>(); ResultOut.add(out_Result.get(0).toString()); for(int i = 0 ; i < out_Result.size()-2; i=i+2){ int f_ele = Integer.parseInt(out_Result.get(i)); int s_ele = Integer.parseInt(out_Result.get(i+2)); String op = out_Result.get(i+1); if(op.equals("+")){ ResultOut.add("+"); Integer res = s_ele - f_ele; ResultOut.add(res.toString()); } else { ResultOut.add("-"); Integer res = f_ele - s_ele; ResultOut.add(res.toString()); } } System.out.println("Final Result is : " + ResultOut); } private int findParent(int idx) { // TODO Auto-generated method stub //System.out.println("In find parent"); if(idx%2 !=0) return (idx-1)/2; else return (idx-2)/2; } private boolean resultCheck(int val) { //System.out.println("In result check"); if (val == target_no) return true; else return false; } public static void main(String[] args) { List<Integer> ll = new ArrayList<Integer>(); ll.add(8); ll.add(7); ll.add(3); ll.add(4); ll.add(5); BackTrack b1 = new BackTrack(ll, 5); b1.startOP(); } }