CskeCode

Amazon Interview Process

On July 5, 1994, Jeff Bezos started the world's most "customer-centric" firm out of his garage in Bellevue, Washington. The American multinational technology corporation Amazon focuses on a wide range of industries, such as digital streaming, cloud computing, artificial intelligence, and e-commerce. Along with Google, Apple, Microsoft, and Facebook, it is regarded as one of the "Big Five" corporations in the American information technology sector.

Amazon is recognized for its massive industry disruptions brought about by technology innovation and size. Being the largest online retailer, provider of AI assistants, and cloud computing platform in the world, Amazon employs over six lakh people, of whom more than 50,000 are Indians. It is currently the second-biggest private employer in the United States and the largest Internet corporation in the world by revenue. Amazon has the largest global brand valuation as a result.

It is very evident that many people desire to work at Amazon and be a part of its evergreen culture given the variety of services it provides. But what exactly is Amazon's recipe for enormous success? Well, if you were to ask every Amazon employee this question, we are rather confident that they would all respond in unison with: "The Leadership Principles of Amazon."

Interview Process

Recruiter Connect: Best way to get noticed by Amazon recruiters is to maintain a good Linkedin profile and message recruiters. The candidate can also apply on the Amazon job portal but it is suggested that they also get a referral from an Amazon employee.
Interview Rounds: Amazon conducts four interview rounds alongside an initial coding test. The coding test consists of DS/Algo problems. The first round is an HR round where they ask behavioral questions along with Computer Science theory questions to the candidate. The next three rounds focus solely on DS/Algo.
After Interviews: The recruiter contacts the candidate after these rounds and tells the verdict. They also look at the candidate’s leadership principles along with technical skills.
Hired: Once the team and you both are comfortable and ready to start, the offer letter is prepared and shared with you by the recruiters and you are HIRED!

Interview Rounds

HR Round(1 Round) This is when they ask computer science theory and behavioural questions to the candidate. The questions may enquire about the candidate’s experience at previous companies and conflicts the candidate might have faced with colleagues/managers.
Data Structures and Algorithms Rounds(3 Rounds) The candidate is asked DS/Algo problems where production ready code might be expected from the candidate. It is not out of the realm of possibility to face minor behavioural questions here as well. The problems range from easy to hard but they are not the sole deciding factor for the final offer. Leadership principles also come into play here. The interviews are conducted on Amazon Chime.

Google Interview Questions

There are two sorts of interviews, phone/hangout interviews and on-site interviews, according to Google's official career page. An excerpt from their official page is provided below.

For candidates for software engineering positions, we are interested in your coding abilities, technical specialties, knowledge of tools or programming languages, and broad understanding of concepts like data structures and algorithms. We prefer to challenge one other's thinking and discover new perspectives, so there is usually some back and forth in these discussions, just like there is on the job. So be ready to thoroughly discuss your solutions. Find the greatest solution by pushing your own limits—that's probably how you think anyway.

Google Questions from Medium to Hard level are as follows:

Easy Level

Find all triplets with zero sum
Generate all binary strings from given pattern
Count of strings that can be formed using a, b and c under given constraints
Find largest word in dictionary by deleting some characters of given string
Find subarray with given sum | Set 1 (Nonnegative Numbers)
Find the longest substring with k unique characters in a given string
Find the two non-repeating elements in an array of repeating elements
Flood fill Algorithm – how to implement fill() in paint?
Meta Strings (Check if two strings can become same after a swap in one string)
Print all Jumping Numbers smaller than or equal to a given value
Sum of all the numbers that are formed from root to leaf paths
The Celebrity Problem
Unbounded Knapsack (Repetition of items allowed)

Medium Level

Backtracking | Set 7 (Sudoku)
Boggle | Set 2 (Using Trie)
Check if a Binary Tree contains duplicate subtrees of size 2 or more
Dynamic Programming | Set 33 (Find if a string is interleaved of two other stri
Connect nodes at same level
Count BST nodes that lie in a given range
Dynamic Programming | Set 11 (Egg Dropping Puzzle)
Dynamic Programming | Set 28 (Minimum insertions to form a palindrome)
Dynamic Programming | Set 31 (Optimal Strategy for a Game)
Dynamic Programming | Set 32 (Word Break Problem)
Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)
Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’
How to print maximum number of A’s using given four keys
Inplace rotate square matrix by 90 degrees | Set 1
Maximum absolute difference between sum of two contiguous sub-arrays
Merge two BSTs with limited extra space
Merge Overlapping Intervals
Modular Exponentiation (Power in Modular Arithmetic)
Paper Cut into Minimum Number of Squares | Set 2
Sum of bit differences among all pairs

Hard Level

Allocate minimum number of pages
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Given a sorted dictionary of an alien language, find order of characters
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)
Implement LRU Cache
Length of the longest valid substring
Median in a stream of integers (running integers)
Sum of bit differences among all pairs
Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming)
Word Break Problem using Backtracking

Rotate matrix by 90 degrees

Set-1

In this given set-1 the problem statement is like Given a square matrix, turn it by 90 degrees in an anti-clockwise direction without using any extra space.

Input:

Matrix: 1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Output: 4 8 12 16

3 7 11 15

2 6 10 14

1 5 9 13

Follow the given steps to solve the problem:

There are N/2 squares or cycles in a matrix of side N. Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2 – 1, loop counter is i
Consider elements in group of 4 in current square, rotate the 4 elements at a time. So the number of such groups in a cycle is N – 2*i.
So run a loop in each cycle from x to N – x – 1, loop counter is y
The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
Print the matrix.

Code Implementation

// cskecode C++ program to rotate a matrix

// by 90 degrees

#include <bits/stdc++.h>

#define N 4

using namespace std;

// An Inplace function to

// rotate a N x N matrix

// by 90 degrees in

// anti-clockwise direction

void rotateMatrix(int mat[][N])

{

// Consider all squares one by one

for (int x = 0; x < N / 2; x++) {

// Consider elements in group

// of 4 in current square

for (int y = x; y < N - x - 1; y++) {

// Store current cell in

// temp variable

int temp = mat[x][y];

// Move values from right to top

mat[x][y] = mat[y][N - 1 - x];

// Move values from bottom to right

mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y];

// Move values from left to bottom

mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x];

// Assign temp to left

mat[N - 1 - y][x] = temp;

}

// Function to print the matrix

void displayMatrix(int mat[N][N])

{

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

cout << mat[i][j] << " ";

}

cout << endl;

}

cout << endl;

}

/* Driver code */

int main()

{

// Test Case 1

int mat[N][N] = { { 1, 2, 3, 4 },

{ 5, 6, 7, 8 },

{ 9, 10, 11, 12 },

{ 13, 14, 15, 16 } };

// Function call

rotateMatrix(mat);

// Print rotated matrix

displayMatrix(mat);

return 0;

}

Time Complexity: O(N2), where n is the side of the array. A single traversal of the matrix is needed.

Auxiliary Space: O(1). As a constant space is needed

Set-2

Inplace rotate square matrix by 90 degrees by transposing and reversing the matrix:

Follow the given steps to solve the problem:

Reverse every individual row of the matrix
Perform Transpose of the matrix

Code implementation

// Cskecode C++ program to rotate a matrix

// by 90 degrees

#include <bits/stdc++.h>

using namespace std;

#define N 4

// An Inplace function to

// rotate a N x N matrix

// by 90 degrees in

// anti-clockwise direction

void rotateMatrix(int mat[][N])

{ // REVERSE every row

for (int i = 0; i < N; i++)

reverse(mat[i], mat[i] + N);

// Performing Transpose

for (int i = 0; i < N; i++) {

for (int j = i; j < N; j++)

swap(mat[i][j], mat[j][i]);

}

// Function to print the matrix

void displayMatrix(int mat[N][N])

{

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

cout << mat[i][j] << " ";

}

cout << endl;

}

cout << endl;

}

/* Driver code */

int main()

{

int mat[N][N] = { { 1, 2, 3, 4 },

{ 5, 6, 7, 8 },

{ 9, 10, 11, 12 },

{ 13, 14, 15, 16 } };

// Function call

rotateMatrix(mat);

// Print rotated matrix

displayMatrix(mat);

return 0;

}

Time Complexity: O(N2) + O(N2) where N is the size of the array.

Auxiliary Space: O(1). As a constant space is needed

Amazon Interview Questions

On July 5, 1994, Jeff Bezos started the world's most "customer-centric" firm out of his garage in Bellevue, Washington. The American multinational technology corporation Amazon focuses on a wide range of industries, such as digital streaming, cloud computing, artificial intelligence, and e-commerce. Along with Google, Apple, Microsoft, and Facebook, it is regarded as one of the "Big Five" corporations in the American information technology sector.

Interview Process

Recruiter Connect: Best way to get noticed by Amazon recruiters is to maintain a good Linkedin profile and message recruiters. The candidate can also apply on the Amazon job portal but it is suggested that they also get a referral from an Amazon employee.
Interview Rounds: Amazon conducts four interview rounds alongside an initial coding test. The coding test consists of DS/Algo problems. The first round is an HR round where they ask behavioral questions along with Computer Science theory questions to the candidate. The next three rounds focus solely on DS/Algo.
After Interviews: The recruiter contacts the candidate after these rounds and tells the verdict. They also look at the candidate’s leadership principles along with technical skills.
Hired: Once the team and you both are comfortable and ready to start, the offer letter is prepared and shared with you by the recruiters and you are HIRED!

Interview Rounds

HR Round(1 Round)

This is when they ask computer science theory and behavioural questions to the candidate. The questions may enquire about the candidate’s experience at previous companies and conflicts the candidate might have faced with colleagues/managers.

Data Structures and Algorithms Rounds(3 Rounds)

The candidate is asked DS/Algo problems where production ready code might be expected from the candidate. It is not out of the realm of possibility to face minor behavioural questions here as well. The problems range from easy to hard but they are not the sole deciding factor for the final offer. Leadership principles also come into play here. The interviews are conducted on Amazon Chime.

Questions

K largest elements from a big file or array.
Find a triplet a, b, c such that a2 = b2 + c2. Variations of this problem like find a triplet with sum equal to 0. Find a pair with given sum. All such questions are efficiently solved using hashing. – Practice here
Binary tree traversal questions like left view, right view, top view, bottom view, maximum of a level, minimum of a level, children sum property, diameter etc.
Convert a Binary tree to DLL – Practice here
Lowest Common ancestor in a Binary Search Tree and Binary Tree.
Implement a stack with push(), pop() and min() in O(1) time.
Reverse a linked list in groups of size k – Practice here
Given two numbers represented by two linked lists, write a function that returns sum list – Practice here
Rotate a matrix by 90 degree.
Stock span problem
Next greater element
Some Dynamic Programming problems like:
Maximum sum subarray such that no elements are consecutive – Practice here
Edit distance
Assembly line scheduling
Why Amazon?

10.Write a program to calculate factorial of a number using thread library

Write a program to calculate factorial of a number using thread library.

//cskecode
//cskecode.blogspot.com
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<pthread.h>
int fact;
void *run(void *param);
int main(int argc, char *argv[])
{
pthread_t tid;
pthread_attr_t attr;
if(argc !=2)
{
printf("Error !");
return 1;
}
if(atoi(argv[1])<O)
{
printf("no. Should be +ive");
return 1;
}
pthread_attr_init(&attr);
pthread_create(&tid, &attr,run, argv[1]);
pthread_join(tid,NULL);
printf("fact= %d in", fact);
}
void *run(void *param)
{
int i, upper;
fact=1;
upperratoi(param);
if(upper>0)
for(i=1;i<=upper; ++i)
fact*=i;
pthread_exit(0);
}
//cskecode.blogspot.com

Output:

9.A program to calculate sum of n numbers using thread library

A program to calculate sum of n numbers using thread library.

cskecode

//cskecode.blogspot.com

#include<stdio.h>

#include<unistd.h>

#include<sys/types.h>

#include<pthread.h>

int sum;

void *run(void *param);

int main(int argc, char *argv[]).

{

pthread_t tid;

pthread_attr_t attr;

if(argc !=2)

{

printf("Error !");

return 1;

}

if(atoi(argv[1])<0)

{

printf("no. Should be +ive");

return 1;

}

pthread_attr_init(&attri

pthread_create(&tid,&attr.run.arguri):

pthread_join(tid, NULL);

printf("Sum = %d in", sum);

}

void *run(void *param)

{

int i,upper;

sum=0 ;

upper=atoi(param);

if(upper>0)

{

for(i=1;i<=upper; ++i)

SUM+=i:

pthread_exit(0);

}

}
//cskecode.blogspot.com

Output:

8.Write program to implement SJF scheduling algorithm (Preemptive)

Write program to implement SJF scheduling algorithm (Preemptive)

//cskecode

//cskecode.blogspot.com
#include<iostream>
using namespace std;
class sched{
public:
int n,bt[10],at[10],tat[10],wt[10],rt[10],finish[10],twt,ttat,total;
void readData();
void computeSRT();
void Init();
void dispTime();
int getNextProcess(int);
};

void sched::readData()
{
cout<<"Enter no. of processes\n";
cin>>n;
cout<<"Enter the burst times in order :\n";
for(int i=0;i<n;i++)
cin>>bt[i];
cout<<"Enter the arrival times in order:\n";
for(int i=0;i<n;i++)
cin>>at[i];
}

void sched::Init()
{
total=0;
twt=0;
ttat=0;
for(int i=0; i<n; i++)
{
rt[i]=bt[i];
finish[i]=0;
wt[i]=0;
tat[i]=0;
total+=bt[i];
}
}

void sched::computeSRT()
{
readData();
Init();
int time,next=0,old,i;
cout<<"Gantt Chart\n ";
for(time=0;time<total;time++)
{
old=next;
next=getNextProcess(time);
if(old!=next || time==0)
{
cout<<"("<<time<<")|==P"<<next+1<<"==|";
}
rt[next]=rt[next]-1;
if(rt[next]==0)
{
finish[next]=1;
}
for(i=0;i<n;i++)
if(i!=next && finish[i]==0 && at[i]<=time)
wt[i]++;
}
cout<<"("<<total<<")"<<endl;
for(i=0;i<n;i++)
if(!finish[i]) {cout<<"Scheduling failed, cannot continue\n"; return;}
dispTime();
}

int sched::getNextProcess(int time)
{
int i,low;
for(i=0;i<n;i++)
if(finish[i]==0){low=i; break; }
for(i=0;i<n;i++)
if(finish[i]!=1)
if(rt[i]<rt[low] && at[i]<=time)
low=i;
return low;
}

void sched::dispTime()
{
for(int i=0;i<n;i++)
{
twt+=wt[i];
tat[i]=wt[i]+bt[i];
ttat+=tat[i];
cout<<"Waiting time for P"<<(i+1)<<" = "<<wt[i]<<", Turnaround time = "<<tat[i]<<endl;
}
cout<<"Avg Waiting time = "<<(double)twt/n<<" and Avg Turnaround time = "<<(double)ttat/n<<endl;
cout<<"Scheduling complete\n";
}

int main()
{
sched s;
s.computeSRT();
}
//cskecode.blogspot.com

Output: