CareerCup

all you need is a binary indexed tree aka fenwick tree

the question effectively requires us to find that particular subset for which difference between sum of its elements and that of the elements in its compliment is minimal. every one of the subsets will have to be examined. IMO, this will be O(2^n).

void f(int[] a, int i, int[] b, int[] c, int r, int[] B, int[] C)
{
	if(i==a.length)
	{
		int diff = abs(sum(b) - sum(c));
		if(diff < r)
		{
			r = diff
			B = b;
			C = c;
		}
	}
	
	f(a, i+1, b+a[i], c, r, B, C);
	f(a, i+1, b, c+a[i], r, B, C);
}


while calling, pass infinity for r

came across this interesting solution in another thread - algohub.blogspot.in/2014/03/replace-each-array-element-with.html

where does log come into picture? IMO, its O(nk)

maintain the following attributes for each of the node u, d denoting number of uphill and downhill edges involved in shortest path to the node. initialize them to zero.

invariant to be maintained : at any given point in time, both u and d cannot be >1 simultaneously.

when considering an edge to be added to the SPT, check whether updating u and d values for the destinaion edge would violate the above invariant. an edge can be added only when the invariant is maintained.

you could use the apporach outlined here - htp/algohub.blogspot.in/2014/04/intersection-of-two-sorted-arrays.html

well i would just scan through to find the max and add 1 to it :)

and how is that done?

@samuel Effectively you would be examining all the contiguous subsets. sum of a subset is derived from the sum of the immediate smaller subset which is where you save cost. Is that correct? (pardon, i could not understand your code)

I would say this cannot be done in O(n). It is necessary that we examine each element and look for existence of its pairs that sums to k. It would take O(n) just to go through each element. In my view, the best possible is O(nlog n)

use kadane's algorithm

node f(node x)
{
	a_head = x
	b_head = x.next
	a=a_head, b = b_head;
	
	while((a!=null) && (b != null))
	{
		a.next = b.next
		a = a.next
		b.next = a.next
		b = b.next
	}
	a.next = b_head
	return a_head;
}

node getBST(int[] a, int start, int end)
{
	if(start>end)
		return null
		
	node x = new node(a[start]);
	
	int i=0;
	for(i=start+1;i<end;i++)
	{
		if(a[i]>a[start])
			break
	}
	
	x.left = getBST(a, start+1, i-1);
	x.right = getBST(a, i, end);
	
	return x;
	
}

getBST(a, 0, a.length-1)

yes it will...the BST property will be violated in that case

really depends on implementation of trie. the classic trie implementation which has a slot for ever possible character in the language at each node would be wasteful of memory. if you design your trie such that each node has a pointer only for characters of strings it stores, it should be fine.

share your thoughts.

m for each i is computed from previous value of m. made me think that there are overlapping subproblems
theres no optimal substructure
you might be right

use dynamic programming
here is a solution in python:

def f(a):
	s=sum(a)
	m=0
	for i in range(len(a)):
		m=m+a[i]
		s=s-a[i]
		if m==s:
			return i

time complexity : O(n)

Divide the 1000 bottles into 2 halves and accumulate drops of each half two form two glasses of wine. Have a slave drink each glass. Check which one of them dies. Take the corresponding half and repeat the process.

No of slaves = log2(1000) ~ log2(1024) =10

this is turning around the question and repeating it...not a reasoning

def f(n):
	if n==1:
		return 0
	if n%10==0:
		c=0
		a=n
		while a%10==0:
			a=a/10
			c=c+1
		return c+f(n-1)
	if n%5==0:
		c=0
		a=n
		while a%5==0:
			a=a/5
			c=c+1
		return c+f(n-1)
	return f(n-1)

100! will have 23 zeroes

pseudocode:

bt(current, target, num_moves, min_so_far)
{
	if(current==target)
	{
		if(num_moves<min_so_far)
			min_so_far = num_moves
		return min_so_far
	}
	
	if(num_moves>min_so_far)
		return min_so_far
	
	candidates = get_candidates(current)
	
	foreach(candidate in candidates)
	{
		min_so_far = bt(candidate, target, num_moves+1, min_so_far)
	}
	return min_so_far
}

input needed :
1. what is the length of the appointment to be scheduled?
2. What is the last time until which an appointment can be scheduled?

once we have these details, follow these steps:
1. arrange already scheduled appointments in increasing order of start time. O(nlogn)
2. traverse through the list and compute difference between end time and start of successive intervals.
3. an appointment can be scheduled if oneo f the following is satisifed:
a) if the gap between any two successive appointments is greater than or equal to the length of the required appointment
b) if there is enough time left in the day after last appointment to accomodate the new appointment

int floor(int val, node x)
{
	if(x==null)
		return null
	if(val>=x.val)
	{
		a = floor(val, x.right)
		if(a==null)
			return x.val
	}
	else
	{
		return floor(val, x.left)
	}
}

def isinc(x):
	l=list(str(x))
	return l==sorted(l)

def isdec(x):
	l=list(str(x))
	b=sorted(l)
	b.reverse()
	return l==b

r=[]

for i in range(30,3001):
	if isinc(i) or isdec(i):
		continue
	r.append(i)

def s(l,n):
	n%=len(l)
	a=len(l)-n
	b=a+n
	i,j=a-n,b-n
	if i<0:
		i=0
	if j<0:
		j=0
	while a>0:
		l[a:b],l[i:j]=l[i:j],l[a:b]
		i,j,a,b=i-n,j-n,a-n,b-n
		if i<0:
			i,j=0,a
	return l

: 4. with this find the middle and last node of the sll

how do you achieve this? how do you know which of the two possibilities from step 3 we have here?