## SDE-3 Interview Questions

- 0of 0 votes
Given a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.

Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.

- 0of 0 votes
There are N (N > 20) team, each team will play 'M' (say M =3) league match against every other team. Design various classes, and write the code and algorithm to find the winner.

Note: One match can be played on a single day, as there is just one stadium.

Note: No team should play matches on consecutive days.

Note: Algorithm should come up with Quarter Final, Semi Final, and Final matches.

Follow-up Question: If N is odd or even.

How your design will be modified if there are 'S' no. of stadiums.

- -1of 1 vote
Design calculator and related class, which returns result of the given expression, e.g if input is (3* 3) + 2 it returns 11.

Identify different OOPS classes and how would you call them.

- 0of 0 votes
Given a 3x3 tic-tac-toe board with players 1 and 2. Find all the possible ways player 1 can lose given a particular configuration of the board.

For example (0 denotes empty spot):

input:

0, 1, 0

2, 2, 1

1, 1, 2

Output: 1 (because the only move for player 2 to win would be to play board[0,0])

The input board can have any configuration (player 1 and 2 can be in all possible spots with any number).

- 1of 1 vote
given a set of digit from 1 to 9 {1,2,3,4,5,6,7,8,9}, write code to find k elements whose sum is equal to n.

e.g.

k=3, n= 9

{1, 2, 6}, {1, 3, 5}, {2, 3, 4}

vector<vector<int>> findKElementsSum(int k, int n)

{

}

- 1of 1 vote
How would you like to efficently find the total number of possible ways with which given string may be converted to whole dictionary words.

Example :

String = “Dogeatscare”

possible combinations – “Dog, eat, scare ” and “Dog, eats, care”

output is 2.

- 0of 0 votes
An art museum has the shape of a square and it contains N*N rooms. Some of the rooms are open and they contain art, other rooms are locked. There are guards in some of the open rooms. The museum's administration is afraid of a break in and they would like to evaluate how well the guards are positioned in the open rooms inside the museum. Precisely, they wish to know for each open room what is the distance to the colest guard. This distance is the min number of rooms a guard needs to pass through to reach that room. The guards can only move through the open rooms North, South, East and West and they can't leave the museum.

'.' is for open room 'G' is for open room where a guard is '#' is for a locked room Noboday can enter or pass through thesse rooms.

- 0of 0 votes
class QueryVector

{

QueryVector(vector values)

{

// Implement

}

vector GetIndices(list filters)

{

// Implement

}

}

Say for example vector is like

{“an”, “apple”, “day”, “keeps”, “doctor”, “away”, “apple”, “iphones”, “cool”, “doctor”, “recommends”}.

GetIndices(“apple”) should return (1, 6)

GetIndices(“doctor”,”cool”) should return (4,8,9)

GetIndices(“random”) should return empty vector ()

GetIndices(“random”,”keeps”,”day”,”doctor”) should return empty vector (2,3,4,9)

Important:

1. There can be millions of values in the input vector of string

2. GetIndices can be called repeatedly and it should be optimized

3. How storage optimization is considered and bitmaps etc are used.

- 0of 0 votes
How to design a Debugger both HLD and LLD?

- 0of 0 votes
Given MxN binary matrix, find the largest sub-square matrix with all 1’s.

- 0of 0 votes
Design a geographically partitioned multi-player card game, that supports multiple players, multiple games at a time.

Each game will have one contractor like ones we have in a bar, He can play a game or just watch it. Integrate payment systems.

First HLD was required, use cases, flow diagram. then a low level design was required all necessary classes where will you use polymorphism, where inheritance, multithreading, synchronised approach if needed, socket connections

- 2of 2 votes
Design a Netflix type system. Start from HLD to LLD.

Consider requirements like search, video serving, authentication, security, serving multi quality video.

- 0of 0 votes
Given an array of integers. We need to answer two types of queries point update and range sum in minimum time.

- 0of 0 votes
Put the given random pointers in linkedlist to point to next greater node such that if you transverse the list using random pointers, list become sorted. duplicates are allowed.

- 1of 1 vote
Find third highest value in a binary tree

- 0of 0 votes
Your input is a double array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.

Ex:

input is {3,4,5,1} --> output: 72

input is {1,1,1,5} --> output: 15

Follow up, if there are numbers <0

- 0of 0 votes
Today Google phone interview I was asked to code multithreading solution to return union of two sorted arrays in java for given number of processors. Does anybody can provide a short neat code sample om that?

- 0of 0 votes
// Create a numeric binary tree structure/classes that have left and right children and an integer numeric value.

// Write a function 'isBalanced' for a node that returns true if the sum of all the children on the left is equal

// to the sum of all the children on the right.

//Example:

// [12] [12].isBalanced() -> True. [3, 3]

// / \

// [3] [1] [1].isBalanced() -> True. [2, 2]

// / \

// [2] [0]

// / \

// [2] [0]

// - Part I: setup and isBalanced() function

// - Part II: implement “allBalancedNodes()” <— given a node, finds all balanced children

// allBalancedNodes(12) -> returns a list of balanced nodes: { [1], ... }

- 0of 0 votes
Given a list of employees and their bosses as a CSV file , write a function that will print out a hierarchy tree of the employees.

- 0of 0 votes
First asked how you can write a tree in a file?

Next question was lets say value of one node is changed, how can you update that in that file without writing the whole tree in file again?d

- 0of 0 votes
Find the first non repeating character in a string. For example if the input string "abcdeabc", non repeating character is "e"

- -1of 1 vote
Find if a mathematical string is balanced in terms of parenthesis. For example "(1+2)" is balanced and "(1+2" is not balanced.

- 0of 0 votes
Design and implement an algorithm to assign an unlimited M number of messages evenly among N number of servers (N will not change).

Input to the algorithm

A message contains a message identifier and a text string. The algorithm will be fed one message at a time.

There are N numbers of servers (N will not change), each can be identified by a unique id.

Output of the algorithm

When the algorithm is called to process a message, it should output the id of the server that the message is assigned to.

- 2of 2 votes
Apple On-site at Cupertino

Team Data Warehousing

Questions on Hadoop, Hive and Spark

I. Given a table with 1B of user ID and product IDs that the users bought, and another table with product ID mapped with product name. We are trying to find the paired products that are often purchased together by the same user, such as wine and bottle opener, chips and beer … How to find the top 100 of these co-existed pairs of products. If going with hadoop, where is the bottleneck and how to optimize?

II. Someone put distribute Random()*ID in a Hive script to prevent data skew. What would be the problem here?

- 1of 1 vote
Apple On-site at Cupertino

Team Data Warehousing

III. Given three letters ABC, where AB->C, AC->B, BC->A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.

For example, “ABACB” goes to “ACCB” (based on AB ->C, convert s[1] and s[2] to C)

“ACCB” goes to “BCB” (based on AC->B)

“BCB” goes to “AB”

“AB” goes to “C”

So it takes 4 steps to change the given string into a single character.

If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return -1.

- 1of 1 vote
Apple On-site at Cupertino

Team Data Warehousing

There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.

Only three pure coding questions were asked.

I. Use a stack to sort given data.

II. Given an array with positive integers only, find the MIN integer that is missing from the array.

- 0of 0 votes
You have given a tree, where each node can have multiple children. You have to find if the tree has a cycle or not.

Ex`A / \ / \ B C / | \ | \ D E F E H | B`

This tree has a cycle from B -> E -> B.

Please note that you only know the nodes that you have traveled in the tree, so at the beginning, you will only know that there is a root node and nothing else about any other node.

The followup question was to print the cycle in the tree if found.

- 0of 0 votes
Design a system having multiple jobs, interacting with each other such that :

1) A job can run for very long periods (1-2 days)

2) A node can fail/crash on which certain job is running

system should be scalable

3) Amount of data getting transferred is huge

4) Data in the system is very sensitive and needs security

job/s can fail

- 0of 0 votes
Top View of a Binary Tree in constant space

- 0of 0 votes
Given a pattern containing only Is and Ds. I for increasing and D for decreasing. Devise an algorithm to print the MINIMUM number following that pattern. Digits from 1-9 and digits can’t repeat.

Example:

1. Input: D Output: 21

2. Input: I Output: 12

3. Input: DD Output: 321

4. Input: II Output: 123

5. Input: DIDI Output: 21435

6. Input: IIDDD Output: 126543

7. Input: DDIDDIID Output: 321654798