## SDE1 Interview Questions

- 0of 0 votes
`Given an array of n * m matrix, and a moving matrix window (size k * k), move the window from top left to bottom right at each iteration, find the median number inside the window at each moving Can you do it better than brutal force method? void getMedian(int[][] matrix, int k){ print median } For matrix [ [1, 5, 3], [3, 2, 1], [4, 1, 9], ] The moving window size k = 2. At first the window is at the start of the array like this [ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5; then the window move one step forward. [ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ] ,get the median (2 + 3) / 2 = 2.5 then the window move one step forward again. [ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ] ,get the median (1 + 2) / 2 = 1.5`

- 1of 1 vote
We are planning an orienteering game.

The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.

However, the players have to pass all the checkpoints (@) on the map.

An orienteering map is to be given in the following format.

########

#@....G#

##.##@##

#..@..S#

#@.....#

########

In this problem, an orienteering map is to be given.

Calculate the minimum distance from the start to the goal with passing all the checkpoints.

Specification

* A map consists of 5 characters as following.

You can assume that the map does not contain any invalid characters and

the map has exactly one start symbol 'S' and exactly one goal symbol 'G'.

* 'S' means the orienteering start.

* 'G' means the orienteering goal.

* '@' means an orienteering checkpoint.

* '.' means an opened-block that players can pass.

* '#' means a closed-block that players cannot pass.

* It is allowed to move only by one step vertically or horizontally (up, down, left, or right) to the

next block.

Other types of movements, such as moving diagonally (left up, right up, left down and right down)

and skipping one or more blocks, are NOT permitted.

* You MUST NOT get out of the map.

* Distance is to be defined as the number of movements to the different blocks.

* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.

* You can assume that parameters satisfy following conditions.

* 1 <= width <= 100

* 1 <= height <= 100

* The maximum number of checkpoints is 18.

- 0of 0 votes
convert prefix to postfix expression

public String convert2postfix(String prefix){

}

- 1of 1 vote
Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array

can you do it without extra space

- 2of 2 votes
There is a maze of size m*n. You are sitting at (0,0). Another person is sitting in another cell. There are some cheeses placed in different cells with a cell value of 2. Some cells are blocked with a value of 1, thus you cannot pass it, while some cells are filled with 0, thus you can pass it.

You can move to left, right, up, down at each step. You have to collect all the pieces of cheese and then reach to Another Person cell. You need to return the minimum no. of steps required to do so.

Public int getShortest(int[][] maze, int[] anotherPersonCell){

}

- 1of 1 vote
In Docker, building an image has dependencies. An image can only be built once

its dependency is built (If the dependency is from outside, then the image can

be built immediately).

Sometimes, engineers make mistakes by forming a cycle dependency of local images.

In this case, ignore the cycle and all the images depending on this cycle.

Input is vector of pair of images (image, its dependency).

Output the order of images to be built in order.

##Example:

```

Example 1:

{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}

Output: master, numpy, tensorflow

Example 2:

{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}

Output: tensorflow

Example 3:

{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}

Ouput: f

- 0of 0 votes
There are n servers, reboot time is S0, S1..Sn-1

There are m tasks, the completion of the time required are T0, T1… Tm-1

How to assign tasks to each server makes the total time the shortest

- 0of 0 votes
Given a binary tree, how do you serialize and deserialize. Remember it is not BST it is a general binary tree which can also have duplicate elements.

- 0of 0 votes
Find the largest repeating sub-string in a string.

ex: banana

ans is: ana

- 0of 0 votes
Input: expression_tree | sequence_of_operations

The input is a single line of text with a expression tree and a sequence of operations separated by | character and ended by a \n newline character. Spaces are allowed in the input but should be ignored.

The expression tree is a sequence of 1-character variables A-Z and with sub expression trees formed by parenthesis (expression_tree). Examples: AB, A(B C D), (AB)C((DE)F)

The sequence of operations is a string of with characters R (reverse) or S (simplify)

Reverse means reverse the order of everything in expression tree. Applying reverse twice in a row cancels out. Example: (AB)C((DE)F) | R should print (F(ED))C(BA)

Simplify means remove the parentheses around the very first element in the expression tree and each of its subexpression trees. Applying S multiple times should have same result as applying S once. Example: (AB)C((DE)F) | S should print ABC(DEF)

String process(String input){

}

- -4of 4 votes
..

- 0of 0 votes
Convert Json string to Map

public Map jsonToMap(String t) {

}

- 0of 0 votes
Design Distributed Web Crawler.

- 0of 0 votes
What if server is slow, how to solve

What if one server is down

- 1of 1 vote
Array has N integers，range[0...N-1]。Set S[k], 0 <= K < N as S[K] = {A[K], A[A[K]], A[A[A[K]]],....},

write a function returns the size of the largest set S[K] for this array. return 0 if empty.

ex:

A = [5, 4, 0, 3, 1, 6, 2]

return 4 because S[2] equals {0, 5, 6, 2} 4 elements

- 0of 0 votes
Given an array of integers and a target number, determine if an arithmetic expression using these integers can be evaluated to the target number, you are allowed to use '+', '-', '*', '/'. Follow-up: when evaluating the expression, take operand precedence into account,

public boolean getTarget(int[] nums, int target){

}

exponentia is ok

- 0of 0 votes
find the Closest leaf to a given node in Binary Tree

can you do it in o(n) time

public TreeNode findCloestLeafNode(TreeNode root, TreeNode target){}

no parent pointer

- 0of 0 votes
validate IP in string format and return the uint32 format

‘1.2.3.4’ -> 0x01020304

- 1of 1 vote
Given a n-nery tree and its deep copy, a node in the original tree, return the corresponding node in the copy

public TreeNode getCopyNode(TreeNode root, TreeNode copy, TreeNode node)

- 0of 0 votes
Write the code to find the median of an unsorted array in average linear time.

followup the array is distributed across many machines.

- 0of 0 votes
Write a function to split a SQL query into individual statements.

give you a String which contains a separate Query with a semicolon ";" return all valid queries

Such as

"select name from courseinfo ;; select * from db1 where home = 'usa' ;"

The main thing to consider is that some special cases such as the escape symbol and the quotation marks inside the semicolon

public List<String> getQuery(String queries){

}

- 0of 0 votes
There is a conference room. N people are joining the conference. You have the start time and end time of each of them visiting it. You are asked to determine the maximum number of people that can be inside the room.

Example – Four people are visiting the conference

Person A B C D

Start (hour) 1 3 2 5

End (hour) 4 5 7 10

Answer will be – 3

- 0of 0 votes
Given a group of movies and their start time, assuming that are 1 hour long,

Returns a movie schedule (no time conflict).

enter:

Movie ("Shining", [14, 15, 16])

Movie ("kill bill", [14, 15])

Movie ("Pulp fiction", [14, 15])

One possible result is shining 16, kill bill 15, pulp fiction 14

public void schedule (HashMap <String, List <Integer >> map) {

}

- 0of 0 votes
friend circle. Given a streaming pairs representing friend relationship

(1, 2) means 1 and 2 are friends, (1, 3) means 1 and 3 are friends

Return all its friends.

List<Integer> getFriends (Iterator<List<Integer>> relations, int id){

}

- 0of 0 votes
given a matrix and a target, return if there is a path who’s sum is == target

Input: matrix, integer output: true or false;

- 0of 0 votes
permute the String including case change

"abc".

For example:

abc

ABC

Abc

aBc

abC

ABc

abC

AbC

- 0of 0 votes
implemnt JSON.stringify()

- 0of 0 votes
Given transactions between group of friends. How to minimize the number of transactions by eliminating redundant cash flow paths?

- 0of 0 votes
Design a suggestions list [system design] for words starting with prefix that user has typed on kindle device . The search is based on most frequent item occurring at the top to least frequent item at the bottom. Most frequent item depends on the usage of word globally.

For e.g user types "dra" . There should be a list of suggestions starting with dra such as dragon, drape, dracula etc based on their frequency of usage.

- 0of 0 votes
Design a image slide show 1) put image method 2) get image 3) random method. Random method should return a list of images such that images should be in randomized order and no image should be displayed twice without exhausting all images at once. I used list to store images . I used random class to generate randomly generated images based on the interval {0,list.size()}. But he insist on using randomization without depending on the list size.