SDE - 1 Walmart interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration90 minutes

Interview date15 Aug 2019

Coding problem2

This was a proctured online coding round where we had 2 questions to solve under 90 minutes . The questions were of easy to medium level I would say with some lenghty implementations .

1. Minimum Numbers Required

Easy

15m average time

85% success

0/40

Asked in companies

You are given an array, 'ARR', consisting of ‘N’ integers. You are also given two other integers, ‘SUM’ and ‘MAXVAL’. The elements of this array follow a special property that the absolute value of each element is not more than ‘MAXVAL’.

Your task is to determine the minimum number of integers required to be added into the array such that the sum of all the elements of the array becomes equal to ‘SUM’.

Note:

All the new numbers being added to the array must follow the original property of the array.

Problem approach

I followed a greedy approach for this question .
Steps :
1) Find the total sum of the array , let's call it TotalSum.
2) Find the difference b/w SUM and TotalSum , Diff=abs(SUM-TotalSum)
3) Divide the Diff by MAXVAL , let quotient =q and remainder=r
4) If r==0 , ans =q else our ans=q+1

Try solving now

2. Maximum Sum Subsequence

Hard

45m average time

55% success

0/120

Asked in companies

You are given an array “NUMS” consisting of N integers and an integer, K. Your task is to determine the maximum sum of an increasing subsequence of length K.

Note:

1. The array may contain duplicate elements.
2. The array can also contain negative integers.
3. Every element of the subsequence must be greater than or equal to the previous element.

The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “NUMS” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

Problem approach

This was a preety good DP-problem . I struggled a bit initially on finding the DP transition but on carefully observing the constraints of the problem , I figured that a O(N^2*K) DP solution will also pass the Test Cases .

Steps :
1) Initiliase a DP array dp[n][k+1] . Store -INF in all cells initally.
2) Let dp[i][j] store the answer for an array of length i and a subsequence of length j
3) Now, for every i , dp[i][1]=arr[i]
4) For each i , find dp[i][j] for every j from 2 to k
4) For every i>=1 , traverse from i-1 to 0 and check if arr[i] > arr[t] where t = [0,i-1] , if we have arr[i]>arr[t] then
dp[i][j] = max(dp[i][j] , arr[i]+dp[t][j-1])
5) Final answer = max(dp[i][k]) where i=[0,n-1]

Try solving now

Round

Medium

Face to Face

Duration50 Minutes

Interview date15 Aug 2019

Coding problem2

Standard Data Structures and Algorithms round . One has to be fairly comfortable in solving algorithmic problems to
pass this round with ease.

1. Check Whether Binary tree Is Complete

Moderate

25m average time

70% success

0/80

Asked in companies

You are given a binary tree. Your task is to check whether the given binary tree is a Complete Binary tree or not.

A Complete Binary tree is a binary tree whose every level, except possibly the last, is completely filled, and all nodes in the last level are placed at the left end.

Example of a complete binary tree :

Problem approach

Using BFS :
1) Initialise a queue which will store the nodes in level order traversal
2) Perform a level order traversal and first push the left child and then right child in the queue .
3) Before pushing , check if we encounter a NULL node or not.
4) If we encounter a NULL node before any NOT NULL node then we can say that it not a complete Binary Tree .
5) Finally if we come out of the loop , finally return 1 as it is a complete Binary Tree.

Using DFS:
1) Call a dfs function which will count the total number of nodes and maxIndex encounterd so far
2) Call the dfs function with root->left and index as 2*index
3) Call the dfs function with root->right and index as 2*index+1
4) If maxIndex>total number of nodes , return 0 as it is not a Complete a Binary Tree else return 1

Try solving now

2. Consecutive elements

Moderate

15m average time

80% success

0/80

Asked in companies

You are given an array arr of N non-negative integers, you need to return true if the array elements consist of consecutive numbers otherwise return false.

For Example: If the given array is [4,3,5] then you should return true as all the array elements are in consecutive order.

Problem approach

Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:

a[i] = a[i - 1] + b[i - 1] b[i] = a[i - 1]

The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].

Try solving now

Round

Medium

Face to Face

Duration40 Minutes

Interview date15 Aug 2019

Coding problem2

This round majorly focused on my projects and some standard questions revolving around Operating Systems and DBMS.

1. OS Question

Print 1 to 100 using more than two threads(optimized approach).

Problem approach

Prerequisite to solve this problem : Multithreading

The idea is to create two threads and print even numbers with one thread and odd numbers with another thread.
Below are the steps:

1) Create two threads T1 and T2 , where T1 and T2 are used to print odd and even numbers respectively.
2) Maintain a global counter variable and start both threads.
3) If the counter is even in the Thread T1, then wait for the thread T2 to print that even number. Otherwise, print that
odd number, increment the counter and notify to the Thread T2 .
4)If the counter is odd in the Thread T2, then wait for the thread T1 to print that even number. Otherwise, print that
even number, increment the counter and notify the Thread T1.

2. DBMS Question

Advantages of using Views.

Problem approach

The advantages of using a view in the table are :
1) It is a subset of the data in table.
2) It store complex queries.
3) It can simplify multiple tables into one.
4) It occupies very little space.
5) It presents the data from different perspectives.

Round

Easy

HR Round

Duration30 Minutes

Interview date15 Aug 2019

Coding problem2

This is a cultural fitment testing round .HR was very frank and asked standard questions. Then we discussed about my role.

1. Basic HR Question

Do you know anything about the company ?

Problem approach

General Tip : Before an interview for any company , have a breif insight about the company , what it does , when was it founded and so on . All these info can be easily acquired from the Company Website itself .

2. Basic HR Question

Why should we hire you ?

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.
Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.
Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.
Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical questions. No coding in most of the cases but some discussions over the design can surely happen.