Cse interview questions

2021-01-13 04:40:52 Minimum Number of Platforms for a Bus Station

You are given a data of n buses that reach a bus station. Two arrays represent arrival and departure times of buses that stop at the station.

You need to find the minimum number of stations so that none of the buses overlap.

Examples :

Input 1 :
arr = [8:00, 5:10, 12:40, 12:00, 12:15, 20:08]
dep = [8:10, 5:30, 12:55, 12:45, 12:50, 20:32]

Output 1 :
3

Explanation 1 :

The buses which arrive at 8:00, 5:10 and 20:08 do not overlap with any other buses as till their departure time, no other buses have arrived.

For the buses which arrive at 12:00, 12:15, 12:40, all the three buses stay at bus station during the interval 12:40 to 12:45 hours as their departure time has not yet arrived during this time interval.

So atleast 3 platforms are needed for the bus station.

(Note that here arr and dep array variable denotes the arrival and departure times of the buses.)

Input 2 :
arr = [18:40, 17:05, 14:12]
dep = [18:50, 17:25, 14:42]

Output 2 :
1

Explanation 2 :

Here we can see that the arrival and departure timings of three buses do not overlap. So minimum number of station needed is 1.

Topic : Greedy Algorithm

Reference(s) ->
GeeksforGeeks

Solution ->
GFG Article Set 1, Set 2

Asked in Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2021-01-10 05:25:02 Clone a Linked List with Next and Random Pointers

You are given a linked list where each node can have two pointers. One pointer pointes to next node as usual. Apart from this there is an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Constraints :

-10000 <= node.value <= -10000
Number of nodes <= 1000

Examples :

Let us say linked list of n nodes is represented as a list of nodes where each node is of form [value, random_index]. value denotes value of data and random_index denotes the index of the node to which random pointer points to. It can range from 0 to n-1, or null if it does not point to any node.

There is also a next pointer which points to next node (or null for last node) as usual.

Input 1 : head_in = [[1,1], [2,1], [3,1]]

Output 1 : head_out = [[1,1], [2,1], [3,1]]

Explanation 1 :

Input list has three nodes with values 1, 2 and 3. Random pointers of all three points to node with index 1 (0-based) which is middle node. Clone of input list is returned.

Input 2 : head_in = [[1,null], [15,1], [101,null], [93,0]]

Output 2 : head_out = [[1,null], [15,1], [101,null], [93,0]]

Explanation 2 :

Input list has four nodes with values 1, 15, 101 and 93. All three points to node with index 1 (0-based) which is middle node.

Random pointer of 0th node points to null, 1st node points to itself, 2nd node again points to null and third node points to 0th node.

Clone of input list is returned.

Topic : Linked Lists

Reference(s) ->
GeeksforGeeks, LeetCode

Solution ->

GFG Article Set 1, Set 2

For implementation in O(1) space, refer this article

Asked in Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2021-01-03 05:03:55 Unspecified Words

There are N words in a dictionary such that each word is of fixed length M and consists of only lowercase English letters that are ('a', 'b', ... , 'z').

A query word is denoted by Q. The length of query word in M. These words contain lowercase English letters but at some places instead of a letter between 'a', 'b', ... , 'z' there is '?'. Refer to the Sample input section to understand this case.

A match count of Q, denoted by match_count(Q), is the count of words that are in the dictionary and contain the same English letters (excluding a letter that can be in the position of ?) in the same position as the letters are there in the query word Q.

In other words, a word in the dictionary can contain any letters at the position '?' but the remaining alphabets must match with the query word.

You are given a query word Q and you are required to compute match_count(Q).

Input format :

First-line contains two space-separated integers N and M denoting the number of words in the dictionary and length of each word respectively.

The next N lines contain one word each from the dictionary.

The next line contains an integer Q denoting the number of query words for which you have to compute match_count().

The next Q lines contain one query word each.

Output Format :

For each of the query word, print match_count in a new line.

Constraints :

1 ≤ N ≤ 5 x 10^4
1 ≤ M ≤ 7
1 ≤ Q ≤ 10^5

Sample Input :

5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n

Sample Output :

2
2
4
2

Explanation for Sample Input :

The two space-separated integers in first line denotes 5 dictionary words, each of length 3 letters. Next 5 lines contain those five words.

Next line containing an integer 4 denotes four queries for which match_count() has to be computed. Then those query words follows in next four lines.

Explanation for Sample Output :

?at
cat and bat end with 'at'.
match count = 2

ma?
map and man start with 'ma'
match count = 2

?a?
cat, map, bat and man have 'a' as their middle letter.
match count = 4

??n
man and pen end with 'n'
match count = 2

Topic : Strings

Reference(s) ->
GeeksforGeeks, Chegg

Solution ->
Ideas can be borrowed from
Stack Overflow, Codeforces blog

Asked in Google

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-12-27 16:59:06 Binary Subtree and Count of Nodes

Given two non-empty binary trees, check if the either tree is a subtree of the other one. Also print the count of nodes in that subtree.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

Examples :

Input 1 :

4
/ \
2 5
/ \
1 3

2
/ \
1 3

Output 1 :

true
3

Explanation 1 :

Here we can see that the internal node corresponding to value 2 of first tree and all its descendents, matches the second tree. So, second tree is a subtree to the first tree. Hence output true.

Also, number of nodes of subtree (second tree) is 3 which have values 2, 1 and 3.

Input 2 :

4
\
9

2
/ \
4 5

Output 2 :

false

Explanation 2 :

The only common node among the two trees is the node corresponding to value 4. But first tree has right child with value 9 while the second tree has no descendants. The criteria for subtree is not satisfied. So, here neither is the subtree of the other.

Since there is no subtree here, we don't output number of nodes of subtree. (Other possibilities like outputting null can be valid too, this can be discussed with the interviewer.)

Topic : Trees

Reference(s) -> GeeksforGeeks, LeetCode

Solution ->

for Binary Subtree,
refer GFG set 1, set 2

for Count of Nodes,
GFG article 1, article 2, Sanfoundry

Asked in Paytm

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-12-13 05:52:59 Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

NOTE :

1. The numbers can be arbitrarily large and are non-negative.

2. Answer should not have leading zeroes. For example, "082" is not a valid answer. Instead "82" should be returned.

3. Do not use built-in big integer libraries available in programming languages like Java and Python.

4. Do not convert the inputs to integer to solve the problem.

Examples :

Input 1 : num1 = "12", num2 = "11"

Output 1 : "132"

Explanation 1 :

Numbers 12 and 11 when multiplied yields 132. Return answer in string format.

Input 2 : num1 = "4983", num2 = "2727"

Output 2 : "13588641"

Explanation 2 :

Numbers 4983 and 2323 when multiplied yields 13588641. Return answer in string format.

Topic : Strings

Reference -> InterviewBit, LeetCode

Solution -> GeeksforGeeks

Asked in Google, Microsoft

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-12-06 16:23:49 Wave Array

Given an array of integers, sort the array into a wave like array and return it.

In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

NOTE : If there are multiple answers possible, return the one that is lexicographically smallest.

Examples :

Input 1 : [1, 2, 3, 4]

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

Explanation 1 :

Possible answers could be : [2, 1, 4, 3] or [4, 1, 3, 2]. We can see that integers at even index places (0-based) are greater than integers at their neighbouring odd index places.

Among these two, first one is preferred as it is lexicographically smallest.

Input 2 : [5, 20, 10]

Output 2 : [10, 5, 20]

Explanation 2 :

Possible answers could be : [10, 5, 20] or [20, 5, 10] among which first one is lexicographically smallest and so is selected as output.

Topic : Arrays

Reference -> InterviewBit

Solution -> GeeksforGeeks, AfterAcademy

Asked in Google, Adobe, Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-11-09 04:07:17 Reverse a Singly Linked List using Recursion

Given pointer to the head node of a linked list, the task is to reverse the linked list using recursion. We need to reverse the list by changing the links between nodes.

Examples :

Input 1 :
1->2->3->4->NULL

Output 1 :
4->3->2->1->NULL

Explanation 1 :
Input list in reversed order is 4->3->2->1->NULL


Input 2 : 1->NULL

Output 2 : 1->NULL

Explanation 3 :
There is only one element in the list ie 1, so reversed ordered ilst is same as input list.

Topic : Linked Lists

Reference -> GeeksforGeeks

Solution -> GeeksforGeeks article 1, article 2

Asked in Paytm

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-11-04 05:59:53 Count Pairs in an Array Whose Sum is Divisible by 60

Given a array of 'n' positive integers, count number of pairs of integers in the array that have the sum divisible by 60.

Example :

Input :
{30, 30 , 23, 37, 83}

Output :
3

Explanation :
Three pairs whose sum is divisible by 60 i.e. (30, 30), (23, 37) and (37, 83). So output 3.

Topic : Hashing

Reference -> GeeksforGeeks

Solution -> GeeksforGeeks article

Asked in PayPal

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-11-01 14:28:20 Painter's Partition Problem

You are given two integers a and b and an array of integers C of size n.

There are a painters available and each of them takes b units of time to paint 1 unit of board. You have to paint all n boards [C0, C1, C2, C3 … Cn-1].

Calculate and return minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of board. Return the ans % 10000003

Note :

1. 2 painters cannot share a board to paint. That is to say, a board
cannot be painted partially by one painter, and partially by another.

2. A painter will only paint contiguous boards. Which means a
configuration where painter 1 paints board 1 and 3 but not 2 is
invalid.

Input Format :

The first argument is integer a.
The second argument is integer b.
The third argument the integer array C.

Output Format :
Return (minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of board) % 10000003.

Constraints :

1 <= a <= 1000
1 <= b <= 10^6
1 <= C.size() <= 10^5
1 <= C[i] <= 10^6

Examples :

Input 1 :
a = 2
b = 5
c = [1, 10]

Output 1 :
50

Explanation 1 :

There are 2 painters each with capability of painting 1 unit of board in 5 units of time.

Possibility 1 : Same painter can paint both the blocks. So time taken will be 1*5 + 10*5 = 55 time units.

Possibility 2 : We can employ two different painters for two boards. These 2 painters will work in parallel and time taken by them will be 1*5 and 10*5 ie 5 and 50 units of time. So time taken to paint both the boards will be max(5, 50) which is 50.

Among both the possibilities, later takes minimun time. So output 50 % 10000003 which is 50 itself.

Input 2 :
a = 10
b = 1
c = [1, 8, 11, 3]

Output 2 :
11

Explanation 2 :

There are 10 painters each with capability of painting 1 unit of board in 1 units of time.
So we can employ 4 painters for four boards with given lengths 1, 8 , 11 and 3. These 4 painters will work in parallel and time taken by them will be 1, 8, 11 and 3 units of time. So time taken to paint all boards will be max(1, 8, 11, 3) which is 11. So output 11 % 10000003 which is 11 itself.

Topic : Binary Search

Reference -> InterviewBit, GeeksToCode

Solution -> GeeksforGeeks - Set 1, Set 2

Asked in Google, Codenation

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-10-27 11:37:02 Course Schedule Given Prerequisites

There are a total of n courses you have to take, labeled from 1 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, find whether it is possible to finish all courses?

Examples :

Input 1:
n = 3, prerequisites = [[0, 1], [1, 2]]

Output 1:
true

Explanation 1:
There are total of three courses. To finish course 0 there are no prerequisites, to finish course 1 course 0 should have been taken and to finish course 2 course 1 should have been taken. So it is possible to complete the three courses in order 0 -> 1-> 2.

Input 2:
n = 2, prerequisites = [[1, 0], [0, 1]]

Outut 2:
false

Explanation 2:
There are total of two courses. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1, which is impossible.

Topic : Graph Data Structure & Algorithms

Reference -> InterviewBit, LeetCode

Solution -> GeeksforGeeks

Asked in Amazon, Google, Twitter

Join our Official Channel @cseinterview Ouvert / Commentaire