## SDE1 Interview Questions

- 0of 0 votes
How does Google know that you are who you say you are?

- 0of 0 votes
How would you design the search future in Google from frontend to backend?

- 0of 0 votes
(Variant of Children-Sum Problem better than O(n^2))

Given a tree, implement a function which replaces a node’s value with the sum of all its childrens’ value, considering only those children whose value is less than than the main node’s value.

Eg: input = 60->50->80->40 , output = 90->40->40->0

- 0of 0 votes
Find if a given number can be expressed in the form of p^q, where p and q are integers

- 0of 0 votes
Find all palindromes in a given string. Single letters are also considered as palindromes.

- 0of 0 votes
Given a number A, find the smallest number which has only 1s and 0s as its digits which divisible by the number A. For example: if the given number A is 4, the smallest number with 1s and 0s is which is divisible by 4 is 100.

- 2of 2 votes
{{

There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.

Your objective is to minimize the number of sort operations and number of data transfer operations.

Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.

}}

- 0of 0 votes
Entry in the log file is like this:

User 1 visited Page 4

User 3 visited Page 2

User 7 visited Page 9

.

.

.

Design an efficient data structure which supports queries like the following:

Which page was visited by exactly 2 users in day?

Which page was visited by only one user exactly 2 times in a day?

Which page was visited by ‘User 3? more than 5 times in a day?

- 0of 0 votes
Design a system for finding the costliest element always whenever we pick up an element from a box.(concept of Max Heap)

- 0of 0 votes
Entry in the log file is like this:

User 1 visited Page 4

User 3 visited Page 2

User 7 visited Page 9

.

.

.

Design an efficient data structure which supports queries like the following:

Which page was visited by exactly 2 users in day?

Which page was visited by only one user exactly 2 times in a day?

Which page was visited by ‘User 3? more than 5 times in a day?

- 1of 1 vote
Given N scientists and K black holes, each scientist can query on radius, size and temperature of a black hole, what data structure would you use?

Following queries are important.

Which scientist had queried on which black hole.

What were the queries made by that scientist.

- 0of 0 votes
In a tennis tournament of N players every player plays with every other player.

The following condition always hold-

If player P1 has won the match with P2 and player P2 has won from P3, then Player P1 has also defeated P3.

Find winner of tournament in O(N) time and O(1) space. Find rank of players in O(NlogN) time.

- 0of 0 votes
Write code for scheduling algorithms for such a cab services provided you have a list of future bookings, and list of cabs in your fleet.

- 0of 0 votes
In an auctioning system, the bidder with the highest bid wins but charged at kth highest price. Develop a system for it. Solved it using a hashmap. Was asked to write a code for the same.

- 0of 0 votes
Design a system which would make a schedule for a user to complete a book in given number of days. A pre condition is that the schedule for every day should end at the end of some chapter.

Ex – 3 chapter with 10 pages each and user has to complete this book in 2 days, then the schedule should be either be 2 chapters on first day and 1 chapter on second or 1 chapter on first day and 2 chapters on second. (code)

- 1of 1 vote
Implement DFS

After I implemented this, I was told to implement it without recursion. He told me to write pseudo code. I wrote it using stacks.

- 1of 1 vote
Given a matrix (0,0 is to the botto9m left like co-ordinate system)of 0s and 1s and two co-ordinates find if there is a path between them, Also you can only travel via 1s and you can only go up or right.

Answer: Backtracking algorithm

- 0of 0 votes
given K sorted arrays merge them

Answer: Told him how to do using merge of merge sort. He wanted me to do another approach I googled later you can use min heap for it.

- 2of 2 votes
Given an array of integers find the element for which the sum of left = sum of right. example -1 100 1 98 1 should return index of 1 i.e 2

Answer: First told him about Brute Force approach and then told him if we can iterate once and get the total sum`int findIndex(A){ int sum =0; for(int i =0;i<A.lenght;i++) { sum+= A[i]; } int lSum=0; for(int i=0;i<A.length;i++) { int rsum = sum - lsum-A[i]; if(lsum==rsum) return i; lsum += A[i]; } return -1; }`

- 0of 0 votes
Given a string having a number:

"625626628"

Here the substrings are in consecutive order except for 1 substring which is missing. Find the missing substring.

Test cases:

"1235678" -> 4 is missing

"9979981000" -> 999 is missing

"624625627" -> 626 is missing

- 3of 3 votes
How can you design a data structure that can do the following operations in O(1) time:

Insert, Delete, Search, Max which returns the maximum number

I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?

- 0of 2 votes
You have given a mathematical expression in string format.

Example: "3+12*3-4/7"

You need to write function which will return final result of the given expression. Don't use Expression Tree and start scanning from left to write.

It should be bug free.

- 0of 0 votes
A 2D matrix is given to you. Now user will give 2 positions (x1,y1) and (x2,y2),

which is basically the upper left and lower right coordinate of a rectangle formed within the matrix.

You have to print sum of all the elements within the area of rectangle in O(1) running time.

Now you can do any pre computation with the matrix.

But when it is done you should answer all your queries in constant time.

Example : consider this 2D matrix

1 3 5 1 8

8 3 5 3 7

6 3 9 6 0

Now consider 2 points given by user (0, 2) and (2, 4).

Your solution should print: 44.

i.e., the enclosed area is

5 1 8

5 3 7

9 6 0

- 1of 1 vote
You have a chess board of size NxN. You have a horse at a given starting position. You also have a function that gives you all the positions that the horse can reach from it's current position.

Given an ending position, find the path to it that uses the minimum number of moves.

- 5of 5 votes
Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

You can assume each number in the array is a positive integer and not greater than 100

Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

- 0of 0 votes
Array of size (n-m) with numbers from 1..n with m of them missing. Find one all of the missing numbers in O(log). Array is sorted.

Example:

n = 8

arr = [1,2,4,5,6,8]

m=2

Result has to be a set {3, 7}.

- 1of 1 vote
Give you a list of Modules of Dependencies,

A --> B,C

B --> D,E,F

D --> F

And please return back a correct build order of Module (input)

- -4of 4 votes
Shorten a List of Strings.

- 0of 2 votes
Design a Black-Jack poker game

- 4of 4 votes
Give an 2d-characters Grid, char[][] A, and a dictionary, List<String> dict. Search all possible words in the 2d-Grid.