CareerCup

Attaching another great resource, use of different data structures in linux kernel - cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

@id
This got me thinking. This may not be very efficient solution because the recurrence relation 'you think' you have here is T(n) = 4T(N/4) + c (where N = n^2) ~ leading to log<base 4>(n^2) complexity. But it's NOT.
Unlike binary search, this does not result in a decision tree at all, since after dividing in four parts, you may not be able to pinpoint one of the parts to proceed and may end up searching each 1/4 from every decision.
Which means that worst time-complexity, my friend, is 4(n^2/4) ~ n^2 (leaving this as an exercise). Let me know if you need anymore clarification.

To scale, how about adding more than more servers (say 50) and having a (sticky?) ELB (elastic load balancer) in front of them, to start with?

@ZSGoldberg "Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same."

You are right about solution failing for duplicates in array.
But we do not necessary need to know that set of indices and set of values are same. So 1 xor 20 xor 1 will still give you 20, since xor is associative, no order needed be maintained like 1 xor 1 xor 2 xor 2 .... etc.
Hope that's clear?

Ok cool, got it. Good one. Also, why scan from 0 to n/2? Shouldn't it be 0 to n-1 ?
Not that it has any impact on overall runtime O(nlogn), but still.

This may not work in most cases, clearly. Consider this sorted array - 3 5 6 9 9 9 9 9 9 9 9 9 9 9. Your solution will keep on decrementing from the end, whereas only removing 3 from the beginning of the array could have given you the `min` no. of removals (=1).

I don't quite get this solution. Just from the looks of it, it's O(nlogn + n * n/2) ~ O(n^2).

Also, consider the sorted array like - 3 3 3 3 3 3 3 3 3 4 5 9
acc to step 3a) scanning from 3, first number with value <=6 is 4 with index 9. Total array size 12. Adding their diff 12 - 9 = 3 to index i? what will you gain out of that?

I think this is a dynamic programming problem and is same as coin change problem. You have say 3 coins 1,2,3 and you've to reach sum 5. All possible ways? 11111, 1112, 122, 23

Above problem can be translated to current problem - you have 5 rocks (N=5) and you have 4 coins (N-1) 1,2,3,4. Count number of ways to reach sum 5. 11111, 1112, ....

Solution for coin change problem - geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Erasmus is right.
For n=3, following above 'correct' formula - f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9
f(3) = 2 * 9 + 3
f(3) = 21

According to permutation logic-
1 2 3 - 3 places, 3 characters - total 3^3 = 27 permutations.
unwanted permutations - 1 2 3 having a b c -> 1 location possible. a b c can be permuted amongst each other at positions [1 2 3] in (nPr ways) - 3P3 ways = 3!

final ans = Total permutations - unwanted permutations
final ans = 27 - 6
final ans = 21

but the question stresses on improving time complexity and not space complexity, no?

no it doesnt. contradicting examples-
v 1 1 10 1
r 0 1 2 1

greedy solution (wrt range) will destroy the bomb with v 10.

another eg:
v 10 5 8
r 5 0 0

greedy solution wrt Value will destroy 5 and 8 both - which are part of actual solution (ans= 23).

Aaand it messes up the formatting again!

If the snake's head moves down, it does not necessarily mean that it's tail is also moving down. Consider below case where H is head, going down and T is tail still travelling to right.
eg:

T=====
              |
              |
             H

One very simple one comes my mind is a 2-D matrix (let's say initialized with 0s).

We keep track of head, tail and length of snake.

if head is in Right direction and so is Tail - you increment [i, n+1] col to 1 and [i, n-1] col to 0 -> to signify that snake has travelled in right direction.

if head is in Down direction and so is Tail - make [n+1, j] to 1 and [n-1, j] to 0

interesting things happen when Snake makes a turn. You can store the history of all turns made by snake. Let's say at any point in Matrix P(bendRow, bendCol) when snake was travelling left-to-right, it makes a down turn. You change direction of 'Head' to Down, but direction of 'Tail' remains the same i.e. Right. So now when snakes moves forward, you change [i, bendCol+1] as 1 and [bendRow-sankeLength-1, j]. When 'Tail' passes over P(bendRow, bendCol), you delete that point.

Sanke die events - If head hits any of the matrix boundaries or lands up on a cell with 1 (i.e. sanke body still exists there).

More details please..were you expected to solve an arithmetic equation of type 10A+20B = X etc?

int findRepetition(int[] array){
 int ans = -1, count = 0, prevMax=0; prevNumber = Integer.MAX;
  for(int i= 0; i< array.length; i++){
	if(prevNumber == array[i]){
		count++;
	    }
	else{
		if(count >= prevMax){
			ans = prevNumber;
			prevMax = count;
			}
	prevNumber = array[i];
	count = 1;
	}
  }
	return ans;
}

Good one. A simple Hashmap with timestamp as key and an atomic counter as value. Assuming 1000 sec per sec - on an avg 1 req per ms. Standard timestamps can easily be generated upto ms - hence least collision. Even if there are more than one req per ms, mutex on counter of that timestamp as key for just 2-3 values will be very cheap computation-wise.

What does this question mean?

It is. If naive sorting is done (by converting 2D array to 1D array), complexity is MlogM (M = N^2). In K-way merge, complexity is MlogN (since heap only contains N elements at any time).
Side note: K-way merge sort is also used to sort extremely long arrays which cannot fit in memory - called as external merge sort.

How does this work for: 1 6 2 4 7 1 8? from the algo, it'll not be able to calculate rain between 6 and 7?

Backtracking will work, only first we have to form the mapping as to who was defeat by how many people. eg d - { b, c } (d was defeated by b and c} etc... Person who didn;t win against anyone, forms array[0] (there may be more than one such persons). Start backtracking on this map.

I meant -
Say you are given 1230 -> number of characters for each place are -
1 2 3 0
_______
3 3 3 6

It can solved mathematically too.
Say you are given 1230 -> number of characters for each place are -
1 2 3 0
_______
3 3 3 4

so total number of result strings you'll get are 3*3*3*6 = 162 (Permutations)

So just create 4 arrays in this case -
1 c,d,e, c,d,e, c, d, e ...(repeat c,d,e 162/3 = 54 times)
2 v,f,r, v,f,r, v,f,r, ....( repeat v,f,r 162/3 = 54 times)
3 b,g,t (162/3 = 54 times)
0 z,a,q,x,s,w (repeat 162/6 = 24 times)

combine all 4 in one by
for ( i=0;i<162;i++)
{ finalArray[i] = a1[i]+a2[i]+a3[i]+a0[i] }