Walmart interview experience Real time questions & tips from candidates to crack your interview

# SDE - 1

Walmart
4 rounds | 10 Coding problems

## Interview preparation journey

Preparation
Duration: 3 months
Topics: Data Structures, Algorithms, System Design, Aptitude, OOPS
Tip

Tip 1 : Must do Previously asked Interview as well as Online Test Questions.
Tip 2 : Go through all the previous interview experiences from Codestudio and Leetcode.
Tip 3 : Do at-least 2 good projects and you must know every bit of them.

Application process
Where: Campus
Eligibility: Above 7 CGPA
Resume tip

Tip 1 : Have at-least 2 good projects explained in short with all important points covered.
Tip 2 : Every skill must be mentioned.
Tip 3 : Focus on skills, projects and experiences more.

## Interview rounds

01
Round
Medium
Online Coding Test
Duration90 minutes
Interview date11 Aug 2021
Coding problem2

This was a proctured online coding round where we had 2 questions to solve under 90 minutes . The questions were a bit lengthy but the implementation part was quite easy .

### 1. Encode the Message

Easy
18m average time
90% success
0/40

#### Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as the character and a single count. For example, the string "aaaabbbccdaa" would be encoded as "a4b3c2d1a2".

Problem approach

Steps:
1) Sort all the words in descending order of their lengths.
2) Initialise res with first word in the vector + "#"
3) Now we just need to find, if other words in the vector + # are substring of res or not. if not, append that word to res.

### 2. Make all elements of the array distinct.

Moderate
30m average time
70% success
0/80

#### You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. In one operation you can increase an element by 1. Your task is to return the minimum number of operations to make the array distinct.

##### Example:
``````Let’s say you have an array/list [1,4,4,5]. We can increase the third element by 1 and the fourth element by 1. Finally, our array will look like [1,4,5,6] where all elements are distinct. Therefore the minimum number of operations is 2.
``````
Problem approach

Steps:
1) The idea is to sort the input , then we move forward from the beginning of the array till the end.
2) As soon as we found a condition that the current element is less than or equal to the previous elements then we need to update the current array element by adding 1 to its prev element .
3) At the same time we need to keep track of result by result += A[i-1]- A[i]+1;

02
Round
Easy
Video Call
Duration50 Minutes
Interview date12 Aug 2021
Coding problem3

This Round was DS/Algo + Core round and it started with formal introduction, followed by 3 problems. We first dicussed the
approach the time complexity and proper code covering all cases for the 2 coding problems . The last question was related to OS and was a bit theoretical .

### 1. Distinct Characters

Moderate
15m average time
85% success
0/80

#### Given a string “STR”, you need to return all the possible non-empty subsequences with distinct characters. You can return the strings in any order.

##### Note:
``````If the same string can be generated multiple times, return them multiple times.
``````

#### For eg. Let the input string be 'cbc'. Then all the subsequences with distinct characters will be - ['c', 'bc', 'c', 'cb', 'b'].

Problem approach

Instead of counting all unique characters and struggling with all possible substrings,
we can count for every char in S, how many ways to be found as a unique char.
We count and sum, and it will be out answer.

Let, index[26][2] record last two occurrence index for every upper characters.
1) Initialise all values in index to -1.
2) Loop on string S, for every character c, update its last two occurrence index to index[c].
3) Count till loop ends . For example, if "A" appears twice at index 3, 6, 9 seperately, we need to count:
-For the first "A": (6-3) * (3-(-1))"
-For the second "A": (9-6) * (6-3)"
-For the third "A": (N-9) * (9-6)"

Time Complexity : O(N)
Space Complexity : O(1)

### 2. NINJA’S PARENTHESES

Moderate
15m average time
85% success
0/80

#### Rules for the game are as follows:

``````For “()” you get a score of 1.
For “x y” you get a score of x + y where x and y are individual pairs of balanced parentheses.
For “(x)” you get a score twice of x (i.e), 2 * score of x.
``````

#### Example :

``````Suppose given string 'STR' is “( ( ) )”.
So we return ‘2’ as input is of the form “(x)”, therefore total score = 2 * score of “()” = 2 * 1 = 2.
``````
##### Note :
``````You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
``````
Problem approach

Approach 1 :

Every position in the string has a depth - some number of matching parentheses surrounding it. For example, the dot in (()(.())) has depth 2, because of these parentheses: (__(.__))

1) Our goal is to maintain the score at the current depth we are on.
2) When we see an opening bracket, we increase our depth, and our score at the new depth is 0.
3) When we see a closing bracket, we add twice the score of the previous deeper part - except when counting (), which has a score of 1.

For example, when counting (()(())), our stack will look like this:

[0, 0] after parsing (
[0, 0, 0] after (
[0, 1] after )
[0, 1, 0] after (
[0, 1, 0, 0] after (
[0, 1, 1] after )
[0, 3] after )
[6] after )

TC : O(N)
SC: O(N)

Approach 2 (Space Optimised) :

Observe that the final sum will be a sum of powers of 2, as every core (a substring (), with score 1) will have it's score multiplied by 2 for each exterior set of parentheses that contains that core.

1) Keep track of balance (the number of ( parentheses minus the number of ) parentheses) of the string.
2) For every ) that immediately follows a (, the answer is 1 << balance, as balance is the number of exterior set of parentheses that contains this core.

TC: O(N)
SC:O(1)

### 3. OS Question

Explain demand paging

Problem approach

Demand paging is a method that loads pages into memory on demand. This method is mostly used in virtual memory. In this, a page is only brought into memory when a location on that particular page is referenced during execution. The following steps are generally followed:

1) Attempt to access the page.
2) If the page is valid (in memory) then continue processing instructions as normal.
3) If a page is invalid then a page-fault trap occurs.
4) Check if the memory reference is a valid reference to a location on secondary memory. If not, the process is terminated (illegal memory access). Otherwise, we have to page in the required page.
5) Schedule disk operation to read the desired page into main memory.
6) Restart the instruction that was interrupted by the operating system trap.

03
Round
Medium
Video Call
Duration40 Minutes
Interview date12 Aug 2021
Coding problem3

I was given 2 preety good questions of DSA in this round . One was related to Binary Trees and the other was a good DP problem in which I struggled a bit but with some hints I was able to solve this problem too . The last question was related to OOPS and was preety easy .

### 1. Create a binary tree from postorder and preorder traversal

Moderate
15m average time
85% success
0/80

#### You are given the ‘POSTORDER’ and ‘PREORDER’ traversals of a binary tree. The binary tree consists of ‘N’ nodes where each node represents a distinct positive integer named from ‘1’ to ‘N’. The task is to return the root node of any binary tree that matches the given ‘POSTORDER’ and ‘PREORDER’ traversals.

##### Example:
``````‘POSTORDER’ = [4, 5, 2, 6, 7, 3, 1]
‘PREORDER’ = [1, 2, 4, 5, 3, 6, 7]
A binary tree that matches the given ‘POSTORDER’ and ‘PREORDER’ traversal is:
``````

``````So, create this binary tree and return the root node ‘1’.
``````
##### Note:
``````1. You can return any binary tree that matches the given ‘POSTORDER’ and ‘PREORDER’ traversals.

2. You can always construct a valid binary tree from the ‘POSTORDER’ and ‘PREORDER’ traversals.
``````
Problem approach

We will preorder to generate TreeNodes, push them to the stack and perform postorder to pop them out.

1) Iterate on pre array and construct node one by one.
2) Stack saves the current path of the tree.
3) node = new TreeNode(pre[i]), if not left child, add node to the left. otherwise add it to the right.
4) If we meet a same value in the pre and post, it means we have completed the construction for current subtree. We pop it from stack.

TC : O(N)
SC: O(N)

### 2. Minimum Cost To Buy Oranges

Moderate
20m average time
70% success
0/80

#### You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

##### Note :
``````Array index 'i' denotes the cost of (i+1)kg packet.
Example: cost[0] is the cost of a 1kg packet of oranges.
``````
Problem approach

This problem was actually a variation Unbounded Kanpsack Problem . I first gave the interviewer a naive recursive
approach and then later optimised it using memoisation .

Naive Recursive Approach :

1) Create a recursive function ( int minCost(cost, idx , w) ) which returns the optimal answer for an array which starts
with index idx and for a given weight w.

2) Now for every index idx , if cost[idx]!=-1 then I have three options :

option1 -> Take that particular element and then recursively call for the whole array again (we won't increment idx
here as we can take an element infinitley many times) with the same idx and a reduced weight w-idx-1(assuming 0-
based indexing) . i.e.,
option1=cost[idx]+minCost(cost,idx,w-idx-1);

option2 -> Take that particular element and then recursively call for the rest of the array with index as idx+1 and a
reduced weight w-idx-1(assuming 0-based indexing) . i.e.,
option2=cost[idx]+minCost(cost,idx+1,w-idx-1);

option3-> Do not take that element at all and then recursively call for the rest of the array with index as idx+1 but with
the same weight w.
option3=minCost(cost,idx+1,w);

Now , return the min({op1,op2,op3})

3)If cost[idx]==-1 , we have only one option - To not take that element at all and then recursively call for the rest of the
array with index as idx+1 but with the same weight w.
i.e. return minCost(cost,idx+1,w)

4)Base Cases :
a) If weight , w==0 then we can simply return 0 (do not take any element)
b) If index >= cost.size() or weight<0 , then simply return the max value of integer (INT_MAX in C++)

TC : O(3^n)
SC:O(n*w)

Dynamic Programmming (Using Memoisation ) :

As we can observe , this problem has both optimal substructure as well as optimal subproblem properties and hence
can be easily memoised using a map (key->pair of index and weight , value->answer for this state) i.e.
dp[{idx,w}= min({op1,op2,op3})
Check if we have previously visited this state or not . If yes simply return the dp value

TC : O(n*w)
SC : O(n*w)

### 3. OOPS Question

Static and Dynamic Polymorphism

Problem approach

Static polymorphism (static binding) is a kind of polymorphism that occurs at compile time. An example of compile-time polymorphism is method overloading.

Runtime polymorphism or dynamic polymorphism (dynamic binding) is a type of polymorphism which is resolved during runtime. An example of runtime polymorphism is method overriding.

04
Round
Easy
HR Round
Duration30 Minutes
Interview date12 Aug 2021
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

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.

### 2. 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 .

Here's your problem of the day

Solving this problem will increase your chance to get selected in this company

What does ROLLBACK do in DBMS?

Start a Discussion
Similar interview experiences
SDE - 1
5 rounds | 6 problems
Interviewed by Walmart
4085 views
SDE - 1
4 rounds | 8 problems
Interviewed by Walmart
703 views
SDE - 1
5 rounds | 8 problems
Interviewed by Walmart
592 views
SDE - 1
5 rounds | 8 problems
Interviewed by Walmart
891 views
Companies with similar interview experiences
SDE - 1
5 rounds | 12 problems
Interviewed by Amazon
104062 views