## pandu.vdp

BAN USER- 0of 0 votes

AnswersYou have given an array of Integers of size n, and a sliding window by 1 integer ,of size k <= n. you have to print minimum number in each window of size k.

- pandu.vdp in India

E.g: given array [3,9,0,3,18,6], i.e.n = 6 and window size k = 3

available windows for above array is [3,9,0] ,[9,0,3],[0,3,18], [3,18,6]

output should be : 0, 0, 0,3| Report Duplicate | Flag | PURGE

Chronus Java Developer Data Structures - 1of 1 vote

AnswersYou have gine n points with x and y cordinates (2 D), and you have to print how many of them are capable of forming a square and for each square print the points that are forming the square.

- pandu.vdp in India| Report Duplicate | Flag | PURGE

Goldman Sachs Financial Software Developer Algorithm - 0of 0 votes

AnswersYou are given a text file which contains all valid english words.(huge one).

- pandu.vdp in India

Now consider a typical mobile keypad in which letters (a,b,c mapped to number '2', and d,e,f mapped to 3..w,x,y,z mapped to 9).

give an algorithms that gives all valid words given a 'n' digit number.

i.e. your given

the following mapping

abc -- 2

def -- 3

ghi -- 4

jkl -- 5

mno - 6

pqr -- 7

stu -- 8

wxyz -- 9

And huge text file with all valid words

write a method

String[] getAllValidWords(String number);

e.g. input 228.

output .: BAT, CAT, ACT, ..etc.

discuss the time and space complexity for your algo.| Report Duplicate | Flag | PURGE

Adap.tv Software Engineer / Developer Algorithm

This is not the optimal one

here is the reason why it is not.

PriorityQueue is essentially a heap.

Complexity of removing an element(not the min or max) from heap takes O(n) time. And your second for loop run 'n-k' times ..which means total time is is O(k(n-k)) which is similar to the brute force one.

Edit: forgot to mention. and every time you are adding an element , which is Heapify operation takes logk time. so your algo would take

O((k+logk) (n-k)). which is slower than bruteforce one

Lets calculate complexity of algorithm.

In brute force way. finding a min element in a window of size 'k' would be O(k). and there exists n-k+1 windows. so total complexity would be O(K * (N-K))

now your algo would also give same complexity if input is sorted order in increasing way.

agree that ur algo is better than brute force way..but we still end up with same complexity. is there any other better approach using any data structures?

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

just for the clarification, for the input {1,3,3,1} and sum 4, what will be the out put?

- pandu.vdp January 30, 2013is it just 1,3 or

1,3 and 3,1 ?