SDE - 1

You are given a rotated sorted array 'a' of length 'n' and a 'key'. You need to determine if the 'key' exists in the array 'a'.

The given sorted array is rotated from an unknown index 'x'. Such that after rotation the array became [a[x], a[x+1]...., a[n-1], a[1]..., a[x-1]], (0-based indexing). For example, if the array is [1, 2, 3, 4, 5] and x = 2 then the rotated array will be [3, 4, 5, 1, 2, 3].

Return True if the 'key' is found in 'a'. Otherwise, return False.

Note: Array ‘a’ may contain duplicate elements.

Example:

Input: a = [6, 10, 1, 3, 5], key = 3

Output: True

Explanation: The array 'a' contains the 'key' = 3, so we return True.

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

It was not a proper coding problem but rather a general discussion on data structures. The interviewer asked about my favorite data structure, and I said it was trees. Later, questions related to trees and binary trees were asked, such as the major differences between them, their use cases, when to use each, and how they are implemented in memory.

I was asked to write some SQL queries and assume the database schema and data types on my own.

Question 1: Write an SQL query to retrieve the top-rated photos from a user’s social media account based on likes and shares, with likes given higher priority than shares.

Question 2: This was a follow-up to the first question. I was asked to do the same for all followers (considering a separate schema where followers are linked to the user) in an optimized manner.