CareerCup

best time is n +logn -2 using tournament trees

@Cyber Phenix almost correct
@avikodak you cannot check by comparing only first two numbers... the second number could be itself missing or part of a bigger number...

The problem can be divided into 2 parts... finding the number sequence and then finding the missing number in that sequence

Guess the number of digits for the first number by reading numbers from the string one by one. If the previous number you have read is x, the next number must be either x + 1 or x + 2. If it is x + 2, remember x + 1 as the missed number, continue until the end of the string anyway to verify that the initial guess was correct. If you read something else than x + 1 or x + 2, the initial guess was wrong and you need to restart with (next) guess.

For example:

9899100101103104105

First guess length 1

read 9
the next number should be either 10 or 11. Read the next two digits, you get 89.
That is incorrect, so the initial guess was wrong.

Second guess length 2

read 98
the next number should be either 99 or 100. Read the next two digits for 99
the next number should be either 100 or 101. Read the next three digits for 100
... 101
... 103 (remember 102 as the missed number)
... 104
... 105
end of input

Guess of length 2 was verified as correct guess and 102 reported as missing number.

stackoverflow.com/questions/19245137/find-the-missing-number-in-a-given-string

LOGIC:
1. Traverse the array forwards, wrapping around when you hit the end (code below)
2. Count the total number of inflection points you find, if num_inflection_points==2 then your array is bitonic.
3. The runtime of this should be O(n).

-

Here's a working example in c++:

bool is_bitonic(const vector<int>& v) {
  bool was_decreasing = v.back() > v.front();
  int num_inflections = 0;
  for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
    bool is_decreasing = v[i] > v[(i+1)%v.size()];
    // Check if this element and next one are an inflection.
    if (was_decreasing != is_decreasing) {
      num_inflections++;
      was_decreasing = is_decreasing;
    }
  }
  return 2 == num_inflections;
}

Notes, depending on your implementation:

Note 1: Here's the basic idea for traversing an array circularly:

for (int i = ip_index; i < array_length; i++) {
   int index = (i + 1) % array_length;  // wraps around to beginning
   // Retrieve the value with
   DoSomethingWithValue(array[index];)
}

Note 2: It might simplify the code to circularly loop length + 1 elemnts, which will guarantee you find both inflection points.

Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.

source : stackoverflow.com/a/3029129/1923790

On the basis of 1 and 3 data we can put a default floor(the floor to which lift returns automatically when no service requests are pending) for that specific time... For instance having the default floor of all the lift to the ground floor (concourse) will be helpful in reducing the average wait time of the employees. Ans similarly in the evening the topmost floor can be set as default floor.

Yup, that's the Moore voting algorithm

When we move the pointer forward over an element e:

        If the counter is 0, we set the current candidate to e and we set the counter to 1.
        If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

    When we are done, the current candidate is the majority element, if there is a majority.

Yes, and to reduce the complexity of finding is a number is prime or not use sieve of Eratosthenes( check out en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to generate all prime numbers upto n/2

Then you can use two for loops { i (0 to len(primes)-1) and j (i to len(primes -1))} to print only those pairs where i*j<=n
the loop -> j (i to len(primes -1)) ensures no repetition and reduces time to check redundant solutions

Python implementation for the same:

def generatePrimes(n):
    sqrtn = int(n**0.5)
    sieve = [True] * (n+1)
    sieve[0] = sieve[1] = False
    for i in range(2, sqrtn+1):
        if sieve[i]:
            m = n/i - i
            sieve[i*i:n+1:i] = [False] * (m+1)
    sieve = [i for i in range(n+1) if sieve[i]] 
    return sieve

def printPairs(n):
    primes = generatePrimes(n/2)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (i*j)<=n:
                print primes [i], primes[j]

#Call from the driver function 
printPairs(100)

small correction
if (r1 > l1)

printAllCombinations(l1, r1-1, l2, r2, l3, r3, str, count + 1);

Logic: the right parentheses can appear in an output string only when there are
already more left parentheses present in the output string. Extending the solution from Gayle's solved problems

c++ code for the problem ... explanation is mostly inline and a brief summary at the end

/*
Since 
n1 pairs of “{} ” brackets
n2 pairs of “[] ” brackets
n3 pairs of “() ” brackets 
let
 l1= r1 =(n1)/2
 l2= r2 =(n2)/2
 l3= r3 =(n3)/2
*/
/*call from driver function */
char str[13];
str[12]=’\0’;
printAllCombinations(2,2,2,2,2,2,str,0);

//count is the index where we have to put the character currently
void printAllCombinations(int l1, int r1, int l2, int r2, int l3, int r3, char *str, int count) {
	if (l1 < 0 || r1 < l1 || l2 < 0 || r2 < l2 || l3 < 0 || r3 < l1 ) return; // invalid state
		if (l == 0 && r == 0) {
			printf(“%s\n”, str); // found one combination, so print it
			return;
		}
		if (l1 > 0) { // try a left curly brace, if there are some available
			str[count] = ‘{‘;  
			printAllCombinations(l1 - 1, r1, l2, r2, l3, r3, str, count + 1);
		}
		if (l2 > 0) { // try a left bracket, if there are some available
			str[count] = ‘[‘;  
			printAllCombinations(l1, r1, l2-1, r2, l3, r3, str, count + 1);
		}
		if (l3 > 0) { // try a left paren, if there are some available
			str[count] = ‘(‘;  
			printAllCombinations(l1, r1, l2, r2, l3-1, r3, str, count + 1);
		}
		
		//Now put the matching braces at all possible combinations
		if (r1 > l1) { // try a right curly brace, if there’s a matching left
			str[count] = ‘)’;
			printAllCombinations(l1, r1-1, l2, r2, l3-1, r3, str, count + 1);
		}
		if (r2 > l2) { // try a right bracket, if there’s a matching left
			str[count] = ‘)’; 
			printAllCombinations(l1, r1, l2, r2-1, l3, r3, str, count + 1);
		}
		if (r3 > l3) { // try a right parenthesis, if there’s a matching left
			str[count] = ‘)’; 
			printAllCombinations(l1, r1, l2, r2, l3, r3-1, str, count + 1);
		}
	}
}

Basically at any current index of the result we have 3 options
1. Fill current index using any of the 3 types of left brackets (this can be done only when the left count of that type >0 )
2. Fill current index using any of the 3 type of right bracket (this can be done only when the left count of that type >right count of that type)
3. print the result if all type of brackets has been consumed

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

#define MAXELT 10001

void main()  //overhead - read the numbers, print the results.
{
  int i=-1,n=0,L[MAXELT],m,s;
  char t[10];
  void largest_and_second_largest(int a[],int n,int *m,int *s);

  do {
    if (i!=-1)
      L[i++]=n;
    else
      i++;
    printf("\nEnter a number>");
    gets(t);
    if (sscanf(t,"%d",&n)<1)
      break;
  } while (1);
  largest_and_second_largest(L,i,&m,&s);
  printf("\nThe maximum is %d and the second-largest is %d.",m,s);
}

//The action lies here
void largest_and_second_largest(int a[],int n,int *m,int *s)
{
  int *I,                       //stores the losers
      size,                     //stores the current level in the tree
      i,j,                      //indexed
      lu,                       //stores the last compared element in the
                                //current level
      max,                      //stores the largest number
      slarge,                   //stores the second largest number
      sindex;                   //stores the index of the second largest number
  void swap(int *a,int *b);

  size=1; lu=-1;                //initialize - level one and no number used
  I=(int *)malloc(sizeof(int)*n);
  for (i=0;i<n;i++)             //initialize - no loser yet
    I[i]=-1;
  for (;;) {                    //loop until size-1 becomes more than n
    i=size-1;
    if (i>=n)
      break;                    //loop exit
    j=size+i;
    if (j>=n && i!=n-1)         //if the last element of the array has
      j=n-1;                    //not been considered, use it
    if (j>=n)
      if (lu<0)
        break;                  //loop exit
      else {
        j=lu;                   //store the used number in lu
        lu=-1;
      }
    for (;;) {                  //another seemingly infinite loop
      if (a[i]>a[j])            //swap if out of order
        swap(&a[i],&a[j]);
      else
        I[i]=I[j];              //otherwise, just store in the loser list
      I[j]=i;
      i=j+size;                 //next number
      if (i>=n)
        break;                  //inner loop exit
      else {
        j=i+size;               //next
        if (j>=n && i!=n-1)     //if the last element of the array has
          j=n-1;                //not been considered, use it
        if (j>=n)
          if (lu>0) {
            j=lu;               //take in last used
            lu=-1;              //empty last used
          }
          else {
            lu=i;               //if there is no earlier last used, store the
                                //current number as last used
            break;
          }
      }
    }
    size=2*size;                //move to the next level
  }
  max=a[n-1];                   //largest is found
  sindex=I[n-1];                //find the second largest by simple comparison
  slarge=a[sindex];             //in the loser list for the maximum
  while (sindex!=-1) {
    sindex=I[sindex];
    if (sindex!=-1 && a[sindex]>slarge)
      slarge=a[sindex];
  }
  *m=max;
  *s=slarge;
  free(I);                      //free and return
}

void swap(int *a,int *b)        //swap two elements
{
  int temp;

  temp=*a;
  *a=*b;
  *b=temp;
}

Source :seeingwithc.org/topic3html.html

It can be done in n+log n-2 comparisons. This question is also in CLRS.

Think of elements as competitors, and a tournament is going to rank them.

First, compare the elements, as in the tree

|
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.

The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

from stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

your third approach will always not result into correct result.. Assuming you are picking 2 elements at a time which is resulting into your 1.5N complexity.. consider following test case

arr = [3,4,1,2,5,6]

min1 = 3
min2 =4
you pick 1 and 2
then compare 1 (as 1<2) with 3 (as 3<4) and update min1 (as 1<4)
and you move to next pair(5,6) and you will be done in next iteration
however the min2 was not updates to 2 which is the correct ans.

According to your approach... 4 is the 2nd smallest element which is currently in min2 which is incorrect!

Yeah but then since you have N threads now merging the answer into a single global variable will need some kind of locking mechanism on that global variable. Now consider this if the number of threads is huge the step of merging the result into a single variable becomes bottleneck and all threads are waiting to take a lock on a single variable so that they can update the total sum...

@kkr.ashish : the solution is correct however you can do it in two iterations rather than 3n
C++ code below for O(2n)

int * prodExceptCurrElem (int * arr, int len){
    if (!arr || len<0) return NULL;
    int * newArr = new int [len];
    int i=0, prodSoFar =1;
    for(;i<len;i++){
        newArr[i] =  prodSoFar;
        prodSoFar *= arr[i];
    }
    prodSoFar = 1;
    for (i=len-1; i>=0; i--){
        newArr[i] *= prodSoFar;
        prodSoFar *= arr[i];
    }
    return newArr;
}

@Itanium as the people have already mentioned that the Q is for subarray not subset which needs to be contiguous.

@algos However there is a cost in this solution of space O(n).

geeksforgeeks.org/find-subarray-with-given-sum/
This above article explains an O(n) solution which requires no extra space and can be used for any target sum and not only 0.

@nice algos
Implementation in python of the same:

def subArraySumZero(intList):
     sumHash= { }
     sumSoFar = 0
     index = 0
     for index in range(0,len(intList)-1):
         sumSoFar += intList[index]
         if sumSoFar in  sumHash.keys():
            print intList[ sumHash[sumSoFar] +1 : index+1]
            return 
         else:
            sumHash[sumSoFar] = index
     print "NO SUCH RESULT"
     
testList  = [2, 3, -4, 9, -1, -7, -5, 6, 5 ]
subArraySumZero(testList)

Method 3 (In-Place Merge using DLL)
geeksforgeeks.org/merge-two-balanced-binary-search-trees/

The approach is correct ... the only issue being that the solution will not scale and for a large number of machines the network traffic may be gargantuan. Consider an example with top ten counts in range of 1million and the number of servers in 10k range (which is not a big number considering the scale of amazon or google scale) so eventually you will ask for all URL which have count >= T/S which is 100 in this case. So you will end up sending a lot more data than is actually needed (as you will be sending URL for counts between 100 and 1 million). Also the bottleneck in such a solution would be central node processing this algorithm which wont scale but as I said earlier the solution is correct but not scalable.

Assumption: While a pairwise intersection of corresponding pixels in the two images....Intersection is white iff both pixels of the pair are white.

Then you can do the recursive intersection as follows:
let A and B be to corresponding nodes in the two trees (or their subtrees)

if rootA.color == "black":
    return A
if rootA.color == "white":
    return B
if rootA.color == "gray" and rootB.color == "gray".
##Pairwise intersect the subtrees of A and B.
##If all four of the returned subtrees have a black root, return a single node tree with a black root.
Otherwise return a tree with a gray root and the four returned subtrees as its subtrees.

Complexity is O(min{|A|, |B|}).

Where ne , nw, se, sw represents 4 subsection of current section of image (north east, north west, south west, south east)

nw|ne
sw|se

A quad tree can have only 3 color of nodes .. black white and gray

The crux is that at each level(depth) if the pixel color is not gray then it represents 4^(k-d) pixels of color same as itself. where k represents the overall size of image of size (2^k X 2^k) and d represents the current depth of node in the tree

Assuming each node has color field: "black"/"white"/"gray"
and 4 field for the 4 child nodes of type node: ne , nw, se, sw

Code in Python:

def quadTreeCountBlackPixels(root, depth, size):
    if (None == root):
        return 0
    if (root.color == “white”):
        return 0   
    elif (root.color == “black”):
        return pow(4, size-depth)
    else:
        seCount = quadTreeCountBlackPixels(root.se, depth+1, size)
        swCount = quadTreeCountBlackPixels(root.sw, depth+1, size)
        neCount = quadTreeCountBlackPixels(root.ne, depth+1, size)
        nwCount = quadTreeCountBlackPixels(root.nw, depth+1, size)
        return seCount + swCount + neCount +nwCount

#initial call to function
totalBlackPixels  = quadTreeCountBlackPixels(root, 0 , k):

#where the image is of size 2^k X 2^k

@ankit thanks for pointing that out... I can do away with curr2 by using prev or vice-versa

node* appendLastNtoBegin(node* head,int n){
    if ((!head) || (!head->next) || n<=0)
        return head;
    node * curr(head), *prev(head);
    int i(1);
    while(curr->next){
        if (i<n) i++;
        else prev = prev->next;
        curr=curr->next;
    }
    if (i<n){
        cout<<"invalid input for N"<<endl;
        return head;
    }
    prev->next=NULL;
    curr->next=head;
    head=prev;
    return head;
}

With this question they just want to know if you know about any scripting languages.. any scripting language will do bash/python/perl. c++/java code in this Q may reduce your chances of getting selected unless its an astonishing solution

If its just for one time then following grep command like:

grep -lr '[1-9]\{3\}-[0-9]\{4\}-[0-9]\{3\}' "*.html" > results.txt

This was an open ended question and he was quite impressed with my answer and I got the offer so it worked. we discussed the test cases for around more than 1.5 hours while include 15 min of categorizing test cases and he said there is no end to it we could discuss it for whole week... basically they wanna see how broad you can think and never say thats it ... as there will be so so many more test cases

yes.. if the tree is not balanced it will result into O(n) search times. one can use AVL or Red black tree for this purpose.

Stl::map itself used red black tree since its balanced and red black tree has advantage over AVL here is that the rotation operation to balance the tree is O(1) whereas in AVL it could be O(logn)

here is an example

1
    /   \
  2      3
 / \    / \
4   5  6   7

The tree has 5 vertical lines

Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7

So the resultant array would be
4, 2, 12, 3, 7

The logic being we will have at max number of 2*h-1 elements in the resultant list where h is the height of the tree

Imagine tree as umbrella and now the columns sum start only at the nodes who are on top arc of the tree ...rest internal nodes are part of sum of some node above it .

I have used
-resArr of 2h-1 elements in which i will store results
-bool initLeft and bool initRight to determine in which direction i need to initiate a new sum and if its false i just sum to the given position and dont initiate sum for new position in resultant array
-pos to determine which column i am adding sum (which will be initially mid pos for root node)
-initially only root will have both initLeft and initRight as true rest nodes will have either one of them as true(if the lie on arc of umbrella) or none

void getVerticalSum(node * root, int*arr, int pos, bool initLeft, bool initRight){
    if (!root || !arr)
        return;
    arr[pos]+=root->data;
    if (root->left)
        getVerticalSum(root->left->right, arr,pos, false, false);
    if (root->right)
        getVerticalSum(root->right->left, arr,pos, false , false);
    if (initLeft) 
        getVerticalSum(root->left, arr, pos-1, true, false);
    if (initRight) 
        getVerticalSum(root->right, arr, pos+1, false, true);
}

Driver function or main:

    int *resArr = new int[2*h-1]; 
    getVerticalSum(root, resArr, h-1, true , true);
    cout<< "\n Vertical sum list is ";
    for (int i=0; i<2*h-1;i++)  cout<<resArr[i]<<"\t";
    delete []resArr;

you have to find vertical sum not the horizontal sum

but in this case its a const space as the input is a 32 bit integer and if u create a bitmap for that it takes 512MB which is independent of number of elements to be analysed and hence constant space

I had a similar Q in MS interview and i suggested the bit vector for each integer of a 32 bit integer... in my case the memory constraint was 1GB and if you create a bit vector it consumes 512 MB only and he said that its correct

@pisaruk If you are gonna use the fraud numbers strings as keys then why dont you create a hash of <fraud numbers, bool> in the first place instead of having hash inside a hash

Almost correct but you missed one case in your 3.ii when you couldnt find a parent whose data is greater then it is the next node then stop at the node whose parent is NULL and now the successor is in right subtree(if it exists) so from root of tree(whose parent is NULL) traverse to the smallest in the right subtree and return that node. and there is changes to the psuedocode also

if ( node.right !=null )
	return node.right
else if ( node.parent.data > node.data )
	return node.parent
else if ( node.parent.data < node.data ) {
	temp = node.parent
	while(temp !=null &&temp.data < node.data){
		node=temp   
		temp = node.parent
         }
	if(temp > node.data)
		return temp
	else if(temp==null){
		 if(node->right)
			while (node->left){
				node=node->left
  			}
			return node
		else
			return null
        }

@JerryC ... yes if the number of fraud patterns are small then its certainly a nice idea(which one should ask the interviewer and in this case most probably it will be). however if the the fraud pattern are large in number then it will be O(n) in searching in linked list. So we can use a balanced BST(AVL, RB) instead of linked list and hence time will be O(1)+O(logn) =>logn

I think it will work but there is a small issue ...you are swapping the data(or its pointer) instead of changing a pointer itself...And in almost all the cases the answer is not acceptable
For example
Assume that the node consists of object or data pointers to more than one data... in that case you are supposed to rearrange the nodes using the pointers rather than swapping the data(or its ptrs) [this is what my interviewer said to me at interview at MS and which seems fair enough]

So similar thing can be achieved by just rearranging next pointers leaving data untouched (obviously i will have to save the pointers to the elements prev to the elements to be swapped)

Following is the c++ code

node* swapkthFirstAndLast(node* head,int k){
    if (head==NULL||k<=0 )return head;
    int i(k);
    node * curr(head), *startPrev(NULL), *startEle(NULL),*tmp(NULL),*prev(NULL), *currBack(head);
    while ((i-1)>0 && curr->next){
        prev = curr;
        curr = curr->next;
        i--;
    }
    if ((i-1)>0){
        cout<<"Invalid value of K"<<endl;
        return head;
    }
    startEle = curr;
    startPrev = prev;
    while(curr->next){
        prev = currBack;
        currBack = currBack->next;
        curr =  curr->next;
    }
    //same elements
    if (currBack == startEle)
        return head;
    //end elements
    if (k==1){
        currBack->next = head->next;
        prev->next = head;
        head->next = NULL;
        head = currBack;
        return head;
    }
    //adjacent 
    if (currBack->next==startEle){
        tmp = startEle->next;
        startEle->next=currBack;
        currBack->next=tmp;
        prev->next= startEle;
        return head;
    }
    //lying elsewhere
    prev->next =  startEle;
    tmp= startEle->next;
    startEle->next=currBack->next;
    currBack->next = tmp;
    startPrev->next = currBack;
    return head;
}

i had tested on k = -ve, 0,1,2,3...,>len(list) on both even and odd lengths and hence covering all four cases mentioned by @Shondik ...but if i still missed any corner case let me know

@Anand... LinkedHashMap can be only used here as it will iterate in the order in which the entries were put into the map whereas HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.

Does anybody know equivalent of LinkedHashMap in C++?

@Anuj is right finding index of element in orderarray will take m operation(m is length of orderArray) hence O(nm)

yes he has explained properly under bottom-up approach while comparing to other approaches

So the logic is... while going bottom up(stack unwinding) you pass min and max at current node to the caller node(parent) and return the total number of nodes if its BST else -1. Nodes who does not satisfy the BST properties, all subtrees above them (which includes this node as well) must also not satisfy the BST requirements. Time complexity O(n) with no extra space

This c++ code is from the same page

int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
                   int &maxNodes, BinaryTree *& largestBST) {
  if (!p) return 0;
  bool isBST = true;
  int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
  int currMin = (leftNodes == 0) ? p->data : min;
  if (leftNodes == -1 ||
     (leftNodes != 0 && p->data <= max))
    isBST = false;
  int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
  int currMax = (rightNodes == 0) ? p->data : max;
  if (rightNodes == -1 ||
     (rightNodes != 0 && p->data >= min))
    isBST = false;
  if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
      maxNodes = totalNodes;
      largestBST = p;
    }
    return totalNodes;
  } else {
    return -1;   // This subtree is not a BST
  }
}

yes... this is standard Knuth shuffle algo

for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

And here is the c++ code for the same

void knuthShuffle(int n){
    int *ar = new int[n];
    int i(0),temp(0);
    for (;i<n;i++) ar[i]=i+1; //initialize array
    while(i>0){
        int r = Random(i-1);//which is similar to ->rand()%i; 
        temp = ar[i-1];
        ar[i-1] = ar[r];
        ar[r] = temp;
        i-=1;
    }
    for(i=0;i<n;i++) cout<<ar[i] <<" ";cout<<endl;
    delete ar;
}

Time complexity: O(n)
Space complexity: O(n)

yes you are right...here is the same implemented in c++

node* appendLastNtoBegin(node* head,int n){
    if ((!head) || (!head->next) || n<=0)
        return head;
    node * curr(head),*curr2(head), *prev(NULL);
    int i(1);
    while(curr->next){
        if (i<n) i++;
        else{
            prev= curr2;
            curr2= curr2->next;
        }
        curr=curr->next;
    }
    if (i<n){
        cout<<"invalid input for N"<<endl;
        return head;
    }
    prev->next=NULL;
    curr->next=head;
    head=curr2;
    return head;
}

@ chisingh , you are right... just rephrasing the logic

Keep 2 queues to keep track of levels
Do BFS
After each level update the max elements and swap currLevelQ and nextLevelQ so that you are always working on currentlevelQ

@suresh ... coolguy's solution is better as u need to modify the original data neither u can use extra space and since the arrays are sorted then
Time taken = n(to find max start element)+
n(elements of that array) * n (number of arrays)* logn(binary search for each element)
=n+n2logn = n2logn

However your's would be O(n3) ... if the arrays would have been unsorted then your solution would be the valid one but here we can take advantage of sorted arrays

Let A and B be two ranges which are limited by [Alow,Ahigh] [Blow,Bhigh]
Now there can be total 7 cases
1. both ranges matches
2. A is contained in B
3. B is contained in A
4. they intersect but A is on right of B
5. they intersect but B is on right of A
6. they dont intersect and B is on right of A
7. they dont intersect and A is on right of B

which have been handled in python code as following

def findDiffAB(Alow,Ahigh,Blow,Bhigh):
    #negetive test case
    if (Alow>Ahigh or Blow>Bhigh):
        return list()
    if(Alow==Blow and Ahigh==Bhigh):
        return list()
    if (Alow>Blow and Ahigh<Bhigh):
        return list()
    if (Alow<Blow and Ahigh>Bhigh):
        return range(Alow,Blow)+range(Bhigh,Ahigh)
    if (Alow>Blow and Ahigh>Bhigh and Alow<Bhigh):
        return range(Bhigh,Ahigh)
    if (Alow<Blow and Ahigh<Bhigh and Blow<Ahigh):
        return range(Alow,Blow)
    if (Ahigh<=Blow):
        return range(Alow,Ahigh)
    if (Alow>=Bhigh):
        return range(Alow,Ahigh)

Obviously 4 cases can be merged two 2 here but i didnt for sake of clarity

Few test cases:
print findDiffAB(2,5,2,5)
print findDiffAB(3,5,2,7)
print findDiffAB(2,15,7,9)
print findDiffAB(12,25,2,5)
print findDiffAB(2,5,12,25)
print findDiffAB(2,5,13,15)
print findDiffAB(12,25,2,5)

@Cerberuz i think i will work with but there is something missing

in the following statement

if dp[j] == true:
               dp[ j+a[i] ] = true

you set true in dp when there was some other element in dp was already true..... but you never set any element of dp to true(before the main for loop)


I think it can be easily fixed by initializing dp[a[i]] = true (and rest as false) . so that you have elements to start with in dp who are true so that dp can grow on top of them (as you already have 1 element who has a sum equal to index of j)

//before main for loop
for i = 1 to n:
    dp[a[i]] = true

in step 2 can you explain why are you trying to search in the rest of array because i dont think it will work for any number of elements
btw this is a subset problem

Yeah i also explained him the trie solution but he was concerned about high amount of space that would be consumed (as each node will contain an array of 26 nodes for next character).. i could have have suggested him compressed trie but we were out of time so we couldnt discuss further

Here is a working code.. in case anyone wanna have a look

node* reverseList(node* head){
    if (!head) return NULL;
    node *curr(head), *prev(NULL), *tmp(NULL),*newHead(NULL);
    while (curr){
        tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    newHead = prev;
    return newHead;
}
node* mergeLastAndFirst(node* head){
    if (head==NULL )return NULL;
    if (head->next==NULL )return head;
    node * curr(NULL), *slow(head), *fast(head);
    node *newHead(NULL), *tail(NULL),*tmp(NULL),*prev(NULL);
    while (fast && fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    tail = reverseList(slow->next); //slow will always have next
    printList(tail);
    slow->next = NULL;
    newHead = curr = tail;
    while(head && tail){
        tmp = tail->next;
        curr->next = head;
        tail = tmp;
        head = head->next;
        prev = curr->next;
        curr->next->next = tail;//->next;
        curr = curr->next->next;
    }
    if (!curr) curr=prev;
    if (head) curr->next = head;
    if (tail) curr->next = tail;
    return newHead;
}

You dont even need to count the number of nodes in linked list... just use the small and fast pointer to find middle

why are you wasting space in creating a extra linked list which is not even needed. this solution can be easily done without any extra space

No extra space/stack/queue required.
Total time 2n=> O(n)

Simple non recursive solution
1. Use small and fast pointer to find middle of linked list (no need to calculate length and waste n operations) Time = n/2
2. Reverse the part of list which is following the middle(slow after 1st step) pointer (i have used it as tail in my code) Time = n/2
3. Merge the two half lists (head and tail lists) Time = n

Total time= n/2+n/2+n=2n

you dont need to use extra space of stack just reverse the list after middle point and use that for final merging

What if there could be a sentence in which more than one valid combination is possible????????/

For instance: Therestonecrushedspirit

1. The rest one crushed spirit
2. There stone crushed spirit