ninhnnsoc
BAN USER
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?
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.
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,
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!
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...
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);
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;
};
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
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.
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;
};
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;
}
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
RepNelson Perez, Software Engineer
Repaliciagreene771, Vashikaran mantra for get my love back at None
Hello! How are you,My name is Alicia Greene I am from London (UK). I am a Business English, Math ...
RepNoahTaylor, abc at A9
Accomplished software developer with many years of experience in development of applications. Excels in every stage of the life cycle ...
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
Replamisobbeya45, Student at None
Hello there, My name is Lamis Obbeya I am from Brooklyn, New York . I am 29 years of age. I ...
RepAugment is a mobile app that lets you and your customers visualize your 3D models in Augmented Reality. If you ...
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
Repmorganweiler771, Employee at None
Hello Everyone, I am Morgan Weiler I am from Mumbai, (India).I enjoy Watching TV, playing guitar, Yoga and reading ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
Rep
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easy-bake-ovens in Fort Walton ...
RepDo you want to marry with your desired person? The Islamic dua for marriage with a loved one has great ...
RepCeliaParker, teacher at Illinoisstate
Experienced teacher with a background in education who is looking to complement graduate studies with the opportunity to teach at ...
Yes, that's top-down vs. bottom-up.
- ninhnnsoc April 18, 2014Recursive with memoization is never worse than bottom-up DP in running time.
It can save space in many cases.