RecruitingForSandvineCanada
BAN USERI'm looking for bright engineers in Ontario, Canada to join us at www.sandvine.com
>Let P(i,j) denote the probability of j heads amongst the coins C_i, C_(i+1), ..., C_(N-1).
In other words, we are trying to eventually determine P(0, K).
Assume the probability of getting a heads for i-th coin is prob[i].
Recurrence:
P(i,j) = prob[i]*( P(i+1, j-1) ) + (1-prob[i])*( P(i+1, j) ) <-- probability theory
Now create a memo over i,j to reduce the runtime to O(numCoins*K).
Bangalore/India too...
- RecruitingForSandvineCanada August 23, 2015Solution:
1) Sort the intervals by END times into a collection S.
2) Remove the first (earliest end time) interval from S -> you will go to that party (count++).
3) Delete all the intervals at the head of S that intersect with the one chosen in 2) as you cannot go to these parties.
4) Go back to 2) in a looping fashion.
Why is this the correct algorithm?
Assume you have a bunch of parties to go to, we are going to prove that we should FIRST pick the one with the earliest end time.
Assume otherwise (for proof by contradiction) that it's advantageous to pick another party... fill in the details.
Sounds good.
- RecruitingForSandvineCanada August 14, 2015This should not be asked in an interview.
There is (IIRC) very very very tricky way to partition an array into two segments while maintaining order, in linear time, and with O(1) extra space.
You could do the above twice to solve this problem in the obvious way.
Oh okay, so the regex has to match the entire string (i.e., as if ^blah$ were used).
- RecruitingForSandvineCanada August 06, 2015void print2ndLast ( Node *head )
{
if ( !head || !head->next ) return; // bad cases
while (head->next->next) head = head->next;
printf("%d\n", head->next->data);
}
cases:
empty
single
two element
long
If it's not a binary tree, just modify this part in the obvious way:
// add children if they exist
if ( root->left ) Q.enqueue(root->left);
if ( root->right ) Q.enqueue(root->right);
// returns the max number of nodes in any level
int levelWithMostNodes( Node *root )
{
if( !root ) // bork out...
queue<Node *> Q;
int currNumInLevel = 0;
int maxNodesAnyLevel = 0;
Q.enqueue(root);
Q.enqueue(NULL); // NULL is a sentinel denoting end of level
while ( ! Q.empty() )
{
root = Q.dequeue();
// if we pulled off sentinel, we finished a level
if ( root == NULL )
{
if ( currNumInLevel > maxNodesAnyLevel ) {
maxNodeAnyLevel = currNumInLevel;
}
if ( !Q.empty() ) Q.enqueue(NULL); //more level(s) to delimit
// reset this as new level starts with next dequeue
currNumInLevel=0;
continue;
}
// an actual node was pulled off...
currNumInLevel++;
// add children if they exist
if ( root->left ) Q.enqueue(root->left);
if ( root->right ) Q.enqueue(root->right);
}
return maxNodesAnyLevel;
}
Doubt there is a known algorithm for NlogN time?
I think this problem can be reduced to 3SUM in both directions, and there is nothing sub quadratic known for 3SUM.
if (A.size() < 2 ) // bad case... or leave this out and let method return -1
minSoFar=A[0];
maxDiffSoFar=-1;
for (int i=1; i < A.size(); i++)
{
maxDiffSoFar = MAX( maxDiffSoFar , A[i] - minSoFar );
minSoFar = MIN ( minSoFar, A[i] );
}
// returns -1 to signal integer array completely decreasing
return maxDiffSoFar;
You sure those are the examples they gave you?
- RecruitingForSandvineCanada August 05, 2015// Original method that is called
int countNumbers(int N)
{
int result[N]; // this works in latest C standard (or malloc/new)
int count=0; // passed by referenced into helper
countNumbersHelper(result, 0, N, count);
return count;
}
int countNumbersHelper(int result[], int posToFill, int N, int &count)
{
// if we have filled N digits into result, then up the count...
if(posToFill = N) {
count++;
return;
}
// if the result array still needs a digit to be filled into 'posToFille'
// ... try all possible digits
for( int i=0; i < 10; i++)
{
if(posToFill == 0 && i==0) continue; // first digit has to be non-zero
//skip if distance to prev. digit < 4
if( posToFill > 0 && abs(result[posToFill-1] , i ) < 4 ) continue;
// Try filling digit 'i' into result and recurse to fill remaining result[ ]
result[posToFill]=i;
countNumbersHelper(result, posToFill+1, N, count);
}
}
Two binary searches? Can you explain?
How would you count frequency of digits?
( There are possibly many overlapping subproblems here, right? ).
Define a shim/API on top of the matrix such that someone can use a single index to treat the elements of matrix as a one dimensional object.
i.e.,
Some map like:
arr(k) = matrix[i][j]
Then sort arr(k) using a regular sorting function.
Now which mapping from k to (i,j) would give the intended result?
We want the matrix to end up being sorted like this, for example with 3x4 matrix, (1, 2, 3, just refer to the order of increasing elements:
13 14 15 16
9 10 11 12
5 6 7 8
1 2 3 4
So the mapping would have to be something like this (assume k, i,j are 0 indexed):
arr(k) = matrix[ k%num_col ][ num_row - (k / num_col) - 1]
If the runtime bigO/bigTheta is denoted with respect to both N and K, then the question seems to me to be impossible to satisfy.
imagine stream like this 0, -1 , -2 , -3, ... (keeps going down)
You cannot make both space O(1) and getMax operation O(1).
Is this for real? I woudl assume Google's hiring committee would have thrown this question out.
- RecruitingForSandvineCanada July 02, 2015convert it into a char array
then
sign=1;
cumulative=0;
BASE=10;
for (int i=0; arr[i] != '\0'; i++) //loop from front until NUL terminator
{
// take care of any preceding signs
if (arr[i]=='+') continue;
if (arr[i]=='-' ) { sign = -1; continue; }
// shift over previous sum by a digit (i.e., multiple by base)
// and current digit to said sum
cumulative = (arr[i]-'0') + cumulative*BASE;
}
return sign*cumulative;
Also, (not important in this small case), Horner's rule might help optimize
- RecruitingForSandvineCanada June 30, 2015What does it return if res == 31 ?
- RecruitingForSandvineCanada June 30, 2015Fisher Yates Shuffle :
for ( i=0; i < A.length -1 ; i++ )
{
j = randInt(A, i, A.length -1);
swap(A, i, j)
}
The -1 on the A.length is not needed, but notice the final iteration if you exclude the -1 does nothing extra vs. the version above (swaps the final element with itself deterministically).
- RecruitingForSandvineCanada June 15, 2015Have two objects refer to each other, and nothing else referring to either of them.
That's a leak.
Ping me for opportunities.
Threads within same process share heap and data segment.
Different process have totally different heap and data segment.
As for stack or code segments.... stack segments are never shared.
Use a LinkedHashSet (non java lovers, read up on it and implement a hash table mapping onto a doubly linked list ).
For opportunities in Waterloo/Toronto, Ontario area, ping me.
SIBLINGS share common parent node.
COUSINS share a common non-parent ancestor node.
FIRST COUSINS share a common parent of parent node.
Email me for opportunities in Toronto/Waterloo, Ontario area.
Use a LinkedHashSet (non java lovers, read up on it and implement a hash table mapping onto a doubly linked list ).
For opportunities in Waterloo/Toronto, Ontario area, ping me.
Use a LinkedHashSet (non java lovers, read up on it and implement a hash table mapping onto a doubly linked list ).
For opportunities in Waterloo/Toronto, Ontario area, ping me.
Use two data structures in tandem:
1) A "move to front" doubly linked list (that is, every time an element is accessed, it gets moved to front of the list.... each node of list represents a page in this case)
2) hash table mapping page identifiers of some sort to references in the double linked list
So here is how things work.
Assume only M pages can exist in the cache.
Now whenever a page is accessed, check to see if it's in the hash table.
Case 1: Cache Miss
----------------------------
If it is NOT, check if number of elements in the LIST is < M.
If it is < M, simply add the element to head of the list, and add corresponding entry in hash table, and move the page into cache.
If we already have M elements in the LIST, we must remove the LRU page.
Use tail pointer to the list and remove the last element there (i.e., delete it from the list, delete it from hash table AND delete the page from the cache itself).
Case 2: Cache hit
-------------------------
Page does exist in hash table. Follow the hash table ("value" is reference to node in doubly linked list) to get the node pointer. Now do some pointer magic to move the node to head of the list.
Everything is O(1).
Email me for opportunities in the Waterloo/Toronto, Ontario area.
Assuming the "ps" on your system required to show all processes of all users is "PSBLAH" and that the kth column is the one that shows memory usage.
(Note k is NOT used as a variable below. Rather it represents a literal number )
Then answer without handling errors is something like this (that is, question is vague, but whatever it is, answer can look like below):
for ip in $(cat $filename); do
echo -n "Memory usage of $process on machine with ip $ip is "
usage=$(ssh $ip "PSBLAH | grep $process | awk '{print $k}' 2>/dev/null )
echo "$usage"
done
Ping me in private if you are looking for opportunities in the Toronto/Waterloo, Ontario area.
- RecruitingForSandvineCanada June 07, 2015And use an unordered_map to prevent dupes from being printed.
e.g., if input was "aaa," this would print a1a twice.
# Assume this is inside a method/function/proc/subroutine/whatever...
# Assume input array is IN and output is OUT
# {In java, we can declare new arrays off heap are zero initialized... assume that or zero initialize it on creation somehow... }
int zeroIndex = -1;
double prod = 1;
# Find zeros in input while accumulating product of
# all non-zero elements
for( int i=0; i < IN.length ; i++ )
{
# Found zero element
if( IN[i] == 0 )
{
# This is second one found, so return OUT as is
if ( zeroIndex >= 0 ) { return OUT; }
# Save spot of zero
zeroIndex = i;
continue;
}
prod *= IN[i];
}
# Case where there was 1 zero...
if ( zeroIndex >= 0)
{
OUT[zeroIndex] = prod;
return OUT;
}
# Calculate output array (in this case, all elements of IN were nonzero)
for( int i=0; i < IN.length ; i++ )
{
OUT[i] = prod / IN[i];
}
return OUT;
Ping me for job opportunities in Toronto/Waterloo area.
- RecruitingForSandvineCanada May 23, 2015O(N) solution:
int i, j;
for ( j=i=arr.length() ; i >=0 ; i--)
{
# Skip over zero elements
if(arr[i] == 0)
continue;
# i landed on index where there is a non-zero element,
# thus copy it back to position j, and move j to next spot to fill.
arr[j] = arr[i];
j--;
}
# Zero fill remaining leading spots in array.
while( j >= 0 )
{
arr[j]=0;
j--;
}
Try using hash tables.
- RecruitingForSandvineCanada August 24, 2015Try sorting one array and binary searching over it.
Runtime you posted in question suggests we have to beat the idea of sorting both arrays.