CareerCup

Yes, that's top-down vs. bottom-up.

Recursive with memoization is never worse than bottom-up DP in running time.
It can save space in many cases.

Yeah, I agree with you.
Also, the next lucky number of empty string should be '4'.

Nice answer!

What if numbers are not distinct then?

Nice idea!
I also think that it will work within the time limit.
+1

However, I think instead of building DP table bottom-up, we can do top-down memoization (with hash table). It may save space...

I think a recursive with memoization solution would do. To save space, memoization can be implemented with hash table.

Pseudo-code may look like:

long long valueOf(long n){

    if (hash[n] != 0) return hash[n];

    if (n<4) return n;

    long long tmp = max(n, valueOf(n/2) + valueOf(n/3) + valueOf(n/4) );
    hash[n] = tmp;	// memoizing the tmp result into the hash.

    return tmp;
};

The hash table once memoized can be used for different function calls, thus it works efficiently for multiple test cases.

Note that, in this case memoization (top-down) may have better space complexity than using DP table (bottom-up).

1. If the input is 77...7 then output 444...44 with an extra digit 4;
2. If the input is a lucky number already: change the last digit 4 in the input into digit 7, and return;

3. If the input is not a lucky number:
Let d be the first un-lucky digit. So the input S can be represented as:
S = lucky_part + d + remain_part

Calculate the next lucky number N as:
if d<4: N = lucky_part + 4 + 44..4
if d<7: N = lucky_part + 7 + 44..4
if d>7: N = nextLuckyNumberOf(lucky_part) + 4 + 44...4
where 44..4 has same length as remain_part

EDITED:
I missed a case: the next lucky number of empty string is '4'

Hi iroodaz,
I found your intuition is correct.

The average path length in a random graph is Lp = ln(N), where N is the number of nodes.
If the graph/network is scale-free (such as internet, social networks, ...), the average path length is 'incredibly short": Lp = ln(N)/ ln ln(N).

You may ask google for: Agata+Fronczak+"Average path length in random networks" to see the proof, which I don't really digest all the maths :))

In this question, can I assume that the sub-graph with A-edge set (or B-edge set) is random? Or since its origin is COMPLETE, it may even be scale-free...

Thus, I can expect the length of the path is less than ln(N).

An other point is that, let k = B/A or A/B, I will never run BFS further than k steps, since after that the resulting path never be shorter than the direct path.

In short, the BFS in this problem is upper bounded by O(m.N), where m = min(k, ln(N))

Further more we can implement an 2-way BFS to further cut down unnecessary search.

P/S: I have another question: Is there any algorithm better than BFS to find a shortest path from u to v in an unweighted graph?

you are correct, thanks!

So, we need to do a BFS on either A-edge set or B-edge set, depends on A<=B or B<=A, and compare the path found with the path going directly from 0 to N-1.

Haha, easy to make mistake then.

looks like an easy question, since your graph is COMPLETE.

1. If A<=B then go directly from node 0 to node (N-1), with a cost of at most A.

2. If A>B:
2.1. Find a shortest path P from node 0 to node (N-1) using only edges in the set "K edges of cost B", using BFS algorithm.
2.2 If cost of P < A, return path P, else go directly from node 0 to node N-1.

So, the question actually asks for BFS algorithm in un-weighted graph.

EDITED:
1. If A<=B: do the same as 2. for the set of cost A edges.

great!
Just O(1) to find the pivot.
After knowing the pivot, things become easy.
+1

Good job!

Your whole idea is the same as pulkit.mehra.001's one.
You choose an efficient heap data structure, with a constant "amortized" time decrease key operation (like Fibonacci heap). Thus, your algorithm is O(k) time, in theory!

However, I think, the most time consuming process is to read in the numbers from files, since reading file takes much more time than doing operations in main memory. That is, reading k numbers takes O(c.k) time, where c is a coeficient for file processing overhead, which is usually very big compared to that for accessing main memory. You may propose O(k) or O(k. log100) algorithms for this problem, but I think the file reading time dominates the algorithm running time. In other words, improving algorithm running time doesn't help much to reduce time for the overall problem.
Although you "abstract" out the files as stacks, you need to read files anyway, isn't it. Your solution (and pulkit.mehra.001's one) requires at most (k+99) times of reading file, which I think is the most efficient already.

In my opinion, this question concerns more about practical issue. Look at the way the interviewer formulated the question: he has a big data file, spitted into 100 files with sorted data... And he asks for "efficient" method, not "optimal" method. This makes me think of a practical issue rather than a pure theoretical problem.

An other point is that, for the solution, we need a heap data structure with a size of just 100, which is fairly small. So which heap implementation is more appropriate, considering the overhead cost for maintaining its structure?
I would say that binary heap is pretty simple yet efficient. It is usually implemented with array. Its simplicity makes the overhead cost negligible. While, for Fibonacci heap (and other theoretically efficient heaps), its complicated implementation may cause a costly overhead, especially for small size (like a size of 100 in this problem).

Anyway, your idea is great!

I have other questions:
1. Can "abstracting" out a file as stack make it faster to read?
2. I've heard of "memory-mapped file". Can it be efficiently used for this problem?

Cheers,

Hi all here!
The original solution of pulkit.mehra.001 is O( k. log100), with at most (k+99) times of reading files.

I think it is the best so far.

Is your solution better than that??

pulkit.mehra.001's solution needs at most (k+99) times of reading file.

I think pulkit.mehra.001's solution, which is O(k log100), is quite efficient already.

It reads the files only k times for k smallest numbers. Reading from file is much slower than accessing ram memory. Thus, I think reading these k numbers, which takes O(c.k) with a big coefficient c, is the bottle neck; O(k log 100) time algorithm for finding the answer is not the bottle neck.

Can you find the k-smallest number in these 100 files with less than k times of reading file?
Can a file be randomly accessed?
IDK!

great job!

If a string contains ":" then your decoder will fail, right?

An implementation in perl may look like:

sub encode{
	my @arrStr = @_;
	$numStr = scalar @arrStr;
	$header = "$numStr "; # a space at last position
	for(int $i = 0; $i <n; $i++){
		$len = length($arrStr[$i]));
		$header = $header ."$len "; # a space at last position
	};
	
	$data = join("",@arrStr);
	
	$encoded = $header.$data;

	return $encoded;
};



sub decode{
	my $encoded = shift;
	($numStr) = split(/\s/,$encoded); 	# first number separated by a space
	$encoded =~ s/^\S+\s*//; 			# delete the first number and a space
	
	@Lens = ();
	for(int $i = 0; $i <numStr; $i++){
		($len) = split(/\s/,$encoded); # length of i-th string;
		push(@Lens, $len);
		$encoded =~ s/^\S+\s//; # delete the number and a space at beginning
	};
	# $encoded now contains only data;
	
	my @arrStr = ();
	for(int $i = 0; $i <numStr; $i++){
		$aStr 		= substr($encoded, 0, $Lens[$i]);	
		$encoded 	= substr($encoded, $Lens[$i]);
		push(@arrStr, $aStr);
	};
	
	return @arrStr;
};

# code isn't debugged!

I think the question asks how to encode a vector of string into a string, and decode the encoded string back to the original string array. So, the hard part is how to decode back...

My approach:
I need to add a "specifically formatted header" into the resulting string, like

resultString = [header][data-from-array];

The header must help us to decode back the data.

So, my header should contain following information:
1. number of strings in the array;
2. length of each string;

Format of the header may look like this:

header="n <space> L1 <space> ... Ln <space>"

where n = number of strings in the array; Li = length of i-th string;
Note: each field of header is separated by EXACTLY 1 space.

Example:

V = { "First", "2nd String", "Last"};
S = "3 5 10 4 First2nd StringLast";

How to DECODE it back?

1. Read n = the number of strings as the first integer in S;
2. Read next n integers L1, L2, ..., Ln;
3. Read from the data field n strings each of length L1, L2, ..., Ln, respectively.
4. Form the array of strings...

how to read it back?

Then you have to sort the input string first, then modify the code not to repeat previous character... A modification can be following (i write in C++)

public void 
permutation(String prefix, String str) {	// str must be sorted first!
	int n = str.length();
	if (n == 0)
		System.out.println(prefix);
	else
		for(int i = 0;i < n;i++){
			if ( i>0 and str.charAt(i) == str.charAt(i-1)) continue;
			permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));      
		}
};

// code in C++:
sort(inputStr.begin(), inputStr.end());

permutation("", inputStr);

What will be the output for a given string "aaa"?

Literally, your description can be translated into Perl code as the following:

#! perl -w

#Paths may not exist!
$absolutePath = "/usr/bin/mail";
$relativePath = "../../../etc/xyz/../abc";

$myPath = $absolutePath ."/". $relativePath;
@myPath = split(/\//,$myPath);

@finalPath = ();
foreach (@myPath){
	if (/\Q..\E/){	# go up 1 level
		pop @finalPath || die "ERROR: Wrong inputs\n";		
	}
	else{
		push @finalPath, $_;
	};
};

$res = join("/",@finalPath);
print $res ."\n";

haha, I choose Perl to implement this:

$exp = q(^ab..*abc$);
$test = q(abyxxxxabc);

print "$exp, $test, " . evaluate($exp, $test)."\n";

sub evaluate{
	my $Exp = shift;
	my $testCase = shift;

	return "false" if ($testCase !~ /^[a-z]+[a-z]$/);	# contain only character in [a-z]?

	if ($testCase =~ $Exp){
		return "true";
	}
	else{
		return "false";
	}
};

Code not checked:

string reverseLettersOnly(string S){
	int start = 0, end = S.length()-1;
	while(start < end){
		while((start <S.length()) and (0 <= S[start] - '0') and (S[start] - '0' <=9)) start++;
		while((end  >=0) and (0 <= S[end] - '0') and (S[end] - '0' <=9)) end--;
		if (start <end) swap(S[start], S[end]);
		start++;
		end--;
	};
	return S;
};

@nomad_coder: thanks! My solution is wrong for the original problem.

it looks correct, but idk. I up-vote yours for people to look at it.

My solution may work for the constraint that:
"Only combination of two CONSECUTIVE sticks is allowed"

Sorry!

EDITED: there is flaw in my post! The order of sticks matters!

Re-formulate the problem:

Given n sticks of length L_1, L_2, ..., L_n, with total length of L.
Only combination of two sticks into one is allowed each time. Every combination costs the sum of the two sticks.

Calculate the minimum cost to combine all n sticks into a stick of length L.

This can be solved by recursive/DP as following.

Let C(u,v) be the minimum cost to join sticks from number u to number v.
The recursive formula will be:

C(u,v) = min { C(u,k) + C(k+1,v) }, for k = u+1 to v-1;

The answer will be C(1,n).

My pseudo code implementation using recursive with memoization:

joinSticks(u,v):

if (u == v) return L[u];
if (Mem[pair(u,v)] != 0 ) return Mem[pair(u,v)];

minCost = maxInt;
for k = u to v-1
	minCost = min { minCost, joinSticks(u,k) + joinSticks(k+1,v) };

Mem[pair(u,v)] = minCost;

return minCost;

The expected number of boys is 1, since they keep making babies until getting a boy :)

The expected number of children is C = 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...

With some tricks we can find that C = 2.

Thus in average each family have 2 children, 1 boy, 1 girl!

Tricks:

C 	= 1/2 + 2/2^2 + 3/2^3 + ... + k/2^k + ...
2C 	= 1 + 2/2 + 3/2^2 + ... + k/2^(k-1) + ...
 	= 1 + (1/2+1/2) + (2/2^2 + 1/2^2) +...+ {(k-1)/2^(k-1) + 1/2^(k-1)} +...
	= {(1 + 1/2 + 1/2^2 +...+ 1/2^(k-1) +...}  +  1/2 + 2/2^2 +...+ (k-1)/2^(k-1) +...
	= 2 + C
=> C = 2

I like this answer the most! Thanks!

bfs...
initiate the queue with all "G" cells.

balanced heap is not a balanced binary SEARCH tree, i believe

Maybe should count by this way:
First 5 coins: 2^5 sums, including 0-sum;
Last 3 coins: only 7 sums (instead of 8), including 0-sum;
Total: 7 * 2^5

Look at first 5 coins (5ruppes,1rupees,50paisa,25paisa,10paisa): none of them can be formed by sum of any subset of others 7 coins. Easy to check that since coin[i] > coin[i+1] + coin[i+2], for i = 1..5
Thus, using first 5 coins we can form 2^5 -1 none zero sums.

For last 3 coins (3paisa,2paisa and 1paisa): we can form only 6 different none zero sums, that is, 1, 2, 3, 4, 5, and 6.

So, the total number of sums can be formed is 6 * (2^5-1) + 6 + (2^5-1) + 1 (for zero-sum).

Please tell me if I am wrong! Thanks!

If we know the size of the dictionary then a straight forward BINARY SEARCH is perfect enough.

If we don't know the size, instead we're only given the query method, then we need to find the index range [st, ed] first, where getWord[st] < theGivenWord < getWord[ed], by REPEATED DOUBLING.
So, try to query at index 1, 2, 4, 8, 16, ..., 2^k,... and find the [st, ed].

After knowing [st,ed], do binary search...

The overall time is O(logn) still.

So, in interview we should use a straight forward approach, right? Is a trickery approach more impressive? Thanks!

Nice idea! O(n) time and O(1) extra space!

Here is a modification:

#include <iostream>

using namespace std;

static long long num = 0;
long long memo[150];

static void jump(int left) {
        if (memo[left]!=0){
            num += memo[left];
            return ;
        }
        if (left == 0) {
                num +=1;
        }
        else if (left < 0) {
                return ;
        }
        jump(left - 1);
        jump(left - 2);
        memo[left] = num;
}

int main() {
        jump(122);
        cout << num << endl;
        return 0;
};

The number of ways to jump to n steps is the n-th Fibonacci number!

F[n] = F[n-1] + F[n-2];
F1 = 1; F2 = 2;

How long does your code take to run for, say, n = 50?

If the space looks ugly then trim them all first.

First, I reverse the whole string: "I am bad" -> "dab ma I"
Then I reverse each word: "dab ma I" -> "bad am I"

Code may look like this:

// reverse word order in a sentence:
// "I am bad" -> "bad am I"
// NNN

#include <iostream>
#include <string>
using namespace std;

string reverseStr(string S, int u, int v){
    for(int i = 0; i<(v-u+1)/2;i++){
        swap(S[u+i],S[v-i]);
    };
    return S;
};

string reverseSentence(string S){
    int st=0, ed=0;
    int len = S.length();
    S = reverseStr(S,0,len-1);
    while(st<len-1){
        while((st<len) and (S[st] == ' ')) st++;
        ed = st;
        while((ed<len) and (S[ed] != ' ')) ed++;
        ed--;
        //cout <<st<<" "<<ed<<endl;
        S = reverseStr(S,st,ed);
        //cout <<S<<endl;
        st = ed+1;
    };
    return S;
};

int main()
{
    string sentence = " This is a sentence with  multiple spaces  .  1 22 333 4444  ";
    string reversed = reverseSentence(sentence);
    cout <<"Original sentence:["<<sentence<<"]\n";
    cout <<"Reversed sentence:["<<reversed<<"]\n";
    return 0;
}

Your algo is O(b): every time you decrease b by 3,4 or 5, you perform 3,4 or 5 MULTIPLY operations...

In fact, your solution is wrong! Example pow(2,6) should give 2^6, while your function gives 2^9.