Question

Goldman Sachs OA | Intern 2023 | On-Campus | India | August 2022 | Set - 21

Answer 1

Time Limit: 30 minutes, 2 questions

 

1. Harry and The Philosopher's Stone

 

Harry is being chased by an unknown enemy while trying to get the Philosopher's stone to a safe place. He stands on one corner of a giant wizard chess board with the door to escape being at the diagonally opposite end of the board.

 

Wizard chess boards are always square in shape, and allow anyone to move only one step at a time in any of the four directions: forward, backward, left and right. Some blocks on the board have mark of Voldemort and if Harry steps on any of those blocks, he will instantly die.

 

Harry is standing at the top-left corner block of the board, and the door is at the bottom right corner block. To avoid capture, Harry needs to get to the escape door as quickly as possible. Help Harry in his quest by writing a program to find out least number of steps needed to reach escape door.

 

Example

 

Input:
7
DVDDD
DDDVD
VVVDD
DVVDV
DDDDD

 

Output:
12

 

Constraints

 

1<=Size of board<=100

 

My approach: Simple iterative BFS would suffice and pass the TC. Store in queue<pair<int,int>>

 

2. Fibonacci Ways

 

Given a Fibonacci sequence, a function f(n) represents the number of ways in which the integer n can be represented as a sum of Fibonacci numbers without repetition of any Fibonacci number.

 

Eg. f(13) = 3, since possible ways are {13}, {8,5}, {8,3,2}. {5, 5, 3} won't be considered since 5 is repeated.

 

Now, S(n) is defined as sum of all f(k) from k=0 to k=n inclusive.

 

Write a program to compute S(n) value for a given n.

 

Example

 

Input:
10

 

Output:
18

 

Constraints

 

1<=n<=4000

 

My approach: Tried a variant of Knapsack. Couldn't complete due to very less time.

Answer 2

Q1 : Similar to Minimum Efforts Path (https://leetcode.com/problems/path-with-minimum-effort/)

 

 def minimumStepsPath(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        
        q = deque()
        cost = [[float('inf') for _ in range(cols)] for _ in range(rows)]
        cost[0][0]  = 0
        if matrix[0][0] == 'V':
            return -1
        heap = [(cost[0][0], 0, 0)]
        
        heapq.heapify(heap)
        
        dx = [-1, 0, 0, 1]
        dy = [0, -1, 1, 0]
        
        inside = lambda x, y: x>=0 and x<rows and y>=0 and y<cols
        
        while heap:
            curr_cost, x, y = heapq.heappop(heap) 
            for d in range(4):
                px = dx[d] + x
                py = dy[d] + y
                if inside(px, py):
                    height = matrix[px][py]
                    if height == 'V':
                        continue

                    new_cost = curr_cost + 1
                    if cost[px][py]>new_cost:
                        cost[px][py] = new_cost
                        heapq.heappush(heap, (new_cost, px, py))
        
        if cost[rows-1][cols-1] == float("inf"):
            return -1
        return cost[rows-1][cols-1]

Answer 3

Q2 (DP - Coin Change/Knapsack)

 

Note that Fibonacci sequence starts at 0. We can compute the sequence while we are looping the dp.
For each Fibonacci sequence number, we can either take or not take.

 

1. If we don't take: dp[i][j] += dp[i-1][j]
2. If we take: dp[i][j] += dp[i-1][j-val]

 

Time O(N * num of Fib number <= N)
Space O(N)

 

        int N = 4000, ans = 0;
        int[] dp = new int[N+1];
        dp[0]=1;
        for (int a = 1, b = 1; b <= N; b+=a,a=b-a){
            for (int i = N; i >= b; i--){ // loop it backward to avoid taking the same element twice.
                dp[i] += dp[i-b];
            }
        }
        for (int i = 0; i <= N; i++){
            ans += dp[i];
        }