Coding Interview | Software Engineer Manager @ Amazon Part 1

Live programming interview with a software development manager at Amazon.
#keeponcoding #tech #programming
Patreon: / keeponcoding
Instagram: / keep_on_coding
Discord: / discord
My Gear: amazon.com/sho...
DISCLAIMER: Links included in this description might be affiliate links. If you purchase a product or service with the links that I provide I may receive a small commission. There is no additional charge to you! Thank you for supporting so I can continue to provide you with free content!

[@praveenbadam9682]

Using python, we can implement more faster :)
a = "abcabcabcdefabc"
b = "abc"
l = []
for i in range(len(a)) :
if b == a[i:i+(len(b))] :
l.append(i)
print(l)
[0, 3, 6, 12]

[@minyoungan9515]

Are both time complexity and space complexity O(N)?

[@h2o313]

time complexity is O(n*m) where n is the length of the haystack, and m is the length of the needle. Optimal solution has O(n+m) though

[@jeffGordon852]

@@minyoungan9515 yes

[@multiHappyHacker]

Simple things are often much harder during an interview for some reason.

[@pablomarch]

One javascript solution using a substring with a complexity of O((m - n) * n):
function (n, h) {
let hP = 0;
const nLen = n.length;
const hLen = h.length;
const matches = [];
while (hP < hLen) {
const hSubLen = hP+nLen;
if (hSubLen > hLen) break;
if (h.substring(hP, hSubLen) === n) matches.push(hP);
hP++;
}
return matches;
}
One other solution with a time complexity of O(m * n) ut harder to understand:
function (n, h) {
let hP = 0;
let nP = 0;
const nLen = n.length;
const hLen = h.length;
const matches = [];
while (hP < hLen) {
if (h[hP] === n[nP]) {
if (nP + 1 === nLen) {
matches.push(hP - nP);
nP = 0;
}
nP++;
} else {
nP = 0;
if (h[hP] === n[nP]) {
nP++;
}
}
hP++;
}
return matches;
}

[@limasntoinf]

This feels real. Good work.

[@MrLerrab]

It's funny how I had this task on my 2nd semester in the university. Lmao

[@mrreese2342]

Yeah me too lol

[@gooddeveloper634]

List results = new ArrayList();
final static char NOTHING = ‘{‘;
while(haystack.indexOf(needle) != -1) {
int index = haystack.indexOf(needle);
results.add(index);
char[] chars = haystack.toCharArray();
chars[index] = NOTHING;
haystack = String.valueOf(chars);
}

[@msh104utube]

Sam, I got a question for you: let's say you're applying for a full stack position, and you can only choose to use Java or C++ (i.e. JS won't cut it here, as this is full stack). You know them both equally well/not well. Which would you choose, considering that you are going to whiteboard it and don't want to leave things out? From what I recall, C++ is a bit easier to whiteboard, but I can be wrong here. It's been a minute since I've done either.

[@tannerbarcelos6880]

It’s easy to forget pointers and references on a whiteboard with c++ when java avoids those nuances . But the flip side of using c++ will show you’re a god lol. If it were me, I’d use java. I’m trying to actually make that decision now as well, but my interview skills are suspect . But I’m going into my senior year in undergrad

[@huaxzhang]

If allowed, and if in C++, I'm wondering if use of library call like strncmp( ) would offer simplification.

[@faizKhan-uv2dl]

I guess it depends, for a bigger task using libraries makes sense. For a problem like this, you need to offer your own algorithm for solving the problem. Otherwise they wont get an idea of how good or bad you are at coding.

[@kinkfactory69]

Where is part 2 ?

[@saideepesh6036]

I think that didn' t go well

[@sunilsutar7780]

Here's O(n) solution in C#
public static List grep(string haystack, string needle)
{
if(haystack.Length < needle.Length)
return new List();

List result = new List();

int needlePointer = 0;

for(int i=0; i

[@filipeperry]

Keeping simply! public static List grep(String text, String pattern) {

int n = text.length();
int m = pattern.length();
List list= new ArrayList();

int i = 0;
while (i

[@mohammedalmukhtar8949]

JS solution. Fewer lines of code than your JAVA code, but would like to get your opinion about its time and space complexity:
const haystack = 'yhyyabcrteeekabchghdhabfh'
const needle = 'abc'
function needleInHaystack(h, n) {
let result = []
for (let i = 0; i < h.length; i++) {
const index = h.indexOf(n, i)
if (index !== -1) {
result.push(index)
i = index + n.length - 1
}
}
return result
}
console.log(needleInHaystack(haystack, needle))

[@user-cd6vy2jg6f]

This is n*m runtime so essentially brute force. There is an O(n) time and O(1) memory solution

[@merryesther3533]

😀😀😁😁😍😍👍👍Call to Action.

[@shenth27]

Such an easy question! lucky interviewee..

[@emreyaln7780]

strnstr

[@olegp1643]

You do realize that he wanted to hear something like Rabin-Karp rolling hash algorithm? It's very rare that straightforward naive solution would be asked by FAANG company.

[@duncanproctor7160]

List findAllNeedles(String needle, String haystack) {
List needleStartingIndexes = new ArrayList();
int currentlyComparingNeedleChar = 0;
for (int ci = 0; ci < haystack.length(); ci++) {
char c = haystack.charAt(ci);
if (needle.charAt(currentlyComparingNeedleChar) == c) {
// Congruent so far
currentlyComparingNeedleChar++;
} else {
// Incongruent
currentlyComparingNeedleChar = 0;
}
if (currentlyComparingNeedleChar == needle.length()) {
// We found a match!
needleStartingIndexes.add(ci - needle.length() + 1);
currentlyComparingNeedleChar = 0;
}
}
return needleStartingIndexes;
}