NVIDIA Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Nice solution and description.
I was also thinking about kind of double buffer storage for produced characters. Producer can have an atomic pointer to one buffer to push characters there, on the other site customers have their own atomic pointers that points on second buffer with already produced characters. Since on customer site it would be read-only operation and on the producer site it is write-only so we can skip mutex locks I guess. Even if that works, the problem is that we need to wait (or synchronize) until all the customer threads have finished processing the "front" buffer to do buffer swap. (I will prepare a code for that and I will upload here later)
May I ask you to say something more (or some link) about the "automaton based approach" that you mentioned regarding looking for pattern because I cannot understand what you meant?
Cheers!!!
class Item:
def __init__(self, SeekString="_", SeekIndex=0):
self.SeekString = SeekString
self.SeekIndex = SeekIndex
def printSeek(l):
for item in l:
print '[',item.SeekString,', ',item.SeekIndex,'] '
def fun():
KnownStrings = ["aa", "ab", "ff"];
InputStream = "abcdegabccaabbaacv";
SeekList = []
CountDict = {item : 0 for item in KnownStrings}
for inChar in InputStream:
for SeekItem in SeekList:
if SeekItem.SeekString != "_":
if SeekItem.SeekString[SeekItem.SeekIndex] == inChar:
# case for one item and that is match
if SeekItem.SeekString[SeekItem.SeekIndex] == SeekItem.SeekString[-1]:
CountDict[SeekItem.SeekString] += 1
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
else :
# case for more item but match
SeekItem.SeekIndex += 1
else:
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
# printSeek(SeekList)
for KnownString in KnownStrings:
if KnownString[0] == inChar:
SeekList.append(Item(KnownString, 1))
# print ''
print CountDict
printSeek(SeekList)
fun()
class Item:
def __init__(self, SeekString="_", SeekIndex=0):
self.SeekString = SeekString
self.SeekIndex = SeekIndex
def printSeek(l):
for item in l:
print '[',item.SeekString,', ',item.SeekIndex,'] '
def fun():
KnownStrings = ["aa", "ab", "ff"];
InputStream = "abcdegabccaabbaacv";
SeekList = []
CountDict = {item : 0 for item in KnownStrings}
for inChar in InputStream:
for SeekItem in SeekList:
if SeekItem.SeekString != "_":
if SeekItem.SeekString[SeekItem.SeekIndex] == inChar:
# case for one item and that is match
if SeekItem.SeekString[SeekItem.SeekIndex] == SeekItem.SeekString[-1]:
CountDict[SeekItem.SeekString] += 1
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
else :
# case for more item but match
SeekItem.SeekIndex += 1
else:
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
# printSeek(SeekList)
for KnownString in KnownStrings:
if KnownString[0] == inChar:
SeekList.append(Item(KnownString, 1))
# print ''
print CountDict
printSeek(SeekList)
fun()
class Item:
def __init__(self, SeekString="_", SeekIndex=0):
self.SeekString = SeekString
self.SeekIndex = SeekIndex
def printSeek(l):
for item in l:
print '[',item.SeekString,', ',item.SeekIndex,'] '
def fun():
KnownStrings = ["aa", "ab", "ff"];
InputStream = "abcdegabccaabbaacv";
SeekList = []
CountDict = {item : 0 for item in KnownStrings}
for inChar in InputStream:
for SeekItem in SeekList:
if SeekItem.SeekString != "_":
if SeekItem.SeekString[SeekItem.SeekIndex] == inChar:
# case for one item and that is match
if SeekItem.SeekString[SeekItem.SeekIndex] == SeekItem.SeekString[-1]:
CountDict[SeekItem.SeekString] += 1
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
else :
# case for more item but match
SeekItem.SeekIndex += 1
else:
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
# printSeek(SeekList)
for KnownString in KnownStrings:
if KnownString[0] == inChar:
SeekList.append(Item(KnownString, 1))
# print ''
print CountDict
printSeek(SeekList)
fun()
class Item:
def __init__(self, SeekString="_", SeekIndex=0):
self.SeekString = SeekString
self.SeekIndex = SeekIndex
def printSeek(l):
for item in l:
print '[',item.SeekString,', ',item.SeekIndex,'] '
def fun():
KnownStrings = ["aa", "ab", "ff"];
InputStream = "abcdegabccaabbaacv";
SeekList = []
CountDict = {item : 0 for item in KnownStrings}
for inChar in InputStream:
for SeekItem in SeekList:
if SeekItem.SeekString != "_":
if SeekItem.SeekString[SeekItem.SeekIndex] == inChar:
# case for one item and that is match
if SeekItem.SeekString[SeekItem.SeekIndex] == SeekItem.SeekString[-1]:
CountDict[SeekItem.SeekString] += 1
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
else :
# case for more item but match
SeekItem.SeekIndex += 1
else:
# SeekList.remove(SeekItem)
SeekItem.SeekString = "_"
# printSeek(SeekList)
for KnownString in KnownStrings:
if KnownString[0] == inChar:
SeekList.append(Item(KnownString, 1))
# print ''
print CountDict
printSeek(SeekList)
fun()
//example with one consuming thread
class MonitorTest
{
Random rnd = new Random();
object key = new object();
bool m_symbolprocessed = true;
char m_symbol = 'a';
ushort m_buffer = 0;
const ushort m_pattern1 = 0x6566;
private void consumeSymbol()
{
lock (key)
{
while (false != m_symbolprocessed)
{
Console.WriteLine("waiting producer");
Monitor.Wait(key);
}
Thread.Sleep(rnd.Next() % 200);
//
//prosessing
if (m_buffer == m_pattern1)
{
Console.WriteLine("Match found");
Thread.Sleep(2000);
}
//end
//
m_symbolprocessed = true;
Monitor.PulseAll(key);
}
consumeSymbol();
}
private void produceSymbol()
{
lock (key)
{
while (true != m_symbolprocessed)
{
Console.WriteLine("waiting consumer");
Monitor.Wait(key);
}
Thread.Sleep(rnd.Next() % 200);
//
//producing
m_symbol = (char)(rnd.Next() % 4 + 100);
m_buffer <<= 8;
m_buffer |= m_symbol;
Console.WriteLine(m_symbol);
//end
//
m_symbolprocessed = false;
Monitor.PulseAll(key);
}
produceSymbol();
}
public void startAllThreads()
{
Thread thAdd = new Thread(new ThreadStart(consumeSymbol));
Thread thSub = new Thread(new ThreadStart(produceSymbol));
thAdd.Start();
thSub.Start();
thAdd.Join();
thSub.Join();
}
}
class Program
{
static void Main(string[] args)
{
MonitorTest mt = new MonitorTest();
mt.startAllThreads();
}
}
Trick question.
Observe the string to counter mapping can be done by (ZoomBA):
strings = { "ab" : 0 , "aa" : 1 , "fff" : 2 , ... }
counters = [ 3, 2, 0, ...]
def increment_counter( s ){
idx = strings[ s ]
#atomic{
// make atomic operation : increment
counters[idx] += 1
}
}
Note that, there is no need to lock anything beyond the increment, as every index access are independent! Only access on the same index are not.
- Chris December 07, 2016