## SDE-3 Interview Questions

- 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.

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

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

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

- 0of 0 votes
Given 2 integers, add them without using any arithmetic operator

- 0of 0 votes
Implement a LRU cache with ttl at each block

- 0of 0 votes
Given some resources in the form of linked list you have to delete all the resources which sum up to 0(Zero) and return the remaining list.

- 0of 0 votes
Find all anagrams of a given string in a file of size 1TB.

- 0of 0 votes
Given two strings print all possible permutations of two strings such that the order of characters are maintained.

- 0of 0 votes
Given an array,generate all valid ip address from the array.

- 0of 0 votes
Find Longest Repeated Substring in the given string.

- 0of 0 votes
Given a equi-weighted uni directed graph and need to find the max distance possible from a given node.

- 0of 0 votes
In a binary tree return the maximum "turns" in tree. A "turn" is defined as LRL or RLR traversal.

- 0of 0 votes
Implement multiple stacks using a single contiguous block of memory

- 0of 0 votes
Write an efficient solution to give the next best available slot in a parking lot given that you need to minimize the effort to park and exit from the lot.