## SDE1 Interview Questions

- 0of 0 votes

AnswersJSON parsing is an essential toolkit in modern web development. Whether you are on the client side or server side, these methods need to be fast, efficient and dependable. But what if one day...

- ajay.raj December 14, 2017 in United States

Suddenly, all of the JSON parser libraries went missing.

You have been called upon to save us all from impending doom.

Please re-implement the standard json parsing methods in your favorite language and restore the world to it's natural order.

Subproblem #1

Write a function, dictionaryToJson to convert a dictionary into a string.

For example, assuming you have dictionary like: dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)), the key field is always a string type, the value field could be a string type or a nested dictionary type. And the output would be "{a:apple,b:{b:blueberry,c:cranberry}}"

Subproblem #2

Write a reverse function, jsonToDictionary to convert a string into a dictionary.

Convert a string into the dictionary. e.g., given the input of “{a:apple,b:{b:blueberry,c:cranberry}}”, output dict(“a”: “apple”, “b”: dict(“b”: “blueberry”, “c”: “cranberry”)).

The names and values only contains letters. You can assume that there is no error in the input. You should not use regular expressions.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersTo a binary array, if you want to move 1 to the array side, 0 to the other side, Can only swap two adjacent elements each time, ask the least number of swap Why? For example, the number of min swaps for [0, 1, 1, 0, 0] is 2 (01100 -> 10100 -> 11000)

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

Google SDE1 - 0of 0 votes

AnswersbalanceSum, return to the array to meet the minimum sum equal to the minimum index. Title conditions are all positive numbers, the array length> = 3, there must be solution. If a = [1,2,1,3] returns 3 because a [1] + a [2] = a [4]

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

Google SDE1 - 0of 0 votes

AnswersGive a string that outputs the largest alphabetical order of all consecutive substrings For example, "ab", substring has {"a", "ab", "b"}, output "b"

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

Google SDE1 - 0of 0 votes

Answersstream reading number, with timestamp, Design data structure to know the minimum value of the past year, the average,

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

Google SDE1 - 0of 0 votes

Answerssorting nested dictionaries

- ajay.raj December 14, 2017 in United States

give a

{b: {cb: cranberry, bb: blueberry} a: apple, c: cherry}

{a: apple, b: {bb: blueberry, cb: cranberry}, c: cherry}

To sort the key output, if there is nested dictionaries, but also to sort| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersIf xi<xj,yi<yj, we say (xj,yj)dominates(xi,yi). Given a set of number pairs (xi,yi),

- ajay.raj December 14, 2017 in United States

how many indomitable pairs are there?| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersMark likes to listen to music while travelling. His iPod™ contains

- ajay.raj December 14, 2017 in United States

N songs and he wants to listen to L (not necessarily different) songs during

a trip. So he creates a playlist such that:

• Every song is played at least once.

• A song can be played again only if at least K other songs have been played

Mark wants to know how many different playlists are possible. Can you help Mark determine this number?

As the number can be very large,

display number modulo 1,000,000,007.

You are given N, K and L.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersGiven the width, height, start point, end point of the grid, and a list of points, you have to go through these points, ask how many paths are there from the start point to the end point, you can only move from (i, j) down and right.

- ajay.raj December 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - -2of 2 votes

AnswerThe design of two functions, cyclecount (num, mod), cycleHistogram (low, high, mod). Probably, cyclecount (num, mod) do digits square sum mod operation. For example mod (12), mod (5) -> square (1) + square (2) mod 5 = 0 -> square (0) mod 5 = 0. Stop return 2. Finished digits square sum after take mod, mod and before the formation of a repetitive cycle. Return form the size before the cycle. CycleHistogram (low, high, mod) will give a [low, high]. Then return a histogram which stores the number of [low, high] inside the cycle size 1,2,3,4,5.

- ajay.raj December 12, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 3of 3 votes

AnswerBob And GCD

- uppubhai December 11, 2017 in India

Bob has an array A of size N. He doesn't like arrays in which the GCD of all elements is not K. He can perform multiple operations on an array. In each operation, he can either increase or decrease the value of an element by 1.

You have to tell the minimum operation Bob will take to make GCD of all elements in an array equal to KK ?

GCD here is Greatest Common Divisor.

Input Format

The first line contains T, the number of test cases.

For Each Testcase :

The first line contains 2 integers - K and N respectively, separated by a space.

The second line contains N integers, separated by a space, in order of their position in array.

Input Constraints

1≤T≤10

1≤N≤10^6

1≤A[i]≤10^6

1≤K≤10^6

Output Format

For each test case, print minimum number of operations Bob take in a new line.

Sample Input

1

5 3

4 5 6

Ans - 2| Report Duplicate | Flag | PURGE

ThoughtWorks SDE1 - -1of 1 vote

AnswersThe best project you have worked till now.

- anonymous December 10, 2017 in India for Office365| Report Duplicate | Flag | PURGE

Microsoft SDE1 Experience - 0of 0 votes

AnswersConvert an Integer to a String.

- anonymous December 10, 2017 in India for Office365

eg 10--->"10",

2.5--->"2.5"

+10--->"+10"

-10----->"-10"

1.25e-7--->0.000000125| Report Duplicate | Flag | PURGE

Microsoft SDE1 Programming Skills - 0of 0 votes

AnswersGiven n line segments, find if any two segments intersect

- anonymous December 10, 2017 in India for Office365

http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/| Report Duplicate | Flag | PURGE

Microsoft SDE1 Data Structures - 0of 0 votes

Answersfind LCA in directed acyclic graph

- ajay.raj December 10, 2017 in United States

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

Facebook SDE1 - -3of 3 votes

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

- ajay.raj December 10, 2017 in United States

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

Google SDE1 - 0of 0 votes

Answersinput: words [['google', 30], ['gogle', '20'], ...]

- ajay.raj December 08, 2017 in United States

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

output: [30, .....]

The query is suffix and prefix, giving the maximum match.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

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

- new December 07, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 Algorithm Arrays Coding Data Structures - 0of 0 votes

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

- ajay.raj December 06, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGiven a function randBetween (double d1, double d2), return a random double between d1 and d2,

- ajay.raj December 06, 2017 in United States

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

Google SDE1 - 0of 0 votes

AnswersThe 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]

- ajay.raj December 06, 2017 in United States

Length of 4.

Followup: how to do two-dimensional array, how to optimize.| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGiven Two string, ask whether they can become the same after just one swap of two chars in one string.

- ajay.raj December 06, 2017 in United States

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

Google SDE1 - 0of 0 votes

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

- ajay.raj December 05, 2017 in United States

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

Google SDE1 - 2of 2 votes

AnswersMaximum Sum of Building Speed

- uppubhai December 04, 2017 in India

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

Practo SDE1 Algorithm - 0of 0 votes

AnswerChoose a random point from one single rectangle.

- ajay.raj December 03, 2017 in United States

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

Google SDE1 - 0of 0 votes

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

- ajay.raj December 02, 2017 in United States

check if a matrix can be all 0s after many of this operation.| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

Answerdesign a sweeping robot, there are three functions:

- ajay.raj December 02, 2017 in United States

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

Google SDE1 - -1of 1 vote

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

- ajay.raj December 02, 2017 in United States

follow-up each child node may have one or more parent nodes,| Report Duplicate | Flag | PURGE

Google SDE1 - 1of 1 vote

AnswersGiven 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

- ajay.raj December 02, 2017 in United States| Report Duplicate | Flag | PURGE

Google SDE1 - 0of 0 votes

AnswersJudge if two arrays has the same pattern,

- ajay.raj December 02, 2017 in United States

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

Google SDE1

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