Google | Phone Screen | Validate Expressions
Anonymous User
3301

Given a set of expression with > and < and unknown variable, check if they are true:
for example

a<b, b<c, a<c => True
a<b, b<c, c<a => false

Seems dfs or topology sort to check cycle can handle

follow up 1:
If not just only unknow variable, but also number ?

a>2, a<b, b<1 => false

Probably on top of previous one , for number additionaly sort them and add to graph like above also add linke 1-> 2

follow up 2:
What if we have =?

a>b, b<=a => false
a>=b, b>=c, c>=a => true

For follow up 2, current my idea is to have have a edge struct to teel where it has equal of not , and using DFS to check:

  • when we see cycle , see node in visting set, if current dfs allow equal and the coming edge include equal , it is valid, don't assert cycle exit
  • otherwise , see node in visiting set while either current dfs doing not allow equal or coming edge doesn't include equal , assert cycle exit

I am not sure if follow up 2 my idea correcet or not, kindly comment on it.

Comments (10)