A road named NoNameUno

For high tech programmer/coder it is vital to find what it takes to get a gainful appointment?

What a candidate can should know before starting interview with targeted companies ?

Assuming a job offer, what experiences can be carried forward to next level or next job(s) ?

For the first question, it's almost always that several rounds of programming / coding tests are required to pass the preliminary gate. Soft skill are good to have, no one wants a unlkeable person in the team. Then comes the possible match with the experience of the candidate! One thing to note:  The questions they ask for interviews in a indication of what the candidate would be doing if (s)he is selected.

Now for the coding questions  --

• How is the preparation ?
• What is the best language one can use ?
• What the data structure(s) and algorithms are requited ?
• How to formulate a problem, then code it ?

Preparation: There are many online sights with questions / hints / answers. One can find at least 10 sites with such questions/hints/answers ? Some are even descriptives about the fundational course, refreshers etc. Some are for free, some are paid. Then there are many videos, offer for mock interviews...

Concerns:  What time line and amount of time disposable to invest on it ? How much is the cost, not including time invested ?

Conclution:  Should one prepare for lots of problems, practice, code, spend money on mock interviews, invest lot of time and money, with the hope that some known problem will be there by pure chance and solve it ???

Ans: No, no, no. Due to many constraints , and using probablitiy one can not even be sure for half a chance unless they are straight forward questions usually covered in course work ( and common langaguare/idioms or day to day work).

Remark: Clasification of the problem is important. Not all problems take same approach/method. And not all are different. So there are groups/clusters of problems. And classification is important.

After about 7 years hacking MacOS kernel, and a year before on BSD 6.0, finally got back to Windows kernel hacking. Surprsing to see how C++ finally got into kernel developments in Windows environment. Also validated the assertion "Forgetfulness is a bliss!". Boy, so many things changed, and yet another is so many things wiped out of memory. Refreshing took some time and lot of frustration/hacking, but in the end it was all good and fond memory lane...

Now shifting gear, back in Linux (Unix like ) hacking. Already find it very interesting, like Windows hacking.

Will post some interesting topics, as I go along !!

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 ?