5 weeks ago

mod2 870

Hyderabad

Interview Experience - 1 | Selected

Round - 1

• Introduce yourself.
• Jumped straight to programming problem.

  Given a M x N grid map, each cell of grid is '1' if there 
  is land, '0' if there is water. Print number of Islands.
  
  
  An island is surrounded by water and is formed by connecting 
  adjacent lands (vertically or horizontally). You can assume 
  outside matrix is completely filled with water.
  

• Resume based questions.
• OOPS.
• Real life Example for binary search.
• CN Questions
• ipv4 vs ipv6
• LAN vs WAN
• Switch
• Router
• OSI Layers
• Some OS questions.
• What are micro services? ( context : from resume)
• General vision on computer science.
• General discussion on security.
• What interests you most in Computer Science and Why?
• Do u have any questions for me?

---

Round 2

• Introduce yourself.
• DBMS - Normal forms, foreign keys, PostgreSQL - advantages
• Resume projects - grilled through CV
  - For each project they ask u more in detail and ask for different scenarios and corner cases in 2nd round, for me only one btp
• project was grilled for almost 35 min.
  - Regarding system stability, approaches tried, what is the most complex part in the whole project, why u chose this approach, why not other approaches etc
• What is mvc architecture?
• General behavioural questions.
• Given 2 roles, what do you choose why?
• What are your goals in future?
• Why apple?
• Do u have any other dream companies?
• Are you interested in devops?
• Do you have any other questions to ask?

---

Round - 3 (HR)

• Introduce yourself.
• How have you taken decisions in your life till now? (Eg. Why Engineering? , Why CSE?, Why IIIT Hyderabad?, Is it peer pressure ?)
• Given a situation where u and ur colleague's ideas are equally important and valid. What would you choose? Why?
• Why Apple?
• What are your strengths and weaknesses? Do ur friends agree that ur opinion matches with them?
• Do you have any questions?

SELECTED

2 hours ago

admin 1.6k

Valsād

Solution

We can treat given grid as an , assuming each grid cell is a node, and two nodes are connected if both of them are land and adjacent in grid.

Now required answer is simply in our graph. We can do it by using DFS, BFS or DSU (Disjoint Set Union) and time complexity remains in each cases.

99% of people end up using DFS, however most for this question is BFS and reason is it has best space complexity!

BFS Solution

Space Complexity proof

  int solve(vector>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          queue> neighbors;
          neighbors.push({r, c});
          while (!neighbors.empty()) {
            auto rc = neighbors.front();
            neighbors.pop();
            int row = rc.first, col = rc.second;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.push({row-1, col}); grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.push({row+1, col}); grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.push({row, col-1}); grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.push({row, col+1}); grid[row][col+1] = '0';
            }
          }
        }
      }
    }

    return num_islands;
  }