## SDE1 Interview Questions

- 0of 2 votes
given a N x N matrix find the no. of times a word is present in that matrix. constraints you can move in 3 directions from one cell 1. forward , 2. down 3. diagonal . Find all teh occurance of all the word

forward means right (x+1,y)

down mean (x,y+1)

diagonal means (x+1,y+1)

it can be done with BFS. {search the no. of occurance of a given word example "sachin" in the whole NxN matrix}

w | s | r | t | g | g|

a | a | c | h | i | n |

k | c | h | u | j | j |

o | h | i | n | y | q |

in this sachin can be found out 3 times.

- 1of 1 vote
Given a huge file 100 million integers. He further divided the file into 100 files with 1 million integers in each and each file is sorted. Needed to find the k smallest integers.

I used the concept of min-heap. Take the first element from each file and construct a min-heap. Take the root,as it is the smallest element and insert the next element from the file which contains the root root element. Heapify the tree and repeat k times.

The interviewer asked if another efficient method exists?

- 3of 3 votes
Given a set of intervals like 5-10, 5-10, 8-12, 9-15

Find the ith smallest number in these intervals.

for eg:-

Suppose we have intervals like 5-10, 8-12.

Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12}

So, 1st smallest number: 5

4th smallest number: 8

5th smallest number: 8 (here is the

change since now we have duplicate elements also) and so on.

- 0of 0 votes
Sliding window problem where window size is 3 and we need to find the minimum from the window.

- 0of 0 votes
Given a list with duplicate values find the first unique elements in it.

for eg: BH BH F AL HJ AL HJ PK

so answer is F

- 0of 0 votes
Given a matrix and need to traverse through it last position from first position and the matrix has 0 and 1 if there is 1 we cant proceed ahead.

- 0of 0 votes
Compare two release version and tell me which is larger

eg: 1.0.10 and 1.0.2

1.0.2 is greater

1.2.0 and 2.1.0

2.1.0 is greater

- 2of 2 votes
An integer array contains elements in increasing order till some point and then decreasing order , return the index of maximum number. Solution should be less than O(n). Ex - {1,2,3,4,5,3,1}

- 1of 3 votes
You are given a string which has numbers and letters. Numbers occupy all odd positions and letters even positions. You need to transform this string such that all letters move to front of array, and all numbers at the end.

The relative order of the letters and numbers needs to be preserved

I need to do this in O(n) time and O(1) space.

eg: a1b2c3d4 -> abcd1234 , x3y4z6 -> xyz346

Please don't submit your answers if it is not fulfilling the time-space complexity requirements.

- 0of 0 votes
There is a file which contains N words. There may be M anagrams in that file, K words on each anagrams. K>=1, M>=1, N>=1. You need to write an algorithm which will create one list for each anagram with k words and group all M lists with one data structure

- 1of 1 vote
Find your own method to balance an unbalanced binary tree.(you must not use existing methods like AVL, red black or b trees)

- 0of 0 votes
Convert a sorted integer Array to balanced binary search tree. This is very simple one and I could do it in O(n) time and O(1)extra space

- 0of 0 votes
Given 2 sorted linked list , merge them into single sorted list. Change the pointers, don't copy data

- 0of 0 votes
Given a read only linked list with next and random pointer , clone the list

- 1of 1 vote
It was a design question. You have to design a game. it has different types of monsters and different weapons. hero would shoot monster. each monster would have some initial health. Each weapon would do some predefined damage to monster. when its health gets 0, monster would die/disappear. and there would be multiple levels. based on level, monster and their behavior would change.

- 0of 0 votes
Given 2 rectangles , find whether they are overlapping or not.

- -1of 1 vote
delete all the nodes from a binary tree that lie on a path whose sum from root to leaf is less than a given value K. Twist was that the node values can be any integer. It may be a negative number.

- 0of 0 votes
Data structure to push, pop and find min element in O(1) time.

- 0of 0 votes
Given a linked list like a1-a2-a3-a4-b1-b2-b3-b4. Convert it into a1-b1-a2-b2-a3-b3-a4-b4

- 0of 0 votes
Given a MXN matrix. To find the number of ways to reach the mth row and nth column cell from 0,0 cell. Find the same if some of the cells are marked as not reachable.

- 0of 0 votes
There is a dictionary of billion words and there is one method provided

String getWord(int index); We can give it index and it will return the String on that index .

Now word is given to us we have to find out its index. O(logn) solution was required.

- 1of 1 vote
Frog can jump 1 or 2 steps write the code to find out number of ways to go up to n steps

- 0of 0 votes
program to pruning a binary tree

- 1of 1 vote
Given:

R number of Red Cards

B number of Black cards

K

Cards needs to be placed in a circle. Start from a position and for every K moves remove that card And repeat the process until all the cards are eliminated.

Question: Position the cards such that the red cards are completely eliminated before the blacks cards are selected for elimination.

- 0of 0 votes
You are given an unsorted array of integers that contain duplicate numbers.

Only one number is duplicated odd number of duplications, other numbers are repeated even number of duplications.

Find this number.

- 0of 0 votes
Find all nodes that are at a distance k from leaf nodes

- 0of 0 votes
Given a number N, find the smallest 3 digits number such that product of its digits is equal to N.For example for N=100 , 3 digits number is 455.

- 0of 0 votes
Given a function “f” in which 0 occurs with probability 0.4 and 1 occurs with probability 0.6. Using function “f” deduce a new function “f1” such that both 0 and 1 occurs with probability 0.5

- 1of 1 vote
You are given a n-ary tree. print all the nodes bottom up except for the right most node at each level.

`1 2 3 4 a b c d e`

print all except 4 (right most at level 1) and e (right most at level 2)

- 0of 0 votes
You are given an unsorted integer array consisting of 1's and 0's. You need to rearrange the array with alternating groups of 0's and 1's. The group length is determined by the function f(x)

f(0) = 1

f(1) = 2

f(n) = [square of f(n-1) - square of f(n-2)]

if you run out of either 1's or 0's, then fill the array with whatever is left.

input: 0,0,1,0,1,1,1,0,0,1,0,0,1,1,0,0

output: 0, 1,1, 0,0,0, 1,1,1,1,1, 0,0,0,0,0

f(1) = 1

f(2) = 2

f(3) = sqr(f(2)) - sqr(f(1)) = 3

f(4) = sqr(f(3)) - sqr(f(2)) = 5

f(5) = sqr(f(4)) - sqr(f(3)) = 16

here we don't have enough 0's left to fill the last group. So, we add the five 0's that were left.