Cse interview questions

2020-10-21 08:35:31 Equal Average Partition

Given an array A with non negative numbers, divide the array into two parts such that the average of both the parts is equal.

Return both parts (if exist). If there is no solution. return an empty list.

NOTE :

1. If a solution exists, you should return a list of exactly 2 lists of integers A and B which follow the following condition :

a) numElements in A <= numElements in B

b) If numElements in A = numElements in B, then A is lexicographically smaller than B (wikipedia)

c) If multiple solutions exist, return the solution where length(A) is minimum.

d) If there is still a tie, return the one where A is lexicographically smallest.

2. Array will contain only non negative numbers.

Input Format :
First and the only argument is an integer array A.

Output Format :
Return 2D array consisting of two rows where each row denoted a partition.

Example :

Input :
A = [1 7 15 29 11 9]

Output :
[9 15] [1 7 11 29]

Explanation :
The average of first part elements is (15+9) / 2 = 12 and the average of second part elements is (1 + 7 + 11 + 29) / 4 = 12. So the input array is divided into two parts such that the average of both them are equal.

Topic : Dynamic Programming

Reference -> InterviewBit

Solution -> GeeksforGeeks article 1, article 2

Asked in Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-10-16 06:30:25 Nearest Smaller Element

Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

Find G[i] for an element A[i] = an element A[j] such that
j is maximum possible AND
j < i AND
A[j] < A[i]

Elements for which no smaller element exist, consider next smaller element as -1.

Input Format :
The only argument given is integer array A.

Output Format :
Return the integar array G such that G[i] contains nearest smaller number than A[i].
If no such element occurs G[i] should be -1.

Examples :

Input 1:
A = [4, 5, 2, 10, 8]

Output 1:
G = [-1, 4, -1, 2, 2]

Explaination 1:

index 1: No element less than 4 in left of 4, G[1] = -1

index 2: A[1] is only element less than A[2], G[2] = A[1]

index 3: No element less than 2 in left of 2, G[3] = -1

index 4: A[3] is nearest element which is less than A[4], G[4] = A[3]

index 4: A[3] is nearest element which is less than A[5], G[5] = A[3]

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

Output 2:
[-1, -1, -1]

Explaination 2:

index 1: No element less than 3 in left of 3, G[1] = -1

index 2: No element less than 2 in left of 2, G[2] = -1

index 3: No element less than 1 in left of 1, G[3] = -1

Topic : Stacks

Reference -> InterviewBit

Solution -> GeeksforGeeks

Asked in Amazon, Microsoft

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-10-11 12:01:30 Intersection Of Sorted Arrays

Given two sorted arrays/lists, find common elements from them.

Examples :

Input 1 :
A : [1 2 3 3 4 5 6]
B : [3 3 5]

Output 1 :
[3 3 5]

Explanation 1 :
Elements 3, 3 and 5 are common to both the arrays/lists A & B.

Input 2 :
A : [1 2 3 3 4 5 6]
B : [3 5]

Output 2 :
[3 5]

Explanation 2 :
Elements 3 and 5 are common to both the arrays/lists A & B.

Topic : Two Pointers

References -> InterviewBit, LeetCode Discuss

Solution -> GeeksforGeeks

Asked in Facebook, Google

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-10-07 02:14:15 Sum of Two Integers

Given two integers a and b, write a function to sum two integers using either increment (++) or decrement (--) operators only.

Note that you cannot use a+b method.

Examples :

Input 1 : a = 5, b = -3

Output 1 : 2

Explanation 1 : 5 + (-3) = 2

Input 2 : a = 50, b = 23

Output 2 : 73

Explanation 2 : 50 + 23 = 73

Topic : Math

References -> careercup

Asked in Apple

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-10-04 11:30:22 Palindrome List

Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively.

Note:
Expected solution is linear in time and constant in space.

Examples :

Input 1: List 1-->2-->1

Output 1: 1

Explanation 1: List has order of elements 1, 2 and 3 when traversed in forward and backward direction.

Input 2: List 1-->2-->3

Output 2: 0

Explanation 2: List has different elements when traversed in forward (1, 2 and 3) and backward (3, 2 and 1) direction.

Topic : Linked Lists

References -> InterviewBit, educative.io

Solution -> GeeksforGeeks

Asked in Amazon, Microsoft

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-09-29 16:00:41 Identical Binary Trees

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal or same if they are structurally identical and the nodes have the same value.

Return 0 (False) or 1 (True) for this problem.

Examples :

Input 1:
1 1
/ \
2 2

[1,2], [1,null,2]

Output 1: 0

Explanation 1:
Both trees have different structure, hence they are not identical. So output 0 corresponding to False.

Input 2:

1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]

Output 2: 1

Explanation 2:
We see here that both the trees are structurally identical and nodes have same values. Hence they are identical. So output 1 corresponding to True.

Topic : Tree Data Structure

References ->

InterviewBit, LeetCode

Solution -> GeeksforGeeks article 1, article 2

Asked in Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-09-14 10:08:18 Kth Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations. Given two integers N and K, find the Kth permutation sequence of numbers from 1 to N.

Note:

Assume that the inputs are such that Kth permutation of N number is always possible.

STL function should not be used in case of C++.

Example :

Input: n = 3, k = 4

Output: "231"

Explanation:

For n = 3, we have 3! or 6 possible unique permutations. By listing and labeling all of the permutations in order, we get the following sequence:

"123"
"132"
"213"
"231"
"312"
"321"

Here we can see that 4th permutation sequence is "231".

Topic : Backtracking

References ->

InterviewBit, LeetCode, GeeksforGeeks

Solution -> GeeksforGeeks

Asked in Amazon

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-09-09 15:38:00 Implement strstr()

Implement a function strstr. It takes two strings as arguments (haystick, needle) and returns the first occurrence of needle in haystack else -1 if needle is not part of haystick.

Example 1:

Input: haystack = "hello", needle = "ll"

Output: 2

Explanation: "ll" is at index location 2 in haystick.

Example 2:

Input: haystack = "aaaaa", needle = "bba"

Output: -1

Explanation: "bba" is not in "aaaaa" so return -1.

Notes:
- Try not to use standard library string functions for this question.
- If needle is an empty string, return 0. But it is great question to ask during interview.

Topic : Strings

References -> InterviewBit, GeeksforGeeks, LeetCode

Solution -> tutorialspoint

Asked in Amazon, Facebook, Microsoft, Wipro, Qualcomm

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-09-03 16:06:25 Spiral Order Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

Input Format:
The first and the only argument contains an integer,n.

Output Format:
Return a 2-d matrix of size nxn satisfying the spiral order.

Constraints:
1 <= n <= 1000

Examples:

Input 1:
n = 3

Output 1:
[ [ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ] ]

Input 2:
n = 4

Output 2:
[ [ 1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7] ]

Topic : Arrays

Asked in Amazon, Microsoft, JP Morgan

References ->
InterviewBit, LeetCode

Solution ->
w3sresource

Join our Official Channel @cseinterview Ouvert / Commentaire

2020-08-27 06:34:40 LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

1. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

2. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity. Capacity indicates the maximum number of unique keys it can hold at a time.

NOTE: If you are using any global variables, make sure to clear them in the constructor.

Example -

LRUCache cache = new LRUCache(2);

cache.put(1, 24);
cache.put(2, 50);
cache.get(1); // returns 24
cache.put(3, 30); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 42); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 30
cache.get(4); // returns 42

Explanation -

First LRUCache is instantiated with capacity of 2. Then cache is initialized with (1, 1) and (2, 2) key-value pairs.

cache.get(1) returns value 24 which corresponds to key 1. Inserting (3, 30) pair evicts least recently used item i.e. with key 2.

Now there is no key 2, so cache.get(2) returns -1. Inserting (4, 42) evicts least recently used item with key 1.

Now cache contains values corresponding to keys 3 and 4. So cache.get(1) returns -1 while cache.get(3) and cache.get(4) returns corresponding values.

Topic : Maps

Asked in Amazon, Microsoft, Adobe, Citigroup

References ->
InterviewBit, LeetCode

Solution ->
GeeksforGeeks article 1, article 2

Join our Official Channel @cseinterview Ouvert / Commentaire