## Software Engineer Intern Interview Questions

- 0of 0 votes
"""

Given a 2d array of 0s and 1s, 0 means water,

1 means land, connected 1s form an island,

count the number of islands on this map.

01010

01001

01101

returns 3

"""

- 0of 0 votes
# Given a dictionary, find all pairs of words that,

# when concatenated together, form a palindrome.

# ‘none', 'xenon': 'nonexenon' is a palindrome

# 'none', 'xexenon': 'nonexexenon' is a palindrome

- 0of 0 votes
Let's assume that we have a binary classification system that classifies sets of samples, the rules for the classification are:

The set is 'GOOD' if ALL the samples are 'GOOD'

The set is 'BAD' if ANY sample in the set is 'BAD'

Based on this we receive an input that contains multiple lines, where each line represents the classification of a set of samples. The format of each line is

class,sample_id_1,sample_id_2,...,sample_id_n

where class will either be GOOD or BAD. The sample IDs represent the samples contained in the classified set.

Now, for generating the output response we have to consider three cases:

If a unique mapping of samples-to-class exists, we output the corresponding mapping (sorted by the samples IDs)

If no consistent sample-to-class is possible, we output the answer NO CONSISTENT

If more than one mapping would be consistent, we output the answer MULTIPLE MAPPING.

To better illustrate the problem, following there are 4 examples

Sample Input

GOOD,10,11

GOOD,11,12

GOOD,10,12

Sample Output

10,GOOD

11,GOOD

12,GOOD

Sample Input

GOOD,10,11

BAD,11,12

Sample Output

10,GOOD

11,GOOD

12,BAD

Sample Input

GOOD,10,11

BAD,11,12

GOOD,11,13

GOOD,12,13

Sample Output

NO CONSISTENT

Sample Input

BAD,10,11

BAD,11,12

Sample Output

MULTIPLE MAPPING

If someone knows how to solve the problem, even if it's just pseudocode I'd really appreciate it

- 1of 1 vote
You are a game developer working on a game that randomly generates levels. A level is an undirected graph of rooms, each connected by doors. The player starts in one room, and there is a treasure in another room. Some doors are locked, and each lock is opened by a unique key. A room may contain one of those unique keys, or the treasure, or nothing.

Implement a representation for a level and write code that, given a level and starting room, returns true if the treasure can be reached by the player—likely requiring them to find certain other keys first—or false if there is no solution.

- 0of 0 votes
Insert node with a given value in a circular sorted linked list.

- 0of 0 votes
Given list of N points find the K closest points to origin i.e((0,0)).

- 0of 0 votes
You are given a positive integer number and you have to return the greatest smaller tidy number of this input number. If the input number itself is tidy, then, it become the answer

Example

Input: 1234

output: 1234

input: 100

output: 99

input 143456

output: 139999.

PS.A tidy number is a number whose digits are in non-decreasing order.

- 0of 0 votes
You are given a positive integer number and you have to return a boolean telling whether the input number is a tidy number or not. A tidy number is a number whose digits are in non-decreasing order. For example, 1234 is a tidy number, 122334 is also a tidy number but 143567 is not a tidy number.

- 1of 1 vote
Interview Question: essentially given a bunch of sets in an array, print out the cross product of all of those sets

- 0of 0 votes
You are given a sorted list of distinct integers from 0 to 99, for instance [0, 1, 2, 50, 52, 75]. Your task is to produce a string that describes numbers missing from the list; in this case "3-49,51,53-74,76-99".

Examples:

[] “0-99”

[0] “1-99”

[3, 5] “0-2,4,6-99”

- -1of 1 vote
Assume (n+1) points on a 2D space. You observe the points from (0,0) with viewing direction and viewing angle.

Given an array (xn,yn), and a viewing angle v (45 degree), find the direction that can observe max number of points.

- 0of 0 votes
Given a sorted array, and given a number n, find number of times n occurs in the array.

- 1of 1 vote
You have a matrix that is sorted as such: For each value, every index to its right and below it must be larger than the current space's value. Likewise, all entries to its left and above it must be smaller than the current value. How would you go about searching this matrix for a specific number, given its sorted nature?

- 1of 1 vote
Just a disclaimer: I doubt you will ever get this interview question. My interviewer even started off by saying, "Hmm, well this isn't really fair, but..." So don't place too much stock in whether or not you can solve this.

Question: You have a group of pigs and buckets of food for said pigs. There are 1,000 buckets of food, and exactly 1 of them is poisoned. Your goal is to determine, by the end of 1 hour, which bucket is poisoned.

The poison takes 30 minutes to kill a pig, and you'd like to kill as few pigs as possible. The number of pigs you can test is limitless, and you can assign a number to each bucket and each pig so that you know exactly which pig ate from which bucket(s). You determine which buckets to feed to which pigs, but you have no timer and no way to guesstimate the time. What is the minimum number of pigs you need to use to solve the problem?

- 0of 0 votes
You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative, move backward n steps. Determine if there is a loop in this array.

For example, given the array [2, -1, 1, 2, 2], index 0 maps to index 2, 1 maps to 0, 2 maps to 3, and so on. There is a loop in this array because 0 maps to 2, 2 maps to 3, and 3 maps to 0 (use the modulo operator).

- 0of 0 votes
Given an n-ary tree, find the longest sequence in it. The sequence doesn't end to start at the root. It can go from leaf to leaf.

- 1of 1 vote
Maximize the expression value which consists of numbers and +,- operators. Write a program using Greedy approach in linear complexity and Dynamic approach with O(n3) complexity.

- 0of 0 votes
Stanford has to select a team of dodgeball players from its class of 2013. There are n students in the class and each student is identified by his/her student ID, which is between 1 and n. The coach has to select K players out of these n students for his team. But there is a twist, if among the K dodgeball players, a player's ID number evenly divides another player's ID number, then there is a high chance of them getting into a fight. The coach will do his best to select the K players so that no pair of players among them will want to fight one another. But if the game turns out to be very popular, this becomes impossible. Complete the function dodgeBall to return the minimum size of K at which it becomes impossible to choose a dodgeball team that has no fighting?

Input Format:

One line of text, containing the size of the class of 2013, n

Constraints:

1 <= n <= 5,000,000,000

n is guaranteed to be an even number

Output Format:

The minimum size of K that guarantees the existence of 2 players who fight with each other in any K-sized subset of the class.

Sample Input:

4

Sample Output:

3

Explanation:

If the team = {1,2,3}: 1&2 or 1&3 can fight with each other

If the team = {1,3,4}: 1&3 or 1&4 can fight with each other

If the team = {2,3,4}: 2&4 can fight with each other

If K=2, then the teams {3,4} or {2,3} will have no fights. So 3 is the smallest value of K for which any K-sized team, must include a fighting pair.

Sample Input:

2

Sample Output:

2

Explanation:

The team = {1,2}: 1&2 can fight with each other

- 0of 0 votes
find the best way to write zig zag sign change algorithm !

- 4of 4 votes
Given the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.

`Input: 6 / \ 3 4 / \ \ 5 1 0 / \ / 9 2 8 \ 7 Output: 9 5 3 2 6 1 7 4 8 0 Input: 1 / \ 2 3 / \ / \ 4 5 6 7 When two nodes share the same position (e.g. 5 and 6), they may be printed in either order: Output: 4 2 1 5 6 3 7 or: 4 2 1 6 5 3 7`

- 2of 2 votes
`|X XX | | X X | | X | | |`

X = land.

Empty space = Water.

Find the number of islands present. (Upto you how you want to represent land and water in the array above)

Answer for the above example: 3

I wish I could draw the diagram better!

Explanation: 3 because:

The three islands are:

X

X

X

XX

X

- 1of 1 vote
Given an input BST, find the minimum value difference between any two nodes in the tree.

e.g:

....10

5 16

........12 20

answer: 2 (it happens between nodes 12 and 10)

describe the test cases you would use here?

- 0of 0 votes
Given a specific type of DAG that forms a pyramid (the links have up-down direction), in which the node labels are integer, find the path that has the maximum sum of node values. what is the time/space complexity of the algorithm?

e.g:

3

/ \

9 4

/ \ / \

1 8 2

/ \ / \ / \

4 5 8 2

answer: <3,9,8,8>, sum = 3+9+8+8=28

- 2of 2 votes
Given two arrays/Lists (choose whatever you want to) with sorted and non intersecting intervals. Merge them to get a new sorted non intersecting array/list.

Eg:

Given:

Arr1 = [3-11, 17-25, 58-73];

Arr2 = [6-18, 40-47];

Wanted:

Arr3 = [3-25, 40-47, 58-73];

- 0of 0 votes
Give java code that takes an instance of the stable marriage problem as input and decides if there is { exactly one} stable matching for this instance (that is, the program outputs either ``unique stable matching'', or ``more than one stable matching'').

input:

3

0 1 2

1 0 2

0 1 2

1 0 2

0 1 2

0 1 2

Output:

more than one stable matching

- 2of 2 votes
find the maximum depth in a binary tree.

- -2of 2 votes
given an integer array , find all combinations which sum to a given number. If a number is used once, it must not be used again.

eg if input array is 6444 and sum =10

output must be just 6 4

Give an O(n) solution

- 0of 0 votes
given a string with only paranthesis - find out if it is balanced or not

eg {}[]()

followup : scale your solution and specify the right data structure to use if you have a lot of such bracket types

- 3of 3 votes
Task schedule: given a sequence of task like A B C(means 3 different tasks), and a coldtime, which means you need to wait for that much time to start next [same] task. Now----

Input: string, n

Output: the best task-finishing sequence.

eg. input: AAABBB, 2

Output: AB_AB_AB

( "_" represents do nothing and wait)

- 0of 0 votes
Write a program to sort the numbers using singly linked list in O(nlogn) time complexity and O(1) space complexity?