## SDE-3 Interview Questions

- 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

- 1of 1 vote
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.

- 0of 0 votes
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

- 0of 0 votes
Implement ConcurrentHashMap class in Java

- 0of 0 votes
Implement LinkedHashMap class in Java

- 0of 0 votes
You have been given a grid with some doors, walls and some empty spaces.

1st part : You have to tell the least no of moves to go from random position in the grid to the nearest door. You can move in four directions only, i.e, left, right, above, below.

2nd part : Least distance of every empty cell to the nearest door. Lots of discussion was done on both the parts of the problem.

- 0of 0 votes
Design garbage collector in Java

- -1of 1 vote
Design a system to upload images and tag them. Ability to search images with single and multiple tags.

- 1of 1 vote
Given a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Generalize to find the remainder for any number k.

- 0of 0 votes
Given a file having many lines of text(words) and given a dictionary having an API function boolean isValid(String word), which will return true is a word passed to this function is valid word in dic.,and will return false if given passed argument is not a valid word in dic.

Now read the file and check if each word as well as all possible words from its L to R and R to L combinations, are valid words in dic. or not.

- 1of 1 vote
Given sequentially placed boxes, each representing a number( which may be positive or negative), we need to select the numbers in order to have the maximum sum, having the constraint that if we select a given box, we cannot select adjacent box to it, but can select any other.