Compass | Karat | IC2 | Screening round | 1 hour
Anonymous User
613
BacktrackingDepth-First SearchInterview

The Interview was of duration 1 hour, The interviewer was very polite.
The stages of interview were:

  • My introduction [5 mins]
  • My project(any one on detail) [10 mins]
  • 2 coding questions [45 mins]
    Note: He was stressing on writing a workable code, He wasn't much interested in listening about non workable code.
  1. Given a list of words : ["cat", "bird", "apple"]
    Given a string : "tacappse"
    We need to find which word can be formed using the characters of the given string only once.** [Anagram type question]**
    private static int[] giveFrequency(String temp) {
        int[] freq = new int[26];
        for (int i = 0; i < temp.length(); i++)  // O(S)
            freq[temp.charAt(i) - 'a']++;
        return freq;
    }

    private static String find_embedded_word(String[] list, String temp) {
        int[] freq = giveFrequency(temp);
        for (int i = 0; i < list.length; i++) {
            int k;
            int freqOfCurrentWord[] = giveFrequency(list[i]);
            for (k = 0; k < 26; k++) {    // O(1)
                if (freq[k] < freqOfCurrentWord[k]) break;
            }
            if (k == 26)
                return list[i];
        }
        return null;
    }
  1. A grid of characters is given, we can move only one step right or one step down from current position,
    Suppose you are at ( i, j ), we can go to either ( i, j+1 ) or ( i+1, j)
    char[][] grid1 = {
    {'c', 'c', 'x', 't', 'i', 'b'},
    {'c', 'c', 'a', 't', 'n', 'i'},
    {'a', 'c', 'n', 'n', 't', 't'},
    {'t', 'c', 's', 'i', 'p', 't'},
    {'a', 'o', 'o', 'o', 'a', 'a'},
    {'o', 'a', 'a', 'a', 'o', 'o'},
    {'k', 'a', 'i', 'c', 'k', 'i'}
    };
    Given a string, we need to find out of the coordinates of the string from start to end if it exists in the grid;
class Coordinate {
    int x, y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
	public static boolean found = false;

    private static void dfs(char[][] arr, String str, int index, int i, int j, int r, int c, List<Coordinate> list) {
        if (!found && (i < 0 || j < 0 || i >= r || j >= c || arr[i][j] == '*' || arr[i][j] != str.charAt(index)))
            return;
        list.add(new Coordinate(i, j));
        char ch = arr[i][j];
        arr[i][j] = '*';
        if (index == str.length() - 1) {
            found = true;
            return;
        }
        if (!found)
            dfs(arr, str, index + 1, i + 1, j, r, c, list);
        if (!found)
            dfs(arr, str, index + 1, i, j + 1, r, c, list);
        if (!found)
            arr[i][j] = ch;
        if (!found)
            list.remove(list.size() - 1);
    }

    private static List<Coordinate> find_word_location(char[][] arr, String str) {
        found = false;
        List<Coordinate> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == str.charAt(0))
                    dfs(arr, str, 0, i, j, arr.length, arr[i].length, list);
                if (!list.isEmpty())
                    return list;
            }
        }
        return list;
    }

It was a simple dfs but I was finding it hard where to stop the backtracking so I used if else with a static boolean like child :D.
Please upvote if it helps :)
Keep hustling

Comments (0)