## SDE1 Interview Questions

- 0of 0 votes

AnswersYou have to implement the following function:

- Rising star November 30, 2017 in India

int MinColoring(int k, char* str);int MinColoring(int k, char* str);static int MinColoring(int k, String str) {}static int MinColoring(int k, string str) {}

The function takes a string 'str' of size 'n' and an integer 'k' as its arguments and returns the minimum no. of paint operation required to achieve the final colored sequence as represented by 'str'.

A paint operation is defined as coloring exactly 'k' consecutive balls out of 'n' balls with a single color.

Assumptions:

n > 0

0 < k <= n

Note:

Paint operation always starts from the ball at index 0

Any ball can be repainted any no. of times

Each character in 'str', represented by small letter alphabets, denotes the final coloring of the ball at that index

If the colored sequence cannot be obtained by any no. of paint operations, return -1

Paint operation can not be performed for less than 'k' balls

Example:

Input:

k: 3

str: rrggg

Output:

2

Explanation:

Since we can color 3 balls at a time, we can first color the balls {0, 1, 2} with color "r". Next, we can color the balls {2, 3, 4} with color "g". As a result, color sequence of the ball will be rrggg. And this was achieved in 2 paint operations.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGenerate a random MxN starting board. It cannot have 3 or more pieces in a

- ajay.raj November 28, 2017 in United States

row (horizontally or vertically) of the same color. K colors.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersRobot walked from the upper left to the lower right, can only go down and to the right, the number of each grid is height,

- ajay.raj November 25, 2017 in United States

If the next cell height is higher than the current, we must pay the difference cost, otherwise no cost,

Find the minimum cost to reach the lower right corner,

Follow up 1, print the minimum cost path;| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersGas station problem, give you a starting point A and End B. An array of oil prices at each gas station index represents the location of each gas station. MPG = V, find the minimum cost of gas from A to B

- ajay.raj November 25, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

Answersgiven a string, and integer k, check if this string contain all the binary string of length k

- ajay.raj November 24, 2017 in United States

For example, k is 2, then 00,10,01,11.

Followup 1, find a string that can contain all binary string of length k.

Followup 2, find a shortest string that can contain all binary string of length k.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersExpression evolution

- ajay.raj November 24, 2017 in United States

expr :: = int | '(' op expr + ')'

op :: = '+' | '*'

Cite a few examples:

"3" -> 3

"(+ 1 2)" -> 3

"(+ 3 4 5)" -> 12

"(+7 (* 8 12) (* 2 (+ 9 4) 7) 3)" -> ...

Public int getValue(String s){

}| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answers

- ajay.raj November 20, 2017 in United States`Insert a number into an array of sorted intervals. For example, [1,4], [6,8], after insert 5, return [1,8]. class Interval{ int start; int end; public Interval(int start, int end){ this.start = start; this.end = end; } } class Solution{ public List<Interval> insert(List<Interval> list, int val){ } }`

| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answersgive a bunch of job dependency, such as A-> B, A -> C, B-> D, and so on, implement two interfaces.

- ajay.raj November 17, 2017 in United States

The first one is get_next_stage, which returns jobs in parallel for the next phase. The second is job_done, which tells you which job completed.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answersdetermine whether a number is the sum of two squares, such as 17 = 16 +1

- ajay.raj November 14, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answers

- ajay.raj November 14, 2017 in United States`Give a matrix, for example 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 Find if there is a rectangle in the matrix, all four corners are 1 For the example, there is only one rectangle, that is 1 0 1 0 1 0 1 0 1`

| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answersclass DirectedGraphNode {

- ajay.raj November 14, 2017 in United States

int label;

List<DirectedGraphNode> neighbors;

DirectedGraphNode(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

check if there is a cycle in a directed graph, if there is a cycle, remove all the cycles| Report Duplicate | Flag | PURGE

Facebook SDE1 - -1of 1 vote

AnswerSachin wants to buy a laptop for programming. he plans on buying a laptop whose price is made of digits 4 and 7 only. The number of 4s and 7s in the price should be equal. You are given laptop brand names and their prices. Find and print the name of the laptop brand that satisfies the above criteria. If there are multiple brands that meet the criteria, print the name of the one with the minimum price. If none of the laptops meet the criteria print -1.

- Rising star November 13, 2017 in India

For example, if Sharon has a choice between laptops 'BestBook' priced at 444777 and 'LapBook' priced at 7744, the solution should indicate ideal choice to be 'LapBook'. Although both 'BestBook' and 'LapBook' have equal number of 4s and 7s in the price, 'LapBook' is priced lower which makes it the right choice for Sharon.| Report Duplicate | Flag | PURGE

Accolite software SDE1 - 1of 1 vote

AnswersYou are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.

- ajay.raj November 13, 2017 in United States

Follow up:

What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answersgiven a string and a segmentation length k

- ajay.raj November 12, 2017 in United States

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.| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answerstrie search, Search Return all words that match the wildcard *

- ajay.raj November 12, 2017 in United States

such as

add ("car")

add ("caw")

add ("cauw")

search ("c*w") returns "caw" and "cauw".| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersThere 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.

- ajay.raj November 10, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answers

- ajay.raj November 09, 2017 in United States`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) { } }`

| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answersthe longest unique value path in a graph

- ajay.raj November 06, 2017 in United States

/**

* 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) {

}

}| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven 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.

- ajay.raj November 05, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersTo determine if two graphs have isomorphism or not

- ajay.raj November 05, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersGive an array A, find the (i, j) pairs that satisfy the condition.

- ajay.raj November 05, 2017 in United States

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]| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

AnswersGiven an array of length n + 1, containing elements 1 through n and a space,

- ajay.raj November 04, 2017 in United States

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| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answersfind a shortest string to cover all of a list of string,

- ajay.raj November 04, 2017 in United States

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

because aab, aabb, bc are all the substring of aabbc| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

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

- ajay.raj November 03, 2017 in United States

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

Facebook SDE1 - 0of 0 votes

AnswerDesign a SparseVector class that implements

- ajay.raj November 03, 2017 in United States

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

increment(int index, int delta), numNonZeros(), and dotProduct(Vector other)| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven 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

- ajay.raj November 03, 2017 in United States

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){

}| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

Answers

- ajay.raj November 01, 2017 in United States`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`

| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGiven a list points on a 2d plane, find

- ajay.raj November 01, 2017 in United States

largest rectangular area that can be formed

for the rectangle only considers those parallel to x and y| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answers

- ajay.raj October 31, 2017 in United States`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){ }`

| Report Duplicate | Flag | PURGE

Facebook SDE1 - 0of 0 votes

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

- ajay.raj October 28, 2017 in United States

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)| Report Duplicate | Flag | PURGE

Facebook SDE1

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