## SDE1 Interview Questions

- 0of 0 votes
given a string and a segmentation length k

For example:

"This is a good day" k = 10

Cut into:

"This (1/4)"

"is a (2/4)"

"good (3/4)"

"day (4/4)"

Each line followed by a suffix in the form of (i/n) has 10 chars including space (except for the last line), return the minimum cut required, for the example, just return 4.

- 0of 0 votes
trie search, Search Return all words that match the wildcard *

such as

add ("car")

add ("caw")

add ("cauw")

search ("c*w") returns "caw" and "cauw".

- 0of 0 votes
There are n bus lines, known bus stops by bus, the bus is bi-direction, ask from station A to station B at least a few transfers.

- 0of 0 votes
`given a binary array, you can flip 0 -> 1 or 1 -> 0 to make all the 1 are in the left part and all the 0 to the right part, return the minimun flip required example 1 1011000 -> 1111000 only need one flip 0 -> 1 example 2 00001 -> 10000 require 2 flips public int findMiniFlip(int[] nums) { } }`

- 0of 0 votes
the longest unique value path in a graph

/**

* Definition for undirected graph.

* class UndirectedGraphNode {

* int label;

* List<UndirectedGraphNode> neighbors;

* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

* };

*/

public class Solution {

public int findLongestUniqueValuePath(List<UndirectedGraphNode> node) {

}

}

- 0of 0 votes
Given a 2d grid map of '1's (land) and '0's (water), find the perimeter of each island. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

- 0of 0 votes
To determine if two graphs have isomorphism or not

- 0of 0 votes
Give an array A, find the (i, j) pairs that satisfy the condition.

Condition 1: A [j] = A [i] + 1, Condition 2: j - i is as large as possible

Followup condition 1 is changed to A [j]> A [i]

- 0of 0 votes
Given an array of length n + 1, containing elements 1 through n and a space,

Requires the use of a given swap (index i, index j) function to sort the array,

You can only swap the gap and a number, in the end, put the gap at the end

- 0of 0 votes
find a shortest string to cover all of a list of string,

For example, [aab, aabb, bc], should return aabbc,

because aab, aabb, bc are all the substring of aabbc

- 0of 0 votes
given 2 list of interval representing users online offline timestamp e.g (already sorted), find all intervals that both of users are online.

e.g A= [(3, 5), (7, 11)] B=[(2, 4), (9, 10)] --> [(3, 4), (9, 10)].

- 0of 0 votes
Design a SparseVector class that implements

Vector interface, which contains 4 methods: get(int index),

increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)

- 0of 0 votes
Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k. your method should be time and space efficent

example

int[] nums = {188930, 194123, 201345, 154243, 154243};

int k = 3;

Output

3, 0, -1

Explanation

For the first window of [188930, 194123, 201345], there are 3 increasing subranges ([188930, 194123, 201345], [188930, 194123], and [194123, 201345]) and 0 decreasing, so the answer is 3. For the second window of [194123, 201345, 154243], there is 1 increasing subrange and 1 decreasing, so the answer is 0. For the third window of [201345, 154243, 154243], there is 1 decreasing subrange and 0 increasing, so the answer is -1.

public int[] getdiff(int[] nums, int l){

}

- 0of 0 votes
`give an enum, where each element has a parent-children relationship, and children's expression is the value of parent append an index, such as enum vehicle { car = 1 toyota = 11 camry = 111 corolla = 112 honda = 12 truck = 2 GMC = 21 } Ask a value, return to his parent, such as GMC = 21, return to the truck`

- 1of 1 vote
Given a list points on a 2d plane, find

largest rectangular area that can be formed

for the rectangle only considers those parallel to x and y

- 0of 0 votes
`There is an unordered interval stream, write a method, returns the total length that all intervals cover by now class Interval{ int start; int end; } public List<Integer> countCoverLength(Iterator<Interval> stream){ }`

- 0of 0 votes
‘.’Matches any single character,' * 'Matches any sequence of characters (including the empty sequence).

There are two input, one is string pattern, and the other is dictionary like dict = ["cat", "cats", "and", "sand", "dog"].

return a boolean: whether to find a dictionary in the pattern match the word

eg: dict = ["cat", "cats", "and", "sand", "dog"].

pattern = "* t", -> true (can match cat)

pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

- 0of 0 votes
How would you store and retrieve values in Memcache if the values are larger than the individual value size allowed by Memcache?

- 0of 0 votes
Find all words [A-Z] in a dictionary (about 1M words) that are made of a subset (in any order) of the chars in the input parameter [A-Z].

ex: input "ACRAT" (10 to 20 chars, up to 30 worst case)

matching words: "A", "CAR", "ACA", "ART", "RAC".

non-matching words: "BAR", "AAA"

follow up : the input is a list of words. Return a list of words that each

list is formed by exactly the characters in the input list.

For example: two lists {“DEBIT”, “CARD”} and{“BAD”, “CREDIT”}

are formed by the same exact group of characters.

- 0of 0 votes
Given a string separated by a space like "123456 abc+efg" determine

the solution by mapping integers to letters like a:1, b:2, c:3, d:4, e:5, f:6.

The only operations allowed were + or -. So the calculated solution

that made the tests pass was 123+456 = 579.

- 0of 0 votes
How many subsets of a given array sum to zero?

- 0of 0 votes
Given numbers 1 through 52, take 5 unique numbers and determine

if the number 42 can be made using any combination of addition (+),

subtraction (-), multiplication (*), and division (/) on those 5 numbers

- 1of 1 vote
/* Intersection of two sorted interval lists, A=[(1,2), (5,7)..]

B=[(2,6)...] return [(5,6)..] */`import java.util.*; class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution { public List<Interval> Intersection(Interval[] i1, Interval[] i2) {}`

- 0of 0 votes
* Given a string on length N. You can swap only the adjacent elements

and each element can be swapped atmost once.

Find the no of permutations of the string that can be generated after

performing the swaps as mentioned.

Ex –

string – “12345”

Ans = 8

Explanations- (All the permutations)

12345

21345

13245

12435

12354

21435

13254

21354

- 0of 0 votes
Given an array of n positive integers, find the number of subarrays

such that product of the elements of those subarrays are less than k.

For eg. Arr= {2, 3, 6} k=10

No of such subarrays= 4

- 1of 1 vote
Print the levels of a binary tree in reverse order using stack and recursion

`Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]`

public List<List<Integer>> levelOrderBottom(TreeNode root) {

}

- 0of 0 votes
given an array, find whether there exists 3 elements a,b,c in it such that a+b=c using efficient method.

- 0of 0 votes
You are provided a BST, which is corrupted. One of the nodes in it has 2 parents.

Let’s say those are parent 1 and parent 2. It is ensured that none

of these parents will be the ancestor of the other. Identify the node,

and remove the link of the wrong parent.

- 1of 1 vote
Given an adjacency matrix of a directed graph, find the number of cycles in the graph

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