CareerCup

@sumit: the question says that only 1 number is repeated n times.
In your test case, 3 and 2 are repeated.

Maintain a bitset of size(7*24*60*60) i.e. num of seconds in a week.
Now, for each interval, mark these bits true.

In the end, if all bits are 1, then the entire week is covered, else not.

Assuming the input to be number of seconds since Sunday 00:00:00, there will be 2
Special cases:
1. an interval spans more than a week, we need to immediately return true.
2. an interval starts at let's say friday and ends on tuesday next week.
For this, we need to set bits for friday-saturday night, and shift offsets of sunday-tuesday by 7*24*60*60

void findPairThatSumsCloseToZero(vector<int> a)
{
    int i, j, best, cur_best, n = a.size();
    int best_start, best_end;
    if (n < 2) return;

    sort(a.begin(), a.end());
    i=0, j=n-1;
    best = a[i] + a[j], best_start = i, best_end = j;

    while (i < j) {
        cur_best = a[i] + a[j];
        if (abs(cur_best) < abs(best)) {
            best = cur_best;
            best_start = i, best_end = j;
        }

        if (cur_best < 0) {
            i++;
        } else if (cur_best > 0) {
            j--;
        } else {
            break;
        }
    }

    printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}

void findPairThatSumsCloseToZero(vector<int> a)
{
    int i, j, best, cur_best, n = a.size();
    int best_start, best_end;
    if (n < 2) return;

    sort(a.begin(), a.end());
    i=0, j=n-1;
    best = a[i] + a[j], best_start = i, best_end = j;

    while (i < j) {
        cur_best = a[i] + a[j];
        if (abs(cur_best) < abs(best)) {
            best = cur_best;
            best_start = i, best_end = j;
        }

        if (cur_best < 0) {
            i++;
        } else if (cur_best > 0) {
            j--;
        } else {
            break;
        }
    }

    printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}

DUP of 13467664

string addBinaryStrings(string a, string b)
{
    string c;
    int carry = 0;
    int lena = a.length(), lenb = b.length();
    int i=lena-1, j=lenb-1, k=max(lena, lenb)-1;

    c.resize(k+1, '0');

    while (i>=0 && j>=0) {
        c[k] = ((a[i]-'0') ^ (b[j]-'0') ^ carry) + '0';
        carry = (carry + (a[i]-'0') + (b[j]-'0')) > 1 ? 1 : 0;
        i--,j--,k--;
    }   

    while (i>=0) {
        c[k] = (carry ^ (a[i]-'0')) + '0';
        carry = (carry+(a[i]-'0')) > 1 ? 1 : 0;
        i--,k--;
    }   

    while (j>=0) {
        c[k] = (carry ^ (b[j]-'0')) + '0';
        carry = (carry+(b[j]-'0')) > 1 ? 1 : 0;
        j--,k--;
    }

    if (carry) return "1" + c;

    return c;
}

bool isReachable(int a[], int n)
{
    int maxwecango = a[0];
    int i = 1;
    
    if (n == 1) return true;
    if (n < 1) return false;
    
    while (i <= maxwecango) {
        if (i == n-1) return true;
        
        if (i+a[i] > maxwecango) {
            maxwecango = i+a[i];
        }
        
        i++;
    }
    
    return false;
}

Very nice approach!

But it fails for the following boundary case:
A[] = {0}

@gevorgk: Awesome!!

@Kim: Because 2D array reserves O(r*c) space even if we will be using only few cells(as it is sparse)

void printLongestSubstringOfUniqueChars(const char *s) 
{
    int i, j, map[256] = {0};
    int n = strlen(s), overall_best = 0, cur_best = 0, overall_offset=0, cur_offset = 0;

    for (i=0; i<n; i++) {
        if (map[s[i]] == 0) {
            map[s[i]] = 1;
            cur_best++;
            if (overall_best < cur_best) {
                overall_best = cur_best;
                overall_offset = cur_offset;
            }   
        } else {
            for (j=cur_offset; j<i; j++) {
                map[s[j]] = 0; cur_best--;
                if (s[j] == s[i]) {
                    j++; break;
                }   
            }   
            cur_offset = j; map[s[i]] = 1; cur_best++;
            printf("cur_offset became %d\n", cur_offset);
        }   
    }   

    printf("ans: ");
    for (i=overall_offset; i<overall_offset+overall_best; i++) {
        printf("%c", s[i]);
    }   
    printf("\n");
}

#include <stdio.h>
#include <stdlib.h>
#define INF (~0)

/* This can be optimized by caching */
unsigned int stick_length(int sticks[], int s, int e)
{
    unsigned int i, ans = 0;
    
    for (i = s; i <= e; i++) {
        ans += sticks[i];
    }

    return ans;
}

unsigned int join_sticks(int sticks[], int s, int e, unsigned int **cache)
{
    int k, p1, p2, tmp;

    if (s > e) return INF;
    if (s == e) return sticks[s];

    if (cache[s][e] != INF) {
        return cache[s][e];
    }

    for (k = s; k < e; k++) {
        p1 = join_sticks(sticks, s, k, cache);
        p2 = join_sticks(sticks, k+1, e, cache);

        /* adding stick lengths, not same as making cost */
        tmp = stick_length(sticks, s, k) + stick_length(sticks, k+1, e);

        /* adding making cost */
        if (k > s) tmp += p1;
        if (k+1 < e) tmp += p2;

        if (tmp < cache[s][e]) {
            cache[s][e] = tmp;
        }
    }

    return cache[s][e];
}

int main()
{
    int i, j;
    int sticks[] = {24, 25, 28, 4, 6, 10, 9};
    // int sticks[] = {2, 3, 4, 6};
    // int sticks[] = {2, 3, 4, 6, 7};
    // int sticks[] = {13, 4, 6};
    int n = sizeof(sticks)/sizeof(sticks[0]);
    unsigned int ans;

    unsigned int **cache;
    cache = (unsigned int **)calloc(n, sizeof(int *));
    for (i = 0; i < n; i++) {
        cache[i] = (unsigned int *)malloc(n*sizeof(int));
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cache[i][j] = INF;
        }
    }

    ans = join_sticks(sticks, 0, n-1, cache);
    printf("ans: %u\n", ans);

    return 0;
}

/* 
 * Find if any anagram of a, is present as a substring in b.
 * Returns offset of string b, where anagram can be found.
 * Otherwise: Returns NULL
 */
char * find_anagram(char *a, char *b)
{
    if (!a || !b) return NULL;

    int     i, j;
    int     offset     = 0;
    int     alen       = strlen(a);
    int     blen       = strlen(b);
    char    hash[256]  = {0};

    for (i = 0; i < alen; i++) {
        hash[a[i]]++;
    }

    for (i = 0; i < blen; i++) {
        /* If char available, decrement count,
         * return if this was the last character to match
         */
        if (hash[b[i]] > 0) {
            hash[b[i]]--;
            if (i-offset+1 == alen) {
                return b+offset;
            }
        } else { /* If character not present OR if character exhausted,
                  * then remove the prefix starting from offset, until we
                  * find first character with the same value as current character
                  * i.e. b[i], At that point, move answer(offset) further.
                  * Example: a = "pqrp"; b = "rqpqpptpqprz";
                  */
            for (j=offset; b[j]!=b[i]; j++) {
                hash[b[j]]++;
            }
            offset = j+1;
        }
    }

    return NULL;
}

Is it possible to do this with recursion and still get O(N^3) complexity?

@BIN: this case will be covered by existing conditions.

#include <stdio.h>
#include <string.h>

#define FALSE 0
#define TRUE  1

typedef unsigned char BOOL;

typedef struct {
    char *input;
    char *pattern;
} test_case;

BOOL regex_match(char *s, char *p)
{
    if ((!s[0] && !p[0]) ||
        (!s[0] && p[0] == '*' && !p[1])) {
        return TRUE;
    }

    if (p[0] == '?' || p[0] == s[0]) {
        return regex_match(s+1, p+1); 
    }

    if (p[0] == '*') {
        return regex_match(s, p+1) || // ignore the '*' completely
               regex_match(s+1, p);   // '*' in pattern consumes s[0]
    }

    return FALSE;
}

int main()
{
    int i;
    test_case tc[] = {
                        {"abcd","abdd"},
                        {"abcd","abcd"},
                        {"abcd","ab?d"},
                        {"","?"},
                        {"ab","?*"},
                        {"a",""},
                        {"","a*b"},
                        {"","****"},
                        {"","*c"},
                        {"",""},
                        {"","*"},
                        {"acfdfcdcdcd","a*cd*cd"},
                        {"abdfpdcdcd","ab*cd"},
                        {"abdfpdcdcd","ab*"},
                     };

    for (i=0; i<sizeof(tc)/sizeof(tc[0]); i++) {
        if (TRUE == regex_match(tc[i].input, tc[i].pattern)) {
            printf("\"%s\" matches \"%s\"\n", tc[i].input, tc[i].pattern);
        } else {
            printf("\"%s\" doesn't match \"%s\"\n", tc[i].input, tc[i].pattern);
        }
    }

    return 0;
}

Maintain a hashmap, where key is the sorted line.
e.g if a line is "3 2 6 1 4", it will be treated as "1 2 3 4 6" in hashtable.

Now, for each line:
1. sort it
2. lookup in hashmap
3. if it is not present, then enter it in hashmap and output it
4. if it is present, then don't do anything and continue to next line.

This code doesn't even compile, and after fixing it, it doesn't solve the following inputs:
1100101
12344680
1299111210

Awesome solution @JancoderSS

It can be due to many reasons e.g.:

1. Memory pressure, vmsize limit reached, connection limits or open file handle limits
2. Network is unreliable
3. Hardware Failure
4. Using Debug v/s regular binary
5. Race conditions (no locks in multi-threaded program)
6. Dynamic Backend(e.g. no. of nodes in a social graph can increase/decrease)
7. Memory leaks.
8. Bugs in shared memory code/data
9. Time Difference b/w your node and another server.
10. Timeouts/ Max Time to Live expired e.g. Session Expiration

What is 'k' here?

Different solutions:

a) Sort the array of strings
b) Put each string in a Set
c) Put each string in a HashMap
d) Construct a Trie from array of strings.

@siva.sai.2020, your solution works only if n is an integer.
It doesn't work if n needs to be 1.5 years e.g.

1) How to find intersection across 'N' sorted arrays:

We can make use of a min-heap.
Insert all A1[0],A2[0],...,An[0] in min-heap.
while min-heap is not empty, keep removing a document id from it.
Then increment the Ai from which this element came.

Whenever we find the same document id popping out 'N' times successively,
that implies that it is present in all the documents.

The idea is similar to merging 'N' sorted arrays.

2) Improvements when one array is small and other is relatively bigger.
Search each element of smaller Array in the bigger one.
complexity: O(m logN) where m<<N

3) Distribute computation across set of machines:
Assuming there are 'M' machines available:

assign N/M (provided M < N) arrays for finding intersections to each of them.
Now wait for each machine's intersection list.

Repeat the same distribution steps, until you get one final list i.e. list of document ids.
Each doument id in this list will contain all the search terms.

@Nova2358 : Can this be done using recursion instead of using explicit stacks,
like the regular BST traversal works.

@gavinashg:
I think it's because we want to minimize cube of empty spaces throughout the paragraph of lines.

Greedy doesn't guarantee that.

@Saimok : Nice!

@lucas.eustaquio:
Nice work! But, it only works on the assumption that arrays A, B, C are sorted.
If that is not the case, then we will have to do a stable sort on these arrays
and store them in aux array taking O(|A| + |B| + |C|) space.

I thought on the same lines.
But I think we can do it in O(|A| + |B| + |C|) time.
This is because the values are already sorted.
We just have to think in terms of a window which contains atleast 1 element
from A,B,C

I think the example states incorrectly that circles whose center is at (0,0) and (0,1)
intersect. Since second circle's radius is 5, and first one's is 1, they don't intersect.

You would also need to have a Hash Table, otherwise how would you know
which BST facebook.com currently belongs to.
i.e. if facebook.com has been visited 4 times(therefore present in BST with key=4), and now we get another visit, how would we know that we have to move it from BST with key=4 to BST with key=5.
That can be achieved with Hash Table, storing a count for each webpage for that particular day.

- Arrays provide contiguous memory, while LL doesn't
- Element at a particular index in an array can be accessed in O(1), for LL it is O(N)
- Adding/Deleting element from the middle in an array is O(N), however for LL it is O(1)
due to rearranging of pointers.
- Arrays are limited due to memory constraints of contiguous allocation.
Linked Lists have no such constraint.

what is the time granularity of one index of the circular array?
Is it no. of connections in one sec or one minute?

Return HTTP 302 Redirect Response, and specify the other data center as the
new target address.

When the client gets the HTTP reply, it will send the request to the second data center
and it will know how to resolve it.

- Show road delays due to accident/fire etc.
- Speed
- Offline Access
- Live Street View
- Traffic updates for commonly traveled paths saved by a user e.g. commute to office/school etc.
- Should highlight recent places visited by Friends
- Support for checking out shops, parks, etc. online via Street View
- Highlight alternate routes in different colors based on travel time, toll, miles etc, no. of red lights etc.
- Show recently searched directions for a particular user
- Show commonly taken paths in a specific area(zipcode, city, state)

Idea is similar to finding majority element in an array.

Let 'x' be the element present 'n' times in the array.
We'll compare 2 consecutive array indices at a time e.g 0,1 2,3 4,5 and so on.
If any of these comparisons finds two matching numbers, then that is our answer.

However there is a corner case where 'x' is present alternately
e.g. x1x2x3x4x5x6x7x8x9xA....
In this case, at the end of 'n' comparisons(see above step), we won't be finding any match. Now, if we compare the last four elements, we are guaranteed to find two x's.
We don't need to scan the whole array as wenlei.zhouwl mentioned.

Few ideas:

- Find people who are common friends to your friends.
Let's say you have 50 friends, a person who is friends with most of these,
is highly likely to be known to you as well.

- Friend suggestion could also be determined from the communities/groups/interests/places
you are part of.

- Photographs tagged with many people including you, can offer very good
friend suggestions.

We can have a number of systems serving a range of key-val pairs.
Periodically, each system will broadcast its range of keys served to other systems.
A client can connect to any system to get the value for a key.
If that particular server doesn't have the answer, it can redirect the client to the
appropriate system.

LinkedHashMap

typedef struct
{
    Mutex m;
    int reader_cnt; // initialize to 0, 0 means available for reader or writer
                    // -1 means taken by a writer
                    // >0 means taken by readers
} RWLock;

int read_lock(RWLock *lock) 
{
    int res = 0;
    MutexLock(lock->m);

    if (reader_cnt == -1 ) // taken by writer
    {
         MutexUnlock(lock->m);
         return -1;
    }

    reader_cnt++;
    MutexUnlock(lock->m);

    return res;
}

int read_unlock(RWLock *lock)
{
    int res = 0;
    MutexLock(lock->m);
     
    if (reader_cnt < 1) {
        MutexUnlock(lock->m);
        return -1;
    }

    reader_cnt--;
    MutexUnlock(lock->m);
    return res;
}

int write_lock(RWLock *lock)
{
    MutexLock(lock->m);

    if (reader_cnt != 0) // taken by other readers or writer
    {
         MutexUnlock(lock->m);
         return -1;
    }    

    reader_cnt--;
    MutexUnlock(lock->m);

    return 0;
}

int write_unlock(RWLock *lock)
{
    MutexLock(lock->m);

    if (reader_cnt != -1)
    {
         MutexUnlock(lock->m);
         return -1;
    }

    reader_cnt = 0;
    MutexUnlock(lock->m);

    return 0;
}

No need to have 2 mutex.

Another approach as opposed to swapping is to make
index A[i]-1 -ve for each 1<=A[i]<=N

Then we can scan the +ve portion of the array to find out the first index which is non-negative. Now we can declare the answer as index+1.
If all indexes are -ve, then N+1 is the answer.

Can you please explain how and why this algorithm works.
Thanks

typedef struct ternary_node {
        node *left, *middle, *right;
        char data;
    } node;

    static int cursor = 0;
    node* preorder_to_tree(char *preorder)
    {
        node *r = new_node(preorder[cursor]);
        if (!r || !preorder) return NULL;

        /* return directly from Leaf Node */
        if (preorder[cursor] == 'l') {
            return r;
        }

        r->left   = preorder_to_tree(++cursor + preorder);
        r->middle = preorder_to_tree(++cursor + preorder);
        r->right  = preorder_to_tree(++cursor + preorder);

        return r;
    }

    node* new_ternary_node(char c) {
        node *tmp = malloc(sizeof(node));
        if (tmp) {
            tmp->data = c;
        }

        return tmp;
    }

/* complexity O(m+n) */

/* k is the key to search */
bool_t search_element_in_sorted_2d_array(int *arr, int m, int n, int k)
{
    int row=0, col=n-1;
    int current;

    do {
        current = arr[n*row+col];

        if (current > k) { /* discard column, decrease column */
            col--;
        } else if (current < k) { /* discard row, increase row */
            row++;
        }
    } while ((row < m && col >= 0) && (k != current));

    if (k == current) {
        printf("Found element %d at arr[%d][%d]\n", k, row, col);
        return TRUE;
    } else {
        printf("Could not find element %d\n", k);
        return FALSE;
    }
}

Each robot will have a starting position.
One starting position would be on left and the other is on right.
Therefore, we can let both robots move right until it reaches other's starting
position. As soon as a robot reaches other's starting position, it would double
its speed. Thus, eventually they will meet.

while (robot_current_posn != other_robot_starting_posn
       && two_robots_meet() == FALSE) {
     move(right, 1);  
}
while ( two_robots_meet() == FALSE ) {
    move(right, 2);
}

1. Sort both arrays in descending order

/* Insert A[0] + B[0] into max heap */
   max_heap.put(0, 0, A[0]+B[0]);
   while (--k) {
       p = max_heap.get();

       if (p.a_index < p.b_index) {
           sum = A[p.a_index] + B[p.b_index+1];
           max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
       } else if (p.a_index > p.b_index) {
           sum = A[p.a_index+1] + B[p.b_index];
           max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
       } else { /* add both adjacent elements */
           sum = A[p.a_index] + B[p.b_index+1];
           max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
           sum = A[p.a_index+1] + B[p.b_index];
           max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
       } 
   }

    p = max_hep.get();
    sum = A[p.a_index] + B[p.b_index];
    printf("kth max sum is formed by A[%d] + B[%d] = %d\n", p.a_index, p.b_index, sum);

Exactly what I thought :)

The complexity is O(N log N) which is same as BST based solution.

@czpete: awesome solution!