CareerCup

This problem can be solved in O(N) time, using a data structure call Deque, which is a queue that can be pushed/popped from both ends, in O(1) time.

The idea is: to maintain a sliding window of size K using deque. Once we push in from the right-end a number x, we need to pop out from the left-end all the numbers that are bigger than x, because these numbers cannot be a minimum of any future k-window.

I explained in details with code at this post:
capacode /array/finding-maximums-for-all-k-windows-in-linear-time/

python:

sentence = "This is a sentence"
reverse = " ".join(word[::-1] for word in sentence[::-1].split(" "))
print reverse	# sentence a is This

116 should be replaced by 18.

Then 1,2,3,4,5,6,7,8,9 is present once.

Should use deque or doubly linked list. Java ArrayList doesn't support RemoveAt(0) well.

One worst-case input is: A = [100000, 99999, 99998, ..., 1], K = 100000/2

Nice try anyway!

I forget to mention that, push/pop from left/right of deque are O(1) time operations, thus the algorithm is O(N) time.

The idea of deque is just an abstraction, we can implement it in different ways. For example, it can be implemented as a doubly linked list.

For java ArrayList:
If RemoveAt(0) is O(K) time, then it's not good. Imagine the case when K = N/2, and numbers are sorted in decreasing order. This case will take O(N.K), which is O(N^2) time.

@zr.roman: Thanks for looking into it!

If we look more carefully with the while loop, we will see that it's not always run in O(K) time.

Analyse by this way will give a tighter bound O(N):
Each element of the array is scanned once. It is added into the deque at most once. And it is removed at most once. So, altogether, the algorithms will take O(N) time.

This is amortized/aggregate analysis.

@zr.roman: It gave [ 9, 5, 5, 5, 5, 4, 3] as expected.

@zr.roman: Thanks for testing.
Change "DQ[0] < i-K" into "DQ[0] <= i-K" should work.

Here is the working code in python:

A = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13] 
A = [9,8,7,6,5,4,3,2,1,0]
N = len(A)
K = 4

from collections import deque
DQ = deque()    # store the index of numbers within the window of size K

RES = []
for i in xrange(N):
    print i, A[i], DQ, RES
    while len(DQ)>0 and A[DQ[-1]] <= A[i]: # Once a new max is encountered, all previous max are useless, thus need to remove
	    DQ.pop()
    while len(DQ)>0 and DQ[0] <= i-K:    # Remove index outside the K-window
        DQ.popleft()
    DQ.append(i)
    if i>=K-1:
        RES.append(A[DQ[0]])

print RES
#[10, 10, 10, 15, 15, 90, 90]

This runs in O(N) time because each element is added and removed from the deque at most once.

EDITED: fixed the bug, after zr.roman's comment.

Using Deque can solve this problem in O(N) time

deque is a queue that can be pushed/popped from both ends. We use a deque DQ to store the elements for the sliding K-window. The trick is that, we only store the elements that are potentially be the maximum of future K-windows. So, if we see a number x that is greater than all elements in the current deque, we know for sure that x now will be the max, and all those elements in current deque will never be the max again. Thus, they must be removed, replacing by x.

Example:
A = [8, 5, 10, 7,9, 4, 1, 1, 1…]
We see 8: nothing to compare
When we see 5: we know that when 8 is out of the future K-window, 5 can potentially be the max of that window. We need to store 5

When we see 10: we know that 8, 5 can never be the max for future K-window. Thus, 8,5 should be removed. The deque now contains only 10

When we see 7: 7 can potentially be the max when 10 is out. Store 7, deque becomes [10, 7]

When we see 9: 7 won’t be the max anymore, remove 7. Store 9, deque becomes [10,9]

And so on..

EDITED: I explained it here:
capacode. com/?p=1042

Be careful if the array doesn't have majority element.

If it doesn't guarantee to have the majority element (>n/2 time), we need to check more positions: k*n/4, k=0..4, to make sure the majority segment cross 2 of our land-marks.

If it guarantees to have majority element, just check middle element is enough.

The key point that makes O(1) time& space possible is that the array is sorted.

The idea is, if the element that repeated >n/2 time (half-major element), they must be next to each other in the array. And they must cross some "land-mark", that is the middle of the array.

So, checking the middle element A[n/2], comparing it with A[0] and/or A[n] can tell whether it's major element. EDITED: A[n/2] must be the answer given if half-majority exists.

For the case of majority > n/4 (quarter-majority): Same idea, however we need more "land-marks". I believe checking position k*n/8 for k = 0..8 will sufficient to check for the majority element.

For the case array is NOT sorted, I think O(1) time is not possible. However, O(n) time, O(1) space algorithm exists. Check this post about majority elements: capacode. com/array/major-element-in-array/ Thanks!

EDITED for the case n/4-majority:
- Check if there is a repeated segment S crosses at least 2 landmarks.
- If S crosses 3 landmarks or more: length of S must be >n/4, found S, done.
- If S crosses only 2 landmarks u and u+1:
Reduce the problem into the case "half-majority" with array from landmark u-1 to landmark u+2.

Suppose we need to build a balanced binary search tree T for the elements in sorted array A, from index "lo" to "hi".

build(A, lo, hi):
The root of T must be the middle element: T.root = A[mid], where mid = (lo+hi)/2

The left subtree of T must be built from A[lo, mid), recursively:
T.left = build(A, lo, mid-1)

The right subtree of T must be built from A[mid+1, hi), recursively:
T.right = build(A, mid+1, hi)

Remember the basecase is when hi-lo <=1.

Complexity:
Since each element of the array A is accessed once, the complexity is O(N), N = length of array A.

If the shortest path has length p. Then, BFS would take O(2^p) time and space.

I believe the length of shortest path is at most log(n) + m/2, for example when m = 2^k-1 and n = 2^k
In that case, BFS would take O(2^(m/2)) time and space, which is exponential.

Worst case complexity is O(logn), I think

Here is a hint:

Represent Fibonacci numbers in matrix form:
(F[n+1], F[n]
F[n], F[n-1])
= A^n, where
A =
((1,1),
(1,0))

Perform fast exponential (repeated squaring) to compute A^n.

(k+1)*a + k(k+1)/2 = N
N = (k+1)(a + k/2)
2N = (k+1)(2a+k)

Then, for N not-too-big, we can use integer factorization to find all pairs (a,k).
Just find all pairs (u,v) that u*v = 2N, considering all positive and negative divisors, then k = u-1, a = (v-k)/2. Of course, v-k must be even, otherwise ignore them.

If a, k are integers, then N must be integer.
If N real, a must be real. But then for any k we can find a. Thus there's not finite #solutions.

I got same answer, in few seconds.

Answer: 3,614,000,181,007,876

This C++ code will run in few seconds to get the answer (3 seconds on my i7 PC):

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
//Shortcuts for laziness:
#define     FOR(i,s,e)      for(int (i) = (s); (i) <  (e); ++(i))
#define     REP(i,n)        FOR(i,0,n)
#define     lli              long long int

const int MILLION = 1000010;

bool Sieve[MILLION];
vector<int> Primes; // list of primes less than 1M;
int N;              // number of primes less than 1M;

void sieve(){
    int n = sqrt(MILLION) +1 ;
    REP(i, MILLION) Sieve[i] = true;

    Sieve[0] = Sieve[1] = false;
    FOR(i,2,n) if (Sieve[i])
        for(int j = i*i; j< MILLION; j+=i)
            Sieve[j] = false;

    FOR(i,2,MILLION)
        if (Sieve[i]) Primes.push_back(i);
    N = Primes.size();
    //FOR(i,2, 100) cout <<Primes[i] % 6<< " "; cout<<endl;
    return;
};

bool is_Prime(lli x){
    REP(i, N) if (x % Primes[i] == 0) return false;
    return true;
}

int main()
{
    sieve();

    lli sum = 0;
    lli LO = 1000000000000;
    lli HI = 1000000100000;

    lli k0 = LO/6;

    lli x = 6*k0+1;

    while(x<HI-6){
        if (is_Prime(x)) sum+= x;
        x+=4;
        if (is_Prime(x)) sum+= x;
        x+=2;
    }

    cout <<sum<<endl;

    return 0;
}

N is too big constant here!

Great solution!

I have same idea.

Below is my implementation in C++, using doubly linked list.

Interesting Java has LinkedHashSet data structure. I don't know whether C++ has the alternative or not.

#include <iostream>
#include <map>      // use unordered_map for hashing in O(1)

using namespace std;

struct Node{
    char item;
    Node * next;
    Node * prev;
};

class List{    // doubly linked list
    private:
        Node * _head;
        Node * _tail;

    public:
        List(){
            _head = NULL;
            _tail = NULL;
        };
        ~List(){};

//insert a new node to the tail of the list:
    Node * insert(char newItem){
        Node *x = new Node;
        x->item = newItem;
        x->next = NULL;
        x->prev = NULL;
        //first element:
        if (NULL == _head){
            _head = x;
            _tail = x;
            return _head;
        };

        //not first:
        _tail->next = x;
        x->prev     = _tail;
        _tail       = _tail->next;
        return x;
    };

//remove a node pointed by x. Precondition: x must be in the list!
    void remove (Node *x){
        if (x == _head){
            if (x == _tail){
                _head = NULL;
                _tail = NULL;
                delete x; x = NULL;

                return;
            };

            _head = x -> next;
            _head -> prev = NULL;
            x->next = NULL; x->prev = NULL;
            delete x; x = NULL;

            return;
        };

        if (x == _tail){    // x != _head
            _tail = x -> prev;
            _tail->next = NULL;
            x->next = NULL; x->prev = NULL;
            delete x; x = NULL;
            return;
        };

        // x in the middle:
        x->prev->next = x->next;
        x->next->prev = x->prev;

        x->next = NULL; x->prev = NULL;
        delete x; x = NULL;
        return;
    };

    char getHead(){
        if (_head) return _head->item;
        else return 0;
    };

    void clear(){
        _head = NULL;
        _tail = NULL;
    };
};


List myDLL;

map<char, Node *> myHash;
map<char, int> Counter;

int main()
{
    myDLL.clear();
    string S = "gaabfcacbdegdfehhoto";

    for(int i = 0; i<S.length(); i++){
        if (Counter.count(S[i]) < 1){       // not in the Counter
            Node *x = myDLL.insert(S[i]);
            myHash[S[i]] = x;
        }else
        if (Counter[S[i]] ==1){
            Node *x = myHash[S[i]];
            myDLL.remove(x);
            myHash[S[i]] = NULL;
        };
        Counter[S[i]]++;
    };


    char c = myDLL.getHead();
    cout <<"First unique character is: ";
    if (c and (Counter[c]==1)) cout <<c<<endl;
    else cout <<" No unique char!"<<endl;
    return 0;
}

How many ways are there for N=20? What is the run time of your program? It's interesting to know.

44
Why?
a. 43 can't be decomposed into sum of 6s, 9s, and 20s.
b. 44 to 49 (6 consecutive numbers) all can be decomposed, thus all numbers equal or larger than 44 also can.

My results:
N=10: 4 ways;
N=11: 44 ways;
N=12: 156 ways;
N=18: 8.924.976 ways

See my post for the not-slow-not-fast code.

This problem is hard for big N. For small N, it can be fast.

Statistics of my simple program:

N = 14: 5.180 ways
N = 15: 32.516 ways
N = 16: 202.900 ways
N = 17: 1.330.622 ways (26 seconds without printing)
N = 18: 8.924.976 ways (190 seconds without printing)

EDIT: Brief explanation:
- Always place the k-th queen at the k-th column;

- If you put a queen at k-th column and i-th row: mark row[i] not-safe, mark the 2 diagonals crossed at square (k,i) not-safe.

- In k-th column: try all "safe" positions. Position i is safe if: row[i], diag1[k+i], diag2[k-i] are safe, and square (k,i) is not knight-move reachable from (k-1)th and (k-2)th already-placed queens.

Note that queens (k-3)th and k-th are never knight-move reachable, since the column distance is 3 already.

My program is a simple backtrack:

#include <iostream>
#include <cmath>      //abs()
using namespace std;

const int Nmax = 20;
bool row[Nmax], col[Nmax], diag1[2*Nmax], diag2[2*Nmax];
int N;
long long nSolutions = 0;
int Queens[Nmax];

void init(){
    for(int i=0; i < Nmax; i++) row[i] = col[i] = true;
    for(int i=0; i < Nmax;i++)
    for(int j=0; j < Nmax;j++)
        diag1[i+j] = diag2[Nmax+i-j] = true;
}

void putAQueen(int k){ // always put k-th queen at column[k];

    if (k >= N){
        nSolutions++;
       // /* // Printing queens' placement:
        cout <<"Way #"<<nSolutions<<endl;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(j!=Queens[i]) cout <<"+";
                else cout<<"Q";
            };
            cout<<endl;
        }
        cout<<endl;
        //*/
    }
    else{
        for(int i=0; i < N;i++)
            if (row[i] and diag1[i+k] and diag2[Nmax + i-k])   // normal queen
            if (k==0 or (k==1 and abs(Queens[k-1]-i) !=2 ) or 
              (k>=2 and (abs(Queens[k-1]-i) !=2) and (abs(Queens[k-2]-i) !=1))){  // knight move check
                
                row[i] = false;
                diag1[i+k] = false;
                diag2[Nmax+i-k] = false;

                Queens[k] = i;
                putAQueen(k+1);

                row[i] = true;
                diag1[i+k] = true;
                diag2[Nmax+i-k] = true;
            }
    }
};

int main()
{
    init();
    N = 16; // N =15: 32.516 ways; N=14: 5.180; N =16: 202.900 
    N = 17; // N =17: 1.330.622 ways (26 seconds without printing)

    N = 18; // N =18: 8.924.976 ways (190 seconds without printing)

    N = 10;

    putAQueen(0);
    cout << nSolutions << endl;
    return 0;
}

For explanation of how it works, 
you can check this post: capacode.com/?p=682

@demo: N can be big, but the frequency is less than N.
Use hash to compute frequency first. Then use counting sort on frequency.

Counting sort sorts the frequencies of the items, not the value of items. Thus, it takes O(N+maxFreq) time and space.

Note: we can't do better than linear time O(N), since we need to check for each and every item.

Should prove that:
In sorted array A: if exist 3 indices i <=j<=k such that A[i], A[j], A[k] form a triangle, so do A[j-1],A[j],A[j+1].

compute maxDiff first, then check the min:

for (int num: nums) {            
	maxDiff = Math.max(maxDiff, num-min);
	min = Math.min(min, num);
}

I think you should compute the maxDiff before checking the new minFound.

int minFound = inf
int maxDiff = 0
for(int i : array){
	if((i - minFound) > maxDiff) maxDiff = i-minFound;
	if(i < minfound) minFound = i;	
}

Your idea works! Complexity is O(N). Can be implemented with O(1) extra space.

I think you can write pseudo-code, and explain the idea at high level description.

Let minBefore(i) = minimum number in the range from [0, i-1].
This array can be computed in O(N) time.

The answer is maxDiff = max(A[i] - minBefore[i]), which can be computed in O(N) time.

This algorithm can be implemented with O(1) space, and use 1 array scanning.

I think your idea works!

Can improve your answer with a clearer explanation and shorter code?

Maybe: put two zeros "00" in the front of the binary representation...

@xyz: the condition you just added is important.
O(1) solution by Imran Khan works now.

This works for the condition if only one local maxima/minima exists.
We also can check whether there has more than one local maxima/minima in a range [u,v].

My one is backtracking algorithm. It should work very fast.

N 23412367188, result: 13272317
N=93512378880, result: 23452182
N=615954598560, result: 13579246
N=559999999440, result: 12345679

#include <iostream>
#include <set>

using namespace std;
set<int> Result;
set<int>::iterator it;
long long N;

void init(){
    Result.clear();
};


bool check(long long N, long long P){
    long long myP = 1;
    while(N > 0){
        myP *= N%10;
        N = N/10;
    };
    return (P == myP);
}

void findSeed(long long N, long long P){
    //basecases:
    if (P > N) return;
    if (check(N,P)){
        Result.insert(N);
        return;
    }

    //recursive:
    for(int d = 9; d >= 2 ; d--)
        if (0==N%d){
            findSeed(N/d, P*d);
        };
}

int main()
{
    N = 23412367188; // result: 13272317

    init();
    if (N<10) cout <<N<<endl;
    else    findSeed(N,1);

    if (Result.size()){
        cout <<N<<": ";
        for(it= Result.begin(); it!= Result.end(); ++it)
            cout <<*it<<" ";
        cout <<endl;
    }

    return 0;
}

Hi guys:

When you have a list of pairs <item, freq>, the freq is an integer with value at most N.
So, you can sort the list based on freq, using counting sort, with time complexity of O(N+max Frequency).

Pseudo code for sorting the list of pairs <item, freq> is following:

Input: List[]

//counting/distributing:
for i = 1..N
	f = List[i].freq;
	maxF = max(maxF, f);
	Counter[f].push_back(i);	// put the index i into the counter f

//collecting:
for f = 1..maxF	// for each freq f in increasing order from 1 to maxF
	S = Counter[f].size()
	for j = 0..S-1
		index = Counter[f][j];
		NewList.push_back(List[index]);		// collect back the items in increasing order of freq

return NewList;	//Note: this counting sort is not stable. To make it stable, one more array is needed. 

//Complexity: O(N) space, O(N+maxF) time

Radix sort works almost the same, except that it works on each digit/character separately, from the least significant position to the most significant position.
(Each iteration of radix sort is a counting sort)

--ninhnn

Since the frequency is at most N, we can use counting sort with O(N) time.

If we are required to output the items in order of their appearance, stable radix sort with O(N) time will do.

Use a hash to count frequency of each unique number, store them in pairs like (unique_num, frequency).

Then sort the item-frequency pair list, in order of decreasing the frequency, using counting sort.

Complexity:
O(N) time for hashing + O(N+ maxFrequency) time for sorting. Note maxFrequency is <= N.
O(N) space for hashing and storing the frequency pair list.
Thus, overall is O(N) time, O(N) space.

Alternatively, we can consider this problem is to find K most frequent items. It can be done in O(N) as well, see this post for detailed discussion: capacode.com/?p=598

The moving rule is so strict that we can calculate the result without searching for it. See lydiahappycat's solution.

No need BFS in this case.

Not sure whether I understand the problem correctly. Following is my idea:

Let Mx be the maximum length of consecutive number sequence (CNS) that ends at node x.

Then for each child c of x, the Mc - maximum length of CNS that ends at c, is calculated as following:

If the value of c (e.g. 4) is consecutive number after value of x (e.g. 3), then Mc = Mx +1
otherwise, start new sequence at c: Mc = 1.

Time complexity: O(N), N = number of nodes in the tree.

Pseudo C++ code (Recursion):

struct TreeNode{
	int val;
	int maxLen; // Mx -- max length of consecutive number sequence that ends at this node.
	TreeNode* V[]; // all childs
}

void findMaxLength(TreeNode x, TreeNode parent){	
	if (x.val == parent.val +1 ) x.maxLen = parent.maxLen + 1;		
	else x.maxLen = 1;
	
	if (x.maxLen > globalMax) globalMax = x.maxLen;
	
	for each child c of x do 
		findMaxLength(c, x);	
};


main(){
	root.maxLen = 1;	
	globalMax = 0;
	for each child v of root 
		findMaxLength(v,root);
		
	cout <<globalMax<<endl;
}

The best algorithm to find shortest path in this case is BFS.
Start from (1,1), do BFS until reaching the goal.

C++ code (with bugs):

int minStep(int m, int n){
	pair<int,int> Que[MMAX*NMAX];
	int	Dist[MMAX*NMAX];

	bool Visited[MMAX][NMAX] = {false}; //bugs

	Que[0] = make_pair(1,1);
	Dist[0] = 0;
	Visited[1][1] = true;	

	top = 0; last = 0;

	while(top <= last){
		pair<int,int> u = Que[top];
		int x = u.first, y = u.second;
	
		if (x==m and y==n) return Dist[top];

		//right:
		if (x+y<=m)
		if (! Visited[x+y][y]){
			last++;
			Que[last] = make_pair(x+y,y);
			Dist[last] = Dist[top]+1;
			Visited[x+y][y] = true;
		};

		//down:
		if (x+y<=n)
		if (! Visited[x][x+y]){
			last++;
			Que[last] = make_pair(x,x+y);
			Dist[last] = Dist[top]+1;
			Visited[x][x+y] = true;
		};

		top++;
	};

	Return INFINITY; // Can't reach to the goal?
};

How does it work for negative numbers?

I think this works!

Only need to revise the return statement:
return (num<21) ? 1+(num/DIV) : rand7();

@phantomlord: excellent! It works.
Can initiate A[n] = A[n+1] = 0, it also works.

@Scott: m is the size of a column.
Imagine you have m arrays (each of size n), sorted already. You want to merge them into 1 single list.

The heap/priority queue is to store the m front elements of m arrays, initially.

Each time, the minimum element x in the heap is extracted, and put into the final list. Suppose x was come from the array k. Then, the next element of k-th array is inserted into the heap. This process continues until all elements are inserted/extracted to/from the heap.

Each insert/extract_min operation takes O(log m) for the heap of size m. Thus, overall time is: mn O(logm) = O(mn logm).

This algorithm takes O(m) space. In implementation, it takes 3m space for the heap: 1 int for the value, 1 int for the number k (for k-th array), 1 int for the index of next element in k-th array.

In C++ we can use pair of pairs, like pair<int val, pair<int k, int id> > to represent element of heap. This way will work without user-defined comparison function.

This is m-way merging of m sorted arrays. It can be solved using min-heap (priority queue) with size m, in O(mn log m) time.

@phantomlord: why don't you give real code and fix the bug for me :)
Thanks!

Sorry, I got problem with my eye. To get down to 227 bits, need at most 33 bits encode/decode at a time.
You can try my code, add restriction on it (say, send exact K cards at a time)...

@phantomlord: fixed first bug! Thanks!

Second bug: each time the window only moves at most 1 position, thus sum is checking at every position.

Nice answer!

I can get to 227 bits (use at most 32bits to encode/decode), using dynamic programming. Look at my post below for details.