## SDE1 Interview Questions

- 0of 0 votes
Given n line segments, find if any two segments intersect

http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

- 0of 0 votes
find LCA in directed acyclic graph

class Node {

int label;

List<Node> neighbors;

Node(int x) {

label = x;

neighbors = new ArrayList<>();

}

}

public List<Node> findLCAINDAG(Node, graph, Node n1, Node n2)

- -1of 1 vote
There is a set, there are some balls, different balls have different weights, for example: [red ball 4, yellow ball 1, green ball 2, blue ball 2]

Ask for the first k-weight combination in this case, if k is 5 then:.

[Red, yellow, green, blue] 9

[Red, green, blue] 8

[Red, yellow, green] 7

[Red, yellow, blue] 7

[Red, Blue] 6 (or [Red, Green])

- 0of 0 votes
input: words [['google', 30], ['gogle', '20'], ...]

queries [['go, le'], ...]

output: [30, .....]

The query is suffix and prefix, giving the maximum match.

- 0of 0 votes
N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

- 0of 0 votes
There are W white beans in the jar, R red beans. Random touch a bean. Touch white beans to eat directly. Touch red beans, put back, touch a bean, whether it is red, eat. Ask the last bean is the probability of white beans.

- 1of 1 vote
Given a function randBetween (double d1, double d2), return a random double between d1 and d2,

returns a random point in a rectangle.

Give a bunch of rectangles, using randBetween to print a random point in the rectangle

follow up: What to do if you call this func many times

- 0of 0 votes
The two arrays [1,2,3,4,5], [2,3,4,5,6] find the first subfix and the second prefix the same longest case, such as the example is [2, 3,4,5]

Length of 4.

Followup: how to do two-dimensional array, how to optimize.

- 0of 0 votes
Given Two string, ask whether they can become the same after just one swap of two chars in one string.

For example:

"abcd", "bacd" Yes, you can swap ab in the first string to make it the same as the second string

"abcd", "adbc" can not

Follow-up, given Two string, ask whether they can become the same after N swaps of two chars in one string g, assuming that the swap does not overlap.

(str [0] <-> str [2] str [2] and str [0] will not be swapped with other locations)

- 0of 0 votes
There is a ball on the nth stairs, and it wants to get to the ground(level 0). There are some sticky stairs, and once the ball lands on the sticky stair, it is stuck and can never move.

During odd turns, you can jump down 1, 2, or 4 stairs. During even turns, you can jump down 1, 3, 4 stairs.

Return the number of ways you can get to ground.

- 0of 0 votes
Maximum Sum of Building Speed

You are the king of Pensville where you have 2N workers.

All workers will be grouped in association of size 2,so a total of N associations have to be formed.

The building speed of the ith worker is Ai.

To make an association, you pick up 2N workers. Let the minimum building speed between both workers be x, then the association has the resultant building speed x.

You have to print the maximum value possible of the sum of building speeds of N associations if you make the associations optimally.

Constraints

1≤N≤5∗10 ^4

1≤Ai≤10^4

Input

First line contains an integer N, representing the number of associations to be made.

Next line contains 2N space separated integers, denoting the building speeds of 2N workers.

Output

Print the maximum value possible of the sum of building speeds of all the associations.

Sample Input

2

1 3 1 2

Sample Output

3

- 0of 0 votes
Choose a random point from one single rectangle.

Choose a random point from multiple rectangles, if there isno overlapping among them.

Choose a random point from multiple rectangles, if there isoverlapping among them.

- 0of 0 votes
given a binary matrix of 01s, each time you click a point (i, j), the bit of the same row and column are all flipped.

check if a matrix can be all 0s after many of this operation.

- 0of 0 votes
design a sweeping robot, there are three functions:

move (), which returns boolean value

turn_left (k), which make robot turns left k times.

turn_right (k), which make robot turns right k times.

Design an algorithm to make robot clean up all room. Timecomplexity, linear in term of room space.

- 0of 0 votes
Given a graph, each node may have one or more children, updating the value of a child node is not less than the parent node.

follow-up each child node may have one or more parent nodes,

- 1of 1 vote
Given a function that returns 0 and 1 with a probability of fifty percent, use this function to generate a random number between a and b with uniform distribution

- 0of 0 votes
Judge if two arrays has the same pattern,

The definition is the relative relationship between each number and other numbers are the same, such as 132, 354, the first number is less than the second, the first less than the third, the second is greater than the third,

So is the same,

132,352 is not the same, because the first 132 is less than the third, the first 352 is greater than the second,

follow up, the array may concern duplicates

- 0of 0 votes
You have to implement the following function:

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.

- 0of 0 votes
Generate a random MxN starting board. It cannot have 3 or more pieces in a

row (horizontally or vertically) of the same color. K colors.

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

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;

- 0of 0 votes
Gas 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

- 1of 1 vote
given a string, and integer k, check if this string contain all the binary string of length k

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.

- 0of 0 votes
Expression evolution

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

}

- 0of 0 votes
`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){ } }`

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

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.

- 0of 0 votes
determine whether a number is the sum of two squares, such as 17 = 16 +1

- 0of 0 votes
`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`

- 0of 0 votes
class DirectedGraphNode {

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

- -1of 1 vote
Sachin 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.

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.

- 1of 1 vote
You 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.

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?