## Recent Interview Questions

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

- 0of 0 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
2 process runs the following code. What will be the output

`// Assume this address is legal address for both the process int *sharedmemoryaddress = 0x1232; void SomeRunningFunction() { for(int i = 1; i < 1000; ++i) { *sharedmemoryaddress = i; sleep(2000); } }`

What does the 2 process print. Consider unicore and multicore processors. What is the significance of sleep here. What are we achieving from sleep.

- 1of 1 vote
WAP in java to find duplicate element in array in one scan.

- 1of 1 vote
Design Uber or Lyft like architecture keeping scale, latency and availability in mind. The design can be at macro level first, that is, major components like persistent store (SQL/NoSQL/redundant), cache, communication/messaging. The design and if time permits, details will then be discussed/challenged.

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

- 0of 0 votes
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
For typical word ladder problem to get the shortest path, BFS has complexity exponential to the word string length. How to optimize?

- 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 long string s and short strings t1, t2, t3 (which can have different length) find the shortest substring of s which contains t1, t2 and t3.

- 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 0 votes
write a program to accept a value for 4x4 matrix. find the total of matrix, minimum and maximum number in matrix

- -1of 1 vote
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
This question is windows based subsystem design to test the design skills. We are working in a complex system which involves multiple process, DLLs, windows services which will be gets installed on our system with the project. We have to design a logger system for this project where in all the multiple subsystem can use this logger system for their logging activities .

Design pattern used

Statically linked or Dynamically linked?

How the logger functions are designed (sample signatures)

How we can improve performance while logging (Think of ETL tracing)

- 0of 0 votes
Sort a set of ip address given either in ascending or descending order

char** SortIPAsc(char** pIPAddress);

char** SortIPDesc(char** pIPAddress);

- 0of 0 votes
Write a method that takes in a positive integer, return the number of 2s between 0 and the input number.

If the input value given is 13, it should return 2 as the number 2 and 12 are between 0 and 13.

If the input value given is 21, it should return 3 as the number 2,12 and 20 are between 0 and 21.

- 0of 0 votes
Implement an algorithm that takes a adjacency list and produces a topological sort of the vertices.

INPUT:

1 2

1 3

1 4

3 5

2 5

4 5

Returns:

1 2 3 4 5

- 0of 0 votes
Validate whether given string is valid JSON fromat string or not.

I/P: {a:b}

O/P: Yes Valid JSON

I/P: {a:b, c:d}

O/P: Yes Valid JSON

I/P: {a:b,c:{e:f}}

O/P Yes Valid JSON

I/P: {a}

O/p: not a valid json

I/P: {{a}}

O/P: not valid JSON

- 0of 0 votes
Reverse k batch nodes in single linked list

I/P: k =3 , 1->2->3->4->5->6->7->8->9

O/P: 7->8->9->4->5->6->1->2->3

I/P: k =3 , 1->2->3->4->5->6->7->8->9->10

O/P: 10->7->8->9->4->5->6->1->2->3

- 0of 0 votes
write a method that takes in 2 int arrays of any size and returns an array that calculates the sum of both.

for example, [1,2,3] and [2,3,4] will return [3,5,7]

Or [1,2,3] and [2,3,5,5] will return [2,4,7,8]

however, if it's like [9,9,2] and [0,1,3] you need to carry the sum so it returns as [1,0,0,5]

** SINGLE DIGIT ONLY

- 0of 0 votes
Imagine you have a row of numbers like below(a traiangle) .By starting at the top of the triangle find the maximum number in each line and sum them up example below

5

9 6

4 6 8

8 7 15

Answer I.e. 5+9+8+7 = 29

writw a code to find the maximum total from top to bottom. Assume triangle can have at most 100000 rows.

Input Output specifications

Input Specification

A string of n numbers (where 0<=n<=10^10)

eg.5#9#6#4#6#8#0#7#1#5

Output Specification

A sum of the max numbers in each line (as string ) or Output invalid in case of invalid input/triangle

Examples

eg1.

Input :5#9#6#4#6#8#0#7#1#5

Output:29

eg 2 .

Input :5#9#6#4#6#8#0#7#1

Output:invalid

eg 2 .

Input :5#9##4#6#8#0#7#1

Output:invalid

- 0of 0 votes
Given N balloons, if you burst ith balloon you get Ai−1∗Ai∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.

Assume that we have extra 1 at left most and right most positions. (don't take in answer just for boundary positions)

Hence if we have left or right boundary positions we multiply 1.

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

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

- 0of 0 votes
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
At regular interval, we are receiving data (Price,Quantity). We need to find Most Sold Price(MSP). Need to design the solution to print the current MSP with total Qty of that price, every time a set of price and its quantity sold is provided as input.

`Time Price Qty MSP(Total Qty) 11:01AM $10.01 100 $10.01(100) 11:03AM $11.01 200 $11.01(200) 11:04AM $12.81 150 $11.01(200) 11:06AM $10.01 210 $10.01(310) 11:07AM $10.01 180 $10.01(490) 11:08AM $12.81 400 $12.81(550) 11:09AM $11.01 200 $12.81(550)`

In the interview, I wrote a solution using priority queue where each element of the priority queue is a tuple consisting of price and quantity. The priority queue arranges itself based on the quantity value of each tuple. When new value comes we access the tuple having the particular price, retrieve its quantity. Delete this tuple and insert a new tuple with the same price and updated quantity.

The interviewer was not satisfied with the solution and commented this is not how a large scale application will be build which is running throughout the day.