How to prepare for technical interviews

You would find tons of information on how to go about preparing for software coding interviews. When you start preparing for coding interviews, there's no silver bullet to tackle the wide variety of interviews.

In general, the basic philosophy of big technology firms like Google, Amazon et. al is that they expect engineers to know a little bit about everything and everything about something. 

I've failed in my interviews with Google, Amazon and Microsoft at different points in my career, but, I've sailed quite smoothly in other seemingly "highly selective" organisations. I'll cover my interview experience with Google in some other post, but, my intention here is to consolidate and elaborate on what I think could be a good strategy to go about preparing for those big tech giants as I move towards the same.

Let's explore few key points and strategies to tackle technical interviews.

1. Learn from your work:  This is the most understated point when it comes to landing your dream job. It is quite obvious that we have a huge area to cover when it comes to preparing for interviews. We really can't focus on everything in the limited time (say a few months/weeks) we have for  the prep. The key lies in the fact that majority of who you are as an engineer is driven through the work you've done so far.
   
   Its usually a good idea to have a top down approach towards understanding a project. Its equally important to ask the right questions.
   
   Few questions to tackle when you are working on a big project at work.
   
   - What problem is this software stack solving?
   - What is the high level architecture of this solution?
   - What part of this software stack am I responsible for?
   - What could have been alternate solutions to solve this problem?
   
   While above is not an exhaustive list, its indicative of the approach to streamline the effort to better grasp what you are doing.
2. Practice your Data structures & Algorithms:
   This is a no-brainer when it comes to preparing for the coding interviews. There are plenty of resources when it comes to picking up practice material, but, its important to stick to one good resource and stay consistent with your preparations.
   
   In my experience, consistency and discipline outweighs brilliance when it comes to creating results. Read about plasticity and growth mindset. 
   
   Here's one viable plan that worked for me, and you could expand on it.
   - Write down all the topics you need to cover for your preparation.
   - Solve at least one problem each day, this is very important, believe me our mind requires daily dose of these exercises to really fire up.
   - Don't rush to look for the solution, at the same time, don't get bogged down by the problem. Take your time to solve the problem, if you still can't unblock yourself and understand the underlying concept. But, you should at least once, sleep over that problem. Let your subconscious mind kick into problem solving.
   I'll write some good resources for preparing for coding interviews.
3. Work on your System Design/Large Scale systems: 
   All tech intensive jobs interviews expect you to have good understanding of System Design and Back-of-the-envelop calculations. This is expected more from someone having experience in the industry. It really doesn't matter if you have worked on such a systems or not.
   
   These interviews usually provide you with a fairly open-ended and vague problem description. e.g. Design a system to monitor files and directory sizes in a data-centre.
   
   These interviews are there to test your approach towards few of the key skills.
   - Communication skills: How well you articulate your understanding of the problem and how well you extract the information from the interviewer to solve the problem. Its more of a collaborative effort between the candidate and the interviewer to workout a solution where candidate is the driver.
   - Engineering Design Skills: As they say, there's no perfect design. But, the designs should be flexible enough to cater to the future requirements. Its very important to first understand the requirements (functional/scalbility etc) and convey to the interviewer about your understanding. Jumping straight towards the whiteboard to pour your initial thoughts is a sign of immaturity. Think aloud and talk about choices with your justification. Keep reading about large scale systems like Google search, Netflix, Uber etc. There are pretty cool technologies these organisations have developed and its always a good idea to get an understanding of them.
   
   

Below are some of the good references for interview preparation.

• Coding practice:
  Leetcode
  HackerRank
  interviewbit
• System Design
  System design
  High Scalability

Minimum Difference Between BST Nodes

This is one of the easier problems to test your Data structures knowledge. I picked
it up from leetcode.

Here's the problem statement:

Given a Binary Search Tree (BST) with the root node root,
return the minimum difference between the values of any two different nodes in the tree.

example:

For the following given binary search tree
                       4
                     /   \
                  2       6
                /   \
              1      3

The minimum difference is 1, between nodes with value 1 and 2 as well as between
nodes with values 2 and 3.

Idea 1:
Iterate over the BST in an inorder fashion and save the numbers in a vector.
The smallest difference is going to be between two adjacent numbers.

Idea 2:
Another idea to attack the problem is to utilize the fact that if we do an in-order
traversal of the BST, we'll get the values in ascending order. 

Based on idea 2 above, we'll employ recursive in-order solution and augment the algorithm to keep two more 'facts' (invariants) at each state of the recursion-tree

• What is the value of the predecessor we've seen, to compare with the current value
• What is the minimum difference seen so far.

Following is the solution:

Question:
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
Solution:

#include <iostream>
#include <string.h>

using namespace std;


void transform(int **data, int M,int N){
 int *prev = new int[N];
 for(int i=0;i<N;++i)
  prev[i]=1;
 for(int i=0;i<M;++i){
  bool setrow = false;
  for(int j=0;j<N;++j){

   bool setcol=false;
   if( prev[j] == 1 && data[i][j] == 0  ){
    prev[j] = 0;
    setrow = true;
    setcol = true;

   } else if (prev[j]==0 && data[i][j]  ){
    data[i][j] = 0;
   }

   if (setcol){
    for(int k=i;k>=0;--k){
     data[k][j]=0;
    }
   }
  }
  if (setrow){
   for(int k=0;k<N;++k){
    data[i][k] = 0;
   }
  }
 }
 delete []prev;
}

void print(int **data, int M, int N){
 for(int i=0;i<M;++i){
  for(int j=0;j<N;++j){
   cout<<data[i][j]<<" ";
  }
  cout<<endl;
 }
}

int main() {
 int **data;
 data = new int* [4];
 for(int i=0;i<4;++i){
  data[i] = new int[5];
 }
 for(int i=0;i<4;++i)
  for(int j=0;j<5;++j)
   data[i][j]=1;

 data[0][3] = 0;
 data[1][2] = 0;
 data[2][3] = 0;

 print(data,4,5);
 transform(data,4,5);
 cout<<"------------------"<<endl;
 print(data,4,5);
        //release memory
       for(int i=0;i<5;++i){
           delete[] data[i];
       }
       delete[] data;
 return 0;
}

Coding Question: rotate a NxN matrix by 90 degrees in-place

Question:
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Solution:

#include <iostream>
using namespace std;

void rotate90(int **array, int N){
    for(int i=0;i<N/2;++i){
        for(int j=i;j<N-1-i;++j){
	    int t1=array[j][N-1-i];
	    array[j][N-1-i] = array[i][j];

            int t2=array[N-1-i][N-1-j];
            array[N-1-i][N-1-j] = t1;

            t1 = array[N-1-j][i];
            array[N-1-j][i] = t2;

            array[i][j] = t1;
       }
    }
}

int main() {
    int **matrix;
    matrix = new int*[5];
    for(int i=0;i<5;++i)
        matrix[i] = new int[5];

    int count=0;
    for(int i=0;i<5;++i)
        for(int j=0;j<5;++j){
        matrix[i][j] = count++;
		}

    for(int i=0;i<5;++i){
       for(int j=0;j<5;++j){
           cout<<matrix[i][j]<<" ";
       }
       cout<<endl;
    }
    cout<<"----------------"<<endl;
    rotate90(matrix,5);
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    //release memory
    for(int i=0;i<5;++i){
       delete[] matrix[i];
    }
    delete[] matrix;
    cout << "" << endl; // prints 
    return 0;
}

Decode a string

Q: We are given a char array like “a1b2c3″ we have to convert this array to array like this “abbccc” .This has to be done in place as we are given that array has just enough space to hold the expanded array. Here's an algorithm to solve this:

#include <iostream>

string decode(string estr){
    int patlen = estr.length();
    int reqdlen=0;
    for(int i=0;i<patlen;++i){
        if( isDigit(estr[i]) ){
            reqdlen+=estr[i]-'0';
        }
    }
 
    string ans;
    ans.resize(reqdlen);
    cout<<ans.length()<<endl;
    //case 1: if patlen >= reqdlen
    //e.g. a1 a1b2
    if( patlen  >= reqdlen ){
        int idx=0;
        char lastchar;
        for(int i=0;i<patlen;++i){
            if( isChar(estr[i]) ){
                lastchar = estr[i];
                ans[idx] = estr[i];
            }else if( estr[i] == '2' ){
              //a1b3 will never come
              //cout<    ans[idx] = lastchar;
              idx++;
            }
        }
    }else if( patlen < reqdlen ){
        //shrink the pattern by moving all chars with
        //count 1
        int idx =0;
        char lastchar;
        int newlen=0;
        for(int i=0;i<patlen;++i){
            if( isChar[estr[i]] ){
              ans[idx++] = estr[i];
            }else if( estr[i] != '1' ){
               idx++;
            }
        }

        newlen = idx;
        //now start filling from the back
        int lastdigit;
        idx=reqdlen-1;
        for(int i=newlen-1;i>=0;--i){
          if( isDigit(estr[i]))
            lastdigit=estr[i]-'0';
          else{
            for(int j=0;j<lastdigit;++j){
               ans[idx--]=estr[i];
            }
            lastdigit=1;
          }
        }
    }
 return ans;
}

int main() {
 cout<<decode("a1b1c1")<<endl;
 cout<<decode("a2b1c2")<<endl;
 cout<<decode("a2b2c2")<<endl;
 cout<<decode("a1b1c5")<<endl;
 cout<<decode("a9b1c5")<<endl;

 return 0;
}

Stacktrace forencis

Many a times you would find the stacktrace ( through pstack or stacktrace files from production) supplied for finding the root cause. There's lot much information you can extract from stack-trace, here’s a summary from my experience in debugging core files.

1. The faulty stack frame

You could pin point the faulty stack frame by looking at the backtrace file, you would see that all the stack-frames (barring one) are under wait (by executing blocking syscall e.g lwp_park or nanosleep et. al). As you know only one context would be in execution and you can identify it by looking at the last call.

Below is an extract of one such faulty stack frame

----------------- lwp# 9 / thread# 9 --------------------

fe241dd0 waitid (0, 22ac, f2372470, 3)

fe234bfc waitpid (22ac, f23725c4, 0, 0, f237261c, fe162b00) + 60

fe22828c system (f237275c, fe272034, 20000, 1, fe26a2b4, f237261c) + 2ec

fe54094c void MyApplication::generateStackTraceFile(MyModule::AppMgrId,long,const char*,bool) (f23728ac, 41c, 20fbc8, f23728ac, fe703c18, fe755050) + 42c

fe5404a4 void MyApplication::fatalSignal(int) (0, fe755050, 211f88, fe758db4, 388, 0) + 5c

fe240a14 __sighndlr (b, 0, f2372c90, fe540448, 0, 1) + c

fe235a30 call_user_handler (b, 0, 0, 100, fd3e1800, f2372c90) + 3b8

fe224220 fileno (0, 7c, ff11f728, ff11d3f4, 2881c, ff11efc4)

0004036c bool FileSender::sendPoll(unsigned short,MyAppEnum::RedEnum,int,unsigned short,unsigned long) (1, 8000, d213b, f2376ddc, 1a1400, 0) + db8

00059504 void FileSender::sendScPoll() (128430, 2affc227, 102024, 16e454, f237886c, 15f000) + f4

......
......

fe54d134 void*BaseThread::execute(void*) (604a08, 3b8, fe755050, 0, 108, 0) + 68

fe2408e8 _lwp_start (0, 0, 0, 0, 0, 0)

----------------- lwp# 10 / thread# 10 --------------------

2. Identifying the last user-space function call

You could see from the stack trace that the last user space API looks like MyApplication::generateStackTraceFile, which is correct, but this is not the probable faulty function responsible for the crash, as this method is generating the trace-back file, this means that the ‘fatal signal’ was raised somewhere down the stack. So, we look down at the stack and see that ‘sendPoll’ is the previous user-space function call. ‘fineno’, call_uesr_handler, __sighndlr are either kernel space or libc based api’s, so we wouldn’t bother about them.

3. Reaching the last statement within the function to pin-point the probable cause of crash.

This is a little trick part. One straight forward way is to attach a debugger to the core, and feel lucky that the core is ‘not corrupt' and you see the line.no. displayed using ‘where’ command, many a times the core is not available and all you have is a stacktrace file from production. If such a case the following information would be useful.

0004036c bool FileSender::sendPoll(unsigned short,MyAppEnum::RedEnum,int,unsigned short,unsigned long) (1, 8000, d213b, f2376ddc, 1a1400, 0) + db8

We pick the function call FileSender::sendPoll and see that there’s an offset db8 mentioned in the stack-trace, this means that the last instruction that caused this process to crash was at an offset of db8 bytes from the starting of the function FileSender::sendPoll

Next steps is to reach at this offset. Unfortunately, we can’t look at the C++ code to determine the bytes offset. What we need to do is compile the corresponding source file to generate an assembly code. On solaris we use SUN’s ‘CC’ compiler, and the corresponding compiler option to generate the assembly code is -S

4. Generating assembly code file for a given source file

Use your compiler's 'generate assembly' switch to generate the code. Something like

bash-3.00$ pwd

/home/skp/cmp/obj/......./

bash-3.00$ ls -l FileSender.s

-rw-rw-r-- 1 skp staff 6640175 Mar 10 12:56 FileSender.s

5. Moving to the offset with-in the function

Now that we have the assembled code, we can go the required offset. I’m listing down the assembled code. The code generated through –S option would have mangled symbols, to de-mangle them you could use c++filt as below

bash-3.00$ c++filt FileSender.s > FileSender_dem.s

! SUBROUTINE bool FileSender::sendPoll(unsigned short,MyAppEnum::RedEnum,int,unsigned short,unsigned long)

!

! OFFSET SOURCE LINE LABEL INSTRUCTION

......

......

bool FileSender::sendPoll(unsigned short,MyAppEnum::RedEnum,int,unsigned short,unsigned long):

/* 000000 2167 */ sethi %hi(0x4c00),%g1

………………….. .

…………………..

…………………..

Now keep moving down till we move to an offset of db8, meaning thereby, that we’ll have to reach an address of 0x0000 + 0x0db8 = 0x0db8

Following line gives the corresponding offset listing

/* 0x0db8 2286 */ call pclose ! params = %o0 ! Result =

Which shows that the last line caused this process to generate ‘fatal signal’ was pclose. The above line shows that the offset was 0x0db8 and corresponding line number within the C++ file is 2286

6. Reviewing the equivalent code

2282 FILE* fd=popen(command,"w");

2283 if (fd == NULL){

2284 Logger.logMsg(MyAppTrace::ERROR,"Fail to execute ");//check for log, if you are luck you might see this log

2285 }

2286 pclose(fd); // this might result in SIGSEGV if fd is NULL

7. Which signal might have caused the crash.

Again we revert back to the stacktrace, it shows

fe235a30 call_user_handler (b, 0, 0, 100, fd3e1800, f2372c90) + 3b8

as one of the calls. A little googling shows that this is a kernel space api that calls the ‘callback’ signal handler and its first argument is the signal number. Which is b, meaning 11 (SIGSEGV)

bash-3.00$ kill -l

1) SIGHUP 2) SIGINT 3) SIGQUIT 4) SIGILL

5) SIGTRAP 6) SIGABRT 7) SIGEMT 8) SIGFPE

9) SIGKILL 10) SIGBUS 11) SIGSEGV 12) SIGSYS

This confirms our debugging and we can provide the corresponding fix.

Hope this is helpful to many how are into debugging stufff.

Meet KUKU

Meet Kuku. I wouldn't write much about kuku, lest Kuku would offended. Kuku is the result of Anoop [ contactanuptop at gmail dot com ] and My creative endeavor.
Do spare some time to put your comments.