JeffD
BAN USERC++, Linux guy
- 0of 0 votes
AnswersGiven 2 equal-length arrays of integers, find pairs, one from each array, that sum to 0.
- JeffD
-- note that one wrinkle of this problem over the more usual form, which is to do this in a single array, is that you can't use the indexes / iterators crossing each other to know to stop, rather their /values/ have to cross (if you're doing it right, at or near 0).| Report Duplicate | Flag | PURGE
PayPal Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat's an efficient way to process a large file, with lines of varying length?
- JeffD
-- I said, break it up and process the pieces in parallel, using fseek to divide up the file, and scan backward and forward for the line terminators to decide which chunk a line belongs to. I think the answer he wanted though was to memory map it.| Report Duplicate | Flag | PURGE
PayPal Software Engineer / Developer Operating System
Well that should work if you wrap num_threads in a mutex; but otherwise you can get your threads incrementing it at the same time, and writing back a value of 1.
Also, you give too many wakeups. You'd want to give num_threads - 1 wakeups (V(barrier)s), because the last thread doesn't need to wait. For that same reason it also doesn't need to increment num_threads to know whether it's the last thread (unless there are other threads coming along behind it, ie you're releasing 'batches' of N threads at a time).
... which yields:
1 Regular file
(the following are all 'special')
2 Directory
3 Symbolic link
4 Named pipe
5 Socket
6 Device file
7 Door -- Solaris only
(What about hard links? Wikipedia's hard link page says that that is a special kind of file, too. Hum. Is Wikipedia wrong to omit it?)
In Unix at least, links can make cycles.
Also you say 'DAG' but, that technically could mean multi-rooted. AFAIK Unix systems are singly-rooted; everything, mounted or otherwise, is somewhere below '/'. I suppose Windows might be considered multi-rooted (fully 'DAG'), with a 'root' per drive.
Between mergesort and quicksort I'd vote for quicksort, because it's in-place as someone has already said, and because it's recursive, and so (I'm mostly guessing) has better cache behavior. Definitely C++'s std::sort is better than C's qsort because with qsort the values are passed via void*, ie you lose the type information, meaning the compiler misses possible opportunities to optimize. Also, C++'s sort is a template, it's possible that the comparison functor will be inlined, something that's not possible with C's qsort. All of this is in Stroustrup's blue book, where he discusses std::sort.
- JeffD October 08, 2010This is nothing; it shouldn't, and doesn't compile because the signatures are not different.
ret-type-only-differs.cpp: In function ‘char A()’:
ret-type-only-differs.cpp:12:8: error: new declaration ‘char A()’
ret-type-only-differs.cpp:6:5: error: ambiguates old declaration ‘int A()’
extern in front of a function prototype is a no-op (it makes no difference); it's all just declaration (apart from 'extern "C" ' forms, that is). extern makes a difference for variables only.
int x; // defined, ie allocated space, here.
extern int y; // declared here - we know there's a y that's an int that we can expect at link time.
// this link says as much, by its silence. I've found the site reliable.
***.cppreference.com/wiki/keywords/extern
And, you can have as many declarations of the same function as you like (for convenience with header files) so, having 2, one with extern and one without really makes no difference.
dfmcla's Feb 28: "This will compile with both statements because the local declaration shadows the scope of the external declaration." - no shadowing happens, the 2nd is just an extra declaration. The compiler will nod, shrug and continue.
Mmmm, yes, I just did that:
# 'bad', '< 5' and 1000 samples
jd@shade:~/projects/interviewQs$ ./rand7
148 156 133 153 135 132 142
and you're right, about the same 'uniformity', by eyeball, as my results above. Neither of them great. But, at 100,000,000 either it's somehow bad luck (but shouldn't be, at 100,000,000) or, I'm right.
# bad; '< 5', 100,000,000
jd@shade:~/projects/interviewQs$ ./rand7
14402060 14431600 14399214 14272500 14112046 14076142 14115245
# good; '< 7' 100,000,000
jd@shade:~/projects/interviewQs$ ./rand7
14306739 14302342 14277656 14270321 14259744 14282261 14300937
# quite a bit more uniform. So, it's a bad test, not a bad algorithm, as far as I can see. Although I'm puzzled, I would have thought the balance would have been much worse.
What I'm going for, is that if you just try to make the number fall between [1..7] that's easy, just add 2 rand5()s together and % 7, + 1. But you'll get the result hitting the lower numbers more often, as the 8,9,10 wraps around to 1,2,3. I'm trying to get rid of the '5-ness' by adding 7 of those random 1..5 numbers together. Perhaps what I was thinking was / 5, not % 7. Though % 7 seems to work ok, perhaps it's equivalent (you'd have to correct what you do with the rand5()s a bit to use / 5. Still, not sure it's right).
Quite nice, and simple. It's equivalent to the HCA (LCA?) Highest Common Ancestor in trees.
There are simpler ways to find /that/ the two are linked but, if it's a singly-linked list, and given that we have to find the point of intersection, this seems simple, and good.
<pre lang="c" line="1" title="CodeMonkey4069" class="run-this">
// A problem with a lot of the solutions above, is that the resulting distribution won't be uniform.
// This is crude, but should be uniform.
#include <stdlib.h>
#include <stdio.h>
int rand5()
{
return (rand() % 5) + 1;
}
int rand7()
{
// cancel out all the +1s at once
int x = -7;
int i;
for (i = 0; i < 7; ++i) {
x += rand5();
}
// now have a number between 0 and 28.
x %= 7;
x += 1;
return x;
}
int main()
{
int dist[7] = {0};
int i;
for (i = 0; i < 1000; ++i) {
dist[rand7()-1]++;
}
for (i = 0; i < 7; ++i) {
printf("%d ", dist[i]);
}
printf("\n");
return 0;
}
jd@shade:/mnt/raid/projects/interviewQs$ ./rand7
137 156 157 140 132 148 130
-- seems relatively even
</pre>
- JeffD September 16, 2010#include <stack>
#include <iostream>
using namespace std;
typedef stack<int> Stack;
void push_to_bottom(Stack& stack, int x);
void reverse(Stack& stack)
{
if (!stack.empty()) {
int x = stack.top();
stack.pop();
reverse(stack);
push_to_bottom(stack, x);
}
}
void push_to_bottom(Stack& stack, int x)
{
if (stack.empty()) {
stack.push(x);
}
else {
int y = stack.top();
stack.pop();
push_to_bottom(stack, x);
stack.push(y);
}
}
// destructive
void dump_stack(Stack& s)
{
while (!s.empty()) {
int i = s.top();
s.pop();
cout << i << ' ';
}
cout << endl;
}
int main()
{
Stack s;
// 5 at bottom
s.push(5);
s.push(4);
s.push(3);
s.push(2);
s.push(1);
reverse(s);
dump_stack(s);
}
jd@shade:/mnt/raid/projects/interviewQs$ ./swap-stack-recursively
5 4 3 2 1
Prateek you had it apart from small errors.
If we were allowed to use 'size()', we could have done a loop at the top, popping off the top, and pushing it to the bottom, size() times. But this way it's pure recursion.
Not d. According to Herb Sutter, once and again chairman of the C++ standards committee, in his book 'Exceptional C++ Style', pg 192, he says: "The inline keyword is not required to have any semantic effect on a C++ program. It doesn't affect other parts of the standard language, in that writing inline on a function does not change how you use the function (for example, /you can still take the function's address/).. ". (Emph. mine.)
- JeffD September 13, 2010
This isn't safe. One of the threads might have seen and incremented the count, decided it has to wait, but gets suspended by the OS before it gets to wait on the condition. The 'last' thread comes through and broadcasts the wakeup to everyone on the condition. The 'slow' thread then finally gets there, but the signal has missed it - signals apply only to threads that are already there. So it waits forever. You have to use a semaphore, which will safely, atomically etc, keep a count.
- JeffD October 11, 2010