A road named NoNameUno

Here is the thought process --

Use an Auxilary array Aux[size], of same type and size. As and when a Set(index, value ) operation happens, enter the value into A[index]=value; Put the index into Aux[] array, and have a counter for howmany such entries are entered, unsigned valid_count.  Now whenever, we see a get count like get(index), we check/search if this index has value or not. This search happens in Aux[] array with the hope we find a value from the current index range 0<= index < valid_count. If we find the index there, we know a valid value will be found and returned. BUT THE PROBLEM IS get(index) is no longer O(1).

This is where we need to introduce another Auxalary array, say Aux2[], the first one is now renamed to Aux1[], A is our original array.

        if (index >= 0 && index < arr_size_){

            myarra_[index] = value;

            aux1_arr_[valid_count_] = index; // keep the current index
of myarray

            aux2_arr_[index] = valid_count_;  // keep the index of aux_arr_

            ++valid_count_;

        }

    }

};


int main(int argc, const char * argv[]) {

    // insert code here...

    int val;

    MyArray myarr(10);

    myarr.set(9, 99);

    val = myarr.get(9);

    myarr.set( 2, 22);

    val = myarr.get(2);

    myarr.set( 3, 45);

    val = myarr.get(3);

    // -- error cases

    val = myarr.get(5); // shoule be -1

    val = myarr.get(-1);

    val = myarr.get(10);



    std::cout << "Hello, World!\n";

    return 0;

}

How do we use array types, in C / C++ algorithms? 

We either allocate on stack ( when using local array to a function ) or using heap memory to use until we free the array objects. We use one of many ways to allocate such array objects, initialize before using it, they either implicitly or explicitly destroy it...

Now there is a situation where you can allocate a really large array object, but you want to avoid initializing it , because it is slow for certain applications. The only methods we need is to have Get, and Set methods to set or get information form a particular index, just like A[i], where i is the index. NOW RANDOM ACCESS PATTERN WILL BE THROWN AT THE IMPLEMENTATION, Our job is to make sure the implementation we design work without any fault.  How do we do that ??

You can use extra or auxilary memory as you want, but in this case performance of CPU is more important.

Try to think about, and come up with a solution... You will certainly miss the WOW moment, if you jump into the code, I will present here.  I was half way, or perhaps 2/3rd of the way. No paper pencil , just talk and think thru, including hold the thinking process -- what if I do this, or that etc. Extra time usually given when two players are hoping to win, an even game if you will. So I was given couple hours to take a shot at it, encouraged to take the path I was thinking.... Do please don't miss the WOW moment.

Probelem statement:

Elements in an array can be retrieved/set in constant time O(1). For

the sake of this problem, assume when you new an array, the allocated

memory will just have garbage — data from their previous life. So

typically you need to traverse the array, and initialize the elements

to some well-known invalid value. Say if we know the valid data is

positive int, then you’d initialize the elements to something like -1

to indicate it’s an invalid value. This way when you get a -1, you

know it’s a garbage value.

For this problem, write a class called MyArray that has three functions:

constructor — MyArray(size_t size)

getter — int get(size_t index)

setter — void set(size_t index, int value)

The requirements are

* No initialization of the array before using it, assume it is very very expensive operation

• The implementation can only use native data types like int and

native array (i.e., cannot use things like HashTable, Set, LinkedList,

etc).

• The getter function returns -1 when the value is a garbage (i.e., an

index that has never been set by client). It has to be 100% correct in

the sense that there is no circumstance where the getter would return

a value X, where X is actually garbage.

• All three functions have to be strictly O(1) — not amortized O(1)

There are 10 sacks containing coins, inside a room. There is a balence outside the room that you can use to weigh and find the sack that has all counterfiet coins. The coins are all same type, say quarters. 

You are allowed to enter the room once. Take as many coins as you want, bring them out and find which sack has all the counterfiet coins. There are plenty of empty sacks inside the room for your use.

It has been a common riddle for some 20+ years, and was asked in different job interviews to see the presence of mind of a candidate.

• It is clear that you will have bring some coins outside to weigh and decide. You can not bring the balence inside. So you will have to have some ways of identification mechanims, to tell which sacks has counterfiet coins.
• Once you find the solution to identification, next is to find the sack by weighing your sample.
• Finally How can you find the solution in minimum number of weighing ?

Due to multicore and hyperthreaded processors, threading is now a common task programmers need to perform whenever possible. Quite often we see ready template code online or even C++ library based implementations that makes it easy or us to cut & paste, make few changes and unleash on to market after several testings...

This is fairly common these days that hardly any programmer can escape due to higher productivity requiremets !

We we do threaded programming, it is sure to have concurrent processing. So we need some kind of synchronizations to make sure we don't corrupt some shared data. Now the question is how to comeup with proper sync mechanism: mutex, spin-lock etc...

Here is an example of such application of threading -

Q: Print a sequence like: 010203040506070809010011012013 .... using threaded routines. One can do it in one thread, but here we need to exercise threading.

It's necessary to see how minimal locking we can do. To do that it is good to look at the state diagram. For example if a thread just print zero, then it has to let other threads to print non-zero. 

Now one more requirement imposed is: Use three threads : One prints zeros, another one prints even numbers, yet another prints odd numbers.

Codition to analyize:: When can zero thread print ? -- It can print after any non-zero got print. When can an even nunber be printed:: - When when zero thd. is not allowed to print, and last non-zero thread was odd number thread.

Now here is an implementation. It is instructive, if you use paper pencil first...

//

//  main.c

//  OS

//

//  Created by Admin on 5/26/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdio.h>

#include "OS.h"

int main(int argc, const char * argv[]) {

    // insert code here...

    testOddEvenPrint();

    printf("\nHello, World!\n");

    return 0;

}

//

//  thd.c

//  OS

//

//  Created by Admin on 5/26/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdbool.h>

#include<stdio.h>

#include<string.h>

#include<pthread.h>

#include<stdlib.h>

#include<unistd.h>

/*

 * Create a multi threaded ( 3 thd ) that prints 0102030405060708....

 * Need mutual exclusion

 */

//pthread_mutex_t mutx;

_Bool IsZero = true;

_Bool IsOddNo = true;

void AC( pthread_mutex_t *L)

{

    // -- waitable may block

    pthread_mutex_lock(L);

    return;

}

void RL( pthread_mutex_t *L)

{

    pthread_mutex_unlock(L);

    return;

}

void *printzero( void *Lock)

{

    pthread_mutex_t* L = (pthread_mutex_t*)Lock;

    for (int i = 0; i < 20; i++){

        AC ( L );

        if ( IsZero ){

            printf("%d", 0);

            IsZero = false;

        }

        RL(L);

    }

    return NULL;

}

void *printOdd( void *Lock )

{

    static int OddNo = 1;

    pthread_mutex_t* L = (pthread_mutex_t*)Lock;

    for (int i = 0; i < 10; i++){

        AC ( L );

        if ( !IsZero && IsOddNo){

            printf("%d", OddNo);

            IsZero = true;

            IsOddNo = false;

            OddNo += 2;

        }

        RL(L);

    }

    return NULL;

}

void *printEven( void *Lock )

{

    static int EvenNo = 2;

    pthread_mutex_t* L = (pthread_mutex_t*)Lock;

    for (int i = 0; i < 10; i++){

        AC ( L );

        if ( !IsZero && !IsOddNo){

            printf("%d", EvenNo);

            IsZero = true;

            IsOddNo = true;

            EvenNo += 2;

        }

        RL(L);

    }

    return NULL;

}

void

testOddEvenPrint()

{

    int err;

    pthread_t tid0thd, tidOddthd, tidEventhd;

    pthread_mutex_t mutx;

    if (pthread_mutex_init(&mutx, NULL) != 0)

    {

        printf("\n mutex init failed\n");

        return ;

    }

    err = pthread_create(&tid0thd, NULL, &printzero, &mutx);

    if (err != 0){

        printf("\ncan't create thread printzero :[%s]", strerror(err));

        return ;

    }

    err = pthread_create(&tidOddthd, NULL, &printOdd, &mutx);

    if (err != 0){

        printf("\ncan't create thread printzero :[%s]", strerror(err));

        return ;

    }

    err = pthread_create(&tidEventhd, NULL, &printEven, &mutx);

    if (err != 0){

        printf("\ncan't create thread printzero :[%s]", strerror(err));

        return ;

    }

    pthread_join(tid0thd, NULL);

    pthread_join(tidOddthd, NULL);

    pthread_join(tidEventhd, NULL);

    pthread_mutex_destroy(&mutx);

    return;

}

Assume two pick pocketers  A, and B,  are settling on their end of the day earnings. The rule is that they will put all their picks on to a table. Then they will pick one coin at a time from either end of the line ( the coins are put on a line). Further assume that the number of coins is even, so both of them can have same number of coins. Fair game, as opposed to lot of things in life :-)

How should they go about picking in tern from either end of line to maxmize gain?

Example worth 1000 brainstorm !

S = { 6, 9, 1, 2, 16, 8 }. 

Greedy approach: Both A, and B will pick the larger of the coins at two ends.

A -> 8, B-> ... complete the process and see if A wins or B. You will see even though A has the first shot at it, A will loose. So greedy approach does not work. So what should be the strategy ? -- Think ...

The approach should be to minimize opponents next gain, rather than maximize your own gain. What an envy ! First approach is called Greedy, and the second approach is Strategy.

So at each turn, one would look at the difference between 2 left end coins and 2 right end coins and maximize the difference. In other words, you pick the greater difference.  

Look at Max {  ( a[i] - a[i+1] ),  ( a[N] - A[N-1] ) },   then pick either A[i] or A[N]

Time to find a functional equation !