CareerCup

I am given an array of Transactions in a ledger. A Transaction object has three things.
1. Sender (which means who started this transaction)
2. Receiver (means who is the destination of transaction)
3. Timestamp (at what time this transaction was executed)

Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:
1. if sender and receiver are same
2. The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A--> C is a valid transaction)

Example:
Transaction
{
Sender;
Receiver;
Timestamp;
}

Example: [T is timestamp here]
A -> B (T=0)
B -> C (T=1)
C -> F (T=0)

findIfTransactionIsValid(A, C) -> this should return true
findIfTransactionIsValid(B,F) -> false (time is backwards)

If the question is still not clear, please see the solution I wrote. I have written a recursive solution and is working but I am seeing help to improve the solution.

Write a retry function, continue to fetch data until u have exhausted max entries. If it fails, continue to retry until retry's have been exhausted.

There are N countries, each country has Ai players. You need to form teams of size K such that each player in the team is from a different country.
Given N and number of players from each country and size K. Find the maximum number of teams you can form.

Given 2 trees T1 & T2 (both can have > 2 childs), write an algorithm to find if T2 is a subtree of T1.

Follow up question, for any branch in T1
a->b->c->d

the following is a valid branch in tree T2(i.e. the isSubTree() algorithm mush evaluate to true in below circumstances)

a->d
a->c->d
c->d

You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output should have the "connected" grid items property to true.

For example:

input = [
      [{value: 0}, {value: 1}, {value: 1}],
      [{value: 0}, {value: 0}, {value: 1}],
      [{value: 1}, {value: 1}, {value: 1}]
    ];

    startRowIndex = 2;
    startColumnIndex = 0;
    
    output = [
      [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
      [{value: 0}, {value: 0}, {value: 1, connected: true}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

This is the first part of the question, this can be easily solved using either DFS or BFS.

The second part is you are given the output of the first function and the same start indices. Along with these two input arguments, you are also given a flipIndex. The grid item at the given flip index will have the value flipped. Now give the updated matrix with the updated "connected" path.

input = [
      [{value: 0}, {value: 1, connected: true}, {value: 1, connected: true}],
      [{value: 0}, {value: 0}, {value: 1, connected: true}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

    startRowIndex = 2;
    startColumnIndex = 0;

    flipRowIndex = 1;
    flipColumnIndex = 2;
    
    output = [
      [{value: 0}, {value: 1}, {value: 1}],
      [{value: 0}, {value: 0}, {value: 0}],
      [{value: 1, connected: true}, {value: 1, connected: true}, {value: 1, connected: true}]
    ];

Optimize the runtime of the following function from O(I * R) to O(I + R):

const cars = [
  {make: "toyota", color: "red", cat: "suv"},
  {make: "honda", color: "black", cat: "sedan"},
  {make: "toyota", color: "red", cat: "sedan"},
  {make: "nissan", color: "blue", cat: "suv"},
];

const rejects = [
  {key: "color", value: "black"},
  {key: "color", value: "blue"},
  {key: "make", value: "honda"},
];

function rejectByKeyValues(items, rejectKeyValues) {
  rejectKeyValues.forEach(keyValue => {
    items = items.filter(ii => ii[keyValue.key] !== keyValue.value);
  });
  return items;
}

Given a list of sorted lists each of size maximum size M, implement an iterator (maintain the order of items as in the original list of lists).

I had a solution requiring extra space using minHeap; However, the interviewer was looking for a constant space solution.

Write AWS lambda function to fetch data from on premises oracle db and migrate to aurora db.

I tried :

var oracledb = require('oracledb-for-lambda');
var os = require('os');
var fs = require('fs');
'use strict';

str_host = os.hostname() + ' localhost\n';

fs.appendFile(process.env.HOSTALIASES,str_host , function(err){
    if(err) throw err;  
});

Can someone show me , i have table with same columns present in oracle db as well as aurora db i want to map form oracle to aurora. How to write it in java or python using aws lambda.

LinkedList :
Input : A>B>C>D>E
Output: A>E>B>D>C

Design a data scrubber.

Say a customer couldn't use Alexa with Philips light bulb. Now customer calls to Alexa/Amazon customer support they figure out the issue is not with Alexa it's with the Philips LED bulb.

Now amazon will redirect their customer call / chat to third party customer support (Philips in this case).

Now somehow we need prevent the possibility of third party customer support trying to exploit our customers. For ex: asking their bank accounts, credit card, Social Security number etc..

How will you do that for AMAZON level ?

How to get flight booking on japan airlines and how to contacts them on japan airlines?

It will gain you more knowledge, intensify your soft skills, strong work ethics and grow your network. What is it?

There are 4 closed boxes and one of them has $100 inside. You can open one of the boxes if you pay x dollars.
If the box you opened is empty, you can keep on opening boxes, but you need to pay x dollars every time.
Up to what amount would you pay?

Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Follow-up: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ?

Two-sum question.

Given two strings of comma-seperated values, sort and return the second list based on the ordering of the first list.

Given an array of 100 numbers, find the (unique set) of duplicate values.

Find all of the different permutations of a string without using any built-in permutation functions. Your answer should not contain duplicates.

You have oracle database table , and AURORA AWS table with same fields , write a java lambda function to migrate data from oracle table to aurora. Also it should be realtime, if a new record is added to oracle it should update aurora db table as well.

Hello All ,

I would like to understand onsite interview experience for amazon lab126 in device os team for QAE role .
Could you please any one share your experience ? I also want to know any system design question will come and detail about your experience as well ?

Given an array of edges between any two points in 2 dimensional space. A single edge is represented by the co-ordinates of two points it is connecting for example (2,3),(4,5) represents and edge connecting points (2,3) and (4,5).Find out the total number of squares possible if all edges are parallel to X or Y axis.
NOTE : Include overlapping squares, squares having one side in common and squares contained within another square. Co-ordinates can have float values.

Example below -
I have considered a very simple input and output combination to keep it short.
Input
{
(0,0),(0,3)
(0,0),(3,0)
(0,3),(3,3)
(3,0),(3,3)
}
Output : 1

Possible Approach : Create a map as below -

Key(Slope of Edge in Degrees) - Value(Array of Edges)
0 - {(0,0),(3,0)},{(0,3),(3,3)}
90 - {(0,0),(0,3)},{(3,0),(3,3)}

While inserting edges in the map, make sure the edges are sorted by max(x1,x2) first and then max(y1,y2).
Pick 2 edges from one slope let's say slope 0, then pick 2 edges from slope 90 and see if square is formed or not. If square not formed, then look at next 2 edges of slope 90 and so on.
Sorting here is an expensive operation.

Please share any better solutions.

You have a bunch of shops. Each shops sells a bundle of chocolates at a fixed cost. You are given an amount and the price sheet of shops. Find the maximum number of chocolates that you can buy with the amount.

Int Calculate(Int Amount, []Int Quantities, []Int Cost) {
  // Implement
}

Other points: (1) You cannot use 'sort' (2) The costliest shop need not sell the maximum number of chocolates. (3) Tricky cases exist. For example: Shop 1 sells 10 chocolates in a 10 $ bundle. Shop 2 sells 9 chocolates in a 1$ bundle. If you have 10$ in your hand, Here the maximum number of chocolates that you can buy is not 10 but 90.

Given a directed graph and a node , find the shortest cycle in a graph with given node .

Given a

struct drop{
	float x_cordinate;
	float radius;
}

Return the number of calls that the function Drop() that returns a drop object, needs to be called so that the interval [0, 1) is covered. For each drop object the range covered are values on a line considering x_cordinate as center and radius as the length added on both sides of the x_cordinate on that line?

int numCalls(const function<drop> Drop){
	drop firstDrop = Drop();
	// Code from here
}

For example, if the first Drop() call returns drop object drop.location as 0.5 (considering points on a 1d axis) and drop.radius as 0.2, then the interval covered is [0.3, 0.7). So how many calls need to be made to ensure the interval [0, 1) is covered. The location and radius can map to any real value.

Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
For example:
input = [(1,4), (2,3)]
return 3
input = [(4,6), (1,2)]
return 3
input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
return 11

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

given an array representing a non-negative integer (ex: 123 represented as [1,2,3]), return the next integer (output: [1,2,4]).
run through all edge cases (ex: [9,9,9,9,9,9,9,9] etc)

Complicated problem statement but was asked to implement binary search

Sparse Scalar vector dot product.
in less than O(n)

Write a uniform random function generator from 1 to n, given a uniform random Boolean generator, which return true or false for a given number randomly.