IMC OA 10/04/2022
Sian Xiao
1383
IMCInterview

The question is just the same as others, for example, anarchaworld and snpriyanka. anarchaworld did good job explained and summarized the questions.

Q1 Does the Path Exist?
You start at (x1, y1) and can move as instructed:

  1. (x + y, y)
  2. (x, x + y)
  3. (x + c, y + c)
  4. you can't reach (x, y) that x + y is a perfect square.

Determine whether a path exists from (x1, y1) to (x2, y2) given c, x1, y1, x2, y2.

I did a BFS search, using memorization.

from math import sqrt
memo = [[-1] * 1001 for _ in range(1001)]

def dfs(c, x1, y1, x2, y2):
    # already tried
    if memo[x1][y1] != -1:
        return memo[x1][y1]
    # obstacles
    if int(sqrt(x1 + y1)) == sqrt(x1 + y1):
        return 0 
    # pass over
    if x1 > x2 or y1 > y2:
        return 0
    # reach!
    if x1 == x2 and y1 == y2:
        return 1
    # dfs try three situations
    up = dfs(c, x1, y1 + x1, x2, y2)
    right = dfs(c, x1 + y1, y1, x2, y2)
    diag = dfs(c, x1 + c, y1 + c, x2, y2)
    
    if up == 1 or right == 1 or diag == 1:
        memo[x1][y1] = 1
    else:
        memo[x1][y1] = 0
    
    return memo[x1][y1]

def canReach(c, x1, y1, x2, y2):
    
    if dfs(c, x1, y1, x2, y2) == 1:
        return "Yes"
    else:
        return "No"

Q2 Busy intersection
MAIN STREET (0), and FIRST STREET (1) intersect and at one time only one direction is open. Determine at which second each car can pass.

The rule is simplied as:

  1. If in the previous second, there is no car passing through, then the first car on FIRST STREET gets to go.
  2. If in the previous second, one car passed, next car in this street can continue to go (unless no car follows and the other street should go).

I did a simulation on this.

from collections import deque

def getResult(arrival, street):
    
    time = 0
    idx = 0
    last = 1  # 1st street goes first
    q1, q0 = deque([]), deque([])
    ans = [0] * len(arrival)
    
    while True:
        # no car was moving so need to increase time
        move = True
        # add cars to queue, same logic below
        while idx < len(arrival) and arrival[idx] == time:
            if street[idx] == 0:
                q0.append(idx)
            else:
                q1.append(idx)
            idx += 1
        # no car in 1st street so we can let main go
        if q0 and not q1:
            last = 0
        # 1st street pop (move) all cars
        while last == 1 and q1:
            ans[q1.popleft()] = time
            time += 1
            move = False
            while idx < len(arrival) and arrival[idx] == time:
                if street[idx] == 0:
                    q0.append(idx)
                else:
                    q1.append(idx)
                idx += 1
        # main street pop (move) all cars
        while last == 0 and q0:
            ans[q0.popleft()] = time
            time += 1
            move = False
            while idx < len(arrival) and arrival[idx] == time:
                if street[idx] == 0:
                    q0.append(idx)
                else:
                    q1.append(idx)
                idx += 1
        # finish main street term, default to 1
        if not q0:
            last = 1
        # need to move on time
        # not += 1 because fail corner case [0, 100000]
        if move:
            time = arrival[idx]
            continue
        # finish all cars
        if not q0 and not q1 and idx == len(arrival):
            return ans

Both solutions passed all test cases, but might be stupid. Thanks.

Comments (1)