SDE - Intern Intuit interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration90 minutes

Interview date10 Aug 2020

Coding problem3

This was an online coding round. 4 questions on DSA were to be solved in 90 minutes.

1. N Queens Problem

Hard

55m average time

35% success

0/120

Asked in companies

You are given an integer 'N'. For a given 'N' x 'N' chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.

A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens. You have to print all such configurations.

Problem approach

DFS can be used to solve this problem. The idea is to place queens in different columns one by one, starting from the leftmost column. As we cannot place 2 queens in the same column, when we place the queen in the nth column and if its valid position, dfs again starting n+1 th column and try placing the next queen in all the rows of n+1th column and find a valid position. If no valid queen row found in n+1th row, backtrack and go to nth column, and change the queen position to the next row and repeat the process.

Try solving now

2. 0-1 Knapsack

Easy

15m average time

85% success

0/40

Asked in companies

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are N items and the ith item weighs wi and is of value vi. Considering the constraints of the maximum weight that a knapsack can carry, you have to find and return the maximum value that a thief can generate by stealing items.

Problem approach

DP can be used to solve this problem efficiently.

Try solving now

3. Add two numbers represented by linked lists

Easy

20m average time

80% success

0/40

Asked in companies

Given two numbers represented by linked lists. Your task is find the sum list and return the head of the sum list.

The sum list is a linked list representation of addition of two numbers.

Problem approach

The steps are:
Traverse the two linked lists in order to add preceding zeros in case a list is having lesser digits than the other one.
Start from the head node of both lists and call a recursive function for the next nodes.
Continue it till the end of the lists.
Creates a node for current digits sum and returns the carry.

Try solving now

Round

Medium

Video Call

Duration45 minutes

Interview date12 Aug 2020

Coding problem2

This was the first online round after the coding round. The interview started off with each other's introductions. Then 2 DSA problems were asked and disussed.

1. The Celebrity Problem

Moderate

30m average time

60% success

0/80

Asked in companies

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party.

Given a helper function ‘knows(A, B)’, It will returns "true" if the person having id ‘A’ know the person having id ‘B’ in the party, "false" otherwise. Your task is to find out the celebrity at the party. Print the id of the celebrity, if there is no celebrity at the party then print -1.

Note:

1. The helper function ‘knows’ is already implemented for you.
2. ‘knows(A, B)’ returns "false", if A doesn't know B.
3. You should not implement helper function ‘knows’, or speculate about its implementation.
4. You should minimize the number of calls to function ‘knows(A, B)’.
5. There are at least 2 people at the party.
6. At most one celebrity will exist.

Problem approach

I used two pointer approach to solve this problem.
If for any pair ('i', ‘j’) such that 'i' != ‘j’, If ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’.
So, the Two Pointer approach can be used where two pointers can be assigned, one at the start and the other at the end of the elements to be checked, and the search space can be reduced.

Try solving now

2. Top View of Binary Tree

Moderate

25m average time

70% success

0/80

Asked in companies

You are given a Binary Tree of 'n' nodes.

The Top view of the binary tree is the set of nodes visible when we see the tree from the top.

Find the top view of the given binary tree, from left to right.

Example :

Input: Let the binary tree be:

Output: [10, 4, 2, 1, 3, 6]

Explanation: Consider the vertical lines in the figure. The top view contains the topmost node from each vertical line.

Problem approach

The approach is to use the preorder traversal of the tree to traverse the tree and check that we have visited the current vertical level and if visited then we can check for the smaller horizontal level node and store it. Else we can just update the vertical level as visited and store the node and horizontal level of the current node.
1) We have to create the map to check whether the horizontal level is visited or not as it will state the horizontal distance of the node from the root node. Where key will represent the horizontal distance and the value is the pair containing the value and level of each node.
2) We will traverse the tree using the preorder traversal.
3) Every time we check if the level of the current horizontal distance is less than the max level seen till now then we will update the value and the level for this horizontal distance.
4) We will pass level-1 for the left child and level+1 for the right child to get the vertical level.
5) Print the values present in the map.

Try solving now