General programming problems

• Often coding interviews involve problems which do not have complicated algorithms or data structures

  • Test ability to work though details and get the edge cases right

  • Practice

1.Check for palindrome

public static boolean isPalindrome(String testString)
{
    testString = testString.toLowerCase();
    
    int index = 0;
    int lastIndex = testString.length() - 1;
    
    while (index < lastIndex)
    {
        char forwardChar = testString.charAt(index);
        char reverseChar = testString.charAt(lastIndex);
        while (forwardChar == ' ')
        {
            index++;
            forwardChar = testString.charAt(index);
        }
        while (reverseChar == ' ')
        {
            index++;
            reverseChar = testString.charAt(lastIndex);
        }
        if (forwardChar != reverseChar)
        {
            return false;
        }
        index++;
        lastIndex--;
    }
    return true;
}

2.Find all points within a certain distance of another point

public static class Point
{
    private int x;
    private int y;
    
    public Point (int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public getX()
    {
        return x;
    }
    public getY()
    {
        return y;
    }
    public double getDistance(Point otherPoint)
    {
        return Math.sqrt(Math.pow(otherPoint.x - x, 2) + Math.pow(otherPoint.y - y, 2));
    }
    public boolan isWithinDistace(Point otherPoint, double distance)
    {
        if (Math.abs(otherPoint.x - x) > distance || Math.abs(otherPoint.y - y) > distance)
        {
            return false;
        }
        return getDistance(otherPoint) <= distance;
    }
}

3.Get the next generation of cell states

• Given a current generation of cells in a matrix, what does the next generation look like? which cells are alive and which are dead? write code to get the next generation of cells given the current generation

1. A live cell with fewer than 2 live neighbors dies of loneliness

2. A dead cell will exactly 2 live neighbors comes alive

3. A live with greater than 2 live neighbors dies due to overcrowding

public static int[][] getNextGeneration(int row, int col, int[][] current)
{
    int[][] next = new int[N][N];
    
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            next[i][j] = getCellState(i, j, current);
        }
    }
}

public static int getCellState(int row, int col, int[][] current)
{
    int liveCount = 0;
    int lastCellIndex = N - 1;
    if (row > 0 && col > 0) {
        liveCount += current[row - 1][col - 1];
    }
    if (row > 0) {
        liveCount += current[row - 1][col];
        if (col < lastCellIndex) {
            liveCount += current[row - 1][col + 1];
        }
    }
    
   if (col >0) {
        liveCount += current[row][col - 1];
        if (row < lastCellIndex) {
            liveCount += current[row + 1][col - 1];
        }
    }
    
    if (row < lastCellIndex) {
        liveCount += current[row + 1][col];
    }
    
    if (row < lastCellIndex && col < lastCellIndex) {
        liveCount += current[row + 1][col + 1];
    }
    
    return lastCellIndex == 2 ? 1 : 0;
}

4.Break a document into chunks

1. A chunk can be 5000 or fewer characters in length (This rule is relaxed only under one condition see below)

2. A chunk should contain only complete paragraphs - This is a hard and fast rule

3. A paragraphs represented by the ':' character in the document

4. List of chunks should be in the order in which they appear in the document (do not set them up out of order)

5. If you encounter a paragraph > 5000 characters that should be in a separate chunk by itself

6. Get all chunks as close to 5000 characters as possible, subject to the constraints above

• Suppose the chunk size is 5, rather than 5000 for ease of testing

a:bb:cc:abcdef:ab:c:d

• The resultant chunks would be

  • chunk 1: a:bb:

  • chunk 2: cc:

  • chunk 3:abcdef:

  • chunk 4: ab:c:

  • chunk 5: d:

public static List<String> chunkify(String doc) {
    List<String> chunkList = new ArrayList<>();
    String[] paragraphs = doc.split(DELIMETER);
    String currentChunk = "";
    for (String para : paragraphs) {
        if (currentChunk.length() + para.length() > CHUNK_SIZE) {
            if (currentChunk.length() > 0) {
                chunkList.add(currentChunk);
                currentChunk = "";
            }
        }
        
        if (para.length() > CHUNK_SIZE) {
            if (currentChunk.length() > 0) {
                chunkList.add(currentChunk);
                currentChunk = "";
            }
            chunkList.add(para + DELIMETER);
            continue;
        }
        
        currentChunk += para + DELIMETER;
    }
    
    if (currentChunk.length() > 0) {
        chunkList.add(currentChunk);
    }
    
    return chunkList;
}

5.Run length encoding and decoding

• "ABBCCC" will be encoded as "1A2B3C"

• "AABBBCCCC" will be encoded as "2A3B4C"

• "1D2E1F" will be decoded as "DEEF"

public static String encode(String originalString) {
    if (originalString == null) {
        return null;
    }
    
    StringBuilder sb = new StringBuilder();
    int currIndex = 0;
    while (currIndex < originalString.length()) {
        char currChar = originalString.chatAt(currIndex);
        int num = 0;
        int compareIndex = currIndex;
        while (compareIndex < originalString.length() &&
               charCurr == originalString.chatAt(currIndex)) {
               compareIndex++;
               num++;
       }
       sb.append(num);
       sb.append(currChar);
       currIndex = compareIndex;
    }
    
    return sb.toString();
}

public static String decode(String encodedString) {
    if (encodedString == null) {
        return null;
    }
    
    StringBuilder sb = new StringBuilder();
    int numStartIndex = 0;
    int numEndIndex = 1;
    while (numEndIndex < encodedString.length()) {
       while (Character.isDigit(Character.charAt(numEndIndex))) {
            numEndIndex++;
       }
       int charIndex = numEndIndex;
       String numString = encodedString.subString(numStartIndex, numEndIndex);
       int num = Integer.valueOf(numString);
       for (int i = 0; i < num; i++) {
           sb.append(encodedString.charAt(charIndex));
       }
       numStartIndex++;
       numEndIndex++;
    }
    
    return sb.toString();
}

6.Add two numbers represented by their digits

• (a + b +餘數) / 10 : 傳到下一位

• (a + b +餘數) % 10 : 該位的答案

• 先用動態的容器如list(vector)儲存答案, 最後再回傳array

public static int[] addNumber(int[] num1, int[] num2) {
    List<integer> digitList = new ArrayList<>();
    int lastIndex1 = num1.length - 1;
    int lastIndex2 = num2.length - 1;
    
    int carry = 0;
    int total = 0;
    int digit = 0;
    while (lastIndex1 >= 0 && lastIndex2 >= 0) {
        total = num1[lastIndex1] + num2[lastIndex2] + carry;
        digit = total % 10;
        carry = total / 10;
        
        digitList.add(0, digit);
        lastIndex1--;
        lastIndex2--;
    }
    
    while (lastIndex1 >= 0) {
        total = num1[lastIndex1] + carry;
        digit = total % 10;
        carry = total / 10;
        
        digitList.add(0, digit);
        lastIndex1--;
    }
    
    while (lastIndex2 >= 0) {
        total = num2[lastIndex2] + carry;
        digit = total % 10;
        carry = total / 10;
        
        digitList.add(0, digit);
        lastIndex2--;
    }
    
    if (carry != 0) {
        digitList.add(0, carry);
    }
    
    int[] sum = new int[digitList.size()];
    for (int i = 0; i < digitList.size(); i++) {
        sum[i] = digitList(i);
    }
    
    return sum;
}

7.Sudoku validator

• Given a sudoku board (complete or incomplete) check whether the current state of the board is valid

• A sudoko board is a 9*9 board which can hold numbers from 1 ~ 9. Any other number on that board is invalid

• For a sudoku board to be valid

  • 1.No row or column should have numbers 1 ~ 9 repeated

  • 2.No designated 3*3 block within the board should have numbers 1 ~ 9 repeated

public static boolean isValid(int[][] sudokuBoard) {
    if (!isValidRowsAndColumns(sudokuBoard)) {
        return false;
    }
    
    if (!isValidBlocks(sudokuBoard)) {
        return false;
    }
    return true;
}

private static boolean isValidRowsAndColumns(int[][] sudokuBoard) {
    List<Set<Integer>> rowList = new ArrayList<>();
    List<Set<Integer>> columnList = new ArrayList<>();
    
    for (int i = 0; i < 9; i++) {
        rowList.add(new HashSet<Integer>());
        columnList.add(new HashSet<Integer>());
    }
    
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            int cellValue = sudokuBoard[row][col];
            if (cellValue == -1) {
                continue;
            }
            if (cellValue < 1 || cellValue > 9) {
                return false;
            }
            
            if (rowList.get(row).contains(cellValue)) {
                return false;
            }
            
            if (columnList.get(col).contains(cellValue)) {
                return false;
            }
            rowList.get(cellValue).add(cellValue);
            columnList.get(cellValue).add(cellValue);
        }
    }
    return true;
}

private static boolean isValidBlocks(int[][] sudokuBoard) {
    List<Set<Integer>> blockList = new ArrayList<Set<Integer>>();
    for (int i = 0; i < 9; i++) {
        blockList.add(new HashSet<Integer>());
    }
    for (int rowBlock = 0; rowBlock < 3; rowBlock++) {    
        for (int colBlock = 0; colBlock < 3; colBlock++) {
            for (int minRow = 0; minRow < 3; minRow++) {    
                for (int minCol = 0; minCol < 3; minCol++) {
                    int row = rowBlock * 3 + minRow;
                    int col = colBlock * 3 + minCol;
                    int cellValue = sudokuBoard[row][col];
                    
                    if (cellValue == -1) {
                        continue;
                    }
                    if (cellValue < 1 || cellValue > 9) {
                        return false;
                    }
                    
                    int blockNumber = rowBlock * 3 + colBlock;
            
                    if (blockList.get(blockNumber).contains(cellValue)) {
                        return false;
                    }
                    
                    blockList.get(blockNumber).add(cellValue);
                }
            }
        }
    }
    return true;
}

8.Increment a number

• A < B < C < D

  • ABB -> ABC

  • ABBC -> ABBD

  • ABCD -> ABDA

public static List<Character> increment(List<Character> originNumber) {
    List<Character> incrementedNumber = new ArrayList<Character>();
    boolean incrementComplete = false;
    int currentIndex = originNumber.size() - 1;
    incrementedNumber.addAll(originNumber);
    
    while (!incrementComplete && currentIndex >= 0) {
        char currentDigit = originNumber.get(currentIndex);
        int indexOfCurrentDigit = digitList.indexOf(currentDigit);
        int indexOfNextDigit = (indexOfCurrentDigit + 1) % digitList.size();
        
        incrementedNumber.remove(currentIndex);
        incrementedNumber.add(currentIndex, digitList.get(indexOfNextDigit));
        
        if (indexOfNextDigit != 0) {
            incrementComplete = true;
        }
        
        if (icurrentIndex == 0 && indexOfNextDigit == 0) {
            incrementedNumber.add(0, digitList.get(0));
        }
        
        currentIndex--;
    }
    
    return currentIndex;
}