## SDE-2 Interview Questions

- 0of 0 votes
There is a car company and customers ask the car company for 'n' cars for start - end time intervals.

A company can get multiples request for the cars, find the minimum numbers of cars that the car company should have, to satisfy all the requirement for the given list of time intervals:

Eg :

for interval 1-3 cars needed are 2

for interval 2 -3 cars needed are 3

for intervals 3-4 cars needed are 4

for intervals 5-6 cars needed are 2

Answer is 5 for above, as we there is overlap between interval 1-3 & 2-3

- 0of 0 votes
I have a photo storage service. The actual photos are present in some storage and the index of these photos is present at some other place. The index is huge, say trillions of photos. Design the class for index node of each photo (with attributes like name*, date*, size*, accesscontrol, camera details, shot details, etc) such that 1. It is serializable. 2. For faster processing, I am interested in first 3 attributes. When deserializing the bytes of object, parse these 3 attributes i.e. instead of deserializing whole class, deserialize only part of the class (members marked by*), other members of class should be deserialized on demand with another call.

How will you test the performance of your serialization/ deserialization?

- 0of 0 votes
there is a chess board of dimension n X n. You are given with 2 squares on that board S(x1,y1) ;M(x2,y2). S is a fixed point. M can move diagonally. it can move any number of steps or jumps in 1 move . Find the minimum number of moves M needs to reach S

- 1of 1 vote
there is a news publishing/subscribing product of Amazon where electronic contents are collected from owners like newspaper, magazines. Customer is using kindle. Design how customer will get the content when his system kindle connects to net. how to send the contents to device?

- 0of 0 votes
This was a design question, discuss data structures/ complexities, etc.

There is a huge HashMap (Key-Value store). This is present in storage, dont worry about the Storage.

1. Build its index. Distributed system for indexing. Different cases: Key is a String/ Double/ complex structure, etc. How will you replicate this index structure - whole index is replicated/ parts of index are replicated.

2. How will you synchronize access (read/ write) if there are multiple replicas of the index partition. What if the actual Storage partition also has replicas.

- 0of 0 votes
You have a function f1() that generates 0 or 1 with the equal probability. Write a function f200() that generates a number between 1 and 200 with equal probability.

- 0of 0 votes
`Please analyze the two slightly obfuscated Tcl procedures below and document the code as it should be. Please change the symbol names to reasonable descriptive names. In addition, an explanation of why these procedures might or might not be useful or suggestions for improvements would be most welcome. This code comes from the application you would be working on. I replaced the names and removed the comments to make the challenge. Feel free to do research and experimentation, but please do not ask anyone else to solve it for you. proc f1 {a} { set n [llength $a] set p {} for {set i 0} {$i < $n} {incr i} { for {set j [expr {$i + 1}]} {$j < $n} {incr j} { lappend p [list [lindex $a $i] [lindex $a $j]] } } return $p }`

`proc f2 {fn lst {vn {}\}} { set result {} lassign $fn a b n if {$n eq {}} { set n {::} } set cl {} foreach n $vn { upvar 1 $n v set cl "${cl}set $n {$v}\n" } set cfn [list $a "${cl}${b}" $n] foreach item $lst { lappend result [apply $cfn $item] } return $result }`

- 0of 0 votes
Given a log file:

some garbage...from:123.54,78.21...more garbage..to:56,82,124.54...more

some more garbage...from:11.54,45.84...garbage..to:115.87,98.65

...

Write a program or shell script to return pairs of (from, to) coordinates.

Assumption: these coordinates will always appear in sequence: from ... to... from ... to...

But these from - to pair may or may not be on same line.

- 1of 1 vote
You have a BST and you need to assign an appropriate value to neighbor of all nodes (Explained in below example)

Node Structure`node { node leftChild, node rightChild, T data, node neighbor }`

A

/ \

B C

/ \ \

D E F

Based on above tree,

Node: Neighbor

A: NULL

B: C

D: E

E: F

- 0of 0 votes
Given an array of stock values of a company. Find out the time when a user would have bought the stock and sold the sock. Basically find the maximum positive difference of any two given elements in an array?

- 2of 2 votes
Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.

For Ex -

1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4

Follow up question - Extend the algorithm to n-ary tree.

- 3of 3 votes
Given a singly connected linked list, find the largest palindrome in the list in O(1) space.

- 3of 3 votes
Given a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.

eg – Consider this linked List structure

“aba” -> “cd” -> “efe” -> “d” -> “caba”

Hence this structure is palindrome .

- 0of 0 votes
Face to Face

Q4) two arrays given to you. First array contains number s. Second array contains key values.

We need to find smallest window in first array which covers all second array elements.

e.g:

Input= {6,7,1,3,2,4,5,2,3,1,2,5}

Keys = {2,5,1}

answer: from 9th index to 11th index is the smallest window.

- 1of 1 vote
Face to face

Q3) stream of numbers coming, get 'n' min elements at any point of time

- 0of 0 votes
Written test:

Q2) in single linked list reverse alternative k nodes.

e.g. k=3 , 1->2->3->4->5->6->7->8->9->10

3->2->1->4->5->6->9->8->7->10

void reverseAlternativeKNodes(node *&head, int k);

- 0of 0 votes
Written Test question:

Q1) Given binary tree find largestPath size from one leaf to another leaf.

int getLargestPathSize(node *root);

- 0of 0 votes
Given an N-ary tree with thousands of nodes in it. Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path.

For example,

A

/ | \

B C D

/ / | \

E F G H

Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:

a) (E-F), (G-H) or

b) (E-G), (F-H) or

c) (E-H), (F-G) or

d) (E-D), (F-G) or

e) (E-D), (G-H) or

f) (E-D), (F-H) or

g) (D-H), (F-G) or

h) (D-G), (F-H) or

i) (D-F), (G-H)

Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.

i.e. E-B-A-C-F —> (E-F) pair

D-A-C-G —> (D-G) pair

D-A-C-H —> (D-H) pair

- 0of 0 votes
Given a tree, and a pointer to some node in the tree, print the left most element in the same level as that node

- 0of 0 votes
Given an input of the calendar objects of 10,000 employees, input is a time interval T and an employee[] array, find the first interval where all the employees in the employee[] array are free for a minimum time interval T (i.e schedule the meeting)

- 0of 2 votes
Given a binary tree, connect all node in the same level in toggle manner.

Toggle the linking every K level. For first K level, you should link to next right node. Next K you should link to next left and so on.

Node structure is :

struct node

{

int data;

struct node *left, *right, *next;

};

Each level next should point to the next right or left node in the level. For last node in each level, next should be NULL

For ex - if K=2 then for first 2 level of tree connect next pointer from left to right and for next 2 levels connect next pointer from right to left and so on.

- 0of 0 votes
Design a restaurant reservation system - You need to design everything from scratch - Identify actors in the system, identify what all data should be stored in persistence storage (and why). How would you make your design scalable?

- 1of 1 vote
Design a data structure which could perform the following operations in O(1):

- Insert(), Delete(), Search(), getRandom()

getRandom() should pick a "random" element from your data structure, and should not be predictable (for instance always picking the "first" element from your DS)

- 1of 1 vote
You are given a stream of incoming strings. Design a data structure, which at any instant, could tell the 100 most repeated words in constant time.

- 0of 0 votes
Given a very large array of sorted integers, find the number of times a particular integer has been repeated in the array. Required complexity : O(logN)

- 0of 0 votes
Given a string regex and another string pat find whether the pattern is acceptable against given regex string.

Regex string contains following characters and special characters:

1. Normal alphabets – a to z and A to Z

2. ‘$’ – all string should end with all characters preceding $

Example:

Regex :abc$ ,

Pattern: abcd(Not acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(acceptable) etc..

3. ‘^’ – all string should start with all characters exceeding ^

Example: Regex : ^abc

Pattern: abcd(acceptable) , abc(acceptable), ab(Not acceptable), dhfusdhabc(NOT acceptable) etc..

Regex: ^ then only pattern acceptable is null.

4. ‘.’ – any character can be mapped to dot except null

Example 1: Regex : .abc

Pattern: Zabc(acceptable) , abc(NOT acceptable), ab(Not acceptable), habc(acceptable) etc..

Example 2: Regex :a.bc

Pattern: abc(NOT acceptable) , aXbc(acceptable), ab(Not acceptable), habc(NOT acceptable) etc..

5. ‘*’-the character just preceding * can be repeated n time where (n>=0)

Example 1: Regex :abc*de

Pattern: abccccccccccde (acceptable), abcde(acceptable), abcccd(not acceptable)

- 0of 0 votes
Given a list a1,a2,a3….an. Comparison between elements is given like a1>a2, a3>a5, a4>a2…..etc. Find whether there are any situations that we can sort the list in to the ascending order on the basis of comparison. Yes or No , explain the conditions

- 0of 0 votes
Given 2D Array of only 0s and 1s, Find the row which gives max decimal value.

Input: int array[3][3] = {{0,1,0,}{1,1,0},{1,0,1}};

Output : 2(second row)...decimal value is 6

- 0of 0 votes
Find the largest substring in s1, such that all characters in the substring are present somewhere in s2

- -1of 1 vote
Design and implement a scalable multi-player N*N TicTacToe game.