Technical interviews.


A college student will tend to be asked questions around C language, operating systems, programming language concepts with a puzzzle thrown in for variety. An experienced candidate will in addition be expected to talk about his projects and role, the toughest challenge he faced, system design questions with grilling on data structures. Once in a while, an interview may also involve an unconventional test.

Test Research Skills:
Ajingo (Linux OS for mobiles, acquired by Motorola) gave my team a computer architecture topic and 30 minutes to research and present. Researching an obscure core technical topic quickly and well enough to present a talk on it will be a very useful skill in any technical career. Not used nearly as often as it should be.

Technical Debate:
A project idea around plausible deniable file systems caught the Ajingo interviewer's attention, but he pretended as if he had never heard of it, and argued why he thought it would not work. He then switched positions, gave us answers to his earlier questions and expected us to shoot down his arguments.Again, a very valuable skill to have. Analysing pros and cons of an approach, discussing them as a team, and comparing competing ideas is a big skill. Also tests ability to think and work as a team. This is a good tactic when a system design question is being asked. Do you generate consensus or try to bulldoze your teammates, or simply roll over and giveup because you don't like a conflict of ideas?

Handling pressure:
We faced a barrage of often unrelated questions in a series of interviews for around three hours with very few breaks in between. Sometimes you may be interviewed by multiple people, this can be intimidating. One of the interviewers may intentionally be disrespectful to you. This is the good cop/bad cop test. This will tire out anyone, and the test is to see how you would handle yourself when exhausted.

The Impossible Question:
Ask a hard problem that you know the interviewee cannnot answer in the given setting and maybe the answer does not even exist because you asked a disguised version of a known hard problem where only heuristics would do. Would you ask followup questions? How and when do you giveup? Do you giveup? If theoretical compuer science is your strong suite, you will reduce it to a known problem statement and arrive at a solve/can't solve answer, but most people wouldn't get there.

Pair programming:
ThoughtWorks does this a lot. This helps verify an interviewee's programming skills, that a programmer can program.

Human Compilation:
Again from ThoughWorks, a written test that is actually a bunch of for/while loops pictured as flowcharts. Effectively, you decode a low level program in some assembly language, and give the answer. I think this is a test of concentation and patience.

Passion Quotient:
What are you passionate about? What is the last book you read? This is to find out if you love your profession and care about your skills, or are you just doing it for the paycheck. Nothing wrong with the latter, but it may mean that you don't improve everyday and likely wouldn't be the best employee they ever had.

Topcoder: Always run system tests in practice.

This post is just to note something that I missed all along.

When practicing in Topcoder practice rooms, just submitting the solution and getting a "submitted for X points" is not enough. There is also a run system test option that should always be tried to ensure that the code really was correct. I wonder why running system tests is not the default in the practice rooms?
Maybe it is because in the real environment, system tests are run after the coding phase had ended, and they expect the coder to think about other cases that have not been mentioned in the problem statement.

I learnt this the hard way, since one of my solutions for the div 2 500 points was successfully challenged, and this prompted me to look for ways to develop more confidence in the code I write.


USACO : Prime cryptarithm


Easier problem overall.

Lost 1 hour in the binary search step, where condition was stated incorrectly by me as >0 when it should have been >=0.

Found a concise way to count number of digits in a number, using Math log to base 10, with special condition for the number 0. I think there might be some better bit twiddling hacks for this, but for now this will do.

/*
ID: abhi
LANG: JAVA
TASK: crypt1
 */

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class crypt1
{
/*

   A B C
    D E

   2 1 0
     4 3

      * * *
   x    * *
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2
    -------
    * * * *

 */

private static int[] assigned  = new int[5];
private static int[] possibleNumbers;
private static int solutionCount=0;
// private static int optionCount=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader reader = new BufferedReader(new FileReader(new File("crypt1.in")));
int possibleNumbersCount = Integer.parseInt(reader.readLine());
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

possibleNumbers = new int[possibleNumbersCount];
for(int i=0;i<possibleNumbersCount;i++) {
possibleNumbers[i]=Integer.parseInt(tokenizer.nextToken());
}
Arrays.sort(possibleNumbers);

assignAndSolve(0);
PrintWriter out = new PrintWriter("crypt1.out");
out.println(solutionCount);
out.close();
// System.out.println(optionCount);
System.exit(0);
}

private static void assignAndSolve(int assignedCount) {
if(assignedCount == 5) {
// optionCount++;
int upper = assigned[0] + (assigned[1]*10) + (assigned[2]*100);
int partialProduct1= upper* assigned[3];
if(!isValid(partialProduct1,3)) {
return;
}
int partialProduct2= upper*assigned[4];
if(!isValid(partialProduct2, 3)) {
return;
}
int sumOfPartialProducts = partialProduct1 + (10*partialProduct2);
if(!isValid(sumOfPartialProducts,4)) {
return;
}
// System.out.println(assigned[2] + " " + assigned[1] + " " + assigned[0] + "\n  " + assigned[3] + " " + assigned[4]);
solutionCount++;
}
else {
for(int i=0;i<possibleNumbers.length;i++) {
assigned[assignedCount]= possibleNumbers[i];
assignAndSolve(assignedCount+1);
}
}
}

private static boolean isValid(int number, int digitCount)
{
int count = (number ==0) ? 1 : (int)Math.log10(number) + 1;
if(count!=digitCount) {
return false;
}
while(number>0) {
int thisDigit=number%10;
if(!(Arrays.binarySearch(possibleNumbers, thisDigit)>=0)) {
return false;
}
number= number/10;
}
return true;
}
}

USACO : calfflac

Just to remind myself later how chaotic my code can be and see my progress as time goes by, this time I want to paste two of my solutions, the first one where I tried to extract common functions and made things too complicated, and the second where I kept things simple. Abstraction and its object oriented cousins are not so helpful when you just want to implement an algorithm,

It seems that if the logic is too convoluted, it gets way out of hand and out of control. Its symptoms are thinking that one more if condition here or there will fix the problem. This only makes the code inordinately long, and then it is just downhill from there.

On the other hand, keeping things simple, having code that runs for the simple cases first, makes it easier to predict where the rest of the test cases are failing.

I also seem to write 90 % of the solution quickly and get stuck trying to pass one or the other test case. That last 10% seems to be taking at least half of the time. Its not the difficulty of the problem, but probably my inexperience. Maybe I should start thinking much more carefully about the corner cases.

I have also noticed that there is a bit of something that I take along from one solution that helps me in the next, cutting those few seconds off my personal time. I am getting faster, from idea to implementation.


Failed Solution:


import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;


public class calfflac2
{
private static String data = null;
private static int maxLength=0, pointer=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
// BufferedReader reader = new BufferedReader(new FileReader(new File("calfflac.in")));
// data = reader.readLine();
// PrintWriter out = new PrintWriter(new File("calfflac.out"));
data="Confucius say: Madam, I'm Adam.";

longestPalindrome();

// out.print(data.substring(pointer, pointer+maxLength));
// out.close();
System.out.println(data.substring(pointer, pointer+maxLength));
System.exit(0);
}

private static boolean isSpecial(char myChar)
{
return myChar=='\n' || myChar==',' || myChar=='\'' || myChar==' ' || myChar==':';
}

private static void longestPalindrome()
{
int upper=0, lower=0, thisLength=0;
// for(int k=0;k<2;k++) {
upper=0;
lower=0;
thisLength=0;
for(int i=0;i<data.length();i++) {
if(isSpecial(data.charAt(i))) // dont' make starting character as special
continue;
// if(k==0) {
// lower=upper=i;
// }
// else {
lower=i;
upper=i+1;
// }

// Just increment and decrement pointers while matching continues, and ignore special characters.
while(true) {
if(lower<0 || upper>data.length()-1) {
break;
}
// ensure that characters are valid.
if(isSpecial(data.charAt(lower))) {
lower--;
continue;
}
if(isSpecial(data.charAt(upper))) {
upper++;
continue;
}

if(Character.toLowerCase(data.charAt(lower))==Character.toLowerCase(data.charAt(upper))) {
thisLength=upper-lower+1;
if(thisLength>maxLength) {
maxLength=thisLength+2;
pointer=lower-1;
}
}

lower--;
upper++;
}
}
}
// }
}

Working solution:

/*
ID: abhi
LANG: JAVA
TASK: calfflac
 */

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;


public class calfflac
{
private static String data="";
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new FileReader(new File("calfflac.in")));
String line="";
while ((line = reader.readLine()) != null) {
data += line + "\n";
}
longestPalindrome();
System.exit(0);
}

private static void longestPalindrome() throws FileNotFoundException
{
int upper=0, lower=0, thisLength=0, maxLength=0, pointer=-1;
// int countSpecial=0, storeSpecial=0;
PrintWriter writer = new PrintWriter(new File("calfflac.out"));
for(int k=0;k<2;k++) {
for(int i=0;i<data.length();i++) {
upper=i+k; lower=i;
thisLength=0;
// countSpecial=0;
while(lower>=0 && upper<data.length() 
&& (Character.toLowerCase(data.charAt(lower))==Character.toLowerCase(data.charAt(upper)))) {
thisLength=upper-lower +1 ;
if(thisLength>maxLength) {
maxLength=thisLength;
pointer=lower;
// storeSpecial= countSpecial;
}
lower--;
while(lower>0 && isSpecial(data.charAt(lower))) {
lower--;
// countSpecial++;
}
upper++;
while(upper<data.length() && isSpecial(data.charAt(upper))) {
upper++;
// countSpecial++;
}
}
}
}
// writer.println(maxLength-storeSpecial);
int count=0;
for(int i=0;i<maxLength;i++) {
if(isSpecial(data.charAt(pointer+ i))) {
count++;
}
}
writer.println(maxLength-count);
writer.println(data.substring(pointer, pointer+maxLength));
writer.close();
}
private static boolean isSpecial(char myChar)
{
return !( (myChar>=65 && myChar<=90) || (myChar>=97 && myChar<=122));
}
}

Barn Repair : USACO, Greedy algorithms


It is beginning to take huge amounts of time to solve these problems, simply because I refuse to read the writeup/tutorials from USACO and also the problem statement properly, and am not as disciplined as I need to be to cover the corner cases in the first cut itself.

Must approach the problem step by step, it is almost always easier than it seems once I start writing the conditions in code.
Must consider what happens if the input is not in sorted order and if the loop breaking conditions are comprehensive.

I was very sloppy when it came to implementation, and refused to observe carefully the boundary conditions. Maybe it is because I write this in the middle of the night.

Another factor that concerns me is the length of this code. Time taken to write code is related to its length, and it needs to get much shorter to be useful.

I think writing the complete logic in detail on paper might be a good exercise, just to see if the IDE is making me too lazy.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class barn1
{
static boolean[] stallStatus ;
static int[] occupiedPositions;
static boolean[] answer;
static int maxBoards=0, stalls=0, countCows=0;

public static void main(String[] args) throws NumberFormatException, IOException
{
// READ INPUTS
BufferedReader reader = new BufferedReader(new FileReader(new File("barn1.in")));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

// INITIALIZE VARIABLES
maxBoards = Integer.parseInt(tokenizer.nextToken());
stalls = Integer.parseInt(tokenizer.nextToken());
countCows = Integer.parseInt(tokenizer.nextToken());


answer= new boolean[stalls+1];
Arrays.fill(answer, false);

occupiedPositions = new int[countCows];
// STORE POSITIONS OCCUPIED BY COWS
for(int i=0;i<countCows;i++) {
int position=Integer.parseInt(reader.readLine());
occupiedPositions[i]=position;
answer[position]=true;
}

Arrays.sort(occupiedPositions);

// Select the board which has longest section that does not need to be covered.
// First, assume that the complete space is one board.
// Guess, we need to keep track of all boards, and search only within all boards.

// ith position is for ith board
int[] boardBegin = new int[maxBoards+1];
int[] boardEnd = new int[maxBoards+1];

int boardCreated=0;
boardBegin[boardCreated]=occupiedPositions[0];
boardEnd[boardCreated]=occupiedPositions[countCows-1];
// iterate over space between each board, using answer array.
// this should be run length encoding type code to find the longest unoccupied length.
boardCreated++;
int selectedBoardIndex=0;
while(boardCreated<maxBoards) { // DO THIS UNTIL WE HAVE BROKEN TO DESIRED COUNT

// Finding the longest run in all boards.
int longestRun=0, thisRun=0, startPosition=0;
for(int boardIndex=0;boardIndex<=boardCreated;boardIndex++) { // IN RANGE MENTIONED
for(int k=boardBegin[boardIndex]; k<boardEnd[boardIndex];) {
if(!answer[k]) {
thisRun++;
if(thisRun>longestRun) {
longestRun=thisRun;
selectedBoardIndex=boardIndex;
startPosition=k-thisRun+1;
}
}
else {
thisRun=0;
}
k=k+1;
}
}

// System.out.println("Longest run is : " + longestRun  + " from,to :" + (startPosition-1) + " " + (startPosition + longestRun));
// Breaking the board.
boardEnd[boardCreated] = boardEnd[selectedBoardIndex];
boardEnd[selectedBoardIndex]=startPosition-1;
boardBegin[boardCreated]=startPosition + longestRun;

sort(boardBegin, boardEnd, boardCreated);
printBoards(boardBegin, boardEnd, boardCreated);
boardCreated++;

int counter=0;
for(int boardIndex=0;boardIndex<boardCreated;boardIndex++) {
for(int k=boardBegin[boardIndex]; k<=boardEnd[boardIndex]; k++) {
// if(answer[k]) {
counter++;
// }
}
}
if(counter==countCows) {
break;
}
}

// CALCULATING STALLS BLOCKED
int counter=0;
for(int boardIndex=0;boardIndex<boardCreated;boardIndex++) {
for(int k=boardBegin[boardIndex]; k<=boardEnd[boardIndex]; k++) {
// if(answer[k]) {
counter++;
// }
}
}
// System.out.println(counter);
PrintWriter out = new PrintWriter(new File("barn1.out"));
out.println(counter);
out.close();
System.exit(0);
}

private static void sort(int[] boardBegin, int[] boardEnd, int boardCreated)
{
for(int i=0;i<=boardCreated;i++) {
for(int j=i+1;j<=boardCreated;j++) {
if(boardBegin[j]<boardBegin[i]) {
int temp = boardBegin[i];
boardBegin[i]=boardBegin[j];
boardBegin[j]=temp;

temp = boardEnd[i];
boardEnd[i]=boardEnd[j];
boardEnd[j]=temp;
}
}
}
}

private static void printBoards(int[] boardBegin, int[] boardEnd, int boardCreated)
{
for(int i=0;i<=boardCreated;i++) {
System.out.print("(" + boardBegin[i] + "," + boardEnd[i] + ")");
}
System.out.println();
}
}

Topcoder: GogoxCake (Single Round Match 530 Round 1 - Division II, Level Two)


For too long I have been focused on dynamic programming, which I must admit is slightly on the harder side when it comes to recognizing and applying quickly. Its evil twin, greedy, is much more implementation friendly.

There is mention of matroid theory, an approach that can be used for theoretically proving if greedy approach is valid to a particular problem or not. But haven't come around to actually reading it.

For now, my personal rules for greedy: if it is an optimization problem, which seems like Dynamic programming, and if bigger problems seem to be a copy of smaller problems and optimal solution to a smaller problem is sure to be part of optimal solution to the bigger problem, then greed is good.

Here is a practice problem from a recent Topcoder SRM(530), solved of course in a leisurely non contest environment. Once it is clear that a greedy solution is possible, it's just implementation.

Notes to myself: Wasted some time when trying to position the cutter over the cake. Made a mistake when evaluating boundary conditions, using the sizes along x and y for both cutter and cake.

Another observation is that one should work with the data structure provided by the problem statement. Trying to convert the input data into a more understandable array of something, or some other custom data structure, is also a waste of time. Exception is when the original data needs to be preserved, in which case a copy may be made using arrayCopy.

public class GogoXCake
{
public String solve(String[] cake, String[] cutter) {
int cutterSizeX = cutter[0].length();
int cutterSizeY = cutter.length;
int cakeSizeX= cake[0].length();
int cakeSizeY=cake.length;
for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cutterSizeX<=cakeSizeX-j && cutterSizeY<=cakeSizeY-i && cake[i].charAt(j)=='.' ) { // if cake is empty, position cutter at this location.
for(int p=0;p<cutter.length;p++) {
for(int q=0;q<cutter[p].length();q++) {
if(cutter[p].charAt(q)=='.' && cake[i+p].charAt(j+q)=='.') {
cake[i+p]=cake[i+p].substring(0, j+q)+ 'X' + cake[i+p].substring(j+q+1);
}
}
}
}
}
}
// for(int i=0; i<cake.length;i++) {
// for(int j=0;j<cake[i].length();j++) {
// System.out.print(cake[i].charAt(j) + " ");
// }
// System.out.println();
// }

for(int i=0; i<cake.length;i++) {
for(int j=0;j<cake[i].length();j++) {
if(cake[i].charAt(j)=='.') { // if cake is empty, position cutter at this location.
return "NO";
}
}
}
return "YES";
}
}

Palindromic Squares : USACO


Slightly easier problem this time.
Simple solution, 
Missed the second condition in :
       if(remainder>base || remainder>=10)
and it took the failing test cases to remind of this mistake.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class palsquare
{
public static void main(String[] args) throws NumberFormatException, IOException
{
// System.out.println(decimalToBaseB(120, 11));
BufferedReader reader = new BufferedReader(new FileReader(new File("palsquare.in")));
int base = Integer.parseInt(reader.readLine());

PrintWriter out = new PrintWriter(new FileWriter(new File("palsquare.out")));

String result;
for(int i=1;i<=300;i++) {
result = decimalToBaseB(i*i, base);
if (isPalindrome(result)) {
// System.out.println(i + " " + decimalToBaseB(i, base) + " " + result);
out.println(decimalToBaseB(i, base) + " " + result);
}
}
out.close();
System.exit(0);
}

private static boolean isPalindrome(String result) {
int middle=result.length()/2;
for(int i=0;i<middle;i++)
if(result.charAt(i)!=result.charAt(result.length()-i-1))
return false;
return true;
}

private static final String symbols = "0123456789ABCDEFGHIJ"; // we support till base 20

private static String decimalToBaseB(int number, int base) {
int quotient=0, remainder=0;
String result="";
while(number!=0) {
quotient = number/base;
remainder = number%base;
if(remainder>base || remainder>=10) {
result= symbols.charAt(remainder) + result;
}
else {
result= remainder + result;
}
number= quotient;
}
return result;
}
}

Powered by Blogger.