Algorithms & Data Structure Interview Essentials

How to approach coding interview

oh_sigh: I’ve worked at 75% of FANGs. My method was basically just bone up on algorithms and data structures by going onto the Wikipedia list and trying to implement them on pen and paper. Practice thinking out loud, practice space management(no backspacing on pen and paper). Know how to analyze runtime of your algorithms.

I chose to interview in python, even though I know other languages better, because it is fairly dense relative to, say java or c++ and easier to write by hand.

> but I'm positive I'd fail a FAANG interview w/o advance prep I work for a FAAN... | Hacker News

// ensure you understood the question - confirm your understanding with interviewer
// think happy path
// think time and space complexity
// think data structure to use
// write pseudo code
// catch edge
// refine pseudo code
// ask interviewer for feedback
// code!

I have noticed when preparing for coding exercise I get stuck at ahem writing a for loop, break statement or a HashMap. Here I’m with20+ years of software engineer experience & getting stumped writing a basis control statement.

The reasons include, one of more of the below

• no practice
• under pressure
• yes, i’ve worked in java (or any other coding language) but recently have looking in infrastructure code e.g. terraform.
• well, i’m currently working on a python/typescript/javascript microservice however that’s not my go to language for coding interview
• my current language is not the one available(e.g. rarely I’ve seen ruby)

So what’s the solution to out of this dilemma?

Core focus of coding exercise is to evaluate your communication skills, understanding of time & space complexity, coming up design as well as an optimal solution & yes, and last but not the least coding the solution in a programming language.

I’ll be focusing on remove the obstacles in coding the optimal solution.

• Practice loops (i.e. not reading 😊)
• Practice use of control statements
• Initialize e.g. an array with some default values
• Creating variable for data structure e.g. HashMap

Loops in Java

The good news, there are only 3

• while
• for & enhanced for
• do … while

The bad news, watch out for the pitfalls

• infinite loop
• out of memory error

// while loop
int j=0;
while(j<10){
   System.out.println("the num is "+ j);
   j++;
}

// for loop
for(int i=0;i<10;i++){
    System.out.println("the num is "+ i);
}
// enhanced for loop
String array[] = { "Hermoine", "Ron", "Harry" };
for(String name: array){
    System.out.println("the name is " + name);
}
// for loop using index
for(int i=0;i<array.length;i++){
    System.out.println("name is "+ array[i]);
}

// do while
int k=0;
do {
    System.out.println("dowhile loop number is "+k);
    k++;
} while (k<10);

Control Statement in Java

A programming language use control statement to control the flow of execution of the program based on business condition/requirements.

These are used to cause the flow of execution to advance or branch based on changes in the state of the program.

The bad news, there are 6 types of decision making

The good news, ?

• If
• If-Else
• Nested If
• If-Else-If
• Switch-case (I was asked to write this in one interview)
• Jump i.e. break, continue & return ٩(๏_๏)۶

🎯🎯🎯 I will start with the 3 jump statements. You will mostly likely encounter one or more of these in coding interview

Break

• To terminate sequence on switch statement
• To exit a loop

Return

• explicitly return from the method. It causes the program control to be transferred back to calling method.

Continue

• stops processing reminder of the code in its body for this particular iteration

for(int i=0;i<10;i++){
    if(i%2 == 0) // skips/stops processing the loop when i is even
      continue;
  
  System.out.println("odd number found "+i);
}

Must know data structure Constructs

iterating characters in a string

initializing an array, hashmap, set, arraylist, linkedlist, queue, stack, binary tree

try o(1)

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

On Java 10+:

for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

Binary Search

public static int binarySearch(int[] array, int target) {
        // Write your code here.
        int start = 0;
        int end = array.length-1;

        while(start<=end){
        int mid = start + (end-start)/2;
        int expectedValue = array[mid];

        if(expectedValue==target)
        return mid;

        if(expectedValue>target){
        end = mid-1;
        } else{
        start= mid+1;
        }

        }

        return -1;
        }

recursive

public static int binarySearch(int[] array, int target) {
        // Write your code here.
        return binSe(array, 0, array.length-1, target);
        }

public static int binSe(int[] array, int start, int end, int target){
        if(start>end)
        return -1;

        int mid = start + (end-start)/2;
        int expectedValue = array[mid];
        if(expectedValue==target)
        return mid;
        else if(expectedValue>target)
        return binSe(array,start, mid-1, target);
        else
        return binSe(array,mid+1, end, target);
        }